Multi-Stage Temporal Difference Learning for 2048 - Technologies and Applications of Artificial Intelligence - page 366

(a) (b) (c)

Fig. 1. Examples of 2048 boards

Consider an example, in which an initial board is shown in Fig. 1 (a). After making
a move to right, the board becomes the one shown in Fig. 1 (b). Then, a new 2-tile is
randomly generated as shown in Fig. 1 (c). The player can repeatedly make moves in
this way.
A game ends when the player cannot make any legal move. The final score is the
points accumulated during the game. The objective of the game is to accumulate as
many points as possible. The game claims that the player wins when a 2048-tile is
created, but still allow players to continue playing.
In a 2048-bot tournament held in [18], all the 2048-bot participants play 100 games.
Their performances are graded by four factors, the win rates, the largest tiles , denoted
by -tiles, plus the reaching ratios of -tiles, the average scores, and the
maximum scores, in a formula described in [18].

2.2 Game Tree Search

A common game tree search algorithm used for 2048 bots is expectimax search [1].
Like most game tree search, the leaves are evaluated with values calculated by
heuristic functions. An expectimax search tree contains two different nodes, max nodes
and chance nodes. At a max node, its value is the highest value of its children nodes, if
any. At a chance node, its value is the expected value of its children nodes, if any, each
with a probability of instances.

Fig. 2. An expectimax search tree