Chris Pollett > Students >
Basani

    ( Print View )

    [Bio]

    [Project Blog]

    [CS297Proposal]

    [Clustering-PPT]

    [Del1]

    [Del2]

    [Del3]

    [Del4]

    [CS297Report-PDF]

    [CS298Proposal-PDF]

    [CS298Presentation-PDF]

    [CS298Report-PDF]

    [Project Code-TAR GZ]

                          

























Extension to PVS algorithm and Autoplay setup

1. Extension to PVS algorithm

Description: 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:
Next move lookup from game database fails because current board position does not exists in the game database.

PVS algorithm is run:

PVS sample run

Explanation:
On Ply 4& above, PVS generates "Qxd5 Ke1 Nf6 Nc3". After Nf6 move, the board position is same as

Qxd5 Ke1 Nf6 (HashKey Match found) Nc3

Game Database has the following sequence:
1. e4 Nc6 2. Ke2 d5 3. Ke1 Nf6 4. exd5 Qxd5

Current board could follow the following sequence after computer makes move Qxd5:
1. e4 Nc6 2. Ke2 d5 3. exd5 Qxd5 4. Ke1 Nf6

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:

PVS code snippet

2. Autoplay setup

Description: 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:
Mon Nov 27 23:11:09 2006] Starting ./White_gnuchess.exe -x...
Mon Nov 27 23:11:09 2006] Starting BLACK engine:
Mon Nov 27 23:11:09 2006] Starting ./Black_gnuchess.exe -x...
Mon Nov 27 23:11:09 2006] init engine black
Mon Nov 27 23:11:09 2006] init engine white
Mon Nov 27 23:11:09 2006] Starting clocks!
Mon Nov 27 23:11:14 2006] WHITE moves 1. e2e4 (gnuchess)
Mon Nov 27 23:11:14 2006] white used: 5.279000s, black used: 0.000000s
Mon Nov 27 23:11:19 2006] BLACK moves 1. ... d7d5 (gnuchess)
Mon Nov 27 23:11:19 2006] white used: 5.279000s, black used: 5.013000s
Mon Nov 27 23:11:24 2006] WHITE moves 2. e4d5 (gnuchess)
Mon Nov 27 23:11:24 2006] white used: 10.285000s, black used: 5.013000s
Mon Nov 27 23:11:29 2006] BLACK moves 2. ... d8d5 (gnuchess)
Mon Nov 27 23:11:29 2006] white used: 10.285000s, black used: 10.015000s
Mon Nov 27 23:11:34 2006] WHITE moves 3. b1c3 (gnuchess)
Mon Nov 27 23:11:34 2006] white used: 15.295000s, black used: 10.015000s
Mon Nov 27 23:11:39 2006] BLACK moves 3. ... d5f5 (gnuchess)
Mon Nov 27 23:11:39 2006] white used: 15.295000s, black used: 15.028000s

How autoplay works:

Autoplay creates two new processes for each gnuchess engine.
It does a fork/exec for White_gnuchess.exe and then fork/exec for Black_gnuchess.exe.

There are two pipes that are created per process:
White_gnuchess.exe: fd1_r and fd1_w
Black_gnuchess.exe: fd2_r and fd2_w

Figure 1: Autoplay process autoplay

Autoplay process-
Reads from fd1_r (reads a move from white chess engine)
Writes to fd2_w (writes the move to black chess engine)

Reads from fd2_r (reads a move from black chess engine)
Writes to fd1_w (writes the move to white chess engine)

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.