2048Solver

2048 webapp and AI solver in Python

Demo (not sped up)

Results

For 100 runs:

• Achieves the 2048 tile 100% of the time

Result	Score
Mean	105,369
Median	99,000
Max	289,920

Features

• Expectimax, an adversarial search for non-deterministic games
• Heuristics
  • Penalty for non-monotonic columns and rows
  • No. of empty spaces
  • No. of potential merges
  • Large values on the edge
• Heuristic weights calculated with CMA-ES
• Bitboard representation for grid
• Transposition table to speed up search
• Multithreading
• Prune nodes below a dynamic probability threshold
• Dynamic depth for search

Potential improvements

• N-tuple network trained with reinforcement learning for evaluation function
• Port to a compiled language for faster performance
• Deep neural network according to recent research

Dependencies

• flask
• cma
• tqdm (for benchmarks)

How to use:

• Run main.py to run flask webapp
• Run calc_cma.py to calculate heuristic weights based on CMA-ES
• Run benchmark.py for benchmarking

References

• This StackOverflow answer for What is the optimal algorithm for the game 2048?
• nneonneo/2048-ai
• ziap/2048-tdl
• W. Jaśkowski, "Mastering 2048 With Delayed Temporal Coherence Learning, Multistage Weight Promotion, Redundant Encoding, and Carousel Shaping," in IEEE Transactions on Games, vol. 10, no. 1, pp. 3-14, March 2018, doi: 10.1109/TCIAIG.2017.2651887.