How to program a machine to play chess ?

Overview

Chess simulators imitate the human reasoning process and compensate their lack of intuition with tremendous computation power. For instance, Cheeky Chess javascript engine evaluates about 10.000 positions per second on an average machine.

Let's analyse how the humans think and determine which move is best : first, we list our possible moves. Then, we try to determine which one is best based on the possible retaliation from the opponent. Good players will look a couple of moves ahead, and pick up the one that advantages them the most in the end.

Tree of possibilities

This reasoning process can be modeled with a tree of possibilities, starting from the board position. Let's consider the following example, white to move :






The move F1-A6 is clearly dumb : the blacks will answer playing B7-A6 and capture the bishop. Thus a move must be avoided if a harsh strike back is possible. Similarly, a move is great if no retaliation exists. Mathematically speaking, we are trying to maximize the value of our move, while our opponent is trying to minimize this value.

After either side moves, the best possible move is represented by Max(Min(X)), X being the board position at the end.

After two moves, the best possible move is represented by
Max(Min(Max(Min(X)))), X being the board position at the end.

After three moves, Max(Min(Max(Min(Max(Min(X)))))). Etc...

The simulator will include two main functions :
  - one function building up the tree of possibilities
  - one function evaluating the resulting board position (good or bad ?)

The results of these "leaves" are brought back to the "root" of the tree (=the current position), by selecting the maximum of the minimum of the maximum of the minimum... This is called a minimax algorithm and it works pretty well.

Evaluation of a position

A first estimation of the resulting position is made up of the sum of the remaining pieces : a pawn is worth 1, a bishop 3, a knight also 3, a rook 5, a queen 9. But as Richard III offering his kingdom for a horse, this approximation must be refined : a pawn on the way to promoting is worth much more, while a pinned or skewed piece can be doomed.

The resulting value is simetrical to both player : a value of 5 to one players equals -5 to the other player.

Tree pruning

The problem with chess programming is the exponential increase of the possibilities : at first there are 20 opening possibilities. If we multiply by the possible blacks moves, we get 400 positions to analyse.
Two moves on either side equal about 20x20x20x20 = 20 ^ 4 = 160.000 possibilities. Three moves ? more than 64 millions possibilities. You get it, the powers of 20 swell really fast !

The solution lies with the pruning of our tree. Pruning means that we won't look at what happens after we play a blunder. Why ? Because we won't play that blunder ! Same for our opponent. Unless he's a retard, he won't give up his queen for free (ok i must admit i did this a couple of times...)

This really shrinks the number of positions to analyse. For instance, Cheeky Chess analyses less than 1% of the global positions available. For more details see this article on wikipedia.

Lame moves

Our algorithm is getting ready but we still need to improve the performances. While studying the branches of our tree, we realise that some blunders are explored X times with the same verdict everytime : LAME ! Indeed, it is likely that if i have the possibility to do a blunder and avoid it, it will show up again next move. Once determined that this move is lame, it is useless to explore it again : lame it is, lame it will ever be !

But... there are some cases where the opponent move drastically changes the interest of a move.



In this example, the bishop move E5-E3 is obviously lame. However, if the whites play later H2-H4 it should be reconsidered. This move should be explored in the branches dealing with H2-H4, not in the others.

The hard part is then to decide what is a lame move, and the level of likeness required to discard them.

Cheeky Chess considers that a move is lame if it is rated 1 point less than another move (1 being the value of a pawn). Once this move has been tagged "lame", Cheeky Chess will not investigate this move if the piece played next by the opponent is located at the same position as when the move was tagged "lame".

Other optimizations

It is useful to vary the depth of the tree depending on the interest of the moves : by default we will check X moves ahead, but it might be useful to dig some more in case of a queen exchange. The interesting moves should also be analysed first : if we exchange pieces and the result is positive, no need to explore other paths.

Of course, doing so we will sometimes miss some opportunities, but the goal is to increase the speed of the program : If we double the running time and harvest something only 5% of the time, that's not worth it.

Programming language

The simulator is coded is javascript, which is running on your web browser. The moves are not sent to a web server for computation, everything is executed on the client side so that you don't depend on the network once the page is downloaded. To my surprise 1500 lines were enough to get a draft version running. Software used :
  - Notepad++ for javascript
  - GIMP for graphics

Graphics

The Brutus mascot is inspired from the website www.how-to-draw-funny-cartoons.com
The chess pieces are photos that come from my pocket game back from high school.

About me

Website developped in 2011 by Frédéric Gaonac'h.

I code in various languages : VB/C#/ASP.NET, SQL, Javascript, XSL...

The idea for this website came from a sophomore computer project that was about making a computer play Connect Four. A chess simulator logic is similar, but the pruning must be optimized if you don't want to see your computer implode.

And btw, i'm a poor chess player... :-)

Any questions, comments ?