Chatty Chess Engine

[greg-kennedy]

The intent is to produce a book that describes a computer's thought process as it makes one chess move.

The book opens with a chess position, followed by an in-depth analysis of the board and potential follow-up moves. The whole thing is presented of a player narrating to themselves, as in "Harry considered moving his bishop from a3 to c5. If he did that, Maude might respond by moving her pawn from f4 to f3. Then..."

At the end of the story, the player will announce their move.

Think of it as a verbose version of the alpha-beta or minimax algorithm. Prior work would include other noisy algorithm output, like this one: https://github.com/dariusk/NaNoGenMo-2014/issues/76

[dluman]

This is a very interesting take on suspense. I look forward to reading it!

[eseyffarth]

I love this idea! Did you see the entry by @nothings from 2014 that turned a similar (but deterministic) problem into a story?

[greg-kennedy]

And... it's done.

Novel: https://github.com/greg-kennedy/ChessBook/blob/master/sample/novel.md

Code (repo): https://github.com/greg-kennedy/ChessBook

Preview

[greg-kennedy]

So, a couple things to note about this.

First, I tried to make this novel "interesting" by using a Mate-in-2 problem, so that White would have an ending to search for instead of just a quiescent position. The actual position I used was from a real game in 2017, "Monika Socko vs Laura Unuk, Riga, 2017". See if you can find the best move : )

Second, if you're unfamiliar with chess algorithms: The Minimax algorithm is a simple recursive algorithm paired with a static evaluation function. Essentially, for each board position, try making every possible move - and then, if you are not deep enough, try every resulting move from there. At the bottom, "calculate" how good you think the position is. Simply, you can assign point values to each piece, and count up the "score" of the board.

The intent of Minimax is to minimize the damage that the opponent will do at every move. You should make the move that results in the "maximum" of all possible opponent "minimums". For Chess, you can assign a massive value to capturing a King, and the engine will automatically seek out attacks and checkmates.

Unfortunately, Minimax alone is highly inefficient. This simple position resulted in 370,000+ words for just a 3-ply search. One improvement comes from Alpha-Beta pruning, which cuts branches of the tree when the outcome is guaranteed equal-or-worse than some already evaluated position. The improvement is dramatic, and its development made chess engines actually viable competitors. In my case, Alpha-Beta was actually TOO efficient and I ended up less than 50,000 words... so, the novel code includes a 10% chance to skip pruning if a position is deemed equally as good as another previously seen. The final sample comes to approximately 51,000 words or so.

There are other scripts in the repository: an Engine module, which can be attached to a Chess state and "play" as Harold. And there is play.pl which can be used to play against the engine. This being NaNoGenMo, I ran out of time for some of the engine features I wanted: castling and en-passant are not supported. It turned out not to matter for my test position.