2048 (3x3, 4x4, 5x5) AI for Android

11 things about 2048 (3x3, 4x4, 5x5) AI

1. (a) Monte Carlo Tree Search (MCTS) is a heuristic search algorithm introduced in 2006 for computer Go, and has been used in other games like chess, and of course this 2048 game.

2. We created an AI that takes advantage of multiple state-of-the-art algorithms, including Monte Carlo Tree Search (MCTS) [a], Expectimax [b], Iterative Deepening Depth-First Search (IDDFS) [c] and Reinforcement Learning [d].

3. Monte Carlo Tree Search Algorithm chooses the best possible move from the current state of game's tree (similar to IDDFS).

4. This technique is commonly used in games with undeterministic behavior, such as Minesweeper (random mine location), Pacman (random ghost move) and this 2048 game (random tile spawn position and its number value).

5. This 2048 AI implementation assigns various heuristic scores (or penalties) on multiple features (e.g. empty cell count) to compute the optimal next move.

6. (b) Expectimax search is a variation of the minimax algorithm, with addition of "chance" nodes in the search tree.

7. (c)Iterative Deepening depth-first search (IDDFS) is a search strategy in which a depth-limited version of DFS is run repeatedly with increasing depth limits.

8. We leverage multiple algorithms to create an AI for the classic 2048 puzzle game.

9. This 2048 RL implementation has no hard-coded intelligence (i.e. no heuristic score based on human understanding of the game).

10. IDDFS is optimal like breadth-first search (BFS), but uses much less memory.

11. (d) Reinforcement learning is the training of ML models to yield an action (or decision) in an environment in order to maximize cumulative reward.