2048-python

June 18, 2014 ยท View on GitHub

This is my 2048 puzzle AI module written in python for an office fun event.

The time limit of every move is 0.1 seconds.

Variants

There are five variants:

  • kcwu.py Normal version.
  • kcwu2.py Based on kcwu.py, multi-process.
  • kcwu_short.py Based on kcwu.py, optimized for maximize (average_score/code_size).
  • kcwu_short2.py Based on kcwu2.py, optimized for maximize (average_score/code_size).
  • kcwu_short_min.py Optimized for minimize (average_score*code_size).

Algorithm

  • Search: expectiminimax. It can search 3 steps ahead using expectiminimax.
  • Eval: inspired from the stackoverflow article, combined with monotoneness, smoothness, and number of blank tile.
    • Weighting of these scores are tuned by hand. I don't know the reason of those magic numbers ;)
  • Optimization:
    • Cut some 4 tile since the probability is low
    • Caching score for search node and eval node.
    • Because python is slow, I put some efforts to optimize for speed and the code is then ugly.

Test result

Result of 100 runs (single thread version):

  • average 85458
  • median 79396
  • max 175484
  • average speed: 17 ms/step

BSD license. The copyright is owned by Google Inc. but this is not official product.