What is the optimal algorithm for the game 2048

Question

I have recently stumbled upon the game 2048  You merge similar tiles by moving them in any of the four directions to make  bigger  tiles  After each move  a new tile appears at random empty position with a value of either 2 or 4  The game terminates when all the boxes are filled and there are no moves that can merge tiles  or you create a tile with a value of 2048   One  I need to follow a well-defined strategy to reach the goal  So  I thought of writing a program for it   My current algorithm   while   game over        for each possible move          count no of merges for 2-tiles and 4-tiles     choose the move with a large number of merges     What I am doing is at any point  I will try to merge the tiles with values 2 and 4  that is  I try to have 2 and 4 tiles  as minimum as possible  If I try it this way  all other tiles were automatically getting merged and the strategy seems good   But  when I actually use this algorithm  I only get around 4000 points before the game terminates  Maximum points AFAIK is slightly more than 20 000 points which is way larger than my current score  Is there a better algorithm than the above

User · Answer

This algorithm is not optimal for winning the game  but it is fairly optimal in terms of performance and amount of code needed     if can move neither right  up or down      direction   left   else         do             direction   random from  right  down  up            while can not move in  direction

User · Answer

My attempt uses expectimax like other solutions above  but without bitboards  Nneonneo s solution can check 10millions of moves which is approximately a depth of 4 with 6 tiles left and 4 moves possible  2 6 4 4  In my case  this depth takes too long to explore  I adjust the depth of expectimax search according to the number of free tiles left   depth   free  gt  7   1    free  gt  4   2   3    The scores of the boards are computed with the weighted sum of the square of the number of free tiles and the dot product of the 2D grid with this     10 8 7 6 5      5  7 1 3     - 5 -1 5 -1 8 -2     -3 8 -3 7 -3 5 -3     which forces to organize tiles descendingly in a sort of snake from the top left tile   code below or on github    x000D   x000D  var n   4  x000D   M   new MatrixTransform n   x000D   x000D  var ai    weights   1  1   depth  1      depth 1 by default  but we adjust it on every prediction according to the number of free tiles x000D   x000D  var snake    10 8 7 6 5   x000D                5  7 1 3   x000D               - 5 -1 5 -1 8 -2   x000D               -3 8 -3 7 -3 5 -3   x000D  snake snake map function a  return a map Math exp    x000D   x000D  initialize ai  x000D   x000D  function run ai    x000D   var p  x000D   while   p   predict ai      null    x000D    move p  ai   x000D     x000D     console log ai grid   maxValue ai grid   x000D   ai maxValue   maxValue ai grid  x000D   console log ai  x000D    x000D   x000D  function initialize ai    x000D   ai grid       x000D   for  var i   0  i  lt  n  i      x000D    ai grid i       x000D    for  var j   0  j  lt  n  j      x000D     ai grid i  j    0  x000D      x000D     x000D   rand ai grid  x000D   rand ai grid  x000D   ai steps   0  x000D    x000D   x000D  function move p  ai      0 up  1 right  2 down  3 left x000D   var newgrid   mv p  ai grid   x000D   if   equal newgrid  ai grid     x000D      console log stats newgrid  ai grid   x000D    ai grid   newgrid  x000D    try   x000D     rand ai grid  x000D     ai steps    x000D      catch  e    x000D     console log  no room   e  x000D      x000D     x000D    x000D   x000D  function predict ai    x000D   var free   freeCells ai grid   x000D   ai depth   free  gt  7   1    free  gt  4   2   3   x000D   var root    path     prob  1 grid  ai grid children       x000D   var x   expandMove root  ai  x000D     console log  number of leaves   x  x000D     console log  number of leaves2   countLeaves root   x000D   if   root children length  return null x000D   var values   root children map expectimax   x000D   var mx   max values   x000D   return root children mx 1   path 0  x000D   x000D    x000D   x000D  function countLeaves node    x000D   var x   0  x000D   if   node children length  return 1  x000D   for  var n of node children  x000D    x    countLeaves n   x000D   return x  x000D    x000D   x000D  function expectimax node    x000D   if   node children length    x000D    return node score x000D     else   x000D    var values   node children map expectimax   x000D    if  node prob      we are at a max node x000D     return Math max apply null  values  x000D      else      we are at a random node x000D     var avg   0  x000D     for  var i   0  i  lt  values length  i    x000D      avg    node children i  prob   values i  x000D     return avg    values length   2  x000D      x000D     x000D    x000D   x000D  function expandRandom node  ai    x000D   var x   0  x000D   for  var i   0  i  lt  node grid length  i    x000D    for  var j   0  j  lt  node grid length  j    x000D     if   node grid i  j     x000D      var grid2   M copy node grid   x000D       grid4   M copy node grid   x000D      grid2 i  j    2  x000D      grid4 i  j    4  x000D      var child2    grid  grid2 prob   9 path  node path children       x000D      var child4    grid  grid4 prob   1 path  node path children      x000D      node children push child2  x000D      node children push child4  x000D      x    expandMove child2  ai  x000D      x    expandMove child4  ai  x000D       x000D   return x  x000D    x000D   x000D  function expandMove node  ai       node  grid path score  x000D   var isLeaf   true  x000D    x   0  x000D   if  node path length  lt  ai depth    x000D    for  var move of 0  1  2  3     x000D     var grid   mv move  node grid   x000D     if   equal grid  node grid     x000D      isLeaf   false  x000D      var child    grid  grid path  node path concat  move   children      x000D      node children push child  x000D      x    expandRandom child  ai  x000D       x000D      x000D     x000D   if  isLeaf  node score   dot ai weights  stats node grid   x000D   return isLeaf   1   x  x000D    x000D   x000D   x000D   x000D  var cells      x000D  var table   document querySelector  table    x000D  for  var i   0  i  lt  n  i      x000D   var tr   document createElement  tr    x000D   cells i        x000D   for  var j   0  j  lt  n  j      x000D    cells i  j    document createElement  td    x000D    tr appendChild cells i  j   x000D     x000D   table appendChild tr   x000D    x000D   x000D  function updateUI ai    x000D   cells forEach function a  i    x000D    a forEach function el  j    x000D     el innerHTML   ai grid i  j        x000D       x000D       x000D    x000D   x000D   x000D  updateUI ai   x000D  updateHint predict ai    x000D   x000D  function runAI     x000D   var p   predict ai   x000D   if  p    null  amp  amp  ai running    x000D    move p  ai   x000D    updateUI ai   x000D    updateHint p   x000D    requestAnimationFrame runAI   x000D     x000D    x000D  runai onclick   function     x000D   if   ai running    x000D    this innerHTML    stop AI   x000D    ai running   true  x000D    runAI    x000D     else   x000D    this innerHTML    run AI   x000D    ai running   false  x000D    updateHint predict ai    x000D     x000D    x000D   x000D   x000D  function updateHint dir    x000D   hintvalue innerHTML                        dir         x000D    x000D   x000D  document addEventListener  keydown   function event    x000D   if   event target matches   r      return  x000D   event preventDefault       avoid scrolling x000D   if  event which in map    x000D    move map event which   ai  x000D    console log stats ai grid   x000D    updateUI ai   x000D    updateHint predict ai    x000D     x000D     x000D  var map     x000D   38  0     Up x000D   39  1     Right x000D   40  2     Down x000D   37  3     Left x000D     x000D  init onclick   function     x000D   initialize ai   x000D   updateUI ai   x000D   updateHint predict ai    x000D    x000D   x000D   x000D  function stats grid  previousGrid    x000D   x000D   var free   freeCells grid   x000D   x000D   var c   dot2 grid  snake   x000D   x000D   return  c  free   free   x000D    x000D   x000D  function dist2 a  b      squared 2D distance x000D   return Math pow a 0  - b 0   2    Math pow a 1  - b 1   2  x000D    x000D   x000D  function dot a  b    x000D   var r   0  x000D   for  var i   0  i  lt  a length  i    x000D    r    a i    b i   x000D   return r x000D    x000D   x000D  function dot2 a  b    x000D   var r   0  x000D   for  var i   0  i  lt  a length  i    x000D    for  var j   0  j  lt  a 0  length  j    x000D     r    a i  j    b i  j  x000D   return r  x000D    x000D   x000D  function product a    x000D   return a reduce function v  x    x000D    return v   x x000D      1  x000D    x000D   x000D  function maxValue grid    x000D   return Math max apply null  grid map function a    x000D    return Math max apply null  a  x000D        x000D    x000D   x000D  function freeCells grid    x000D   return grid reduce function v  a    x000D    return v   a reduce function t  x    x000D     return t    x    0  x000D       0  x000D      0  x000D    x000D   x000D  function max arr       return  value  index  of the max x000D   var m    -Infinity  null   x000D   for  var i   0  i  lt  arr length  i      x000D    if  arr i   gt  m 0   m    arr i   i   x000D     x000D   return m x000D    x000D   x000D  function min arr       return  value  index  of the min x000D   var m    Infinity  null   x000D   for  var i   0  i  lt  arr length  i      x000D    if  arr i   lt  m 0   m    arr i   i   x000D     x000D   return m x000D    x000D   x000D  function maxScore nodes    x000D   var min     x000D    score  -Infinity  x000D    path     x000D      x000D   for  var node of nodes    x000D    if  node score  gt  min score  min   node  x000D     x000D   return min  x000D    x000D   x000D   x000D  function mv k  grid    x000D   var tgrid   M itransform k  grid   x000D   for  var i   0  i  lt  tgrid length  i      x000D    var a   tgrid i   x000D    for  var j   0  jj   0  j  lt  a length  j    x000D     if  a j   a jj       j  lt  a length - 1  amp  amp  a j     a j   1     2   a j      a j  x000D    for    jj  lt  a length  jj    x000D     a jj    0  x000D     x000D   return M transform k  tgrid   x000D    x000D   x000D  function rand grid    x000D   var r   Math floor Math random     freeCells grid    x000D     r   0  x000D   for  var i   0  i  lt  grid length  i      x000D    for  var j   0  j  lt  grid length  j      x000D     if   grid i  j     x000D      if   r    r    x000D       grid i  j    Math random    lt   9   2   4 x000D        x000D       r    x000D       x000D      x000D     x000D    x000D   x000D  function equal grid1  grid2    x000D   for  var i   0  i  lt  grid1 length  i    x000D    for  var j   0  j  lt  grid1 length  j    x000D     if  grid1 i  j     grid2 i  j   return false  x000D   return true  x000D    x000D   x000D  function conv44valid a  b    x000D   var r   0  x000D   for  var i   0  i  lt  4  i    x000D    for  var j   0  j  lt  4  j    x000D     r    a i  j    b 3 - i  3 - j  x000D   return r x000D    x000D   x000D  function MatrixTransform n    x000D   var g       x000D    ig       x000D   for  var i   0  i  lt  n  i      x000D    g i        x000D    ig i        x000D    for  var j   0  j  lt  n  j      x000D     g i  j      j  i   i  n-1-j   j  n-1-i   i  j       transformation matrix in the 4 directions g i  j     up  right  down  left  x000D     ig i  j      j  i   i  n-1-j   n-1-j  i   i  j       the inverse tranformations x000D      x000D     x000D   this transform   function k  grid    x000D    return this transformer k  grid  g  x000D     x000D   this itransform   function k  grid       inverse transform x000D    return this transformer k  grid  ig  x000D     x000D   this transformer   function k  grid  mat    x000D    var newgrid       x000D    for  var i   0  i  lt  grid length  i      x000D     newgrid i        x000D     for  var j   0  j  lt  grid length  j    x000D      newgrid i  j    grid mat i  j  k  0   mat i  j  k  1    x000D      x000D    return newgrid  x000D     x000D   this copy   function grid    x000D    return this transform 3  grid  x000D     x000D    x000D  body   x000D   font-family  Arial  x000D    x000D  table  th  td   x000D   border  1px solid black  x000D   margin  0 auto  x000D   border-collapse  collapse  x000D    x000D  td   x000D   width  35px  x000D   height  35px  x000D   text-align  center  x000D    x000D  button   x000D   margin  2px  x000D   padding  3px 15px  x000D   color  rgba 0 0 0  9   x000D    x000D   r   x000D   display  flex  x000D   align-items  center  x000D   justify-content  center  x000D   margin   2em  x000D   position  relative  x000D    x000D   hintvalue   x000D   font-size  1 4em  x000D   padding  2px 8px  x000D   display  inline-flex  x000D   justify-content  center  x000D   width  30px  x000D    x000D   lt table title  press arrow keys  gt  lt  table gt  x000D   lt div class  r  gt  x000D       lt button id init gt init lt  button gt  x000D       lt button id runai gt run AI lt  button gt  x000D       lt span id  hintvalue  title  Best predicted move to do  use your arrow keys  tabindex  -1  gt  lt  span gt  x000D   lt  div gt  x000D   x000D   x000D

