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 a 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 are slightly more than 20,000 points which are way larger than my current score. Is there a better algorithm than the above?

Answer 1

One of the ways to tackle this game is Monte-Carlo(MC) Algorithm. It is based on a heuristic search algorithm that provides the most promising moves.

To detect which move(↑, →, ↓, ←) is most promising we can do the following tasks:

• Execute a series of background runs.
• Bundle them up by initial groups.
• Get the average final score for each initial move.
• Now, pick the initial move which has the highest final score.

Here is a piece of code for implementing the algorithm:

func getBestMove(tiles: [Tile]) -> ShiftDirection?

var grids = [[Tile]]()

    for _ in 1...numberOfRuns {

 grids.append(copyTiles(originalTiles: tiles))

    }

    var runs = [Run]()

    for grid in grids {

if let run = generateRun(grid: grid) as Run? {

runs.append(run) }

    }

    return getBestMoveForRuns(runs: runs)

}

struct Run {

    var initialMove: Direction

    var finalScore: Int

}

private func getBestMoveForRuns(runs: [Run]) -> ShiftDirection? {

   grid !runs.isEmpty else {

          print("Received no runs - end of game")    return nil

      }

let runsForUp = runs.filter { $0.initialMove.direction == .up }//$0 is the key means it is the name of the move that you will perform 

let runsForDown = runs.filter { $0.initialMove.direction == .down }

      let runsForLeft = runs.filter { $0.initialMove.direction == .left }

      let runsForRight = runs.filter { $0.initialMove.direction == .right }

let averageScoreForUp = getAverageScoreForRuns(runs: runsForUp)

      let averageScoreForDown = getAverageScoreForRuns(runs: runsForDown)

      let averageScoreForLeft = getAverageScoreForRuns(runs: runsForLeft)

      let averageScoreForRight = getAverageScoreForRuns(runs: runsForRight)

      var selectedMove: ShiftDirection?

      switch [averageScoreForUp, averageScoreForDown, averageScoreForLeft, averageScoreForRight].max() {

      case averageScoreForUp?:

          selectedMove = .up

      case averageScoreForDown?:

          selectedMove = .down

      case averageScoreForRight?:

          selectedMove = .right

      case averageScoreForLeft?:

          selectedMove = .left

      default:

          break

      }

      return selectedMove

  }

• ShiftDirection will receive the value of the best move.

• We are giving the value of the current board to the getBestMove function, which provides each tile with their value and position.

• Then we will introduce a variable grid that contains an array of tiles.

• In for loop, we are copying our board state n number of times. Here n is the number of moves.

• For each copied board we will execute a random run function so that we will get the initial move and the final score. The random run function is very simple, you just have to perform random actions till we have no moves available.

• In the function getBestMovesForRun, we will initialize the initial moves to the respective variable and the average score run so that we get to know about the initial moves and final score.

• After that we will select the best possible move in the switch case:

If the average score is up then we will perform up function and the same goes for all the cases.

I hope you like the answer!

If you want to make your career in Artificial Intelligence then go through this video: