Perft

Ed Gilbert · Post by **Ed Gilbert** » Sat Dec 06, 2008 17:11

Hi Rein,

Rein Halbersma wrote:You can very easily compute the timings for Move Generation and Make/Unmake by comparing the results of bulk and no-bulk counting. The difference between e.g. perft(11,BULK=1) and perft(11,BULK=0) on the initial position is 1665861398 pairs of Make/Unmake calls. Then you need also the timings for ply=10 for both and then you can deduce the timings for a move_generate() call as well.

Aren't you measuring a lot more than make/unmake with those numbers? Here is my perft function without 'bulk counting':

Code: Select all

INT64 Perft(BOARD *board, int color, int depth)
{
	MOVELIST movelist;
	int n_moves, i;
	INT64 nodes;

	if (depth == 0)
		return(1);
 
	n_moves = build_movelist(board, color, &movelist);

	nodes = 0;
	for (i = 0; i < n_moves; ++i)
		nodes += Perft(movelist.board + i, color ^ 1, depth - 1);
 
	return(nodes);
}

In my case, makemove is simply passing the pointer argument "movelist.board + i", and there is no unmake. But at leaf nodes the benchmark actually measures a function call with 3 arguments, and then a test for (depth == 0) in the called function. It seems wrong to equate this time with makemove.

-- Ed

Rein Halbersma · Post by **Rein Halbersma** » Sat Dec 06, 2008 17:33

Ed Gilbert wrote:Hi Rein,
Rein Halbersma wrote:You can very easily compute the timings for Move Generation and Make/Unmake by comparing the results of bulk and no-bulk counting. The difference between e.g. perft(11,BULK=1) and perft(11,BULK=0) on the initial position is 1665861398 pairs of Make/Unmake calls. Then you need also the timings for ply=10 for both and then you can deduce the timings for a move_generate() call as well.
Aren't you measuring a lot more than make/unmake with those numbers? Here is my perft function without 'bulk counting':
Code: Select all
INT64 Perft(BOARD *board, int color, int depth)
{
	MOVELIST movelist;
	int n_moves, i;
	INT64 nodes;

	if (depth == 0)
		return(1);
 
	n_moves = build_movelist(board, color, &movelist);

	nodes = 0;
	for (i = 0; i < n_moves; ++i)
		nodes += Perft(movelist.board + i, color ^ 1, depth - 1);
 
	return(nodes);
}
In my case, makemove is simply passing the pointer argument "movelist.board + i", and there is no unmake. But at leaf nodes the benchmark actually measures a function call with 3 arguments, and then a test for (depth == 0) in the called function. It seems wrong to equate this time with makemove.

-- Ed

Hi Ed,

Yes you are right of course. The best way to measure the make/unmake it to run it a billion times and time it. In any case, I think that doing a perft with bulk-counting can be misleading as well since it ignores the depth=0 nodes altogether.

Rein

BertTuyt · Post by **BertTuyt** » Sat Dec 06, 2008 19:01

I did some tests with Perft where I called the Movegenerator and/or Move Routine 2 times.
The results are summarized in the next table.

Code: Select all

BULK=0    Perft   +MG     +MO     +MG+MO 
Initial   47,92   63,46   60,93   76,30 
Random    26,02   34,90   33,38   42,03 
Woldouby  12,96   17,61   16,04   20,69

+MG means MoveGenerator called 2 times
+MO means Move Function called 2 times

In the next table (based on these results) I have summarized the time spent in Perft , MoveGenerator (MG) and Move Function (MO).

Code: Select all

BULK=0    Perft   MG      MO
Initial   19,37   15,54   13,01 
Random     9,68    8,88    7,46
Woldouby   5,23    4,65    3,08

To be honest, Im a little surprised that the Perft overhead is so big.
Maybe I have "overlooked" something, or my Perft implementation consumes to much time.
Anyway Rein/Ed and others, hope you have a better clue.
Next to that Im interested to learn how my figures compare with other (especially if something is wrong with my perft, MoveGenerator or Move Function).

Bert

Ed Gilbert · Post by **Ed Gilbert** » Sat Dec 06, 2008 19:34

