Perft

BertTuyt · Post by **BertTuyt** » Sun Jul 13, 2008 11:22

Ed,

I also did the other 2 positions this morning (Sunday).
Same nodes count.
For the second position you gave time was 52.18 sec (again with little variation) and the third one 18.49 sec.
Remarkably is that although my results are structural slower (we use the same 2.4Ghz Quad-processor), there are significant differences between the 3 examples.

In the first example Damage is at 80% of your speed ( 55.86 sec compared with 69.50 sec), for the other 2 the numbers are 58% ( 30.27 sec compared with 52.18 sec) and 93% ( 17.19 sec compared with 18.49 sec).

I might do some additional book-keeping when i do moves and removes (example update tempo, man-count, material value, hash-value), but it seems that my king-routine is less efficient. Thats the only explanation i can give so far.
Any clues are welcomed.

Im now enjoying holiday, so will finish the new search-routine, and the parallel implementation, so we might do a match in the next weeks.

Bert

BertTuyt · Post by **BertTuyt** » Sun Jul 13, 2008 11:29

Gerard,

I agree with your result regarding the "Rein position", also I got a 3 possibilities with Damage. I did not try it do find it myself, im just a human.

Bert

Ed Gilbert · Post by **Ed Gilbert** » Mon Jul 14, 2008 01:17

I get 12 different moves from Rein's last test position.

perft -d1 -p -f W:WK1:B9,10,11,12,13,20,21,22,23,24,31,32,33,34,41,42,43,44.
depth 1: W:WK1:B9,10,11,12,13,20,21,22,23,24,31,32,33,34,41,42,43,44.
depth 0: B:WK5:B9,20,43,44.
depth 0: B:WK5:B9,24,43,44.
depth 0: B:WK3:B10,24,43,44.
depth 0: B:WK25:B9,10,43,44.
depth 0: B:WK3:B10,20,43,44.
depth 0: B:WK40:B9,10,20,23.
depth 0: B:WK45:B9,10,20,23.
depth 0: B:WK18:B9,10,20,34.
depth 0: B:WK28:B9,10,20,24.
depth 0: B:WK5:B9,20,23,24.
depth 0: B:WK30:B9,10,20,23.
depth 0: B:WK35:B9,10,20,23.
perft(1) 12 nodes, 0.00 sec, 12 knodes/sec

What am I missing?

-- Ed

Rein Halbersma · Post by **Rein Halbersma** » Mon Jul 14, 2008 07:50

Ed Gilbert wrote:I get 12 different moves from Rein's last test position.

perft -d1 -p -f W:WK1:B9,10,11,12,13,20,21,22,23,24,31,32,33,34,41,42,43,44.
What am I missing?

-- Ed

The position you give is not mine but Gerard's position! Nobody gave a node count for that so far. Do you get 3 moves for the one I gave?

Ed Gilbert · Post by **Ed Gilbert** » Mon Jul 14, 2008 14:31

Thank you Rein for spotting my error. On your test position I do get 3 moves.

-- Ed

TAILLE · Post by **TAILLE** » Tue Jul 15, 2008 10:48

Rein Halbersma wrote:
Ed Gilbert wrote:I get 12 different moves from Rein's last test position.

perft -d1 -p -f W:WK1:B9,10,11,12,13,20,21,22,23,24,31,32,33,34,41,42,43,44.
What am I missing?

-- Ed
The position you give is not mine but Gerard's position! Nobody gave a node count for that so far. Do you get 3 moves for the one I gave?

Yes Ed, I (sorry Damy) found also 12 moves for the position I proposed
Gérard

FeikeBoomstra · Post by **FeikeBoomstra** » Tue Jul 15, 2008 14:22

I like to come back on the timing. What exactly did you guys measure?

1) Did you populate the leaf-nodes, or did you stop after you calculated the number of moves for that level?

2) Did you just timed the move-generation at level n, or was the timer also running at levels less than n?

Ed Gilbert · Post by **Ed Gilbert** » Tue Jul 15, 2008 17:34

Hi Feike,

I simply copied the C code for Perft from this link: http://chessprogramming.wikispaces.com/perft and substituted my move generator function. I did not use any of the speedup tricks mentioned at the link, like bulk counting or hashing. In main() I called perft() inside an iterative deepening for loop.

Code: Select all

for (i = 1; i <= depth; ++i) {
    t0 = clock();
    nodes = Perft(&board, color, i);
    printf("perft(%d) %I64d nodes, %.2f sec, %.0f knodes/sec\n",
           i, nodes, TDIFF(t0), (double)nodes / (1000.0 * TDIFF(t0)));
}