User · Answer

I became interested in the idea of an AI for this game containing no hard-coded intelligence  i e no heuristics  scoring functions etc   The AI should  know  only the game rules  and  figure out  the game play  This is in contrast to most AIs  like the ones in this thread  where the game play is essentially brute force steered by a scoring function representing human understanding of the game   AI Algorithm  I found a simple yet surprisingly good playing algorithm  To determine the next move for a given board  the AI plays the game in memory using random moves until the game is over  This is done several times while keeping track of the end game score  Then the average end score per starting move is calculated  The starting move with the highest average end score is chosen as the next move   With just 100 runs  i e in memory games  per move  the AI achieves the 2048 tile 80  of the times and the 4096 tile 50  of the times  Using 10000 runs gets the 2048 tile 100   70  for 4096 tile  and about 1  for the 8192 tile   See it in action  The best achieved score is shown here     An interesting fact about this algorithm is that while the random-play games are unsurprisingly quite bad  choosing the best  or least bad  move leads to very good game play  A typical AI game can reach 70000 points and last 3000 moves  yet the in-memory random play games from any given position yield an average of 340 additional points in about 40 extra moves before dying   You can see this for yourself by running the AI and opening the debug console    This graph illustrates this point  The blue line shows the board score after each move  The red line shows the algorithm s best random-run end game score from that position  In essence  the red values are  pulling  the blue values upwards towards them  as they are the algorithm s best guess  It s interesting to see the red line is just a tiny bit above the blue line at each point  yet the blue line continues to increase more and more     I find it quite surprising that the algorithm doesn t need to actually foresee good game play in order to chose the moves that produce it   Searching later I found this algorithm might be classified as a Pure Monte Carlo Tree Search algorithm   Implementation and Links  First I created a JavaScript version which can be seen in action here  This version can run 100 s of runs in decent time  Open the console for extra info    source   Later  in order to play around some more I used  nneonneo highly optimized infrastructure and implemented my version in C    This version allows for up to 100000 runs per move and even 1000000 if you have the patience  Building instructions provided  It runs in the console and also has a remote-control to play the web version   source   Results  Surprisingly  increasing the number of runs does not drastically improve the game play  There seems to be a limit to this strategy at around 80000 points with the 4096 tile and all the smaller ones  very close to the achieving the 8192 tile  Increasing the number of runs from 100 to 100000 increases the odds of getting to this score limit  from 5  to 40   but not breaking through it    Running 10000 runs with a temporary increase to 1000000 near critical positions managed to break this barrier less than 1  of the times achieving a max score of 129892 and the 8192 tile   Improvements  After implementing this algorithm I tried many improvements including using the min or max scores  or a combination of min max and avg  I also tried using depth  Instead of trying K runs per move  I tried K moves per move list of a given length   up up left  for example  and selecting the first move of the best scoring move list   Later I implemented a scoring tree that took into account the conditional probability of being able to play a move after a given move list   However  none of these ideas showed any real advantage over the simple first idea  I left the code for these ideas commented out in the C   code   I did add a  Deep Search  mechanism that increased the run number temporarily to 1000000 when any of the runs managed to accidentally reach the next highest tile  This offered a time improvement    I d be interested to hear if anyone has other improvement ideas that maintain the domain-independence of the AI   2048 Variants and Clones  Just for fun  I ve also implemented the AI as a bookmarklet  hooking into the game s controls  This allows the AI to work with the original game and many of its variants   This is possible due to domain-independent nature of the AI  Some of the variants are quite distinct  such as the Hexagonal clone

