Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
doc
 
 
sql
 
 
 
 
 
 
 
 
 
 
highscore

Solver2048

Demo

You can view a live stream of the A.I. in action here: http://32768.eu.

Build

Main article: Building Solver2048

TL;DR: git clone https://github.com/mmiermans/solver2048.git && cd solver2048/Solver2048 && make && ./Debug/Solver2048

Performance

  • Max-tile histogram and score box-plot are included below the live stream.
  • Up to 17 million nodes/second.
  • Evaluates every possible position, up to 12 moves ahead.
  • Reaches the 16384 tile 55% of the time.
  • Reached the 32768 tile after 42 games in 48 hours.

Design

The solver has the following features:

  • The game state is stored compactly in a 64-bit integer bitboard.
  • A depth-first search is performed on an expectimax tree with alternating max and chance nodes.
  • Max and chance nodes are generated simultaneously to remove some duplicate nodes early on.
  • More duplicate nodes are prevented with a custom hashmap, which sacrifices theoretical correctness for raw performance and memory efficiency.
  • A simple and efficient cost function is used: sum all tiles, except those lying in a decreasing zig-zag pattern starting from the upper-left corner.
  • The solver cleverly determines the look-ahead (depth of the decision tree):
    • The look-ahead is based on the cost of the previous move, such that more computational time is spent on bad board positions.
    • The look-ahead is restricted to a range that depends on the sum of all tiles.
    • If there is a sharp increase in cost after the board is evaluated, then the evaluation is performed again with maximum look-ahead.