-- Ed

BertTuyt · Post by **BertTuyt** » Wed Jul 16, 2008 12:33

Also Damage found only 12 moves in the position Gerard posted.
Seems that our movegenerators with the addition of redundant move removal seem to work.

Ed and I have posted times for all the 3 positions mentioned in this topic, could the others do the same (with the mentioning of hardware used).

Bert

FeikeBoomstra · Post by **FeikeBoomstra** » Wed Jul 16, 2008 13:32

perft( 1) 14 nodes in 0 sec,
perft( 2) 55 nodes in 0 sec,
perft( 3) 1168 nodes in 0 sec,
perft( 4) 5432 nodes in 0 sec,
perft( 5) 87195 nodes in 0.01 sec,
perft( 6) 629010 nodes in 0.05 sec,
perft( 7) 9041010 nodes in 0.55 sec,
perft( 8) 86724219 nodes in 5.36 sec,
perft( 9) 1216917193 nodes in 74.07 sec,

Ed Gilbert · Post by **Ed Gilbert** » Wed Jul 16, 2008 13:47

Feike, what is new with BoomstraDam? Have you made any progress with the parallel search? Any other interesting improvements? After the last tournament in France, Jaap Bus wrote that he thought several of the programs were getting stronger.

-- Ed

FeikeBoomstra · Post by **FeikeBoomstra** » Wed Jul 16, 2008 13:51

perft( 1) 6 nodes in 0 sec,
perft( 2) 12 nodes in 0 sec,
perft( 3) 30 nodes in 0 sec,
perft( 4) 73 nodes in 0 sec,
perft( 5) 215 nodes in 0 sec,
perft( 6) 590 nodes in 0 sec,
perft( 7) 1944 nodes in 0 sec,
perft( 8) 6269 nodes in 0 sec,
perft( 9) 22369 nodes in 0.01 sec,
perft(10) 88050 nodes in 0.01 sec,
perft(11) 377436 nodes in 0.05 sec,
perft(12) 1910989 nodes in 0.23 sec,
perft(13) 9872744 nodes in 1.08 sec,
perft(14) 58361333 nodes in 5.94 sec,
perft(15) 346200814 nodes in 34.75 sec,

Intel Pentium D at 2.4 Ghz (using one core) running Linux 64 bits
C-program compiled with Intel's C+compiler -O3

FeikeBoomstra · Post by **FeikeBoomstra** » Wed Jul 16, 2008 14:15

Hi Ed,

no, the basic thing was that I found two fundamental problems in the way I handled "useless sacrifice", so the program is more robust now.

My current view was that I could make the most progress to improve the playing strentgh in improving my evaluation function, so I started a project to go over a big number of positions and find the postions where the static evaluation of the position differs substantially from the best position evaluated at say 6 or 8 levels deeper.

But now I look at my figures for move generation, I see I am 2 times slower than you and Bert. Upto now I can't find where I am wasting my time.

TAILLE · Post by **TAILLE** » Wed Jul 16, 2008 14:44

Hi,
I tried to buid the ranking of the program for the perft(11) function on the initial position. The result seems the following
1 665 861 398 nodes generated with only one core.
1) Kingsrow = 56" with an Intel Q6600 2,4 GHz
2) Damage = 70" with an Intel Q6600 2,4 GHz
3) Damy = 83" with an Intel core 2 duo 2,0 GHz
4) Boomstradam = 130"with xxx 2,1GHz

As far as I am concerned I am not very satisfied with the code generated by the compiler. The optimisation is not satisfactory. For your information I used Visual Studio Standard Edition 2008. What is your developpement environment ?

Gérard

TAILLE · Post by **TAILLE** » Wed Jul 16, 2008 15:13

TAILLE wrote:Hi,
I tried to buid the ranking of the program for the perft(11) function on the initial position. The result seems the following
1 665 861 398 nodes generated with only one core.
1) Kingsrow = 56" with an Intel Q6600 2,4 GHz
2) Damage = 70" with an Intel Q6600 2,4 GHz
3) Damy = 83" with an Intel core 2 duo 2,0 GHz
4) Boomstradam = 130"with xxx 2,1GHz

As far as I am concerned I am not very satisfied with the code generated by the compiler. The optimisation is not satisfactory. For your information I used Visual Studio Standard Edition 2008. What is your developpement environment ?

Gérard

I have just removed from the code some statistical functions. Instead of 83" I obtain now 74". I can look now for a better optimisation but I guess I will not get a significant gain.
Gérard