# 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

### Note

Comments are closed.

## 18 CommentsOldest to Newest

**1**of 18

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

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

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

(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

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; endOutput:

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

**6**of 18

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 endA 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 endOutput:

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

**7**of 18

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 endWith 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

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

**10**of 18

@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.isMovedwith

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

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

**13**of 18

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; endA 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

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

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

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

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 endClass:

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 endOther 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

## Recent Comments