Perft

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Perft

Post by Ed Gilbert » Fri Jul 04, 2008 03:41

Many of the chess programmers use a utility program called Perft which is very useful for testing the correctness and speed of move generators. It walks the move generation tree to a fixed depth and counts all the leaf nodes. I created one of these for 10x10 draughts to allow comparisons with someone who is creating a new draughts engine. Does anyone else have such a utility program for draughts? It is extremely simple to create if you have a working move generator. I used the source code from this web page almost unmodified and linked it in with the move generator from Kingsrow. http://chessprogramming.wikispaces.com/perft If anyone has a perft or is interested to build one, we can do some node count comparisons.

-- Ed

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sat Jul 05, 2008 15:05

Ed, I will implement this tomorrow (= Sunday).
Maybe you can already post your results here, nodecount en timing, I will do the same tomorrow.

Bert

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sat Jul 05, 2008 15:16

Forgot to mention, lets start with the initial board position, white to move, thats an easy start.

Bert

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Perft

Post by TAILLE » Sat Jul 05, 2008 17:22

Ed Gilbert wrote:Many of the chess programmers use a utility program called Perft which is very useful for testing the correctness and speed of move generators. It walks the move generation tree to a fixed depth and counts all the leaf nodes. I created one of these for 10x10 draughts to allow comparisons with someone who is creating a new draughts engine. Does anyone else have such a utility program for draughts? It is extremely simple to create if you have a working move generator. I used the source code from this web page almost unmodified and linked it in with the move generator from Kingsrow. http://chessprogramming.wikispaces.com/perft If anyone has a perft or is interested to build one, we can do some node count comparisons.

-- Ed
Hi Ed,
I do not have such algorithm but it is of course quite easy to program. Stricly speaking it is obviously better to have a fast generator but I am not sure that even a 2 factor will change significantly the strength of a program. It seems to me that the time taken at the nodes of the explored tree is far less important compared to the time taken at the leaves of this tree.
As a consequence it would be more interesting to test up to n levels of the tree and to continue the generation until a stable (no capture) position is reached.
That way you evaluate at least one program on each leaf : the program which looks at a capture.
The second important program is the position evaluation but here the situation is far more complicated because it is often more interesting to loose some time in order to build a more accurate evaluation.
Gérard

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Sat Jul 05, 2008 20:53

This is what I get for the start position:

perft(1) 9 nodes, 0.00 sec, 9 knodes/sec
perft(2) 81 nodes, 0.00 sec, 81 knodes/sec
perft(3) 658 nodes, 0.00 sec, 658 knodes/sec
perft(4) 4265 nodes, 0.00 sec, 4265 knodes/sec
perft(5) 27117 nodes, 0.00 sec, 27117 knodes/sec
perft(6) 167140 nodes, 0.00 sec, 167140 knodes/sec
perft(7) 1049442 nodes, 0.03 sec, 32795 knodes/sec
perft(8) 6483961 nodes, 0.22 sec, 29473 knodes/sec
perft(9) 41022423 nodes, 1.30 sec, 31629 knodes/sec
perft(10) 258895763 nodes, 8.33 sec, 31080 knodes/sec
perft(11) 1665861398 nodes, 55.86 sec, 29822 knodes/sec

Gerard, I agree with you that the speed of the move generator is not very important. IMO the primary benefit of this little tool is to check the correctness of the move generator. If you get the same node count for perft(11) that I do, then that is a nice quick check of 1.6 billion positions, a good confirmation that our move generators agree. Later I will post some results for other positions, some involving kings.

The Kingsrow move generator does not use 'ghost squares' or rotated bitboards, so it is probably slower than what most of the draughts programs are using because it has to generate moves from the even and odd rows separately.

It is also interesting to note what is probably a small bug in the perft source code at the link I gave. It does not count a leaf node if there are no legal moves at a position (the side has lost) and the target depth has not been reached. However I did not try to fix this, for the purpose of this program it does not matter and it is much more important that everyone uses the same algorithm, so we can just point to the web page and say that's the standard measurement that we are making.

-- Ed

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE » Sat Jul 05, 2008 22:32

For the time being my PC is reformating all my endgame database and it is not available for this perft function.
I will be able to run such test in a few days.
What configuration did you use for your test : processor ? multicore ? Ghz ?

Ed, during my reformating process I was able to verify all the remaining counters (win, draw, loss up to 7 pieces) and I did not find any discrepancy with your figures. Very good news, isn't it ?
Doesn't it prove that our moves generator are correct ?
Gérard

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Sun Jul 06, 2008 09:53

