# Submit your algorithms to solve 2048! 18

Posted by **Jiro Doke**,

Jiro's pick this week is 2048 MATLAB.

**"2048"**

Need I say more? I'm certain that many of you know what I'm talking about. 2048 is an online and mobile game created by Gabriele Cirulli recently. All I can say is that it is an addictive game that has already resulted in a few MATLAB implementations.

A couple of weekends ago, I also spent a day implementing a MATLAB version. I probably spent more time than I needed to on trying to make it look as close as possible to the original version, but it was a lot of fun.

But then, one of my colleagues, Seth (who was also just featured in this blog last week), suggested including a mechanism for feeding in different algorithms to solve the game. There must be an AI algorithm that would solve the game or produce a high score consistently.

In the app, I've included the ability to select a MATLAB function as the solving algorithm. Then you can see the algorithm in action as it tries to solve the game. The algorithm must be defined as a MATLAB function that takes in a 4x4 matrix representing the game board (NaN for empty spots) and returns a character array representing the direction to move ('up', 'down', 'right', or 'left'). Here's an example of a simple algorithm that randomly chooses a direction.

function direction = myAI(board) d = {'up', 'down', 'right', 'left'}; direction = d{randi(4)};

I've also included a command line simulator, which you can use to do a montecarlo simulation of a particular algorithm.

game = Game2048Simulator(@myAI); simulate(game, 1000) % 1000 simulations viewResult(game, 25) % 25 histogram bins

We can display the highest score and compute what percentages of the simulation resulted in each of the highest block.

% Display highest score disp(['Highest score: ', num2str(max(game.Result.Score))]) disp(' ') % Get the unique values for high blocks highblocks = game.Result.HighestBlock; blocks = unique(highblocks); % Compute the percentage of occurrance for each high block value nSims = length(highblocks); for id = 1:length(blocks) percentage = nnz(highblocks == blocks(id)) / nSims; disp([num2str(blocks(id)), ' ', num2str(percentage*100), '%']) end

Highest score: 3172 16 0.2% 32 6.8% 64 34.5% 128 49.7% 256 8.8%

**Submit your algorithm!**

So here's a challenge for you. Submit your algorithm and win some MathWorks swag! I will give prizes for each of the following criteria:

- Highest score - In the example above,
**3172**. - Highest block OR in the case of a tie for "Highest block", the one with the highest percentage for the highest block. In the
example above,
**8.8% for 256**.

*It was brought to my attention that since the simulator I've included with the File Exchange entry would stop the game once
you reach 2048, I am limiting the highest score you could get. For my next update, I will change it so that the game will
continue until no more blocks can move.*

If your algorithm is fairly short, please submit the algorithm through the comments for this blog post. Be sure to use code formatting. For lengthy algorithms or multi-function algorithms, feel free to email them to me (as ASCII text).

In the next blog post I write, I will go over some of the winning algorithms you have submitted.

Enjoy!!

Get the MATLAB code

Published with MATLAB® R2014a

**Category:**- Picks

## 18 CommentsOldest to Newest

**1**of 18

Interestingly, going clockwise around the 4 directions has significantly better performance than random directions. For 1000 simulations, this strategy had a mean score of 2319, a median of 2354, and a max score of 7000:

function direction = myAI_sequential(~) % Sequentially select directions from "moves" cell array persistent counter if isempty(counter) counter = 0; % Initialize counter end % The order in which moves are selected moves = {'left','up','right','down'}; direction = moves{mod(counter,length(moves))+1}; counter = counter+1;

**2**of 18

A slight modification that simply doubles each move.

function direction = myAI_sequential_double(~) persistent counter if isempty(counter) counter = 0; end % The order in which moves are selected moves = {'left','left','up','up','right','right','down','down'}; direction = moves{mod(counter,length(moves))+1}; counter = counter+1;

Output:

Highest score: 3408 32 2.4% 64 25.4% 128 52.3% 256 19.9%

**3**of 18

It’s not very clever and it gets stuck occasionally, but it doubled my last attempt.

function direction = myAI_left(board) persistent counter if isempty(counter) counter = 0; end % The order in which moves are selected if ((sum(sum(isnan(board))) == 4 && sum(isnan(board(:,4))) == 4) ||... (sum(sum(isnan(board))) == 8 && sum(sum(isnan(board(:,3:4)))) == 8) ||... (sum(sum(isnan(board))) == 12 && sum(sum(isnan(board(:,2:4)))) == 4)); moves = {'right'}; else moves = {'left','up','down','left'}; end direction = moves{mod(counter,length(moves))+1}; counter = counter+1;

Results from 100 iterations:

Highest score: 6644 32 4% 64 13.5% 128 54.5% 256 27.5% 512 0.5%

**4**of 18

Typo in the above algorithm.

The last conditional should read:

(sum(sum(isnan(board))) == 12 && sum(sum(isnan(board(:,2:4)))) == 12)

The 4 is an error. Now the algorithm will not get stuck.

**5**of 18

Focusing on one (e.g. top left) corner gives some improvement to the above. For 1000 simulations, this strategy had a mean score of 2604.5, a median of 2500, and a max score of 7548:

function direction = myAI_Pooya(board) % One algorithm to solve 2048 % Pooya Rezaei moves_main = {'up', 'left'}; % The main moves that are used sequentially moves_aux = {'down', 'right'}; % Auxiliary moves if the board gets stuck persistent prev_board new_board counter repeat_counter if isempty(prev_board) prev_board = nan(4,4); % initialize previous board end if isempty(counter) counter = 0; % Initialize counter repeat_counter = 0; % Initialize repeat_counter to count the number of % times the board is the same (gets stuck) end new_board = board; if all(~isnan(prev_board(:)) == ~isnan(new_board(:))) repeat_counter = repeat_counter+1; end if repeat_counter < 15 direction = moves_main{mod(counter,2)+1}; else repeat_counter = 0; % make sure that moves_aux is selected such that if 'down' is selected, % next is 'up'. And if 'right' is selected, next move is 'left'. direction = moves_aux{2-mod(counter,2)}; end prev_board = board; counter = counter+1; end

