Previous Page Next Page The inner work of a chess program

I am often asked the question, how does a chess program work? It's not such a big problem to answer that question except when it was asked by a journalist as he/she immediately added restrictions like, do it in 2 minutes or say it in 3-4 one-liners. I do understand the sentiment of the journalist but it doesn't work that way, you need to invest some energy to understand the dynamics involved. Here goes.......
Introduction

A chess program is software, just software like any other of the hundreds of (software) programs you have on your PC. A program is a set of instructions the computer understands and executes.

If you can teach a computer the rules of bookkeeping so can you teach a computer the rules of chess, there is nothing mysterious on that.

A chess program is divided into 3 sections (modules):
The rules of Chess

  • To play chess the program needs to understand the rules of chess, so this module contains all the rules, how knights move, the castling rules, the pawn promotion rules, stalemate, checkmate and so on. The module will return a list of all legal moves, for the start position the list will contain 20 moves.

  • When this part is ready you already have a program that can play legally chess, just pick a (random) move from the list of all legal moves and move it to the screen, wait for the opponent response and repeat the process.

  • So that's the first part, the most easiest part. All it takes is a reasonable programmer, knowing the rules of chess and a couple of weeks of spare time, you don't even need to be a chess player to make a chess program.

  • However, a chess program that just plays random moves isn't going to be very successful, in fact it will lose 99.99% of its games against any ordinary novel chess player, what it needs is intelligence and that's what's the next 2 parts are all about, Search and Chess Knowledge.

The Search Algorithm

  • The Search Algorithm emulates the look ahead process human chess players do when it's their turn to move. Have a look at the diagram, with black to move it looks very attractive to capture the rook playing 1..Nc2xa1, however any reasonable chess player will not do that because he will find himself checkmated the next move with 2.Qf3xf7#.

  • That's what a human chess player does, while considering his own move(s) he lookes ahead what his oppenent might do, that's the mechanism. The great chess players of our time and those of history have one thing in common, they could look ahead many moves, sometimes up to 20 moves and foresee all the consequences.

  • It's exactly that where computers excel, the look ahead process, its technical name: SEARCH. Where humans, even the great players, make mistakes in their calculations (the look ahead process) computers can search flawlessly, let's move to the next diagram to demonstrate this.
  • In this position GM Shirov played the beautiful 1.Rxg7+!! and checkmated his opponent 14 moves later! After the game Shirov claimed that no computer could be able to find this move.

  • GM Shirov was wrong, a chess program with a good search algorithm can find the mate combination very easily. REBEL for instance finds the move 1.Rxg7+ in 4 seconds and announces the mate 10 seconds later, all this on a poor 850 Mhz PC.

  • This is certainly much faster than GM Shirov did during his game as he had to calculate the complete mate combination very carefully before playing the move.

  • All it needs for a chess program is to have a good search algorithm to find such beautiful tactical turns, there is no special chess knowledge needed, just knowing the legal rules and a clever search algorithm.


    The Chess Knowledge

  • However, we are still not there. Not every position in chess is about checkmate or material gain, a chess program that plays 1.Ng1-f3 2.Nf3-g1 3.Ng1-f3 4.Nf3-g1 from the start position is candidate to lose all its games despite the fact there are no direct material losses present, what the program is still missing is positional and strategic understanding of the game, that's where Chess Knowledge comes in, the heart of a chess program.

  • Let's consider the start position, see diagram. We know that the first module will generate for us a list of all legal moves, 20 in this case. But what is the best move from those 20? Here is how it works, for each move (of the 20) the Chess Knowledge Module is called and the module returns a number also known as the score of the position.

  • So all 20 moves will get a score see example below, then simply the move with the highest number is chosen as the best move and send to the screen, e2-e4 in this case, as simple as that!
    
    e2-e4 40  d2-d4 36  Ng1-f3 30  Nb1-c3 28  c2-c4 27  e2-e3 20   d2-d3 20   c2-c3 12  g2-g3  10  b2-b3  10
    a2-a3  8  a2-a4  7   b2-b4  4   h2-h3  4  f2-f3  0  f2-f4  0  Nb1-a3 -8  Ng1-h3 -8  h2-h4 -30  g2-g4 -40
    
    
    
    These numbers, how does it work?

  • The Chess Knowledge Module will represent a position in a number also known as the score of the position. Let's consider how the Chess Knowledge Module will translate the position after 1.e4 into a number, the score of 40 in this case, see diagram.

  • The first phase will check all pieces on the board and calculate the score via a formula. For instance the value of a pawn is 100, so 100 is added to "score", the value of a knight is 300, so 300 is added to "score", making "score" 400. For the bishop the value is also 300, the rook is 500, the queen is 900, the king is irrelevant. When counting all the white pieces we get a "score" of 3900 in total.

  • We repeat this process for the black pieces, only that the values of the pieces are subtracted instead of added to "score". If things are done well "score" will contain the value of "0", the correct material balance of this position.

  • The second phase is to evaluate all the positional characteristics of the position, characteristics are: mobility of the light pieces, king safety, pawn structure, center control, pins, bishop pair, various endgame knowledge and so on, a sophisticated chess program has hundreds of characteristics. All the characteristics are (again) represented by numbers and added to "score".

  • For the position after 1.e4 (see diagram) mobility, pawn structure and center control look dominant, the Chess Knowledge Module will recognize those patterns and add 12 points for mobility to "score", 18 points for pawn structure and 10 points for center control, making "score" 40 in total.

  • The score of 40 is passed (connected) to the move 1.e4 and then the next move (of the 20) is evaluated till all 20 moves are evaluated and the move that has the highest number is considered as the best move and thus is played.

    As far as I know nowadays all available chess programs work this way, others have tried different approaches such as former world champion Michael Botvinnik with his program PIONEER in the early 80's but so far the above explained skeleton still is superior.
    Previous Page Next Page
  • Copyright © 1984 - Ed Schröder
    Mail Me