Original Game: https://play2048.co/

Expectiminimax

In a zero-sum game, for example chess, you want your next move to give you the best odds at a winning position. At the same time you must consider that your opponent will move in such a way to decrease your odds as much as possible. It’s zero-sum because each of the opponent’s moves strictly takes or gives benefit resulting in a zero-net benefit for every player

However, each time you move in 2048, a new 2 or 4 tile will appear in a random location, you decide your move considering some random chance (not against a player who may have a clear best move). Expecti-minimax is an altered version of normal zero-sum decision trees to take this into account.

alpha-beta-pruning

The idea is that once you have your expanded game decision tree, it may be too large to traverse every node. Each player move then has the possibility for a random tile to be filled as either 2 or 4. With 8 open squares this is 16 possibilities. To help traverse the tree efficiently, you can "prune" branches of the tree with weak scores.

In the worst case the pruning algorithm may not be able to remove any nodes in the decision tree from being explored. The chance of pruning nodes is higher if the traversal is done in order of higher to lower scores for the player moves and vice-versa.

A good explanation can be viewed at Sebastian Lague’s youtube video here: https://www.youtube.com/watch?v=l-hh51ncgDI

Efficient Deque

For efficient breadth-first search (BFS) expansion of possible states in memory I implement an CircularDeque structure. Nodes held in array with quick add, poll, clear, etc. functionality.

Calculating max capacity

https://en.wikipedia.org/wiki/M-ary_tree

We know that the max number of children for a 2048 node is 4 (one for each direction). This changes if we take into consideration that with random chance, for each of the 4 moves, a random tile is placed. For an empty board that is a multiple of 4 (directions) x 32 (16 squares randomly could be either 2 or 4).

The properties of m-ary trees, where the total number of nodes in a complete m-ary tree of height h is given by:

Summation of nodes (m) at level 0..i = (m^(i+1) - 1)/(m - 1)

For a max depth of 5, and max 32 * 4 children there is a max total of 34,630,287,489 nodes. This is practically too large so we need a more constrained way of checking.

In expectiminimax, we can treat the random tile as the adversary which is attempting to create the worst possible board. Therefore, we can constrain number of nodes by picking only the worst possible random tile at that move. This constrains the total to depth 5 and 4 children = 1365, which will allow us to explore much deeper possibilities. A depth of 10 and 4 possible children = 1,398,101 nodes. Depth here is more important than considering all possible random tiles at each move.