Output:

Highest score: 7548 32 0.4% 64 7.6% 128 36.3% 256 49.6% 512 6.1%

**6**of 18

A simple greedy algorithm. At each step, try to make a move in all 4 directions, and pick the one that results in most blocks empty. Ties are broken randomly. With 100 runs, it achieves highest score 12640.

function direction = greedyAI(board) moves = {'left','up','right','down'}; bestEmptyCells = 0; direction = moves{randi(4)}; for i = 1:length(moves) tryGame = TwentyFortyEight(false, false); tryGame.Board = board; move(tryGame, moves{i}); if tryGame.isGameOver || ~tryGame.isMoved emptyCells = -1; else emptyCells = nnz(isnan(tryGame.Board)); end if emptyCells >= bestEmptyCells bestEmptyCells = emptyCells; direction = moves{i}; end end

A boolean property “isMoved” is added to the class TwentyFortyEight to keep an record if a “move” actually moves any block. It’s updated towards the end of the move() method.

function move(obj, direction) ... if ~isequalwithequalnans(obj.Board, m) ... obj.isMoved = true; else obj.Movement = reshape(1:16,4,4); obj.isMoved = false; end end

Output:

Highest score: 12640 64 1% 128 16% 256 47% 512 34% 1024 2%

**7**of 18

Implemented a look-ahead-n-step greedy algorithm. The AI entry point is the following. “level” specifies how many steps to look ahead.

function direction = recurAI(board) level = 2; [direction, bestEmptyCells, bestScore] = emptyAndScoreAIRecur(board, level);

Then “emptyAndScoreAIRecur” is called recursively to find the best level-step move. In evaluating a move, it’s first ranked according to the number of empty cells it will lead to. If tied in empty cell number, then ranked according to the score the move leads to.

function [direction, bestEmptyCells, bestScore] = emptyAndScoreAIRecur(board, level) assert(level > 0); moves = {'left','up','right','down'}; bestEmptyCells = 0; bestScore = 0; direction = moves{randi(4)}; for i = 1:length(moves) tryGame = TwentyFortyEight(false, false); tryGame.Board = board; move(tryGame, moves{i}); if tryGame.isGameOver || ~tryGame.isMoved emptyCells = -1; score = -1; else score = tryGame.thisScore; emptyCells = nnz(isnan(tryGame.Board)); if level > 1 [tmpDir, emptyCells, recurScore] = emptyAndScoreAIRecur(tryGame.Board, level - 1); score = score + recurScore; end end if score > bestScore bestScore = score; direction = moves{i}; elseif score == bestScore if emptyCells > bestEmptyCells bestEmptyCells = emptyCells; direction = moves{i}; elseif emptyCells == bestEmptyCells direction = moves{i}; end end end

With 2-level recursion (look ahead 2 steps), it gets this in 100 runs:

Highest score: 15840 256 9% 512 58% 1024 33%

**8**of 18

Following on from Guanfeng’s approach, I compute all combinations of 3 moves, with all possible new tiles considered. At the end, every board reachable after 3 moves has a probability, and I marginalize the number of empty spaces left over the first of the 3 moves, to give the expected number of free spaces. I then simply choose the move which maximizes this.

The first game I ran this on it scored 12000+. The second game it got a 2048 square and continued on to score 32188! I have to say it is breathtaking to watch in action.

I haven’t tried getting it to look more moves ahead. It’s a trivial change to the code but the memory and computational requirements increase exponentially.

Anyway, here’s the code:

function d = oliverAI(B) % Convert to log board B(isnan(B)) = 1; B = uint16(log2(B)); % Slide in each direction d = []; A = zeros(4, 4, 0, 'uint16'); for d_ = 1:4 C = slide(B, d_); if ~isequal(B, C) A = cat(3, A, C); d = [d; d_]; end end B = A; p = ones(size(d)); for a = 2:3 % For each board in B, consider all possible positions and values for % the new tile B = reshape(B, 16, []); N = sum(B == 0, 1); % Number of free squares I = zeros(sum(N)*2, 1); i = 0; % Expand the boards array to hold all possible examples for b = find(N) I(i+1:i+N(b)*2) = b; i = i + N(b) * 2; end B = B(:,I); d = d(I); p = p(I); i = 0; % For each board for b = find(N) j = find(B(:,i+1) == 0); % Add in the new 2s for c = 1:N(b) p(c+i) = p(c+i) * (0.9 / N(b)); B(j(c),c+i) = 1; end i = i + N(b); % Add in the new 4s for c = 1:N(b) p(c+i) = p(c+i) * (0.1 / N(b)); B(j(c),c+i) = 2; end i = i + N(b); end B = reshape(B, 4, 4, []); % Slide all the boards in each direction A = zeros(4, 4, 0, 'uint16'); d__ = zeros(1, 0); p_ = []; for d_ = 1:4 C = slide(B, d_); M = any(reshape(B ~= C, 16, [])); A = cat(3, A, C(:,:,M)); p_ = [p_; p(M)]; d__ = [d__; d(M)]; end B = A; p = p_; d = d__; end % Maximize the expected number of zeros after the moves d = accumarray(d(:), sum(reshape(B, 16, []) == 0, 1)' .* p(:), [4 1]); d_ = max(d); d = find(d_ == d); if numel(d) > 1 d = d(ceil(rand(1)*end)); end % Output the string for the direction d_ = {'up', 'down', 'right', 'left'}; d = d_{d}; function B = slide(B, dir) persistent lut if isempty(lut) % Precompute the fast lookup for sliding up [a, b, c, d] = ndgrid(0:11); a = [a(:)'; b(:)'; c(:)'; d(:)']; lut = zeros(size(a)); % Compute the slide manually for b = 1:size(a, 2) d = a(:,b); d = d(d ~= 0); for c = 1:numel(d)-1 if d(c) == d(c+1) && d(c) d(c) = d(c) + 1; d(c+1:end) = [d(c+2:end); 0]; end end lut(1:numel(d),b) = d; end lut = uint16(lut); % Compress for better use of cache end % Do the slide using fast table look up sz = size(B); % Transpose if dir > 2 B = permute(B, [2 1 3]); end % Reverse direction if dir == 2 || dir == 3 B = B(end:-1:1,:,:); end % Do the lookup B = reshape(lut(:,sum(bsxfun(@times, uint16([1 12 144 1728]'), B), 1, 'native')+1), sz); % Reverse direction if dir == 2 || dir == 3 B = B(end:-1:1,:,:); end % Untranspose if dir > 2 B = permute(B, [2 1 3]); end

