Arduino 2048

Using the PuTTY terminal emulator to support the development of a BASIC interpreter running on an Arduino got me wondering about the potential for even greater interaction. What better than a game? 

PuTTY supports VT100 escape sequences for positioning the cursor on screen and also has some limited support for colour. This was sufficient for a version of the 2048 game originally devised by Gabriele Cirulli. You can play it online at http://gabrielecirulli.github.io/2048/

My Arduino C version uses the keyboard arrow keys (on the PC running PuTTY) with the playing board displayed in the PuTTY window. SetPuTTY up with a serial connection to the Arduino with no local echo.

‘S’ starts a new game at any time.
‘X’ starts a test solver that maximises the score from every move
‘Y’ starts a test solver that uses a repeated pattern
‘Z’ available on the Arduino Due version starts a test solver that uses a Monte-Carlo simulation

VT 100 control

VT100 terminal control escape sequences can be found here http://www.termsys.demon.co.uk/vtansi.htm

In addition, arrow key presses generate the following escape sequences. UP is <Esc>[A, DOWN is <Esc>[B, RIGHT is <Esc>[C and LEFT is <Esc>[D

The game runs happily on an Arduino Uno and could probably be adapted to use a touch sensitive display. If you try that then please do let me know and consider publishing your code.

Testing the Code

In order to complete testing the code, I created a simple automated game player that always took the maximum score increase from any position as the next move. This helped me eliminate a bug in the end game but the automated solver did not play very well. I then tried a solver based upon a set of “rote moves” widely said on the Internet to be an effective strategy. This, frankly, was worse.

My final attempt saw me trying a “Monte-Carlo” algorithm which quite often makes a reasonable stab at the game. This runs 200 (or more) simulated and random games from the current board position to their end before picking the best move. The fudged and messy code is included in one of the downloadable versions but don’t try and run this on anything with less than the power of a Due as you would need lots of patience waiting for moves on a Uno or Mega 2560 (where they take about 11 seconds each).

The maths behind the game

This is still a long way from a great solver but there may be an excuse to be found in the complexity of this apparently simple game. There is a nice series of posts by John Lees-Miller on the subject that explains the maths of just how many moves are needed to solve the game and the vast number of potential game positions.

Commentary on the code

The code can be downloaded from my Arduino C book website

Global variables and constants:
#define SIZE 4
#define WHITE 47
#define BLACK 40
#define WIN 2048
#define MONTECOUNT 200

const char blank[] = "         ";
char* cellColours[] = {"41;2;37", "42;2;30", "43;2;30", "44;2;37", "45;2;37", "46;2;30", "41;1;37", "42;1;37", "43;1;30", "44;1;37", "45;1;37"};
int board[SIZE][SIZE];
char eStart[] = {27, '[', '\0'}; // first 2 chars of VT100 terminal escape sequences
bool wasEsc = false, gameOver = false, gameWon = false;
char keyBuff[2];
int kPos = 0, moves, hScore = 0, uScore;


The game play uses a 4 x 4 board represented by a 4 x 4 int array of values. The cellColours[] array stores a sequence of background colours for different board cell content values. hScore retains a high score value during a playing session.

The setup:
void setup() {
   Serial.begin(115200);
   randomSeed(analogRead(A0) + analogRead(A1));
   Serial.print(eStart);
   Serial.print("2J"); // erase screen and place cursor homw
  
   initBoard();
   drawBoard();
}

The setup() function establishes a serial connection to the PuTTY terminal window, attempts to randomise the randomSeed value using values from 2 of the analogue pins that the code assumes are not connected to any external components. The terminal window is then cleared, the playing board initialised and then drawn to the terminal.

The initBoard() function:
void initBoard() {
  for(int i = 0; i < SIZE; i++) {
    for(int j = 0; j < SIZE; j++) {
      board[i][j] = 0;
    }
  }
  addRandom();
  addRandom();
  gameOver = gameWon = false;
  showResult();
  uScore = moves = 0;
}

The board array values are set to zero. Could have used memset() here. Two random cells are given an initial value, game tracking values are initialised and the progress display updated.

The drawBoard() function:
void drawBoard() {
  curPlace(1,1);
  char buff[5], num[10];
  for(int r = 0; r < SIZE; r++) {
    for(int c = 0; c < SIZE; c++) {
      const char* sColour = (board[r][c] == 0) ? "47;2;30" : getColour(board[r][c]);
      setBackground(sColour);
      for(int sr = 0; sr < 5; sr++) {
        curPlace(sr + r * 5 + 1, c * 9);
        if(sr == 2) {
          if (board[r][c] == 0) {
            Serial.print("    *    ");
          } else {
            intToString(board[r][c], buff);
            int sl = strlen(buff);
            int sp = (9-sl)/2;
            strcpy(num, blank);
            for(int p = 0; p < sl; p++) {
              num[sp++] = buff[p];
            }
            Serial.print(num);
          }
        } else {
          Serial.print(blank);
        }
      }
    }
  }
  setBackgroundC(BLACK);
  setForeground(WHITE);
  showScore();
}

This function displays the board in the PuTTY window. Some board cells have a zero value but those with a positive score have the integer value displayed against a shaded background colour. The intToString() function builds the string value for a cell in the buffer buff[] so that it can be displayed centred within the game board cell.

The intToString() function:
void intToString(int iVal, char buff[]){
  int i = 0;
  do {
    buff[i++] = iVal % 10 + '0';
  } while ((iVal /= 10) > 0);
  buff[i--] = '\0'; // terminate the string
  int h;
  // now reverse the string
  for(int j= 0; j < i; j++, i--) {
    h = buff[j];
    buff[j] = buff[i];
    buff[i] = h;
  }
}

Pretty standard code for converting an int value to a char array although this one has been simplified by removing code for a negative argument.

The addRandom() function:
int addRandom() {
  // adds a 2 or 4 in a random empty cell and returns count of cells found empty
  // as we are here we can also check for a win
  byte toCells[16];
  int setVals[] = {2,2,2,2,2,4};
  int ctr = 0, cell = 0;
  for(int i = 0; i < SIZE; i++) {
    for(int j = 0; j < SIZE; j++) {
      if(board[i][j] == 0) {
        toCells[ctr++] = cell;
      } else if(board[i][j] == WIN) {
        gameWon = gameOver = true;
      }
      cell++;
    }
  }
  if(ctr > 0) {
    int c = toCells[random(0, ctr)];
    int r = c / 4;
    c -= r*4;
    board[r][c] = setVals[random(0,6)]; //should return 2 or 4 in ratio 5:1
  }
  return ctr;
}

Finds all of the empty (zero value) cells and while running through the list also checks to see if any of them contain the winning value. Once the empty cells have been located then a random one is selected from the list and set to 2 or 4 hopefully in a ratio of 5 to 1.

The main program loop() function:
During game play, the function accepts incoming bytes from the serial interface looking for arrow key presses. Once identified, these are passed to moveBoard().

The moveBoard() function:
bool moveBoard(int r1) {
  for(int i = 0; i < r1; i++) {
    rotateBoard();
  }
  bool moveMade = tryMove();
  r1 = (4 - r1) % 4;
  for(int i = 0; i < r1; i++) {
    rotateBoard();
  }
  if(moveMade) {
    moves++;
    if(uScore > hScore) {hScore = uScore;}
    drawBoard();
    delay(500);
    int zCells = addRandom();
    if(gameWon) {
      showResult();
      return moveMade;
    }
    if(zCells > 0) {
      drawBoard();
    }
    if(zCells <= 1) {
      if(!canMerge2()) {
        gameOver = true;
        showResult();
      }
    }
  }
  return moveMade;
}

The moveBoard function manages the players moves. The use of the rotateBoard() function greatly simplifies this. The user can move in any of four directions but by “rotating” the board array the game position only has to be evaluated from one perspective. Once rotated the tryMove() function can be called to slide the game values in that direction evaluating any collisions. Once a move has been evaluated, the board can be rotated back to the correct orientation and a test made using canMerge2() to see if there are any remaining moves possible.

The Boolean function tryMove():
bool tryMove() {
  // tries moving each of the cells towards zeroth row (after any rotate)
  // looking for merges
  bool moveMade = false;
  int mergeStop[] = {-1,-1,-1,-1};
  for(int r = 1; r < SIZE; r++){
    for(int c = 0; c < SIZE; c++) {
      if(board[r][c] != 0) {
        int tr = r-1;
        int nPos = -1;
        while (tr >=0) {
          if(board[tr][c] == 0) {
            nPos = tr;
          } else {
            if(board[tr][c] == board[r][c] && mergeStop[c] < tr) {
              board[tr][c] <<= 1;
              uScore += board[tr][c];
              board[r][c] = 0;
              nPos = -1;
              moveMade = true;
              mergeStop[c] = tr;
            }
            break;
          }
          tr--;
        }
        if(nPos >=0) {
          board[nPos][c] = board[r][c];
          board[r][c] = 0;
          moveMade = true;
        }
      }
    }
  }
  return moveMade;
}

The code looks for non-zero cell values that can be moved towards the zeroth row. If they “meet” with a cell with the same value then they merge. Extra check is made to stop any further sliding on a column that has seen a successful merge.

If a move is made then the score is updated and a new random cell given a new value.

Game Over:
A game terminates if the player achieves a cell with a value of 2048 or if no further moves are possible.

Improvements:

There are probably a great number of improvements that could be made to this bit of fun. Feel free to make suggestions or contribute code in the comments.

copyBoard() could use memcpy()

testMove could be merged into tryMove with a flag to control score updates.

The setVals[] byte array in the addReandom() function should probably be global.

A better test game player could be developed but there are few shortcuts. There have to be at least 938 (or 939) moves made before 2048 can be achieved. The random nature of the newly populated cells where position and value can have an impact makes “look ahead” strategies problematic without even more processing power than is available on an Arduino Due.

Grab a copy of the code from the book web site.

Comments

Popular posts from this blog

BASIC for Arduinos

Caenorhabditis Elegans (C. Elegans) Nematode Project