User · Answer

I copy here the content of a post on my blog    The solution I propose is very simple and easy to implement  Although  it has reached the score of 131040  Several benchmarks of the algorithm performances are presented     Algorithm  Heuristic scoring algorithm  The assumption on which my algorithm is based is rather simple  if you want to achieve higher score  the board must be kept as tidy as possible  In particular  the optimal setup is given by a linear and monotonic decreasing order of the tile values  This intuition will give you also the upper bound for a tile value   where n is the number of tile on the board     There s a possibility to reach the 131072 tile if the 4-tile is randomly generated instead of the 2-tile when needed   Two possible ways of organizing the board are shown in the following images     To enforce the ordination of the tiles in a monotonic decreasing order  the score si computed as the sum of the linearized values on the board multiplied by the values of a geometric sequence with common ratio r lt 1        Several linear path could be evaluated at once  the final score will be the maximum score of any path   Decision rule  The decision rule implemented is not quite smart  the code in Python is presented here    staticmethod def nextMove board recursion depth 3       m s   AI nextMoveRecur board recursion depth recursion depth      return m   staticmethod def nextMoveRecur board depth maxDepth base 0 9       bestScore   -1      bestMove   0     for m in range 1 5           if board validMove m                newBoard   copy deepcopy board              newBoard move m add tile True               score   AI evaluate newBoard              if depth    0                  my m my s   AI nextMoveRecur newBoard depth-1 maxDepth                  score    my s pow base maxDepth-depth 1               if score  gt  bestScore                   bestMove   m                 bestScore   score     return  bestMove bestScore     An implementation of the minmax or the Expectiminimax will surely improve the algorithm  Obviously a more sophisticated decision rule will slow down the algorithm and it will require some time to be implemented I will try a minimax implementation in the near future   stay tuned   Benchmark   T1 - 121 tests - 8 different paths - r 0 125   T2 - 122 tests - 8-different paths - r 0 25   T3 - 132 tests - 8-different paths - r 0 5  T4 - 211 tests - 2-different paths - r 0 125  T5 - 274 tests - 2-different paths - r 0 25  T6 - 211 tests - 2-different paths - r 0 5        In case of T2  four tests in ten generate the 4096 tile with an average score of  42000  Code  The code can be found on GiHub at the following link  https   github com Nicola17 term2048-AI It is based on term2048 and it s written in Python  I will implement a more efficient version in C   as soon as possible

User · Answer

There is already an AI implementation for this game here  Excerpt from README      The algorithm is iterative deepening depth first alpha-beta search  The evaluation function tries to keep the rows and columns monotonic  either all decreasing or increasing  while minimizing the number of tiles on the grid    There is also a discussion on Hacker News about this algorithm that you may find useful

User · Answer

Many of the other answers use AI with computationally expensive searching of possible futures  heuristics  learning and the such  These are impressive and probably the correct way forward  but I wish to contribute another idea   Model the sort of strategy that good players of the game use   For example   13 14 15 16 12 11 10  9  5  6  7  8  4  3  2  1   Read the squares in the order shown above until the next squares value is greater than the current one  This presents the problem of trying to merge another tile of the same value into this square   To resolve this problem  their are 2 ways to move that aren t left or worse up and examining both possibilities may immediately reveal more problems  this forms a list of dependancies  each problem requiring another problem to be solved first  I think I have this chain or in some cases tree of dependancies internally when deciding my next move  particularly when stuck     Tile needs merging with neighbour but is too small  Merge another neighbour with this one   Larger tile in the way  Increase the value of a smaller surrounding tile   etc       The whole approach will likely be more complicated than this but not much more complicated  It could be this mechanical in feel lacking scores  weights  neurones and deep searches of possibilities  The tree of possibilities rairly even needs to be big enough to need any branching at all

