16 Apr 2017:
In the last few months I’ve been studying some extra computer science through edX. Most recently, I have been working through the ColumbiaX AI course , which seems to follow AI AMA pretty closely, at least for the first half. The course has had a few projects, but I really enjoyed the most recent one: writing a search agent to play 2048.
2048 is a tile based game that involves shifting around tiles on a board in order to produce larger powers of two by combining tiles of the same value. The game becomes increasingly difficult and succeeding in creating a 2048 tile is considered a win. Some people manage to go quite a lot higher though.
The project had a few specific requirements:
- 100 milliseconds real-time move limit
- Must implement minimax
- Must implement alpha-beta pruning
The real-time move limit was a fun requirement to work with. This necessitated searching in a manner that would enable immediate termination, but still return a reasonable move choice. I chose to address this with an iterative deepening search (IDS) and a fairly shallow initial search depth.
Minimax allows the search agent to choose moves based on an opponent playing optimally against them. In 2048, the opponent places a tile in a random location, with a value of 2 or 4 and a probability of 90% or 10% respectively. In my implementation, the player simply assumes that the opponent will play whatever move is the worst for the player.
Alpha-Beta pruning is a branch and bound algorithm and allowed pruning of branches that offer a better outcome to the opponent than others that you already can choose. Since there would be no reason to offer the opponent that option, the entire branch can be pruned and that time can be spent searching elsewhere.
Another interesting dimension of the project was the depth of the search tree. It was infeasible to reach the bottom of the search tree for most of the game duration with the real-time move limit in place. Ultimately, game states had to be evaluated through heuristic functions that aimed to define the “goodness” of a node. I designed my heuristics by playing the game myself and watching a much-better-than-me 2048 player tackle the game. The heuristics essentially tell the game “how to play” rather than just “how to win.” My heuristics focused on keeping the board tidy and using either monotonic rows or columns. Additionally, it tried to cheat one more layer of depth by rewarding potential block merges and empty space. Some poor performance was worked out by coding in an additional death-flag that made sure any game-losing node would have a terrible score, no matter how “good” the rest of the board looked.
I’ve seen some amazing 2048 solvers out there, and mine is not remotely optimized. Still, it tends to win two times for every loss with an average best-block score of 1700 =).