Skip to content

Free games for graphing calculators: NumWorks, TI-Nspire CX, Casio fx-CG50 and soon TI-84 Plus CE. Balatro, Celeste, Hollow Knight, Minecraft and more.

7.3 KB
Raw Blame
/* Ultimate Tic-Tac-Toe's rules and computer, checked on a computer (make test):
 * - the rules on hand-made positions: where a move sends the other player, a small board won or full,
 *   the big board won, a draw;
 * - thousands of random games: every move legal, the game always ends, never more than 81 moves;
 * - the computer at every level only ever plays legal moves, takes a win in one, never hands one
 *   over, and the levels beat each other in order: hard over normal over easy over random. */
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static long budget;
static long ticks;
static bool search_stop(void) { return ++ticks > budget; }
static uint32_t seed = 12345;
static uint32_t rnd(void) {
  seed ^= seed << 13;
  seed ^= seed >> 17;
  return seed ^= seed << 5;
}
#include "../src/rules.h"

static int fails;
#define CHECK(c, ...)                            \
  do {                                           \
    if (!(c)) {                                  \
      fails++;                                   \
      printf("FAIL %s:%d ", __FILE__, __LINE__); \
      printf(__VA_ARGS__);                       \
      printf("\n");                              \
    }                                            \
  } while (0)

static int random_move(const pos_t *p) {
  uint16_t mv[9];
  int n = legal(p, mv), k = (int)(rnd() % (unsigned)n);
  for (int b = 0; b < 9; b++)
    for (unsigned m = mv[b]; m; m &= m - 1)
      if (!k--) return b * 9 + __builtin_ctz(m);
  return -1;
}
static bool is_legal(const pos_t *p, int m) {
  uint16_t mv[9];
  legal(p, mv);
  return m >= 0 && m < 81 && (mv[m / 9] >> m % 9 & 1);
}
/* the computer's move at a level, as src/main.c sets them: 1 easy, 2 normal, 3 hard; the search
   may go on `calls` times 512 nodes */
static int cpu(const pos_t *p, int level, long calls) {
  static const int depth[4] = {0, 1, 3, 30}, noise[4] = {0, 90, 10, 0};
  ticks = 0, budget = calls;
  return think(p, depth[level], noise[level]);
}

static void rules(void) {
  pos_t p = {.next = -1};
  uint16_t mv[9];
  CHECK(legal(&p, mv) == 81, "81 moves to start");
  play(&p, 4 * 9 + 2); /* X in the middle board, top right cell: O goes to the top right board */
  CHECK(p.next == 2 && p.turn == 1, "sent to board 2");
  CHECK(legal(&p, mv) == 9 && mv[2] == 0777, "9 moves in board 2");
  /* O wins the top left board with its bottom row, X sending O back there each time */
  p = (pos_t){.next = -1};
  int seq[] = {0 * 9 + 0, 0 * 9 + 8, 8 * 9 + 0, 0 * 9 + 7, 7 * 9 + 0, 0 * 9 + 6};
  for (int i = 0; i < 6; i++) {
    CHECK(is_legal(&p, seq[i]), "move %d legal", i);
    play(&p, seq[i]);
  }
  CHECK(p.won[1] == 1 && p.won[0] == 0 && p.over == 1, "O has board 0: %o %o", p.won[0], p.won[1]);
  CHECK(p.next == 6 && !is_legal(&p, 0 * 9 + 1), "X sent to board 6, board 0 closed");
  p = (pos_t){.next = -1};
  p.mark[0][0] = 0003, p.turn = 0, p.next = 0;
  play(&p, 2);
  CHECK(p.won[0] == 1 && (p.over & 1), "X wins board 0");
  CHECK(p.next == 2, "sent to board 2: %d", p.next);
  /* sent to a board that is over: anywhere */
  p = (pos_t){.next = 3};
  p.over = 1, p.won[1] = 1, p.mark[1][0] = 0007;
  play(&p, 3 * 9 + 0);
  CHECK(p.next == -1, "board 0 over: a free move");
  CHECK(legal(&p, mv) == 81 - 9 - 1, "free move: every board but 0, %d", legal(&p, mv));
  /* a full board with no line is over but won by nobody */
  p = (pos_t){.next = 5, .turn = 1};
  p.mark[0][5] = 0b011100101, p.mark[1][5] = 0b100011000; /* O fills the last cell, 1: no line */
  int c = __builtin_ctz(~(p.mark[0][5] | p.mark[1][5]) & 0777);
  play(&p, 5 * 9 + c);
  CHECK((p.over >> 5 & 1) && !(p.won[0] >> 5 & 1) && !(p.won[1] >> 5 & 1), "board 5 full, nobody's: %o %o",
        p.mark[0][5], p.mark[1][5]);
  /* the big board: three in a row wins, a full one without is a draw */
  p = (pos_t){.next = -1};
  p.won[1] = 0124, p.over = 0124;
  CHECK(result(&p) == 2, "O wins on the diagonal");
  p.won[1] = 0, p.won[0] = 0, p.over = 0777;
  CHECK(result(&p) == 3, "draw");
}

