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://matthieu.benoit.free.fr/68hc11/vt100.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.

<Updated 17/09/2022 to fix a broken link>

Comments

Post a Comment

Popular posts from this blog

Unicode output from an Arduino.

Image
I have been working hard on a second edition for my book called "Practical Arduino C". The new edition has an extra chapter focusing on adding an Internet capability to Arduino boards plus some additional data structures. Overall, the text has been polished and the index extended and tidied. I have also changed the way the book is being published and sold. This has halved the retail price while still ensuring fast delivery when ordered from Amazon ( Amazon UK link here ). One item that featured in the first edition has been dropped as with hindsight it became clear that it did not add to the reader's learning experience. It made sense therefore to move the section on Unicode output over the Arduino serial interface to a blog post here. Unicode Characters The Arduino C is a great tool for manipulating, displaying and communicating ASCII encoded characters, which is perfect if the language you want to use is based upon the Latin character set. Most recent programming
Read more

Arduino: How to scroll long text on OLED screen

 While exploring a new and tiny SSD 1306 OLED screen as a useful user interface I hit on the need to scroll some longish text across the screen. This did not seem to be a feature of the Adafruit library I was using to run the device. So I am introducing this working demo of my solution to the problem. The solution is to position the start point of the text in steps towards the left and beyond the left hand edge of the screen. The screen "clips" the text and displays all it can across the width of the screen. The demo includes some fixed text at the top of the screen and scrolls the long text below. #include <SPI.h> #include <Wire.h> #include <Adafruit_SSD1306.h> #define SCREEN_WIDTH 128 // OLED display width, in pixels #define SCREEN_HEIGHT 32 // OLED display height, in pixels #define OLED_RESET -1 // Reset pin # (or -1 if sharing Arduino reset pin) #define SCREEN_ADDRESS 0x3C ///< See datasheet for Address; 0x3D for 128x64, 0x3C for 128x32 Adafr
Read more

Arduino Regular Expressions

The first chapter of a wonderful book titled “Beautiful Code” (O’Reilly 2007) was written by Brian Kernighan who described an episode from when he and Rob Pyke were writing a book together called “The Practice of Programming”. They wanted to include a discussion on regular expressions but also wanted to include the code of an implementation. Existing code bases would have been a book length by themselves. Rob Pyke developed 30 lines of C code in less than two hours that implements a substantial part of the day to day usage of regular expressions. The code can be described as beautiful for its elegant efficiency. The final line of the chapter reads “I don’t know of another piece of code that does so much in so few lines while providing such a rich source of insight and further ideas”. The code handles the following constructs: Character Meaning c Matches any literal character (in this case ‘c’) . (full stop) Matches any single character
Read more