Bert, this is off topic, but I am interested to know how you are progressing with the 7pc db build. I know you stopped it for a while to work on parallel search, but do you have it running again, and how far along is it?

I'm still building the 8pc db. According to today's logfile it is 7.47% complete based on the number of positions that have been resolved and verified.

-- Ed

BertTuyt · Post by **BertTuyt** » Sat Dec 06, 2008 19:41

Ed, I stopped all activities as my work consumes too much time.
During Xmas period I will restart and focus on Parallel Search.

Most likely I will start with the 7p database when I get my new computer ( a Intel 2.93 Ghz , with 12 GByte Memory).

Bert

pascaljunq · Post by **pascaljunq** » Sun Dec 07, 2008 17:52

Hi,

I try my move generator and something is wrong for woldouby position :
perft : 1 Nodes : 6
perft : 2 Nodes : 12
perft : 3 Nodes : 30
perft : 4 Nodes : 73
perft : 5 Nodes : 215
perft : 6 Nodes : 590
perft : 7 Nodes : 1944
perft : 8 Nodes : 6267

for perft8, I obtain 6267 instead of 6269

by ply :
Perft8 25-20 nodes : 2825
Perft8 27-22 nodes : 984
Perft8 28-22 nodes : 1025
Perft8 33-29 nodes : 357
Perft8 34-29 nodes : 786
Perft8 37-31 nodes : 290
perft8 total Nodes : 6267

by capture :
perft 8 Nodes : 6267
cap 0 : 4393
cap 1 : 1029
cap 2 : 660
cap 3 : 121
cap 4 : 45
cap 5 : 11
cap 6 : 8
cap 7 : 0
cap 8 : 0
cap 9 : 0
sum : 6267

Could you provide same stats to help me to fix !

Thx

Ed Gilbert · Post by **Ed Gilbert** » Sun Dec 07, 2008 19:01

Pascaljunq,

It looks like 25-20 has the difference. Here is my output.

Code: Select all

perft -d7 -fB:W20,27,28,30,32,33,34,35,37,38:B12,13,14,16,18,19,21,23,24,26.
perft(1) 2 nodes, 0.00 sec, 2 knodes/sec
perft(2) 12 nodes, 0.00 sec, 12 knodes/sec
perft(3) 34 nodes, 0.00 sec, 34 knodes/sec
perft(4) 100 nodes, 0.00 sec, 100 knodes/sec
perft(5) 301 nodes, 0.00 sec, 301 knodes/sec
perft(6) 955 nodes, 0.00 sec, 955 knodes/sec
perft(7) 2827 nodes, 0.00 sec, 2827 knodes/sec

-- Ed

TAILLE · Post by **TAILLE** » Sun Dec 07, 2008 19:56

Hi Pascaljunk,

Yes the problem seems to come after 25-20.

In order to help you I have the following results
25-20 : 2827
25-20 14x25 : 319
25-20 24x15 : 2508

Gérard

Rein Halbersma · Post by **Rein Halbersma** » Sun Dec 07, 2008 20:54

BertTuyt wrote:I did some tests with Perft where I called the Movegenerator and/or Move Routine 2 times.

In the next table (based on these results) I have summarized the time spent in Perft , MoveGenerator (MG) and Move Function (MO).
Code: Select all
BULK=0    Perft   MG      MO
Initial   19,37   15,54   13,01 
Random     9,68    8,88    7,46
Woldouby   5,23    4,65    3,08
To be honest, Im a little surprised that the Perft overhead is so big.
Maybe I have "overlooked" something, or my Perft implementation consumes to much time.
Anyway Rein/Ed and others, hope you have a better clue.
Next to that Im interested to learn how my figures compare with other (especially if something is wrong with my perft, MoveGenerator or Move Function).

Bert

I have translated your last table to percentages

Code: Select all

Perft   MG      MO
40,4%	32,4%	27,1%
37,6%	34,1%	28,3%
40,4%	35,9%	23,8%