User · Answer

I think I found an algorithm which works quite well  as I often reach scores over 10000  my personal best being around 16000  My solution does not aim at keeping biggest numbers in a corner  but to keep it in the top row                Please see the code below   while   game over         move direction up      if   move is possible up              if  move is possible right   amp  amp  move is possible left                 if  number of empty cells after moves left up   gt  number of empty cells after moves right up                     move direction   left              else                 move direction   right            else if   move is possible left                 move direction   left            else if   move is possible right                 move direction   right            else               move direction   down                      do move move direction

User · Answer

Algorithm  while  game over        for each possible move          evaluate next state      choose the maximum evaluation     Evaluation  Evaluation       128  Constant         Number of Spaces x 128        Sum of faces adjacent to a space    1 face  x 4096         Sum of other faces   log face  x 4          Number of possible next moves x 256         Number of aligned values x 2      Evaluation Details  128  Constant    This is a constant  used as a base-line and for other uses like testing      Number of Spaces x 128    More spaces makes the state more flexible  we multiply by 128  which is the median  since a grid filled with 128 faces is an optimal impossible state     Sum of faces adjacent to a space    1 face  x 4096     Here we evaluate faces that have the possibility to getting to merge  by evaluating them backwardly  tile 2 become of value 2048  while tile 2048 is evaluated 2     Sum of other faces   log face  x 4     In here we still need to check for stacked values  but in a lesser way that doesn t interrupt the flexibility parameters  so we have the sum of   x in  4 44         Number of possible next moves x 256    A state is more flexible if it has more freedom of possible transitions      Number of aligned values x 2    This is a simplified check of the possibility of having merges within that state  without making a look-ahead   Note  The constants can be tweaked

User · Answer

