Chess AI

I’ve been writing a chess AI.

I’m sure many of you have written one. It’s easy. It’s just chess.

Except for two things. If you want to make it play a good game it’s a lot harder to program. If you want to make it a play a good game that can compete against other AI chess AIs like stockfish. Well then. Now you’re spending your nights watching some YouTube videos and reading some papers.

I set a goal of evaluating 1 million moves per second. Which is middling for a chess AI. Not the best, but also not the worst.

The problem with that is the most important part of a chess AI is your static board evaluation function, the function you say, “here’s a move, here’s the result, give it a score please” and magically it returns an integer that says “this board sucks” or “that’s checkmate!”. Okay, I’m simplifying here, but a good board evaluation function counts the material, which is the pieces, and then things like the pawn structure, the king shield, the end game mop up eval, if you have “piece boards” they can figure in here too since those encourage “human” like moves from your chess engine, most piece boards can be somewhat replaced by a good opening book strategy gleaned from actual human games, but sometimes you get told to play against another AI without an opening book so you had better be ready.

That board evaluation function, you can’t skip out on making it really simple, but you do need to make it REALLY fast.

The first version of my chess AI that beat me evaluated around 8k/moves per second. I thought I was the bees knees, an AI that beat me! But then I played it against stockfish and got absolutely destroyed.

And oh, you need to add something called the UCI protocol if you want to play other chess AIs, and every GUI app that implements the UCI protocol does so slightly differently. Test everywhere or look silly.

And so the quest started. I had already added alpha / beta pruning, the ability for my AI to realize it was searching down a bad tree. So everything from here on out was learning.

I started to watch grand master tournaments so when I watched my AI play I could at least talk a good game even if it was already playing better than me. I watched chess class lessons to get better myself so I could program a better AI. Seriously, if you go to my YouTube now the welcome page is “Magnus, 4000 ELO?” and so forth. It’s a great community actually. I’m even a fan of Gotham Chess, his commentary on the community and tournament matches is really good and his commentary on AI matches is especially illuminating.

And then I hit 40k/moves per second by adding bit boards. Representing my chess board using 64bits, one 64bit integer for each piece. Incredible fast move generation and attack generation.

And then I hit 100k/moves per second by adding threading to my negamax function. Oh negamax? It’s the zero sum evolved version of minimax. You learn a lot making a chess AI.

And then I hit 250k/moves per second by fixing a bug to actually count the leaf nodes I visited. Doh.

By now I was using a Zobrist cache to quickly cache and hash move states. Zobrist hashing is great for any game board btw.

And then I added iterative depth and transposition tables. That is, the unintuitive method of starting by only going to depth 1, then depth 2, and so forth but using the information from the previous depth search to sort the moves you evaluate so the alpha beta cut off kicks in hopefully very early on most nodes. Because of iterative depth searches I can also search deeper later in the game and no longer have a fixed depth. My endgame has improved tremendously.

And so today I’ve hit 1 million moves per second. I can get to endgame with stockfish now, it’s still beating me, and probably always will, stockfish has a brilliant endgame, but it no longer destroys my AI.

So yes. Write a chess AI. It’s easy. It’s just chess.

?