Chris Pollett >
Students > [Bio] [Del1] [Del2] [Del3] [Del4] |
Extension to PVS algorithm and Autoplay setup1. Extension to PVS algorithmDescription: In GNU chess when the current board position is not found in the game database (Book) then the next move is calculated using the PVS algorithm. My goal was to modify PVS algorithm such that game database is compared at each search depth. As PVS algorithm tries to refine aplha (or beta) by searching several ply along the game tree, it is possible to reach a board position with some future moves which can be found in the game database. That is, two games can reach the same board positions even though they do not have the same sequence of moves. Assume two games:1. a b 2. c d 3. e f 2. c b 2. a d 3. e f At move 3, the board position is same even though the initial sequence of steps is different. Thus their HashKey derived from current board position should be same. My extension to PVS algorithm was to compare current board's HashKey at each search depth during PVS calculation with board HashKeys in the game database. If a matching board position was found then the move leading to that board position was returned and the PV search was terminated. I implemented a special option called '-b' in GNU chess program which ran the program with the above extension. In order to test this extension the chess program was run against a dummy game database that had only one simple game as follows: dumb.pgn----------- 1. e4 Nc6 2. Ke2 d5 3. Ke1 Nf6 4. exd5 Qxd5 5. Ke2 Qe4# {computer wins as black} 0-1 During the actual play if the user makes the following moves: 1.e4 Nc6 2. Ke2 d5 3. exd5
Now computer's next move with the new extension will be: PVS algorithm is run:
Explanation:
Game Database has the following sequence:
Current board could follow the following sequence after computer makes move Qxd5: Thus PVS stopped at Ply 4& and used the PVNode at that point instead of going ahead. Without the extension the PVS code would have searched until Ply7 and in this case would have still returned move Qxd5. Snippet of PVS extension code:
2. Autoplay setupDescription: With Autoplay setup I was able to make chess engines play against each other. This feature is very useful since enhancements made to the GNU chess engine and the original engine can play against each other and their performance can be compared. Autoplay is an open source chess program that connects two xboard or winboard protocol compliant chess engines and lets them play against each other. GNU chess is an xboard compliant chess engine and it could be run in the engine mode using the -x option. The engine displays the information in the Coordinate Notation that uses only the squares that the pieces were on to denote movements. (such as 1.e2e4 e7e6) I was able to modify the Autoplay source code such that it stored all the moves made in a .PGN format which I could later run it on xboard to view the complete game. Autoplay can be started like this: ./autoplay.exe -1 "./White_gnuchess.exe -x" -2 "./Black_gnuchess.exe -x"
Sample Run output:
Mon Nov 27 23:11:09 2006] Starting WHITE engine: How autoplay works: Autoplay creates two new processes for each gnuchess engine.
There are two pipes that are created per process: Figure 1: Autoplay process Autoplay process- Autoplay process does a select(fd1_r, fd2_r) and reads the data on whichever filedescriptor the data has arrived on. Then, it writes the data to the other engine. |