EDIT  This is a naive algorithm  modelling human conscious thought process  and gets very weak results compared to AI that search all possibilities since it only looks one tile ahead  It was submitted early in the response timeline   I have refined the algorithm and beaten the game  It may fail due to simple bad luck close to the end  you are forced to move down  which you should never do  and a tile appears where your highest should be  Just try to keep the top row filled  so moving left does not break the pattern   but basically you end up having a fixed part and a mobile part to play with  This is your objective     This is the model I chose by default   1024 512 256 128   8   16  32  64   4   2   x   x   x   x   x   x   The chosen corner is arbitrary  you basically never press one key  the forbidden move   and if you do  you press the contrary again and try to fix it  For future tiles the model always expects the next random tile to be a 2 and appear on the opposite side to the current model  while the first row is incomplete  on the bottom right corner  once the first row is completed  on the bottom left corner    Here goes the algorithm  Around 80  wins  it seems it is always possible to win with more  professional  AI techniques  I am not sure about this  though    initiateModel     while  game over            checkCornerChosen       Unimplemented  but it might be an improvement to change the reference point      for each 3 possible move          evaluateResult       execute move with best score     if no move is available  execute forbidden move and undo  recalculateModel        evaluateResult          calculatesBestCurrentModel        calculates distance to chosen model      stores result      calculateBestCurrentModel            according to the current highest tile acheived and their distribution        A few pointers on the missing steps  Here    The model has changed due to the luck of being closer to the expected model  The model the AI is trying to achieve is   512 256 128  x   X   X   x   x   X   X   x   x   x   x   x   x   And the chain to get there has become    512 256  64  O   8   16  32  O   4   x   x   x   x   x   x   x   The O represent forbidden spaces      So it will press right  then right again  then  right or top depending on where the 4 has created  then will proceed to complete the chain until it gets     So now the model and chain are back to    512 256 128  64   4   8  16   32   X   X   x   x   x   x   x   x   Second pointer  it has had bad luck and its main spot has been taken  It is likely that it will fail  but it can still achieve it     Here the model and chain is     O 1024 512 256   O   O   O  128   8  16   32  64   4   x   x   x   When it manages to reach the 128 it gains a whole row is gained again     O 1024 512 256   x   x  128 128   x   x   x   x   x   x   x   x

User · Answer

I wrote a 2048 solver in Haskell  mainly because I m learning this language right now   My implementation of the game slightly differs from the actual game  in that a new tile is always a  2   rather than 90  2 and 10  4   And that the new tile is not random  but always the first available one from the top left  This variant is also known as Det 2048   As a consequence  this solver is deterministic   I used an exhaustive algorithm that favours empty tiles  It performs pretty quickly for depth 1-4  but on depth 5 it gets rather slow at a around 1 second per move   Below is the code implementing the solving algorithm  The grid is represented as a 16-length array of Integers  And scoring is done simply by counting the number of empty squares   bestMove    Int - gt   Int  - gt  Int bestMove depth grid   maxTuple    gridValue depth  takeTurn x grid   x    x  lt -  0  3   takeTurn x grid          gridValue    Int - gt   Int  - gt  Int gridValue        -1 gridValue 0 grid   length   filter    0  grid  --  lt   SCORING gridValue depth grid   maxInList   gridValue  depth-1   takeTurn x grid    x  lt -  0  3      I thinks it s quite successful for its simplicity  The result it reaches when starting with an empty grid and solving at depth 5 is   Move 4006  2 64 16 4   16 4096 128 512   2048 64 1024 16   2 4 16 2   Game Over   Source code can be found here  https   github com popovitsj 2048-haskell

User · Answer

I m the author of the AI program that others have mentioned in this thread  You can view the AI in action or read the source  Currently  the program achieves about a 90  win rate running in javascript in the browser on my laptop given about 100 milliseconds of thinking time per move  so while not perfect  yet   it performs pretty well  Since the game is a discrete state space  perfect information  turn-based game like chess and checkers  I used the same methods that have been proven to work on those games  namely minimax search with alpha-beta pruning  Since there is already a lot of info on that algorithm out there  I ll just talk about the two main heuristics that I use in the static evaluation function and which formalize many of the intuitions that other people have expressed here  Monotonicity This heuristic tries to ensure that the values of the tiles are all either increasing or decreasing along both the left right and up down directions  This heuristic alone captures the intuition that many others have mentioned  that higher valued tiles should be clustered in a corner  It will typically prevent smaller valued tiles from getting orphaned and will keep the board very organized  with smaller tiles cascading in and filling up into the larger tiles  Here s a screenshot of a perfectly monotonic grid  I obtained this by running the algorithm with the eval function set to disregard the other heuristics and only consider monotonicity   Smoothness The above heuristic alone tends to create structures in which adjacent tiles are decreasing in value  but of course in order to merge  adjacent tiles need to be the same value  Therefore  the smoothness heuristic just measures the value difference between neighboring tiles  trying to minimize this count  A commenter on Hacker News gave an interesting formalization of this idea in terms of graph theory  Here s a screenshot of a perfectly smooth grid  courtesy of this excellent parody fork   Free Tiles And finally  there is a penalty for having too few free tiles  since options can quickly run out when the game board gets too cramped  And that s it  Searching through the game space while optimizing these criteria yields remarkably good performance  One advantage to using a generalized approach like this rather than an explicitly coded move strategy is that the algorithm can often find interesting and unexpected solutions  If you watch it run  it will often make surprising but effective moves  like suddenly switching which wall or corner it s building up against  Edit  Here s a demonstration of the power of this approach  I uncapped the tile values  so it kept going after reaching 2048  and here is the best result after eight trials   Yes  that s a 4096 alongside a 2048     That means it achieved the elusive 2048 tile three times on the same board

