Tic-tac-toe vs minimax on an ESP32-C3

// Tic-tac-toe against an unbeatable computer, on a 2.8 inch touch screen.
//
// Wiring, board to module:
//   display   CS -> GPIO 7   DC -> GPIO 2   SCK -> GPIO 4   MOSI -> GPIO 6
//             RST and LED -> 3V3   VCC -> 3V3   GND -> GND
//   touch     T_CS -> GPIO 10   T_CLK -> GPIO 0   T_DIN -> GPIO 3   T_DO -> GPIO 1
//
// You are X and you tap a square to play it. The computer is O. Whoever moves
// first changes every game, so you also get to watch it open.
//
// # Why it cannot lose
//
// Tic-tac-toe is small enough for the computer to look at EVERY way the game
// can go. That is the whole trick, and it is called minimax:
//
//   - If the game is over, score it: +10 if O won, -10 if X won, 0 for a draw.
//   - If not, try every empty square for whoever is to move, ask "what is this
//     position worth?" by playing the same question out for the other side,
//     and keep the best answer for the player whose turn it is.
//
// Each player picks the move that is best for THEM, so O picks the biggest
// score and X the smallest. When both play perfectly, the best O can do from
// the empty board is a draw, so a perfect O never loses. You can still draw it
// every time, but you cannot beat it. If you beat it, the sketch has a bug!
//
// A win that comes sooner is worth a little more than one that comes later
// (10 minus the number of moves so far), so when the computer can win it wins
// at once instead of dawdling, and when it must lose... it never must.
//
// # Alpha-beta, the shortcut
//
// Looking at every game from the empty board is about 550,000 positions.
// Alpha-beta pruning skips branches that cannot change the answer: once we
// know a move is worse than one we already have, we stop looking at it. The
// screen shows how many positions the computer really looked at.
//
// # Reading the touch panel
//
// The XPT2046 chip reports raw counts, about 200 at one edge of the glass and
// 3900 at the other. map() turns them into pixels. The touch chip has its own
// little SPI bus here, so it never gets in the display's way.

#include <SPI.h>
#include <Adafruit_GFX.h>
#include <Adafruit_ILI9341.h>
#include <XPT2046_Touchscreen.h>

const uint8_t TFT_CS = 7;
const uint8_t TFT_DC = 2;
const uint8_t TOUCH_CS = 10;
const uint8_t TOUCH_CLK = 0;
const uint8_t TOUCH_MISO = 1;
const uint8_t TOUCH_MOSI = 3;

Adafruit_ILI9341 tft(TFT_CS, TFT_DC);
SPIClass touchBus(TOUCH_CLK, TOUCH_MISO, TOUCH_MOSI, TOUCH_CS);
XPT2046_Touchscreen touch(TOUCH_CS);

// The screen is 240 wide and 320 tall. The board is 3 squares by 3.
const int16_t CELL = 72;
const int16_t BX = 12;   // left edge of the board
const int16_t BY = 52;   // top edge of the board

const uint16_t BG = 0x0821;     // very dark blue
const uint16_t GRID = 0x7BEF;   // grey
const uint16_t X_COLOUR = 0x07FF; // cyan
const uint16_t O_COLOUR = 0xFD20; // orange
const uint16_t WIN_COLOUR = 0x07E0; // green
const uint16_t TEXT = 0xFFFF;

const int8_t EMPTY = 0;
const int8_t HUMAN = 1; // X
const int8_t AI = 2;    // O

int8_t board[9];
int8_t winLine[3];
bool humanStarts = true;
bool over = false;
int wins = 0, losses = 0, draws = 0;
long nodes = 0;
uint8_t moveNo = 0;

