The move generator.

If we want the engine to play, the program should be able of generating a list of  potential moves to be played, later we will know how the engine choose which is the best move to play, but for now we must be clear that Initially the program will generate the mentioned list. The program should of course be able to perform castling, en passant moves and pawn promotions.  And of course it should not make illegal moves, for example to stay in check after a move, although for speed reasons the generated list of potential moves can include illegal moves but later will be eliminated.

To generate the list, we must think of a 64 board squares,and for example to each square we associate a value between 0 and 63, starting from A1 to H8.  From the standpoint of white to move a pawn we shall add  8 to the initial square if the pawn moves one square or 16 if advance two squares, if it take diagonally it will be necessary to add 7 or 9, on the other hand from the standpoint of  black pices we shall have to subtract. For the remaining pieces we would do the same procedure. We must take into account the size of the board and when a piece make a move cannot fall out of the board, for it we must impose some conditions. To make this work easier some programmers have invented to generate moves in boards sizes of 12x10 or 12x12 or 16x8, but then they convert it to the normal 8x8 square board, if the move of the piece fall out the standard 8x8 board, that move is illegal.  

 

The evaluation function

Is what allows us to value each position, when we want to value a position at  least we must check the material or chess pieces of each side, same as is done by a human. To each piece we can give a value, for example 1 for the pawn, 3 for the bishop and knight , 5 for the rook and 9 for the queen . The total evaluation wil be the sum of the values of the pieces of a player less the other. Only with this and if the program plays with a deep search depth, the program will look  alive and will play, winning to many human or some other engine.

But apart from the material, is important that the program, like a good chess player, consider a number of other things, for example something well known by a good amateur, that it is important to occupy the center board with pawns and pieces such as knights and bishops, develop his pieces as soon as possible, castling, have the maximum possible mobility and space, that the king is safe after castling, try to keep the pair of bishops, move the rooks to the open or semi –open columns, keep the pawns structure,try to get passed pawns to promote them, etc..  As much more things we teach the program, it will play better, but just as important as a good evaluation is that the search along the tree is as effective as possible and that the program do not get lost in infinite possible combinations.  There are those who makes the programs to evaluate much, making it slow in searches and therefore not very effective because is possible that cannot reach an adequate level of depth and miss a combination, there are others who seek for high speed search but with very little evaluation , so the program will be a tactical monster but will fail in their positional play and especially in the endgame. This is  because we must try to look for a balance between the two alternatives.

 

 

 

A program or a human who only think of the immediate reply of the opponent, will be very weak, to play well you have to think not only in the immediate response but must be able to see how the position would be further moves ahead. A player who wants to be considered at  least a good  fan should be thinking which will be at least  his third move ahead, considering that the opponent moves will be 6, this is called in chess, 6 ply depth.

 

Deep Blue in his famous encounter against Kasparov reached a depth of 14 plies today  this depth is reached by many programs.

 

If we said that in each middle game position there are about 35 possibilities, if we want to think ply = 6,this are 35x35x35x35x35x35 = 1.838.265.625 combinations !!!!!!!!!!!!

 

Of course no human is capable of analyzing the such number of combinations, humans discard the mayority of the possibilities of  a position by intuition, for example why to take with the queen a protected pawn if I am going to lose the queen, so I will not further research there, but always you have take into account the possibility of a sacrifice,for example we can sacrifice the queen if a couple of moves later we mate.

 

A chess program, also neglect chances or have to take into account all possibilities and combinations?

 

If our program look for all the possibilities and is capable of analyzing 500,000 positions per second would need 1.838.265.625 / 500000 = 3676 sec, nearly one hour to search up to ply = 6. So if a program wants to be competitive cannot consider all positions, must think a bit like a human.

 

Fortunately, someone realized that is not needed a program that analyze all possibilities, like the human they discarded potential possibilities, the program prune the variants tree if  it see  that is not going to get a higher evaluation and do it with a mathematically method  similar to what would to a human but without making mistakes. Aproximately for a position  in which there are 35 possibilities, the engine with a feature called alphabeta cutoff  stay only with square root of 35 possibilities to consider,that is to say the machine will focus only on 6 possibilities , which makes the machine to play twice as deep in the same time.

 

And what do good programs as Shredder, Fritz, etc., to reach search depths greater than 16 plies in less than 3 minutes?

 

Good question, for that there are many techniques that allow programs to speed up to the maximum the search,and also these programs use highly developed techniques to prune the variation tree to the maximum, this is often called selectivity. With all these techniques best programs manage to reduce the number of moves to examine, normally from 6 to 2, although in this case run risks of missing something.