Chess AI

Wouldn't it be cool if I could build a chess AI that was so awesome it could never lose...Gary Kasparov's nightmare? He'd probably just say mine cheated too. It would be cool, however on my quest to do just that I got distracted and spent most of my time making my chess board look rad. So I only got as far as making a chess AI that could play about as well as I do, not great but it'll beat your niece twice removed who took up chess last year.

You see there are a handful of really cool JavaScript libraries that do some basic functions. Things like, build up a basic chess board, you’ve seen the one, it’s brown and tan and boring.

Then a basic library for move validation, which, as it turns out, is a lot harder to pull together in a few hours than you might think. They are kind of famous at the moment but chessboard.js and chess.js cover these necessities respectively. They aren’t particularly maintained at the minute, and as a lot of my life revolves around React, so I thought I’d dive in and have a go at some updating and wrangling of libraries into not only react but TypeScript. Cue one whole afternoon being cross with my computer for not letting me win. I got there in the end, but oh goodness If I had a recommendation for learning to build a chess AI, it would be to not get bogged down in the details of aesthetics and TypeScript, because you have a feeling it could be good.

So as mentioned already, once I got off the wagon of compatibility and setting up a working environment, I moved swiftly on to tinkering with aesthetics. Now this project introduced me to a new library called Rough.js, if you haven’t played with this before it is really, really cool. Wanna make something look hand drawn and more akin to a sketch in a notebook? Then Rough.js is your friend. Easy to use and just works after you get past the little hitch of it not wanting to work with TypeScript out of the box.

Rough.js is really, really cool!

Alrighty So we now have a functioning chessboard that knows what’s what when it comes to Castelling or En Passant. How is this going to work? Well there are a million and one articles ad blogs and academic papers on the subject. It turns out that people have been working on a good chess AI since we could program computers. The earliest I found was Alan Turing in 1946 working on the problem. Which seems about right, I heard he had something to do with beating the Nazis, not getting a very good thank you from the British government and probably wanted something to do that could take his mind off that thank you.

The founder of Game Theory, John von Neumann, defined Chess as a two person zero sum game with complete information.  Now the basics of that statement are that there are two people playing the game, and those players are set against each other so that as one player improves their situation they do so at the expense of the other player (zero sum-game) complete information being that everything is on the board to be seen. The opposite of which would be a game like Cluedo where information is hidden intentionally. If you’re into your Computer History von Neumann wrote the first version of a Chess solving AI for the MANIAC I which utilised the Minimax algorithm that again he pointed out was a good way to solve a two person zero sum game with complete information.

The Minimax algorithm is a process for deciding the minimum loss in a worst case scenario. (I’m paraphrasing). In a nutshell, if you picture all of a games possible moves in a tree, so you make one move and that opens up more moves and each subsequent move opens up more. All of these moves can then be worked through and the least bad one found. Essentially the algorithm alternates between minimising and maximising the outcome of each move. It maximises your moves and minimises the opponents. In chess, however there is a hitch. After each player makes their first move there are now 400 different combinations that could be played. After two moves a piece there are 72,084. 9 million after three and over 288 billion possibilities after each players fourth move. The tree that would represent these moves is already massive in a game that typically lasts in the 35 to 40 moves territory. Using Minimax alone would currently be impossible with the required computing power to work through the entire tree looking for the least worst scenario. This requires a degree of looking ahead to have an understanding of what can happen moving forward, but this compounds the computations required and becomes unfeasible. But the further we look ahead the better chance we have of maximising our position while minimising our opponents.

So we need something to take a bit of the grunt work out of this scenario. We have a scenario that while increasing the search depth (how far ahead in the tree the algorithm looks) improves play, it also slows down in execution time. Another algorithm called Alpha-beta pruning can help us with this. We can look holistically at the tree structure and remove branches that are not going to be explored by the opponent given the logic that a player will chose moves that will optimise their chances of winning. So if we see a branch is not optimal for them to even consider we can prune it from the tree and not examine it. This in turns speeds up the processing.

That is the crux of everything I’ve written. Deep Blue it is not, but it will play some pretty decent chess and it looks cool. The practicalities of the work is built on the idea of being able to take any chessboard scenario and assign it a score. This allows the minimax algorithm to quantify good and bad moves. I saw this image online that really drove it home for me:

To achieve the ability to evaluate a board and come up with a score you need to weight two things. The first thing is to weight the value of the pieces. and this would typically look something like: Pawn 100, Knight 280, Bishop 320, Rook 479, Queen 929, King 60,000. Then you need to weight the possible moves of each playable piece. This type of evaluation has been done for as many decades as chess AIs have been built and has been simplified into a process called piece square tables, where an array of 8 arrays each having 8 values in them represent the board. If you like Python just think list every time I say array. Then you weight the "positions" on the board. An example would see a knight have the centre positions highly weighted as that is where they do the best work at holding back the opponent or capturing pieces. Each piece square table is then reflected to represent the opponent.

Now, the tweaking of these weights and piece square table values is a delicate art that takes an inside out knowledge of chess and playing it. Remember that I can only beat your niece twice removed, and to be fair to my own playing abilities that would only be if I cheated. Saying that I've stolen these values (as it looks like a lot of people have who've built chess AIs) from Sunfish.py. But once the values are in place you can iterate though the values finding the highest or indeed the lowest value moves to make for any given board position.

And this was how I spent Christmas break. So while it has made it over the first hurdle of working, it needs some love, I might give it a few hours per month to work on issues and add a few features. Here's my GitHub:  https://github.com/matthew-davis/chessai