// The eight lines that win: three rows, three columns, two diagonals.
const int8_t LINES[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

/** Look at the best squares first: the centre, then corners, then edges. Better pruning. */
const int8_t ORDER[9] = {4, 0, 2, 6, 8, 1, 3, 5, 7};

/** 0 while nobody has won, else HUMAN or AI. */
static int8_t winner(int8_t *line = 0) {
  for (uint8_t i = 0; i < 8; i++) {
    int8_t a = board[LINES[i][0]];
    if (a != EMPTY && a == board[LINES[i][1]] && a == board[LINES[i][2]]) {
      if (line) {
        line[0] = LINES[i][0];
        line[1] = LINES[i][1];
        line[2] = LINES[i][2];
      }
      return a;
    }
  }
  return 0;
}

static bool full() {
  for (uint8_t i = 0; i < 9; i++) {
    if (board[i] == EMPTY) return false;
  }
  return true;
}

/**
 * What is this position worth to `player`, who is about to move? (Negamax: the
 * same function scores both sides, and what is good for one is bad for the
 * other, so we flip the sign on the way back.)
 *
 * `depth` is how many moves have been played since the real position, so a
 * quicker win scores higher. alpha and beta are the scores each side is
 * already sure of; a branch that falls outside them is cut off.
 */
static int negamax(int8_t player, int alpha, int beta, int depth) {
  nodes++;
  int8_t other = (player == AI) ? HUMAN : AI;
  // The previous mover may just have won. If so, that is bad for `player`.
  if (winner() == other) return -(10 - depth);
  if (full()) return 0;
  int best = -100;
  for (uint8_t k = 0; k < 9; k++) {
    int8_t cell = ORDER[k];
    if (board[cell] != EMPTY) continue;
    board[cell] = player;
    int score = -negamax(other, -beta, -alpha, depth + 1);
    board[cell] = EMPTY;
    if (score > best) best = score;
    if (best > alpha) alpha = best;
    if (alpha >= beta) break; // the other side would never let us get here
  }
  return best;
}

/** The best square for the computer, and how it scored. */
static int8_t chooseMove(int &scoreOut) {
  nodes = 0;
  int8_t bestCell = -1;
  int best = -100;
  for (uint8_t k = 0; k < 9; k++) {
    int8_t cell = ORDER[k];
    if (board[cell] != EMPTY) continue;
    board[cell] = AI;
    // Alpha is the best we have found so far; anything not better is cut off.
    int score = -negamax(HUMAN, -100, -best + 0, 1);
    board[cell] = EMPTY;
    if (score > best) {
      best = score;
      bestCell = cell;
    }
  }
  scoreOut = best;
  return bestCell;
}

// ---- drawing --------------------------------------------------------------

static int16_t cellX(int8_t cell) { return BX + (cell % 3) * CELL; }
static int16_t cellY(int8_t cell) { return BY + (cell / 3) * CELL; }

static void thickLine(int16_t x0, int16_t y0, int16_t x1, int16_t y1, uint16_t colour) {
  for (int8_t d = -2; d <= 2; d++) {
    tft.drawLine(x0 + d, y0, x1 + d, y1, colour);
    tft.drawLine(x0, y0 + d, x1, y1 + d, colour);
  }
}

static void drawMark(int8_t cell, int8_t who) {
  int16_t x = cellX(cell);
  int16_t y = cellY(cell);
  if (who == HUMAN) {
    thickLine(x + 14, y + 14, x + CELL - 14, y + CELL - 14, X_COLOUR);
    thickLine(x + CELL - 14, y + 14, x + 14, y + CELL - 14, X_COLOUR);
  } else {
    for (int8_t r = 20; r <= 24; r++) tft.drawCircle(x + CELL / 2, y + CELL / 2, r, O_COLOUR);
  }
}

static void printAt(int16_t x, int16_t y, uint8_t size, uint16_t colour, const char *text) {
  tft.setTextSize(size);
  tft.setTextColor(colour);
  tft.setCursor(x, y);
  tft.print(text);
}

static void status(const char *text, uint16_t colour) {
  tft.fillRect(0, 272, 240, 20, BG);
  int16_t w = 0;
  for (const char *p = text; *p != '\0'; p++) w += 12;
  printAt((240 - w) / 2, 274, 2, colour, text);
}

static void drawScore() {
  tft.fillRect(0, 296, 240, 24, BG);
  tft.setTextSize(1);
  tft.setTextColor(X_COLOUR);
  tft.setCursor(10, 300);
  tft.print("YOU ");
  tft.print(wins);
  tft.setTextColor(O_COLOUR);
  tft.setCursor(86, 300);
  tft.print("AI ");
  tft.print(losses);
  tft.setTextColor(GRID);
  tft.setCursor(150, 300);
  tft.print("DRAWS ");
  tft.print(draws);
}

static void drawBoardFrame() {
  tft.fillScreen(BG);
  printAt(30, 14, 3, TEXT, "TIC-TAC-TOE");
  for (int8_t i = 1; i < 3; i++) {
    tft.fillRect(BX + i * CELL - 2, BY + 4, 4, 3 * CELL - 8, GRID);
    tft.fillRect(BX + 4, BY + i * CELL - 2, 3 * CELL - 8, 4, GRID);
  }
}

static void finishGame() {
  over = true;
  int8_t who = winner(winLine);
  if (who != 0) {
    // Light the winning line in green.
    int16_t x0 = cellX(winLine[0]) + CELL / 2, y0 = cellY(winLine[0]) + CELL / 2;
    int16_t x1 = cellX(winLine[2]) + CELL / 2, y1 = cellY(winLine[2]) + CELL / 2;
    thickLine(x0, y0, x1, y1, WIN_COLOUR);
  }
  if (who == HUMAN) {
    wins++;
    status("YOU WIN!", WIN_COLOUR);
    Serial.println("result human");
  } else if (who == AI) {
    losses++;
    status("AI WINS", O_COLOUR);
    Serial.println("result ai");
  } else {
    draws++;
    status("A DRAW", TEXT);
    Serial.println("result draw");
  }
  drawScore();
  tft.fillRoundRect(60, 244, 120, 24, 6, GRID);
  printAt(72, 249, 2, BG, "NEW GAME");
}

static void aiMove() {
  status("THINKING...", GRID);
  int score;
  int8_t cell = chooseMove(score);
  board[cell] = AI;
  moveNo++;
  drawMark(cell, AI);
  Serial.print("ai ");
  Serial.print(cell);
  Serial.print(" score ");
  Serial.print(score);
  Serial.print(" nodes ");
  Serial.println(nodes);
  if (winner() != 0 || full()) {
    finishGame();
  } else {
    status("YOUR MOVE", X_COLOUR);
  }
}

static void newGame() {
  for (uint8_t i = 0; i < 9; i++) board[i] = EMPTY;
  over = false;
  moveNo = 0;
  drawBoardFrame();
  drawScore();
  Serial.print("new game, ");
  Serial.println(humanStarts ? "you start" : "ai starts");
  if (humanStarts) {
    status("YOUR MOVE", X_COLOUR);
  } else {
    aiMove();
  }
  humanStarts = !humanStarts;
}

/** The raw touch, turned into screen pixels. */
static bool readTouch(int16_t &px, int16_t &py) {
  if (!touch.touched()) return false;
  TS_Point p = touch.getPoint();
  px = map(p.x, 200, 3900, 0, 240);
  py = map(p.y, 200, 3900, 0, 320);
  return true;
}

void setup() {
  Serial.begin(115200);
  Serial.println("Mokxi ESP32-C3: tic-tac-toe against minimax");
  tft.begin();
  tft.setRotation(0);
  touch.begin(touchBus);
  touch.setRotation(0);
  newGame();
}

bool wasTouching = false;

void loop() {
  int16_t x, y;
  bool touching = readTouch(x, y);
  // Act once per touch, when the finger lands.
  if (touching && !wasTouching) {
    Serial.print("touch ");
    Serial.print(x);
    Serial.print(' ');
    Serial.println(y);
    bool onButton = x >= 60 && x < 180 && y >= 244 && y < 268;
    if (over) {
      if (onButton) newGame();
    } else if (x >= BX && x < BX + 3 * CELL && y >= BY && y < BY + 3 * CELL) {
      int8_t cell = (int8_t)(((y - BY) / CELL) * 3 + (x - BX) / CELL);
      if (board[cell] == EMPTY) {
        board[cell] = HUMAN;
        moveNo++;
        drawMark(cell, HUMAN);
        Serial.print("you ");
        Serial.println(cell);
        if (winner() != 0 || full()) {
          finishGame();
        } else {
          aiMove();
        }
      }
    }
  }
  wasTouching = touching;
  delay(10);
}