Gerard, yes that is good to hear that you have finished confirming all the WLD counts. That probably is a good verification of our move generators also, although it only tests for positions with a maximum of 5 pieces on one side. It is probably possible to have a bug that does not show up until more than 5 pieces are present on a side. I also recently made a small change to the move generator code to remove some redundant captures, as the older code would sometimes list a capture move more than once if the sequence of squares jumped was in a different order but the result boards ended up the same. The older code removed redundant captures only when there were more than 32 capture moves in the move list, because I thought it was slightly more efficient to not check for these redundant moves in those cases. Actually the main reason I made the change is to make it easier to compare the Perft output with someone else's results.

I obtained the perft output on an Intel Q6600 which IIRC is 2.4GHz. It is a quad core although that is not relevant because perft is not multi-threaded.

-- Ed

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Sun Jul 06, 2008 10:33

Here is some more perft output:

perft -d9 -f B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
perft(1) 14 nodes, 0.00 sec, 14 knodes/sec
perft(2) 55 nodes, 0.00 sec, 55 knodes/sec
perft(3) 1168 nodes, 0.00 sec, 1168 knodes/sec
perft(4) 5432 nodes, 0.00 sec, 5432 knodes/sec
perft(5) 87195 nodes, 0.00 sec, 87195 knodes/sec
perft(6) 629010 nodes, 0.03 sec, 19657 knodes/sec
perft(7) 9041010 nodes, 0.31 sec, 28885 knodes/sec
perft(8) 86724219 nodes, 2.69 sec, 32251 knodes/sec
perft(9) 1216917193 nodes, 30.27 sec, 40207 knodes/sec


perft -d15 -f W:W25,27,28,30,32,33,34,35,37,38:B12,13,14,16,18,19,21,23,24,26.
perft(1) 6 nodes, 0.00 sec, 6 knodes/sec
perft(2) 12 nodes, 0.00 sec, 12 knodes/sec
perft(3) 30 nodes, 0.00 sec, 30 knodes/sec
perft(4) 73 nodes, 0.00 sec, 73 knodes/sec
perft(5) 215 nodes, 0.00 sec, 215 knodes/sec
perft(6) 590 nodes, 0.00 sec, 590 knodes/sec
perft(7) 1944 nodes, 0.00 sec, 1944 knodes/sec
perft(8) 6269 nodes, 0.00 sec, 6269 knodes/sec
perft(9) 22369 nodes, 0.00 sec, 22369 knodes/sec
perft(10) 88050 nodes, 0.02 sec, 5503 knodes/sec
perft(11) 377436 nodes, 0.02 sec, 22202 knodes/sec
perft(12) 1910989 nodes, 0.08 sec, 24190 knodes/sec
perft(13) 9872645 nodes, 0.42 sec, 23340 knodes/sec
perft(14) 58360286 nodes, 2.33 sec, 25058 knodes/sec
perft(15) 346184885 nodes, 17.19 sec, 20140 knodes/sec

The first position is something that I logged once during a random position test. It had 530 entries in a move list before removing redundant captures. All but 14 were redundant.

The second position is from a Woldouby game.

I seem to get a lot of timing variation between successive runs of perft. In Windows Task Manager I can see that the cpu utilization varies between 27% and about 17%. Maybe I need to set the affinity of the perft program to one particular core to make it more consistent.

-- Ed

BertTuyt
Posts: 1573
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sun Jul 06, 2008 22:36

Herewith my results, you see that from depth 8 onwards the nodes-count is different.
I guess the reason is due to my movegenerator does not check for duplicate moves (same from and to, but different sequence of killed opponent pieces).
I assume that this duplicate moves are only possible when the number of killed pieces is greater equal 4.
Anyway, will dig into this within one week, when my holiday starts.

Perft(1) N = 9 0.00 sec. KN/sec = 0
Perft(2) N = 81 0.00 sec. KN/sec = 0
Perft(3) N = 658 0.00 sec. KN/sec = 0
Perft(4) N = 4265 0.00 sec. KN/sec = 0
Perft(5) N = 27117 0.00 sec. KN/sec = 0
Perft(6) N = 167140 0.01 sec. KN/sec = 11142
Perft(7) N = 1049442 0.06 sec. KN/sec = 16657
Perft(8) N = 6483971 0.31 sec. KN/sec = 20781
Perft(9) N = 41022614 1.78 sec. KN/sec = 23072
Perft(10) N = 258935682 11.25 sec. KN/sec = 23020
Perft(11) N = 1666207133 69.86 sec. KN/sec = 23852

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE » Sun Jul 06, 2008 23:20

