The slides above show a tree with 3 levels:
Leaf nodes are the utility nodes, and the nodes present above the utility nodes are called chance nodes. Chance nodes calculate the average of their children, the utility nodes, giving the expected utility as the value upon them. The maximizer is at the root node, so it moves toward the maximum expected utility node and afterward toward the maximum available utility node.
Expectimax in 2048 game
It is considered an efficient approach to solving the 2048 game problem. Its trick is to think a little into the future. Before making any move, we consider what would happen if the move is made.
It follows the following steps to optimize moves in this game:
Firstly, the current state is represented by representing the values and positions of the tiles on the grid.
A tree is constructed to represent all the possible moves from the current state.
Since a new tile appears with every move, the chance node represents the appearance of a new one in an empty cell after the player’s move.
Leaf nodes represent the “goodness” of a state (using the heuristic function (its explanation is beyond the scope of this answer)) by considering the following factors:
arrangement of tiles
values of tiles
potential for tile merges
So, from the root node, the algorithm takes the move, resulting in the best-expected state.
The whole process is repeated recursively after each move.
In short, it calculates an expected score for each move by considering the probability of each tile appearing and the potential outcome of each move. It chooses the move that results in the highest expected score based on that calculated expected score.
It is important to note that this approach can help you achieve high scores and perform well in most scenarios by helping you make smarter choices for playing this game, but it is still not guaranteed to make optimal moves every time you use this approach.
Wrap up
To wrap this up, 2048 is a complex game, and finding an optimal solution is difficult. None of the algorithms guarantee optimal moves in every situation. However, we use algorithms like Expectimax to make smarter choices for playing this game.