My figures are totally different (run on my own PC, so that's why I measure in percentages since my timings are a factor of 2.5-3 off):

Code: Select all

Perft   MG      MO
20,5%	57,9%	21,6%
15,4%	58,8%	25,8%
16,7%	64,6%	18,8%

Somehow I spent a lot of time in move generation, and very little in function calls and make/undo.

Ed, what is your breakdown?

Rein

Rein Halbersma · Post by **Rein Halbersma** » Sun Dec 07, 2008 21:19

Just to be complete: in the previous post I used my own method (rather than Bert's, Ed's or a hybrid). Here is my perft() code:

Code: Select all

unsigned long long Search::perft(unsigned int ply, unsigned int depth) 
{        
        MoveList move_list = move_table[ply];

        if (depth > BULK_COUNTING) {
                //MoveGenerator::KEEP_STATS = false;
                unsigned int num_moves = move_generator.generate_all_moves(move_list, current_position); 
                unsigned long long nodes = 0ULL;
                current_position.flip_color();
                for (unsigned int i = 0; i < num_moves; ++i) {
                        current_position ^= *move_list;
                        nodes += perft(ply + 1, depth - 1);
                        current_position ^= *move_list++;
                }                               
                current_position.flip_color();
                return nodes;
        } else {
                //MoveGenerator::KEEP_STATS = true;
                return (BULK_COUNTING? move_generator.generate_all_moves(move_list, current_position) : 1);
        }
}

For clarity: Search is a C++ class containing current_position as a member, the ^= is an overloaded operator that performs 3 XOR operations on the 3 struct fields of current_position. The rest should be rather straightforward to read.

Rein

pascaljunq · Post by **pascaljunq** » Sun Dec 07, 2008 21:48

Thank you Ed,

I need your help again !

My output after 25-20 :

perft : 1 Nodes : 2
perft : 2 Nodes : 12
perft : 3 Nodes : 34
perft : 4 Nodes : 100
perft : 5 Nodes : 301
perft : 6 Nodes : 955
perft : 7 Nodes : 2825 (instead of 2827 !)

by ply :
Perft7 14-25 nodes 319
Perft7 24-15 nodes 2506
perft7 sum Nodes 2825

Could you show your output again please ?

Thx

Pascal

TAILLE · Post by **TAILLE** » Sun Dec 07, 2008 22:03

pascaljunq wrote: My output after 25-20 :

perft : 1 Nodes : 2
perft : 2 Nodes : 12
perft : 3 Nodes : 34
perft : 4 Nodes : 100
perft : 5 Nodes : 301
perft : 6 Nodes : 955
perft : 7 Nodes : 2825 (instead of 2827 !)

by ply :
Perft7 14-25 nodes 319
Perft7 24-15 nodes 2506
perft7 sum Nodes 2825

Could you show your output again please ?

Thx

Pascal

Hi Pascal,
The problem is after 25-20 24-15. instead of 2506 I find 2508 so :
25-20 24-15 and now :
28-22 : 850
30-24 : 10
34-29 : 241
37-31 : 15
27-22 : 317
30-25 : 592
33-29 : 483

Gérard

pascaljunq · Post by **pascaljunq** » Sun Dec 07, 2008 22:25

Hi Gerard,

One step again :

after 25-20 24-15 33-29

Perft5 12-17 nodes 159
Perft5 14-20 nodes 113
Perft5 15-20 nodes 119
Perft5 18-22 nodes 25
Perft5 19-24 nodes 34
Perft5 26-31 nodes 31
perft5 sum 481 (instead of 483 !)

Thx for your help !

Je suis à la limite de la crise de nerf !

Pascal

TAILLE · Post by **TAILLE** » Sun Dec 07, 2008 22:47

Hi Pascal,

25-20 24-15 33-29 18-22 : 27 (instead of 25)
and now
27x20 : 18
29x20 : 9

Gérard

pascaljunq · Post by **pascaljunq** » Sun Dec 07, 2008 23:59

Hi gerard

After 25-20 24-15 33-29 18-22 29x20

next is 22x22 with 7 nodes

maybe 22x22 is not allowed then correct are 22x31 and 22x33

do you confirm ?

Sorry if you have spend a lot of time but i am a beginner !

Thx

Pascal