 |
|
MAP Links Contact Us Books Glossary ECO Search Tools FAQ News
HOME CLUBS BANNERS 
BLOG VIRTUAL MUSEUM ARTICLES CAISSA FORUM
 | |||
 |
|
|
|
|
1o) Algorithms used in Chess Programming
The game tree is the tree of all legal moves, containing all possible lines of play starting from the initial position. Each node represents a position and all branches starting from this node represent all possible moves from this position. It is constructed recursively, with a limited depth because of the limits of machines. The minimax algorithm evaluates first the position in each leaf of the tree. The basic principle is to choose the best move when it's your turn to move and to suppose that your adversary will do likewise. So you will always choose the move that corresponds to the maximal evaluation and suppose that your adversary will choose the move that corresponds to the minimal evaluation (for you). Les us suppose it's White to move. The algorithm proceeds from the leaf to the root, it goes back up to the nodes above the leaves and associates the minimum of the values of the leaves that depends on it if the level of leaves corresponds to black moves, or the maximum if this level corresponds to white moves. It goes back up one step again and does the same thing with the tree with a depth decreased by one unit, where the nodes of the previous step serve as leaves at this step. So it alternates taking the minimum of node values, and then the maximum, etc... as far as the root. The alpha-beta algorithm works like the minimax algorithm but refrains from evaluating some nodes when it is not necessary. It avoids continuing the analysis of a node if this node is less interesting than a node already analysed. For example: let us suppose that it's White to move and that the leaves of the tree correspond to White moves. So we must associate to each node the maximum of the values of the leaves that depend on it. If in the evaluation of one node from the leaves we find one leaf which value is superior to the value of a node already evaluated, then computing the minimum of the maxima will not require evaluating the remaining leaves because whatever the values of the remaining leaves may be, the value of the node will still be superior to the previous node. This principle is applied to the entire tree from the root.
2o) The Generator of Legal Moves
We browse the pieces and generate all possible moves of each piece according to its specific mode of move. An elementary move is represented by a vector, for example the vector (1,2) represents one of the 8 possible movements of the Knight. We must take into account the fact that some pieces have a long range (like Queen, Rook and Bishop) and others haven't: this means that their elementary moves can be continued in all authorized directions. Each kind of piece is defined with a table of directions (vectors) and with a variable which indicates if it has long range or not. Of course, the pawns need a particular treatment (the direction depends on the color, rule for first move, capture en passant, capture and move are in different ways, promotion).
«Computer Art - Image generated A solution would be for each move generated to check if after playing it the King is in check and in this case to remove this move from the list. The problem of this approach is that the function that verifies if the King is in check is rather "expensive", and will be used a lot of times. A more economic method is to limit this verification to the case where the King is already in check (this case is relatively rare, and in this case this approach is almost obliged), and to prevent from moving a piece which would place the King in check. When the King is not already in check the only way to put him in check, except the fact of moving the King itself, is to move a pinned piece (and it may depend on directions). So it suffices to make precede the analysis by a function that starts from the position of the king and browses all directions to specify which pieces are pinned and in which directions. The great advantage of this approach is that this function is applied once for all. Of course if the list is empty this means that the King is Stalemated or Mated. © Antoine Bruneau - April 2008 |
||||
|
[This page was conceived by Antoine Bruneau - John E Hawkes has contributed to the English presentation of this article - All data is copyrighted by: © Antoine Bruneau & Chess-Theory]
*** FOR PLEASANT SURFING AROUND THIS SITE:
*** FOR DISCOVERING WHO WE ARE:
******** ©-«Chess-Theory.com»-2004-2008 ******** |
 |
«Images taken from the Thinking Machine 4 - 