**9**of 18

I just ran my code looking 4 moves ahead. It is much slower, but it speeds up when the board gets more cluttered (as there are fewer possible new tiles to consider). Of course, when the board gets more cluttered is exactly when you might want to look more moves ahead, so some dynamic selection of the number of moves to look ahead might be sensible. Having said that, it only made 12476 on the first go, so it doesn’t seem to offer much improvement over 3 looking moves ahead.

**10**of 18

Wow, this is great, everyone! I’m impressed at these algorithms!

@Guanfeng Liang, at least for this post, I don’t want to change the original class definition, in order to keep everything the same and fair for everyone. So I simply replaced your

~tryGame.isMoved

with

isequalwithequalnans(tryGame.Board, board)

These should be equivalent. You also had

score = tryGame.thisScore;

which I replaced with

score = max(tryGame.Scores);

Keep them coming!

**11**of 18

I thought a bit more about how I choose the direction based on the marginalization, and made a few improvements. Firstly, instead of marginalizing over the first move, I marginalize over sets of N moves. Secondly, instead of maximizing expected number of free squares, I maximize expected gain in score. Finally, I do some dynamic selection of number of moves to look ahead; when the board is more cluttered, I look more moves ahead.

I have run this code on one game only so far. It mostly runs as fast as a human could play (just pressing random keys), but does slow down when you get to only 2 free tiles, as I look 5 moves ahead at that point. However, it’s only about a second in that case too (on my decent PC). The result was: score – 36560, highest square – 2048, moves – 1900.

I’m sure improvements could be made, especially in taking into account the probability of the game ending, and minimizing this.

Here’s the code:

function d = oliverAI(B) % Convert to log board B(isnan(B)) = 1; B = uint16(log2(B)); % How many moves should we look ahead movesAhead = 3 + sum(sum(B(:) == 0) < [3 7]); % Slide in each direction d = []; s = []; A = zeros(4, 4, 0, 'uint16'); for d_ = 1:4 [C, s_] = slide(B, d_); if ~isequal(B, C) A = cat(3, A, C); d = [d d_]; s = [s; s_]; end end B = A; p = ones(numel(d), 1); for a = 2:movesAhead % For each board in B, consider all possible positions and values for % the new tile B = reshape(B, 16, []); N = sum(B == 0, 1); % Number of free squares I = zeros(sum(N)*2, 1); i = 0; % Expand the boards array to hold all possible examples for b = find(N) I(i+1:i+N(b)*2) = b; i = i + N(b) * 2; end B = B(:,I); d = d(:,I); p = p(I); s = s(I); i = 0; % For each board for b = find(N) j = find(B(:,i+1) == 0); % Add in the new 2s for c = 1:N(b) p(c+i) = p(c+i) * (0.9 / N(b)); B(j(c),c+i) = 1; end i = i + N(b); % Add in the new 4s for c = 1:N(b) p(c+i) = p(c+i) * (0.1 / N(b)); B(j(c),c+i) = 2; end i = i + N(b); end B = reshape(B, 4, 4, []); % Slide all the boards in each direction A = zeros(4, 4, 0, 'uint16'); d__ = zeros(a, 0); p_ = []; s_ = []; for d_ = 1:4 [C, s__] = slide(B, d_); M = any(reshape(B ~= C, 16, [])); A = cat(3, A, C(:,:,M)); p_ = [p_; p(M)]; s_ = [s_; s(M)+s__(M)]; d__ = [d__ [d(:,M); zeros(1, sum(M))+d_]]; end B = A; p = p_; s = s_; d = d__; end % Compute the expected gain in score for a each set of moves and maximize % over this [s_, d_] = max(accumarray(((4 .^ (0:movesAhead-1)) * (d-1))'+1, double(s(:)) .* p(:), [4^movesAhead 1])); d_ = mod(d_ - 1, 4) + 1; % Maximize the expected number of zeros after the moves %[d, d] = max(accumarray(d(1,:)', sum(reshape(B, 16, []) == 0, 1)' .* p(:), [4 1])); % Output the string for the direction d = {'up', 'down', 'right', 'left'}; d = d{d_}; function [B, s] = slide(B, dir) persistent lut lutf luts if isempty(lut) % Precompute the fast lookup for sliding up [a, b, c, d] = ndgrid(0:13); a = [a(:)'; b(:)'; c(:)'; d(:)']; lut = zeros(4, size(a, 2), 'uint16'); % Compress for better use of cache luts = zeros(size(a, 2), 1, 'uint16'); % Compress for better use of cache s_ = 2 .^ (1:14); % Compute the slide manually for b = 1:size(a, 2) d = a(:,b); d = d(d ~= 0); s = 0; for c = 1:numel(d)-1 if d(c) == d(c+1) && d(c) d(c) = d(c) + 1; s = s + s_(d(c)); d(c+1:end) = [d(c+2:end); 0]; end end lut(1:numel(d),b) = d; luts(b) = s; end lutf = flipud(lut); % Make a flipped table too end % Do the slide using fast table look up switch dir case 1 I = sum(bsxfun(@times, uint16([1 14 196 2744]'), B), 1, 'native') + uint16(1); B = reshape(lut(:,I), 4, 4, []); case 2 I = sum(bsxfun(@times, uint16([2744 196 14 1]'), B), 1, 'native') + uint16(1); B = reshape(lutf(:,I), 4, 4, []); case 3 I = sum(bsxfun(@times, uint16([2744 196 14 1]), B), 2, 'native') + uint16(1); B = permute(reshape(lutf(:,I), 4, 4, []), [2 1 3]); case 4 I = sum(bsxfun(@times, uint16([1 14 196 2744]), B), 2, 'native') + uint16(1); B = permute(reshape(lut(:,I), 4, 4, []), [2 1 3]); end if nargout > 1 s = sum(reshape(luts(I), 4, []), 1, 'native')'; end

**12**of 18

Clearly there is a way to go, though, as this page, which I’ve just found, demonstrates:

http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048

My algorithm is similar to the expctimax algorithm of nneonneo, though they are looking 8 moves ahead and have a different cost function.

**13**of 18

This attempt reflects how I usually start my (manual) games in such a way that doesn’t require too much thinking.

function direction = downAI(board) % algorithm that tries to put biggest numbers in lower right corner % freeware dirs = {'down', 'right', 'left', 'up'}; persistent prevdir oldboard if isempty(prevdir) prevdir = 1; end if isempty(oldboard) oldboard = nan(4,4); end if isequaln(board,oldboard) dir = prevdir + 1; else dir = 1; end direction = dirs{dir}; prevdir = dir; oldboard = board; end

A thousand iterations yields the following scores

Highest score: 7552 32 0.6% 64 8.9% 128 37.7% 256 48.4% 512 4.4%

**14**of 18

Hi Everyone :)

My strategy is to focus on filling up the last row, trying to keep the largest number in the bottom-left corner by avoiding “right” steps when the bottom row is not filled with numbers. I oly allow “up” moves when there is no other way to go.

I implemented a function that executes steps so I can look 2 level deep into the game and the move that I choose is the one that results in the maximum profit (score gain) in the upcoming 2 moves.

The result look quite well, with a few games WON! :) Highest score: 22264 128 0.5% 256 7% 512 45% 1024 43.4% 2048 4.1%

function direction = myAI(board) up = 'up'; down = 'down'; left = 'left'; right = 'right'; if (isnan(board(4,1)) && isLeftPossible(board)) direction = left; return; end if (isnan(sum(board(4,:))) && isDownPossible(board)) direction = down; return; end [b1, benefits(1), s(1)] = executeStep(board, 'left'); [~, benefitsL(1), stepsL(1)] = executeStep(b1, 'left'); [~, benefitsL(2), stepsL(2)] = executeStep(b1, 'right'); [~, benefitsL(3), stepsL(3)] = executeStep(b1, 'down'); benefits2(1) = benefits(1) + max(benefitsL); [b2, benefits(2), s(2)] = executeStep(board, 'right'); [~, benefitsL(1), stepsL(1)] = executeStep(b2, 'left'); [~, benefitsL(2), stepsL(2)] = executeStep(b2, 'right'); [~, benefitsL(3), stepsL(3)] = executeStep(b2, 'down'); benefits2(2) = benefits(2) + max(benefitsL); [b3, benefits(3), s(3)] = executeStep(board, 'down'); [~, benefitsL(1), stepsL(1)] = executeStep(b3, 'left'); [~, benefitsL(2), stepsL(2)] = executeStep(b3, 'right'); [~, benefitsL(3), stepsL(3)] = executeStep(b3, 'down'); benefits2(3) = benefits(3) + max(benefitsL); [maxBenefit, index] = max(benefits2); if (index == 1 && maxBenefit > 0 && isLeftPossible(board)) direction = left; return; elseif (benefits2(2) > benefits2(3) && ~isnan(sum(board(4,:))) && isRightPossible(board)) direction = right; return; elseif (benefits2(3) > benefits2(2) && isDownPossible(board)) direction = down; return; end if (index == 2 && maxBenefit > 0 && ~isnan(sum(board(4,:))) && isRightPossible(board)) direction = right; return; elseif (benefits2(1) > benefits2(3) && isLeftPossible(board)) direction = left; return; elseif (benefits2(3) > benefits2(1) && isDownPossible(board)) direction = down; return; end if (index == 3 && maxBenefit > 0 && isDownPossible(board)) direction = down; return; elseif (benefits2(2) > benefits2(1) && ~isnan(sum(board(4,:))) && isRightPossible(board)) direction = right; return; elseif (benefits2(1) > benefits2(2) && isLeftPossible(board)) direction = left; return; end if (isDownPossible(board)) direction = down; return; end if (isLeftPossible(board)) direction = left; return; end if (isRightPossible(board)) direction = right; return; end direction = up; end function [resBoard profit numMerges] = executeStep(board, step) b = board; restirct = zeros(4,4); profit = 0; numMerges = 0; index = 0; if (strcmp(step, 'left')) for i=1:4 for j=2:4 if (~isnan(b(i,j))) if (~isnan(b(i,j-1)) && b(i,j) ~= b(i,j-1)) continue; end for n=j-1:-1:1 index = 0; if(~isnan(b(i,n))) index = n; break; end end if (index == 0) b(i,1) = b(i,j); b(i,j) = NaN; elseif (b(i,j) == b(i,index) && restirct(i,index) == 0) b(i,index) = b(i,index)*2; restirct(i,index) = 1; b(i,j) = NaN; profit = profit + b(i,index); numMerges = numMerges + 1; elseif (b(i,j) == b(i,index) && restirct(i,index) == 1) b(i,index+1) = b(i,j); b(i,j) = NaN; elseif (b(i,j) ~= b(i,index)) b(i,index+1) = b(i,j); b(i,j) = NaN; else b(i,index) = b(i,j); b(i,j) = NaN; end; end end end elseif (strcmp(step, 'right')) for i=1:4 for j=3:-1:1 if (~isnan(b(i,j))) if (~isnan(b(i,j+1)) && b(i,j) ~= b(i,j+1)) continue; end for n=j+1:4 index = 0; if(~isnan(b(i,n))) index = n; break; end end if (index == 0) b(i,4) = b(i,j); b(i,j) = NaN; elseif (b(i,j) == b(i,index) && restirct(i,index) == 0) b(i,index) = b(i,index)*2; restirct(i,index) = 1; b(i,j) = NaN; profit = profit + b(i,index); numMerges = numMerges + 1; elseif (b(i,j) == b(i,index) && restirct(i,index) == 1) b(i,index-1) = b(i,j); b(i,j) = NaN; elseif (b(i,j) ~= b(i,index)) b(i,index-1) = b(i,j); b(i,j) = NaN; else b(i,index) = b(i,j); b(i,j) = NaN; end; end end end elseif (strcmp(step, 'down')) for i=3:-1:1 for j=1:4 if (~isnan(b(i,j))) if (~isnan(b(i+1,j)) && b(i,j) ~= b(i+1,j)) continue; end for n=i+1:4 index = 0; if(~isnan(b(n,j))) index = n; break; end end if (index == 0) b(4,j) = b(i,j); b(i,j) = NaN; elseif (b(i,j) == b(index,j) && restirct(index,j) == 0) b(index,j) = b(index,j)*2; restirct(index,j) = 1; b(i,j) = NaN; profit = profit + b(index,j); numMerges = numMerges + 1; elseif (b(i,j) == b(index,j) && restirct(index,j) == 1) b(index-1,j) = b(i,j); b(i,j) = NaN; elseif (b(i,j) ~= b(index,j)) b(index-1,j) = b(i,j); b(i,j) = NaN; else b(index,j) = b(i,j); b(i,j) = NaN; end; end end end elseif (strcmp(step, 'up')) for i=2:4 for j=1:4 if (~isnan(b(i,j))) if (~isnan(b(i-1,j)) && b(i,j) ~= b(i-1,j)) continue; end for n=i-1:-1:1 index = 0; if(~isnan(b(n,j))) index = n; break; end end if (index == 0) b(1,j) = b(i,j); b(i,j) = NaN; elseif (b(i,j) == b(index,j) && restirct(index,j) == 0) b(index,j) = b(index,j)*2; restirct(index,j) = 1; b(i,j) = NaN; profit = profit + b(index,j); numMerges = numMerges + 1; elseif (b(i,j) == b(index,j) && restirct(index,j) == 1) b(index+1,j) = b(i,j); b(i,j) = NaN; elseif (b(i,j) ~= b(index,j)) b(index+1,j) = b(i,j); b(i,j) = NaN; else b(index,j) = b(i,j); b(i,j) = NaN; end; end end end end resBoard = b; end function res = isLeftPossible(board) res = false; for i=1:4 for j=2:4 if (~isnan(board(i,j))) % if left number simmilar or ther is void on left if (board(i,j) == board(i,j-1) || isnan(board(i,j-1))) res = true; return; end end end end end function res = isRightPossible(board) res = false; for i=1:4 for j=1:3 if (~isnan(board(i,j))) % if left number simmilar or ther is void on left if (board(i,j) == board(i,j+1) || isnan(board(i,j+1))) res = true; return; end end end end end function res = isDownPossible(board) res = false; for i=1:3 for j=1:4 if (~isnan(board(i,j))) % if left number simmilar or ther is void on left if (board(i,j) == board(i+1,j) || isnan(board(i+1,j))) res = true; return; end end end end end

**15**of 18

Hi Everyone!

I improved a bit my previous code. Now, while keeping the main strategy, I look 3 steps ahead. This leads to a significant improvement. I only post the modified code segment now.

After 1000 simulations: Highest score: 22312 128 0.4% 256 6.2% 512 39.2% 1024 46.5% 2048 7.7%

... % look 3 steps into the left branch [b1, benefits(1), ~] = executeStep(board, 'left'); [b11, benefitsL(1), ~] = executeStep(b1, 'left'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(1) = benefitsL(1) + max(benefitsL2); [b11, benefitsL(2), ~] = executeStep(b1, 'right'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(2) = benefitsL(2) + max(benefitsL2); [b11, benefitsL(3), ~] = executeStep(b1, 'down'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(3) = benefitsL(3) + max(benefitsL2); benefits2(1) = benefits(1) + max(benefitsL); % look 3 steps into the right branch [b1, benefits(2), ~] = executeStep(board, 'right'); [b11, benefitsL(1), ~] = executeStep(b1, 'left'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(1) = benefitsL(1) + max(benefitsL2); [b11, benefitsL(2), ~] = executeStep(b1, 'right'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(2) = benefitsL(2) + max(benefitsL2); [b11, benefitsL(3), ~] = executeStep(b1, 'down'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(3) = benefitsL(3) + max(benefitsL2); benefits2(2) = benefits(2) + max(benefitsL); % look 3 steps into the down branch [b1, benefits(3), ~] = executeStep(board, 'down'); [b11, benefitsL(1), ~] = executeStep(b1, 'left'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(1) = benefitsL(1) + max(benefitsL2); [b11, benefitsL(2), ~] = executeStep(b1, 'right'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(2) = benefitsL(2) + max(benefitsL2); [b11, benefitsL(3), ~] = executeStep(b1, 'down'); [~, benefitsL2(1), ~] = executeStep(b11, 'left'); [~, benefitsL2(2), ~] = executeStep(b11, 'right'); [~, benefitsL2(3), ~] = executeStep(b11, 'down'); benefitsL(3) = benefitsL(3) + max(benefitsL2); benefits2(3) = benefits(3) + max(benefitsL); % decide to move to overall max profit [maxBenefit, index] = max(benefits2); ...

**16**of 18

This code solves the puzzle, although not necessarily every time. Early moves are made quickly, although it slows down during later stages of the puzzle as it looks further ahead. (See comments in code for details.)

function direction = myAI_JRM(board) %DESCRIPTION: Decides which move to make next given a 2048 board. %AUTHOR: Jeremy R. Manning (manning3@princeton.edu) %DATE: April 17, 2014 %the list of moves to choose from moves = {'left','up','right','down'}; %N_RUNS specifies how many times to simulate each move %DEPTH specifies how many moves to look ahead %relative_weights specifies how much to factor in each criteria (used to %evaluate how "good" a board position is): % first element: overall score % second element: number of empty spaces % third element: a gradient that pushes high numbers to the bottom right % fourth element: a score that gives better values to boards with more % similar numbers (e.g. a board with all of the same % number would get the highest score). %EXPONENT: controls how quickly the gradient (whose influence is controlled %by the third element of relative weights vector) falls off. Setting %EXPONENT = 0 nullifies the effect of the gradient (i.e. no position %preference for the tiles). %this section re-weigths the relative preferences and the number of %positions to look ahead depending on which tiles are on the board. in %general, early moves are done relatively more quickly than later moves. N_RUNS = 1; if sum(board(:) == 1024) == 2 DEPTH = 4; relative_weights = [100 25 0.1 0.1]; elseif max(board(:)) >= 512 DEPTH = 3; relative_weights = [50 50 20 20]; elseif max(board(:)) >= 128 DEPTH = 2; relative_weights = [50 75 40 10]; else DEPTH = 1; relative_weights = [25 100 80 5]; end EXPONENT = 1; %compute all possible moves up to specified depth move_combos = get_move_combos(moves, DEPTH); %compute gradient (that pushes high-valued tiles to the bottom right) board_weights = get_board_weights(board, EXPONENT); %initialize the scores (need one score for each category, for each %combination of moves) [scores, empties, weights, evenness] = deal(zeros(1, size(move_combos, 1))); %estimate the scores for each combination of moves, averaged over N_RUNS %trials for i = 1:size(move_combos, 1) for j = 1:N_RUNS [s, e, w, v] = estimate_improvement(board, move_combos(i, :), board_weights); scores(i) = scores(i) + s; empties(i) = empties(i) + e; weights(i) = weights(i) + w; evenness(i) = evenness(i) + v; end scores(i) = scores(i)/N_RUNS; empties(i) = empties(i)/N_RUNS; weights(i) = weights(i)/N_RUNS; evenness(i) = evenness(i)/N_RUNS; end %compute the optimal move combination given the scores and the relative %weights ind = opt([scores ; empties ; weights ; evenness], relative_weights); best_combo = move_combos(ind, :); %return the first move in the combination direction = best_combo{1}; %if the move didn't change the board, move randomly until the board does %change. while board_unchanged(board, direction) direction = moves{select_random(1:length(moves))}; end %%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% HELPER FUNCTIONS %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% function[x] = board_unchanged(board, direction) %does this move have any effect? tmp = TwentyFortyEight(false); tmp.Board = board; tmp.move(direction); x = all(nanequal(board(:), tmp.Board(:))); function[x] = nanequal(a, b) %computes element-wise equality, taking nan's into account x = (isnan(a) & isnan(b)) | (a == b); function[score, empty, weighted_position, evenness] = estimate_improvement(board, ms, w) %for the given combination of moves (ms), estimate the scores of the result tmp = TwentyFortyEight(false); tmp.Board = board; for i = 1:length(ms) tmp.move(ms{i}); end score = nan_max(tmp.Scores); empty = sum(isnan(tmp.Board(:))); weighted_position = nansum(tmp.Board(:).*w(:)); counts = arrayfun(@(i)(count(tmp.Board, i)), 2.^(1:11)); evenness = mean(counts(counts ~= 0)); function[x] = nan_max(x) %computes the global maximum of a matrix, ignoring nan's x = max(x(~isnan(x(:)))); function[x] = select_random(xs) %selects a random element of the vector xs x = xs(randi(length(xs))); function[ms] = get_move_combos(moves, depth) %compute every combination of moves, up to the specified depth if depth == 1 ms = moves(:); else xs = fullfact(length(moves).*ones(1, depth)); ms = moves(xs); end function[w] = get_board_weights(board, exponent) %compute the gradient that pushes high-valued tiles to the lower right d = size(board, 1); w = repmat(1:d, d, 1).*repmat(transpose(1:4), 1, d); w = w.^exponent; function[ind] = opt(x, weights) %assign a value to each move combination by weighting the given %combination-specific scores weights = weights./sum(weights); ind = zeros(1, size(x, 2)); for i = 1:size(x, 1) ind = ind + weights(i).*normalize(x(i, :)); end ind = find((ind == max(ind))); if length(ind) > 1 ind = select_random(ind); end function[x] = normalize(x) %normalize the values in x (ignoring nan's) to range from 0 to 1. then set %all nan's to 0. x = x - nanmin(x(:)); x = x./nanmax(x(:)); x(isnan(x)) = 0;

**17**of 18

I am newbie compare to those before me. I just do it for fun and to learn Matlab OOP.

I used sum of square of the elements in the board. If else statements are used to keep the max tile in right bottom direction and prevent the invalid move. Is a bit of mess and some of the if else statement might be redundant but i don’t have time to clean them up. Well, it gives me 11.5% chance to get the 2048 tile.

128 0.6% 256 6.2% 512 34.9% 1024 46.8% 2048 11.5%

function direction = myAIFinal(board) %myAIFinal AI for Matlab 2048 %% Some parameter and variable initialisation d = {'right','down','left','up'}; % choice of direction %% Shifting and evaluation EvalMove = zeros(1,4); % First shift stepone = ShiftBoard(board); % Second shift steptwo1 = ShiftBoard(stepone.LeftBoard); steptwo2 = ShiftBoard(stepone.RightBoard); steptwo3 = ShiftBoard(stepone.UpBoard); steptwo4 = ShiftBoard(stepone.DownBoard); % evaluate left EvalTemp = zeros(1,4); Boards = {steptwo1.LeftBoard;steptwo1.RightBoard;steptwo1.UpBoard;steptwo1.DownBoard}; for i = 1:4 EvalTemp(i)=SumOfSquare(Boards{i}); end EvalMove(3) = max(EvalTemp); % evaluate right EvalTemp = zeros(1,4); Boards = {steptwo2.LeftBoard;steptwo2.RightBoard;steptwo2.UpBoard;steptwo2.DownBoard} ; for i = 1:4 EvalTemp(i)=SumOfSquare(Boards{i}); end EvalMove(1) = max(EvalTemp); % evaluate up EvalTemp = zeros(1,4); Boards = {steptwo3.LeftBoard;steptwo3.RightBoard;steptwo3.UpBoard;steptwo3.DownBoard} ; for i = 1:4 EvalTemp(i)=SumOfSquare(Boards{i}); end EvalMove(4) = max(EvalTemp); % evaluate Down EvalTemp = zeros(1,4); Boards = {steptwo4.LeftBoard;steptwo4.RightBoard;steptwo4.UpBoard;steptwo4.DownBoard} ; for i = 1:4 EvalTemp(i)=SumOfSquare(Boards{i}); end EvalMove(2) = max(EvalTemp); %% Decision time % CurrentBoard = BoardInfo(board); board0 = Replace0orNaN(board,1); BoardData = {stepone.RightBoard0,stepone.DownBoard0,stepone.LeftBoard0,stepone.UpBoard0}; InvalidMove = FindInvalid(BoardData,board0); AvoidMove = FindAvoid(BoardData,board0); [MaxTile, index] = max2(board0); if index(1)==4 && index(2)~=4 && isnan(board(4,4))==1 direction = 1; % disp('haha') if isequal(BoardData{1},board0)==1 direction= 2; if isequal(BoardData{2},board0)==1 direction= 3; end end elseif isequal(BoardData{1},BoardData{2},BoardData{3},board0)==1 direction = 4; elseif isequal(BoardData{1},BoardData{2},board0)==1 direction = 3; elseif sum(isfinite(board(4,:)))==4 [~, Index] = max(EvalMove(1:3)); direction = Index; if isequal(EvalMove(1),EvalMove(2))==1 && EvalMove(1)>EvalMove(3) direction= randi(2); TempD = [1,2]; TempD(TempD==direction)=[]; if any(AvoidMove==direction)==1 && any(AvoidMove==TempD)==0 direction = TempD; elseif isequal(BoardData{direction},board0)==1 direction = TempD; end if isequal(BoardData{1},BoardData{2},board0)==1 direction= 3; end end if isequal(EvalMove(1),EvalMove(2),EvalMove(3))==1 direction= randi(3); if direction == 2 && any(AvoidMove==direction)==1 direction = randsample([1,3],1); end end if isequal(EvalMove(1),EvalMove(3))==1 && EvalMove(1)>EvalMove(2) && index(1)==4 && index(2)==4 if isequal(BoardData{3},board0)==1 direction = 1; else direction = 3; end end % Prevent merge to left if it cause and empty space on the last row if direction==3 && sum(isfinite(stepone.LeftBoard(4,:)))=64 && index(1)<4 && board0(index(1)+1,index(2))==0 %if max is not at row 4, take a down shift next direction = 2; elseif isequal(EvalMove(1),EvalMove(2))==1 direction= randi(2); if direction ==2 && any(AvoidMove==2)==1 && any(InvalidMove==1)==0 direction = 1; elseif isequal(BoardData{direction},board0)==1 TempD = [1,2]; TempD(TempD==direction)=[]; direction = TempD; end end end % failsafe steps if isequal(BoardData{1},board0)==1 && direction==1 if isequal(BoardData{2},BoardData{3},board0)==1 direction= 4; else direction= randi(2)+1; end elseif isequal(BoardData{2},board0)==1 && direction==2 if isequal(BoardData{1},BoardData{3},board0)==1 direction= 4; else direction= randsample([1,3],1); end elseif isequal(BoardData{3},board0)==1 && direction==3 if isequal(BoardData{1},BoardData{2},board0)==1 direction= 4; else direction= randi(2); end elseif isequal(BoardData{4},board0)==1 && direction==4 direction= randi(3); end direction = d{direction}; function InvalidM = FindInvalid(TempBoards,OriBoard) InvalidM = zeros(1,4); for ii = 1:4 if isequal(TempBoards{ii},OriBoard)==1 InvalidM(ii)=ii; end end InvalidM(InvalidM==0) =[]; end function AvoidM = FindAvoid(TempBoards,OriBoard) AvoidM = zeros(1,4); for ii=1:4 AvoidM(ii)=IsSquareBoard(TempBoards{ii})*ii; end AvoidM(AvoidM==0)=[]; InvalidM = FindInvalid(TempBoards,OriBoard); AvoidM = [AvoidM InvalidM]; if isempty(AvoidM)==0 AvoidM = unique(AvoidM,'stable'); end end end

Class:

classdef ShiftBoard < handle %ShiftBoard Generating the board data after shiting to left, right, Up %and Down. Constructor ShiftBoard(Board) only accept matrix with board %data with value NaN on the empty tile(s). % Class properies include LeftBoard, RightBoard, UpBoard, DownBoard properties OriBoard LeftBoard RightBoard UpBoard DownBoard LeftBoard0 RightBoard0 UpBoard0 DownBoard0 end methods function MovedBoard = ShiftBoard(Board) % contructor to initialise all the variables MovedBoard.OriBoard = Board; MovedBoard.LeftBoard = ShiftBoard.MovedLeft(MovedBoard); MovedBoard.RightBoard = ShiftBoard.MovedRight(MovedBoard); MovedBoard.UpBoard = ShiftBoard.MovedUp(MovedBoard); MovedBoard.DownBoard = ShiftBoard.MovedDown(MovedBoard); MovedBoard.LeftBoard0 = Replace0orNaN(MovedBoard.LeftBoard,1); MovedBoard.RightBoard0 = Replace0orNaN(MovedBoard.RightBoard,1); MovedBoard.UpBoard0 = Replace0orNaN(MovedBoard.UpBoard,1); MovedBoard.DownBoard0 = Replace0orNaN(MovedBoard.DownBoard,1); end end methods (Static) function Tempboard = shiftLeft(Board) % shifting the board to the left Tempboard = zeros(4,4); for row = 1:4 counter = 1; for column = 1:4 if isnan(Board(row,column))==0 Tempboard(row,counter) = Board(row,column); counter = counter+1; end end end Tempboard = Replace0orNaN(Tempboard,0); %Replace 0 with NaN as the array is initialised with 0 end function Tempboard = shiftRight(Board) % Shift to Right Tempboard = zeros(4,4); for row = 1:4 counter = 4; for column = 4:-1:1 if isnan(Board(row,column))==0 Tempboard(row,counter) = Board(row,column); counter = counter-1; end end end Tempboard = Replace0orNaN(Tempboard,0); %Replace 0 with NaN as the array is initialised with 0 end function Tempboard = shiftDown(Board) % Shift Down Tempboard = zeros(4,4); for column = 1:4 counter = 4; for row = 4:-1:1 if isnan(Board(row,column))==0 Tempboard(counter,column) = Board(row,column); counter = counter-1; end end end Tempboard = Replace0orNaN(Tempboard,0); %Replace 0 with NaN as the array is initialised with 0 end function Tempboard = shiftUp(Board) % Shift up Tempboard = zeros(4,4); for column = 1:4 counter =1; for row = 1:4 if isnan(Board(row,column))==0 Tempboard(counter,column) = Board(row,column); counter = counter+1; end end end Tempboard = Replace0orNaN(Tempboard,0); %Replace 0 with NaN as the array is initialised with 0 end function Tempboard = MovedLeft(MovedBoard) % Shiting including adding if applicable Board = MovedBoard.OriBoard; Tempboard = ShiftBoard.shiftLeft(Board); for row = 1:4 for column = 1:3 if isnan(Tempboard(row,column))==0 && isnan(Tempboard(row,column+1))==0 if Tempboard(row,column) == Tempboard(row,column+1) Tempboard(row,column) = Tempboard(row,column)*2; Tempboard(row,column+1) = NaN; end end end end Tempboard = ShiftBoard.shiftLeft(Tempboard); end function Tempboard = MovedRight(MovedBoard) % Shiting including adding if applicable Board = MovedBoard.OriBoard; Tempboard = ShiftBoard.shiftRight(Board); for row = 1:4 for column = 4:-1:2 if isnan(Tempboard(row,column))==0 && isnan(Tempboard(row,column-1))==0 if Tempboard(row,column) == Tempboard(row,column-1) Tempboard(row,column) = Tempboard(row,column)*2; Tempboard(row,column-1) = NaN; end end end end Tempboard = ShiftBoard.shiftRight(Tempboard); end function Tempboard = MovedDown(MovedBoard) % Shiting including adding if applicable Board = MovedBoard.OriBoard; Tempboard = ShiftBoard.shiftDown(Board); for column = 1:4 for row = 4:-1:2 if isnan(Tempboard(row,column))==0 && isnan(Tempboard(row-1,column))==0 if Tempboard(row,column) == Tempboard(row-1,column) Tempboard(row,column) = Tempboard(row,column)*2; Tempboard(row-1,column) = NaN; end end end end Tempboard = ShiftBoard.shiftDown(Tempboard); end function Tempboard = MovedUp(MovedBoard) % Shiting including adding if applicable Board = MovedBoard.OriBoard; Tempboard = ShiftBoard.shiftUp(Board); for column = 1:4 for row = 1:3 if isnan(Tempboard(row,column))==0 && isnan(Tempboard(row+1,column))==0 if Tempboard(row,column) == Tempboard(row+1,column) Tempboard(row,column) = Tempboard(row,column)*2; Tempboard(row+1,column) = NaN; end end end end Tempboard = ShiftBoard.shiftUp(Tempboard); end end end

Other custom function:

function BoolAns = IsSquareBoard( TempBoard ) %IsSquareBoard Function use to check does a board form after a move will %result in a square board. % TempBoard as input of 4x4 matrix representing 2048 board with 0 for % empty tiles TempBoard(all(TempBoard==0,2),:)=[]; TempBoard(:,all(TempBoard==0,1))=[]; [row,column] = size(TempBoard); FreeTiles = sum(sum(TempBoard==0)); if (row<4 || column <4) && FreeTiles ==0 BoolAns = 1; else BoolAns = 0; end end function OutputBoard = Replace0orNaN( Board , SwitchKey ) %Replace0orNaN replace the 0 or NaN element in the board matrix to each %other. % Usage OutputBoard = Replace0orNaN( Board , SwitchKey ) where % OutputBoard is the output, Board is the board matrix of interest and % SwitchKey is a value of 0 (replace 0 to NaN) or 1 (replace NaN to 0) if SwitchKey ==0 Board(Board==0)=NaN; elseif SwitchKey ==1 Board(isnan(Board)==1)=0; else fprintf('Invalid SwitchKey in function Replace0orNaN aggument \n') end OutputBoard =Board; end function SumSq = SumOfSquare( TempBoard ) %SumSquare Calculate the sum of square of every element in the board. % Calculate the sum of square of every element in the board. The input % argument is 4x4 matrix representing 2048 board with NaN for the empty % tiles. % freeT = nnz(isnan(TempBoard)==1); TempBoard = Replace0orNaN(TempBoard,1); [~,MaxIndex]=max2(TempBoard); SumSq = sum(sum(TempBoard.^2)); if MaxIndex(1)==4 && MaxIndex(2)==3 && TempBoard(4,4)~=0 SumSq = SumSq - abs(TempBoard(4,4)^2-TempBoard(3,4)^2); end end

**18**of 18

I also used the max2 function downloaded from mathwork for the codes above.

## Recent Comments