Hi Ed.
OK for all node counters for the perft function beginning with the intial position.
Ed Gilbert wrote: B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
perft(1) 14 nodes, 0.00 sec, 14 knodes/sec
perft(2) 55 nodes, 0.00 sec, 55 knodes/sec
...
Here my figure for perft(2) is 184 nodes and the following ones are of course also different.
Ed Gilbert wrote: W:W25,27,28,30,32,33,34,35,37,38:B12,13,14,16,18,19,21,23,24,26.
perft(1) 6 nodes, 0.00 sec, 6 knodes/sec
perft(2) 12 nodes, 0.00 sec, 12 knodes/sec
perft(3) 30 nodes, 0.00 sec, 30 knodes/sec
perft(4) 73 nodes, 0.00 sec, 73 knodes/sec
perft(5) 215 nodes, 0.00 sec, 215 knodes/sec
perft(6) 590 nodes, 0.00 sec, 590 knodes/sec
perft(7) 1944 nodes, 0.00 sec, 1944 knodes/sec
perft(8) 6269 nodes, 0.00 sec, 6269 knodes/sec
perft(9) 22369 nodes, 0.00 sec, 22369 knodes/sec
perft(10) 88050 nodes, 0.02 sec, 5503 knodes/sec
perft(11) 377436 nodes, 0.02 sec, 22202 knodes/sec
perft(12) 1910989 nodes, 0.08 sec, 24190 knodes/sec
perft(13) 9872645 nodes, 0.42 sec, 23340 knodes/sec
perft(14) 58360286 nodes, 2.33 sec, 25058 knodes/sec
perft(15) 346184885 nodes, 17.19 sec, 20140 knodes/sec
OK for all node counters

By the way the number of knodes/sec generated by Damy is very poor. Something like 10000 knodes/sec. In a certain sense it is a very good news for me because I know I will be able to improve this part of the program ! For the moment it is not my first priority. I have to consolidate the handling of the 7 pieces database, I have to improve by MTD best algorithm and also I have to build a new multiprocessor version.

Gérard

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Mon Jul 07, 2008 00:51

Hi Gerard,
TAILLE wrote:Here my figure for perft(2) is 184 nodes and the following ones are of course also different.
It seems one of us has a bug, unless your move generator does not remove some duplicate moves? Here is a printout of the depth 2 tree. What additional moves do you have?

perft -d2 -p -f B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
depth 1: B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
depth 0: W:W6,37,46:BK17,K29.
depth 0: W:W6,37,46:BK17,K24.
depth 0: W:W6,37,46:BK17,K34.
depth 0: W:W6,37,46:BK17,K40.
depth 0: W:W6,37,46:BK17,K45.
depth 0: W:W6,37,46:BK17,K35.
depth 0: W:W6,37,46:BK13,K17.
depth 0: W:W6,37,46:BK17,K18.
depth 0: W:W6,37,46:BK7,K17.
depth 0: W:W6,37,46:BK2,K17.
depth 0: W:W6,37,46:BK12,K17.
depth 0: W:W6,37,46:BK1,K17.
depth 0: W:W6,37,46:BK17,K19.
depth 0: W:W6,37,46:BK8,K17.
perft(1) 14 nodes, 0.00 sec, 14 knodes/sec
depth 2: B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
depth 1: W:W6,37,46:BK17,K29.
depth 0: B:WK1,37,46:BK17,K29.
depth 0: B:W6,32,46:BK17,K29.
depth 0: B:W6,37,41:BK17,K29.
depth 0: B:W6,31,46:BK17,K29.
depth 1: W:W6,37,46:BK17,K24.
depth 0: B:WK1,37,46:BK17,K24.
depth 0: B:W6,32,46:BK17,K24.
depth 0: B:W6,37,41:BK17,K24.
depth 0: B:W6,31,46:BK17,K24.
depth 1: W:W6,37,46:BK17,K34.
depth 0: B:WK1,37,46:BK17,K34.
depth 0: B:W6,32,46:BK17,K34.
depth 0: B:W6,37,41:BK17,K34.
depth 0: B:W6,31,46:BK17,K34.
depth 1: W:W6,37,46:BK17,K40.
depth 0: B:WK1,37,46:BK17,K40.
depth 0: B:W6,32,46:BK17,K40.
depth 0: B:W6,37,41:BK17,K40.
depth 0: B:W6,31,46:BK17,K40.
depth 1: W:W6,37,46:BK17,K45.
depth 0: B:WK1,37,46:BK17,K45.
depth 0: B:W6,32,46:BK17,K45.
depth 0: B:W6,37,41:BK17,K45.
depth 0: B:W6,31,46:BK17,K45.
depth 1: W:W6,37,46:BK17,K35.
depth 0: B:WK1,37,46:BK17,K35.
depth 0: B:W6,32,46:BK17,K35.
depth 0: B:W6,37,41:BK17,K35.
depth 0: B:W6,31,46:BK17,K35.
depth 1: W:W6,37,46:BK13,K17.
depth 0: B:WK1,37,46:BK13,K17.
depth 0: B:W6,32,46:BK13,K17.
depth 0: B:W6,37,41:BK13,K17.
depth 0: B:W6,31,46:BK13,K17.
depth 1: W:W6,37,46:BK17,K18.
depth 0: B:WK1,37,46:BK17,K18.
depth 0: B:W6,32,46:BK17,K18.
depth 0: B:W6,37,41:BK17,K18.
depth 0: B:W6,31,46:BK17,K18.
depth 1: W:W6,37,46:BK7,K17.
depth 0: B:WK1,37,46:BK7,K17.
depth 0: B:W6,32,46:BK7,K17.
depth 0: B:W6,37,41:BK7,K17.
depth 0: B:W6,31,46:BK7,K17.
depth 1: W:W6,37,46:BK2,K17.
depth 0: B:WK1,37,46:BK2,K17.
depth 0: B:W6,32,46:BK2,K17.
depth 0: B:W6,37,41:BK2,K17.
depth 0: B:W6,31,46:BK2,K17.
depth 1: W:W6,37,46:BK12,K17.
depth 0: B:WK1,37,46:BK12,K17.
depth 0: B:W6,32,46:BK12,K17.
depth 0: B:W6,37,41:BK12,K17.
depth 0: B:W6,31,46:BK12,K17.
depth 1: W:W6,37,46:BK1,K17.
depth 0: B:W6,32,46:BK1,K17.
depth 0: B:W6,37,41:BK1,K17.
depth 0: B:W6,31,46:BK1,K17.
depth 1: W:W6,37,46:BK17,K19.
depth 0: B:WK1,37,46:BK17,K19.
depth 0: B:W6,32,46:BK17,K19.
depth 0: B:W6,37,41:BK17,K19.
depth 0: B:W6,31,46:BK17,K19.
depth 1: W:W6,37,46:BK8,K17.
depth 0: B:WK1,37,46:BK8,K17.
depth 0: B:W6,32,46:BK8,K17.
depth 0: B:W6,37,41:BK8,K17.
depth 0: B:W6,31,46:BK8,K17.
perft(2) 55 nodes, 0.03 sec, 2 knodes/sec

