Multi-Stage Temporal Difference Learning for 2048-like Games
  Szubert and Jaskowski successfully used temporal difference (TD) learning
together with n-tuple networks for playing the game 2048. However, we observed
a phenomenon that the programs based on TD learning still hardly reach large
tiles. In this paper, we propose multi-stage TD (MS-TD) learning, a kind of
hierarchical reinforcement learning method, to effectively improve the
performance for the rates of reaching large tiles, which are good metrics to
analyze the strength of 2048 programs. Our experiments showed significant
improvements over the one without using MS-TD learning. Namely, using 3-ply
expectimax search, the program with MS-TD learning reached 32768-tiles with a
rate of 18.31%, while the one with TD learning did not reach any. After further
tuned, our 2048 program reached 32768-tiles with a rate of 31.75% in 10,000
games, and one among these games even reached a 65536-tile, which is the first
ever reaching a 65536-tile to our knowledge. In addition, MS-TD learning method
can be easily applied to other 2048-like games, such as Threes. Based on MS-TD
learning, our experiments for Threes also demonstrated similar performance
improvement, where the program with MS-TD learning reached 6144-tiles with a
rate of 7.83%, while the one with TD learning only reached 0.45%.