User · Answer

This is not a direct answer to OP s question  this is more of the stuffs  experiments  I tried so far to solve the same problem and obtained some results and have some observations that I want to share  I am curious if we can have some further insights from this  I just tried my minimax implementation with alpha-beta pruning with search-tree depth cutoff at 3 and 5  I was trying to solve the same problem for a 4x4 grid as a project assignment for the edX course ColumbiaX  CSMM 101x Artificial Intelligence  AI   I applied convex combination  tried different heuristic weights  of couple of heuristic evaluation functions  mainly from intuition and from the ones discussed above   Monotonicity Free Space Available  In my case  the computer player is completely random  but still i assumed adversarial settings and implemented the AI player agent as the max player  I have 4x4 grid for playing the game  Observation  If I assign too much weights to the first heuristic function or the second heuristic function  both the cases the scores the AI player gets are low  I played with many possible weight assignments to the heuristic functions and take a convex combination  but very rarely the AI player is able to score 2048  Most of the times it either stops at 1024 or 512  I also tried the corner heuristic  but for some reason it makes the results worse  any intuition why  Also  I tried to increase the search depth cut-off from 3 to 5  I can t increase it more since searching that space exceeds allowed time even with pruning  and added one more heuristic that looks at the values of adjacent tiles and gives more points if they are merge-able  but still I am not able to get 2048  I think it will be better to use Expectimax instead of minimax  but still I want to solve this problem with minimax only and obtain high scores such as 2048 or 4096  I am not sure whether I am missing anything  Below animation shows the last few steps of the game played by the AI agent with the computer player   Any insights will be really very helpful  thanks in advance   This is the link of my blog post for the article  https   sandipanweb wordpress com 2017 03 06 using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer  and the youtube video  https   www youtube com watch v VnVFilfZ0r4  The following animation shows the last few steps of the game played where the AI player agent could get 2048 scores  this time adding the absolute value heuristic too   The following figures show the game tree explored by the player AI agent assuming the computer as adversary for just a single step

User · Answer

I am the author of a 2048 controller that scores better than any other program mentioned in this thread  An efficient implementation of the controller is available on github  In a separate repo there is also the code used for training the controller s state evaluation function  The training method is described in the paper   The controller uses expectimax search with a state evaluation function learned from scratch  without human 2048 expertise  by a variant of temporal difference learning  a reinforcement learning technique   The state-value  function uses an n-tuple network  which is basically a weighted linear function of patterns observed on the board  It involved more than 1 billion weights  in total   Performance  At 1 moves s  609104  100 games average   At 10 moves s  589355  300 games average   At 3-ply  ca  1500 moves s   511759  1000 games average   The tile statistics for 10 moves s are as follows   2048  100  4096  100  8192  100  16384  97  32768  64  32768 16384 8192 4096  10     The last line means having the given tiles at the same time on the board    For 3-ply   2048  100  4096  100  8192  100  16384  96  32768  54  32768 16384 8192 4096  8    However  I have never observed it obtaining the 65536 tile

User · Answer

