Manipulating the pawns
Next we deal with pawns. Sunfish doesn’t do minor promotion, ie pawns are only promoted to queens if they reach row 8 (line 201). If a pawn moves two squares then we keep track of the square behind, in case an en passant capture is possible. If the pawn makes an en passant capture then the appropriate square is obliterated. We return a new Position object, remembering to rotate it to account for the next player’s point of view.
The valuation function value() calculates the relative value of a given move. We start by calculating the difference between the value piece’s positions before and after the move. If the player has captured a piece then that piece’s value at its capture position is added. If castling results in the king being checked, then the value will go sky high (precluding that move). If castling did take place, then the value needs to be adjusted according to the rook’s new position. Finally, we account for pawn promotion and en passant capture.
We’ll give an overview of the search logic section at the end, but it’s worth having a brief look at the user interface section (which starts at line 338). The parse() function converts from a two digit co-ordinate string (such as a4 ) to the relevant list index (61 in this case). The render() function does the opposite. The print_pos() function nicely prints the board, complete with Unicode characters in lieu of actual graphics and labelled axes for the ranks and files.
The final function main() sets up the initial layout and defines the main game loop. Each iteration starts by displaying the board and asking for a move. We use the regular expression ‘([a-h][1-8])'*2 (line 369) to check that the move is of the correct form, ie a pair of co-ordinates. If it is, and that move is legal for the current position (it’s generated by pos.gen_moves() ) then we proceed, otherwise we ask again. Then we reverse the board for the computers turn and use the engine’s search function to find the best move. If this move results in a checkmate, or fails to resolve a checkmate then the game is done, otherwise the move is printed and the board updated.
The code we’ve discussed so far can easily be adapted to a two-player game like we saw in the Gomoku tutorial. However, what is much more interesting is the code that figures out the machine’s next move. Amazingly, the engine itself (ignoring the lengthy pst dictionary and all the code we’ve already covered) occupies less than a hundred lines.
Sunfish is based on the MTD(f) minimax search algorithm introduced in 1994, adapted to use binary trees. MTD uses so-called alpha-beta pruning for evaluating the game tree, so we build up a tree of possible moves and discard any which we can show lead to positions that are provably worse off than others we have evaluated. A technique called iterative deepening is used to temper the depth of the search, so that we don’t go too far down one particular rabbit hole. Calculating a move begins with a call to the search() function. We limit both the depth (line 305) and the breadth (initially using the NODES_SEARCHED variable) of the search to stop things getting out of control. The real magic happens in the bound() function.
The move tree is stored in the ordered dictionary tp , which is indexed by our position string pos and so previously calculated positions can be looked up efficiently. When we come to analysing all possible moves (line 270), we sort the generated positions in reverse order by their value, which ensures copacetic positions get the attention they deserve. We use bound() recursively to construct a game tree from each possible move, adding appropriate moves to tp (line 293). Alas, the end of the page approaches so here is where we sign off.
You’ll find some helpful comments to aid your understanding of the engine code, so why not experiment by tweaking parameters and seeing what breaks? If you want to learn more about the intricacies of programming chess, make sure and check out the Chess Programming wiki ( https://chessprogramming.wikispaces.com), it will prove a valuable resource.