-- Ed

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Mon Jul 07, 2008 14:12

Gerard,

As a quick test, you might want to check these 2 positions:

B:W7,K8,K21,K44:BK2.
B:W33,34,K43,44:B29.

Kingsrow gives the number of moves as 1 in each. If your move generator gives 2 for either of these, that would explain the difference.

-- Ed

User avatar
FeikeBoomstra
Posts: 306
Joined: Mon Dec 19, 2005 16:48
Location: Emmen

Post by FeikeBoomstra » Mon Jul 07, 2008 16:32

perft( 1) 9 nodes in 0.00sec
perft( 2) 81 nodes in 0.00sec
perft( 3) 658 nodes in 0.00sec
perft( 4) 4265 nodes in 0.00sec
perft( 5) 27117 nodes in 0.00sec
perft( 6) 167140 nodes in 0.02sec
perft( 7) 1049442 nodes in 0.09sec
perft( 8) 6483961 nodes in 0.52sec
perft( 9) 41022423 nodes in 3.25sec
perft(10) 258895763 nodes in 20.43sec
perft(11) 1665861398 nodes in 130.09sec

I get the numbers like Ed. But it goes slower. My move generator consists of two parts: the actual move generator and a routine that populates the board. So populate is not called in case of a cut-off. Populate also calculates the hashvalue of the board.
I am running linux 64 bits on a single processor with 2.1Ghz.

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE » Mon Jul 07, 2008 16:33

Hi Ed,
Ed Gilbert wrote: B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24.
No worry Ed. It is only a misunderstanding of the initial position. I used to list first the men and then the kings. So, I calculated the perft function on the following position :
B:W6,9,10,11,20,21,22,23,30,K31,K33,K37,K41,K42,K43,K44,K46:BK17,K24.
With the good initial position I did not find any discrepancy with your node figures.
Gérard

Ed Gilbert
Posts: 854
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert » Mon Jul 07, 2008 17:26

Hi Bert,
BertTuyt wrote:I assume that this duplicate moves are only possible when the number of killed pieces is greater equal 4.
Yes, and since moves with at least 4 pieces captured are relatively infrequent, it has negligible affect on speed to avoid listing these. If you do store them then your move tables have to be large enough to hold something like 700 - 800 worst case moves. With no redundant moves I think the worst case is less than 128.

-- Ed

Post Reply