kleemans.ch

I wrote a simple Chess AI - try it out here (white to move):

Ever since I read the paper of Claude Shannon from 1949 I was intrigued by the simplicity of the approach on how to create a simple Chess AI.

The paper suggests to create an evaluation function f(position) which evaluates a given board position and returns a score:

• positive for a winning position
• 0 for a draw position
• negative for a losing position

The example function in the paper is:

f(P) = 200(K-K') + 9(Q-Q') + 5(R-R') + 3(B-B'+N-N') + (P-P') - 0.5(D-D'+S-S'+I-I') + 0.1(M-M')+...

where the capital letters stand for the number of pieces, for example R = white Rooks for example, and the primed letters are black pieces. The last part takes weak pawns (doubled, backward, isolated) into consideration and also mobility, counted as number of possible moves.

Searching the tree

Now that a given position can be scored, how to proceed? The second part of the AI is to search for the best move, by trying out all legal moves from the current position, and evaluating the position the board will be in at that point.

Repeat that, and you have a search for depth 2, 3, 4 and so on. The only problem is that at each point, the possibilities will fairly quickly explode so a depth of around 3 will already take up quite some time to evaluate. If, for example, there are 20 possible moves, and after each subsequent move 20 moves are possible, this leads to the following:

• 20^1: 20 positions
• 20^2: 400 positions
• 20^3: 8000 positions

So for a search depth of 3, already 8000 positions would need to be searched.

With a tree of board positions (starting with the current position) and their score, we can now evaluate the best move. This is called Minimax, and fairly common for games with perfect information available. It basically means, that for our own moves, we want to maximize the score (pick our best move), while for our opponents moves, we try to minimize the score (assume the opponent picks the best possible move). This can then further be optimized, by pruning branches that we're absolutely sure will not be able to reach.

Tweaking the evaluation function

I wanted to come up with a custom evaluation function, so the engine will really behave differently from what you're maybe used to. It uses the following criteria to evaluate a position:

1. Game state: If the game is over, 0 is returned for a draw or 200 / -200 for a win of black / white respectivly.
2. Material: The material is counted and weighted for both sides, with values Q = 9.35, R = 4.85, B = 3.25, N = 2.85, P = 1.
3. Mobility: Number of legal moves available (weighted with 0.05)
4. Pawn structure: Penalty for doubled and isolated pawns (weighted with 0.5)
5. Center control: Control of center (weighted by 0.2 and additionally by amount of remaining pieces)

The Chess Programming Wiki was really helpful and provides a lot of insights into the topic. I used chess.js for the chess rules and chessboard.js for the visualization.

You can find the source code at Github: chess-engine