static void random_games(void) {
  for (int g = 0; g < 20000; g++) {
    pos_t p = {.next = -1};
    int n = 0;
    while (!result(&p)) {
      int m = random_move(&p);
      CHECK(is_legal(&p, m), "random move legal");
      play(&p, m);
      CHECK(++n <= 81, "more than 81 moves");
      if (n > 81) break;
    }
    /* what result() says matches the marks */
    uint16_t won[2] = {0, 0};
    for (int b = 0; b < 9; b++)
      for (int t = 0; t < 2; t++)
        if (three(p.mark[t][b])) won[t] |= (uint16_t)(1 << b);
    CHECK((won[0] & won[1]) == 0, "a board won twice");
    CHECK(won[0] == p.won[0] && won[1] == p.won[1], "won boards kept right");
  }
}

/* a game between two levels (0: random), the hard one searching `calls` x 512 nodes a move; 1 if X
   wins, 2 if O does, 3 a draw */
static int match(int x, int o, long calls) {
  pos_t p = {.next = -1};
  while (!result(&p)) {
    int lv = p.turn ? o : x, m = lv ? cpu(&p, lv, lv == 3 ? calls : 1 << 30) : random_move(&p);
    CHECK(is_legal(&p, m), "level %d played an illegal move %d", lv, m);
    if (!is_legal(&p, m)) return 0;
    play(&p, m);
  }
  return result(&p);
}
/* the games a wins against b, playing X then O, `rounds` times */
static int duel(int a, int b, int rounds, long calls) {
  int w = 0;
  for (int i = 0; i < rounds; i++) w += (match(a, b, calls) == 1) + (match(b, a, calls) == 2);
  return w;
}

static void computer(void) {
  /* a win in one: X has two in the top row of board 0 and the boards 1 and 2 won */
  for (int lv = 1; lv <= 3; lv++) {
    pos_t p = {.next = 0};
    p.mark[0][0] = 0003, p.won[0] = 0006, p.over = 0006, p.mark[0][1] = 0007, p.mark[0][2] = 0007;
    p.mark[1][0] = 0300, p.mark[1][3] = 0001;
    int m = cpu(&p, lv, 100);
    CHECK(m == 2, "level %d misses the win: %d", lv, m);
  }
  /* no win in one handed over: O to play in board 0, where X threatens the top row and owns boards 1
     and 2. Sending X to a board that is over (1 or 2) or to board 0 would let X win. */
  for (int lv = 2; lv <= 3; lv++) {
    pos_t p = {.next = 0, .turn = 1};
    p.mark[0][0] = 0003, p.won[0] = 0006, p.over = 0006, p.mark[0][1] = 0007, p.mark[0][2] = 0007;
    p.mark[1][0] = 0100, p.mark[1][4] = 0001, p.mark[1][5] = 0020;
    int m = cpu(&p, lv, 100);
    CHECK(is_legal(&p, m), "level %d illegal: %d", lv, m);
    play(&p, m);
    uint16_t mv[9];
    legal(&p, mv);
    for (int b = 0; b < 9; b++)
      for (unsigned k = mv[b]; k; k &= k - 1) {
        pos_t q = p;
        play(&q, b * 9 + __builtin_ctz(k));
        CHECK(result(&q) != 1, "level %d plays %d and X wins with %d", lv, m, b * 9 + __builtin_ctz(k));
      }
  }
  /* each level beats the one below (hard with a small search, so that the check stays quick) */
  int er = duel(1, 0, 5, 0), nr = duel(2, 0, 5, 0), ne = duel(2, 1, 5, 0), hn = duel(3, 2, 3, 8);
  printf("out of 10: easy beat random %d, normal random %d, normal easy %d; out of 6: hard normal %d\n", er, nr, ne,
         hn);
  CHECK(er >= 8 && nr >= 9 && ne >= 8 && hn >= 5, "a level doesn't beat the one below");
  /* how fast: a hard move from the start, 200 x 512 nodes */
  clock_t t0 = clock();
  pos_t p = {.next = -1};
  cpu(&p, 3, 200);
  printf("%d nodes in %.2f s here\n", nodes, (double)(clock() - t0) / CLOCKS_PER_SEC);
}

int main(void) {
  rules();
  random_games();
  computer();
  printf(fails ? "%d FAILED\n" : "all checks passed\n", fails);
  return fails != 0;
}