Grids and AIs

These programs have one thing in common: a grid, closed rules, and very soon the urge to write something that plays in the player’s place. It is the same path that later leads to OptiChess and to the game solver.

2048. The complete game, with a menu (new game, load, options), saving, a choice of grid size and tiles drawn up to 131,072. A second version, picked up later, rewrites the core for Numba: each possible move is evaluated by finishing the game at random a large number of times, in parallel, and the computer picks the move with the best average. Expectimax and finer Monte Carlo stayed on the wish list.

Connect 4. The grid is encoded as two integers, a position and a mask, and a line of four is tested with a few bit shifts, the same idea as the bitboards in chess engines. Around it, a series of opponents of growing strength: random, one that wins when it can and blocks when it must, a minimax with alpha-beta pruning, and a statistician that plays a hundred games for each move. A thousand-game tournament ranks them.

Sudoku. A backtracking solver, then a generator: fill a grid at random, remove digits. Six levels, from beginner to “devilish”, depending on how many cells are emptied. Nothing yet guarantees a unique solution; it is the first line of the to-do list.

Chess. The first chess program, in 2019: a board, pieces moved with the mouse, checks for legal moves and for check, then a minimax opponent on an evaluation of material and piece placement. It turned out too slow to go far, and that slowness is what decided the next engine, written in C++.