Taboun, the chess bots I build
Taboun is the name of the chess bots I write. This post says what they are, how they play, how I find out which one is the strongest, and what building them taught me.
Last December I wrote a chess program in twenty lines. It looked at the legal moves and picked one at random. It lost to everyone, which was the point. It was the first version of Taboun, and every version since has kept what the previous one did and added exactly one idea. Nine months later there are fourteen of them, they all live side by side, and you can play any of them. The code is on GitHub.
One idea at a time
The rule of the project is simple. Each version keeps everything the previous one did and changes one thing. Taboun 0.2 looks one move ahead for each side and counts the pieces. Taboun 0.3 learns that a knight in the centre is worth more than a knight in the corner. Taboun 0.4 stops exploring the branches that cannot change the result, which buys it one more half move of depth in the same time. And so on, up to 0.14.
The fourteen versions are a short course in classical chess programming, and the ideas fall into three families.
Most of them are about searching better. Looking at captures and checks first, so that bad branches are abandoned sooner, in 0.5. Following a sequence of captures to its end before judging a position, in 0.6, because a position in the middle of an exchange means nothing. Remembering positions already analysed, in 0.7. Searching one ply deep, then two, then three, and reusing what was learnt each time, in 0.8. Stopping when the clock says so and keeping the best move found so far, in 0.10. Preferring the fastest mate, in 0.12. And in 0.14 the whole toolbox of modern engines, killer moves, null move pruning, late move reductions, futility pruning, each behind a switch so that it can be turned off and measured on its own.
A few are about judging positions better. Tables that give each piece a value depending on its square, in 0.3. Mobility, pawn structure and king safety, in 0.9. Then in 0.13 the tables of PeSTO, borrowed from the engine RofChade, tuned automatically and blended according to the phase of the game. That last change threw away every line of handwritten evaluation, and the bot got stronger.
And two are about knowledge rather than thinking. An opening book in 0.11, and in 0.14 the option of endgame tables, which give the exact result of any position with few pieces left.
What strikes me, reading them in order, is how little of the strength comes from chess knowledge and how much from the plumbing. The biggest jumps in the ranking below belong to 0.12, which mostly got better at remembering, to 0.14, which is pure search technique, and to 0.10, which only learnt to use its clock. The one version that is nothing but better chess knowledge, 0.13 with its tuned tables, gains less than any of those.
Play
The Play page lets you play any version with either colour, or sit two of them at the board and watch. Each bot gets two seconds per move, and the versions that have an opening book keep it against visitors, which is why their first moves come out instantly.
The arena
I wanted to know which version is the strongest, and by how much, so I made them play a tournament. The conditions are always the same. Sixty seconds per game plus six tenths of a second per move, one processor thread each, no opening book, and the same hundred openings for everyone. Each pair of bots plays every opening twice, once with each colour. That makes two hundred games per pairing and 2,600 per bot. The result is on the Arena page.
The ratings come from Ordo, a program that computes Elo-like ratings from game results, and I show the error margin next to each one. Two caveats. The scale is internal to this group, I pinned 0.2 at 1000, so 2254 does not mean anything on Lichess. And 0.1 is barely on the scale, with 28 draws in 2,600 games and not a single win, so its number is not worth much.
The head to head table is the more interesting one. 0.11 is 0.10 plus an opening book, and books are off in the arena, so they are the same program and they sit next to each other, as expected. 0.7 is 0.6 plus a transposition table, and it loses to 0.6, 93 to 107. I did not expect that and I have not found the reason yet.
A published run never changes. Its folder has the games, the ranking, the openings and a manifest with the commit of the code, the versions of the tools, the hardware and the exact command, so the tournament can be run again and give the same list. The script refuses to start if the code has uncommitted changes. When a new version arrives it only plays the versions already published, their games are kept, and the ranking is recomputed over everything. That is how 0.14 got on the list after 2,600 games rather than 18,200.
Every game can be replayed in the browser.
What comes next
The 0.x line is the classical one, handwritten search and handwritten evaluation. The next line, 1.x, will learn its evaluation from games instead of being told it, first with a small network that orders moves, then with the kind of network that modern engines use. The rule stays the same. One idea per version, and a tournament to find out whether the idea was worth it.
Everything is in the repository, from the twenty lines of the random bot to the arena scripts. If you want to beat them, 0.1 is a good place to start, and 0.14 is not.