I developed a 2048 AI using expectimax optimization  instead of the minimax search used by  ovolve s algorithm  The AI simply performs maximization over all possible moves  followed by expectation over all possible tile spawns  weighted by the probability of the tiles  i e  10  for a 4 and 90  for a 2   As far as I m aware  it is not possible to prune expectimax optimization  except to remove branches that are exceedingly unlikely   and so the algorithm used is a carefully optimized brute force search   Performance  The AI in its default configuration  max search depth of 8  takes anywhere from 10ms to 200ms to execute a move  depending on the complexity of the board position  In testing  the AI achieves an average move rate of 5-10 moves per second over the course of an entire game  If the search depth is limited to 6 moves  the AI can easily execute 20  moves per second  which makes for some interesting watching   To assess the score performance of the AI  I ran the AI 100 times  connected to the browser game via remote control   For each tile  here are the proportions of games in which that tile was achieved at least once   2048  100  4096  100  8192  100  16384  94  32768  36    The minimum score over all runs was 124024  the maximum score achieved was 794076  The median score is 387222  The AI never failed to obtain the 2048 tile  so it never lost the game even once in 100 games   in fact  it achieved the 8192 tile at least once in every run   Here s the screenshot of the best run     This game took 27830 moves over 96 minutes  or an average of 4 8 moves per second    Implementation  My approach encodes the entire board  16 entries  as a single 64-bit integer  where tiles are the nybbles  i e  4-bit chunks   On a 64-bit machine  this enables the entire board to be passed around in a single machine register   Bit shift operations are used to extract individual rows and columns  A single row or column is a 16-bit quantity  so a table of size 65536 can encode transformations which operate on a single row or column  For example  moves are implemented as 4 lookups into a precomputed  move effect table  which describes how each move affects a single row or column  for example  the  move right  table contains the entry  1122 -  0023  describing how the row  2 2 4 4  becomes the row  0 0 4 8  when moved to the right    Scoring is also done using table lookup  The tables contain heuristic scores computed on all possible rows columns  and the resultant score for a board is simply the sum of the table values across each row and column   This board representation  along with the table lookup approach for movement and scoring  allows the AI to search a huge number of game states in a short period of time  over 10 000 000 game states per second on one core of my mid-2011 laptop    The expectimax search itself is coded as a recursive search which alternates between  expectation  steps  testing all possible tile spawn locations and values  and weighting their optimized scores by the probability of each possibility   and  maximization  steps  testing all possible moves and selecting the one with the best score   The tree search terminates when it sees a previously-seen position  using a transposition table   when it reaches a predefined depth limit  or when it reaches a board state that is highly unlikely  e g  it was reached by getting 6  4  tiles in a row from the starting position   The typical search depth is 4-8 moves   Heuristics  Several heuristics are used to direct the optimization algorithm towards favorable positions  The precise choice of heuristic has a huge effect on the performance of the algorithm  The various heuristics are weighted and combined into a positional score  which determines how  good  a given board position is  The optimization search will then aim to maximize the average score of all possible board positions  The actual score  as shown by the game  is not used to calculate the board score  since it is too heavily weighted in favor of merging tiles  when delayed merging could produce a large benefit    Initially  I used two very simple heuristics  granting  bonuses  for open squares and for having large values on the edge  These heuristics performed pretty well  frequently achieving 16384 but never getting to 32768   Petr Mor  vek   xificurk  took my AI and added two new heuristics  The first heuristic was a penalty for having non-monotonic rows and columns which increased as the ranks increased  ensuring that  non-monotonic rows of small numbers would not strongly affect the score  but non-monotonic rows of large numbers hurt the score substantially  The second heuristic counted the number of potential merges  adjacent equal values  in addition to open spaces  These two heuristics served to push the algorithm towards monotonic boards  which are easier to merge   and towards board positions with lots of merges  encouraging it to align merges where possible for greater effect    Furthermore  Petr also optimized the heuristic weights using a  meta-optimization  strategy  using an algorithm called CMA-ES   where the weights themselves were adjusted to obtain the highest possible average score   The effect of these changes are extremely significant  The algorithm went from achieving the 16384 tile around 13  of the time to achieving it over 90  of the time  and the algorithm began to achieve 32768 over 1 3 of the time  whereas the old heuristics never once produced a 32768 tile    I believe there s still room for improvement on the heuristics  This algorithm definitely isn t yet  optimal   but I feel like it s getting pretty close     That the AI achieves the 32768 tile in over a third of its games is a huge milestone  I will be surprised to hear if any human players have achieved 32768 on the official game  i e  without using tools like savestates or undo   I think the 65536 tile is within reach   You can try the AI for yourself  The code is available at https   github com nneonneo 2048-ai

[algorithm] What is the optimal algorithm for the game 2048?

Examples related to algorithm

Examples related to logic

Examples related to artificial-intelligence

Examples related to 2048