Computer draughts tournament, Culemborg (2012.09.16)

[BertTuyt]

Michel, your perft score is extremely fast ( i assume it is for an 11 ply search).
So far (if my memory is right) Harm was record holder. See below.

The 3 standard positions on my Core2 2.53GHz (E7200), 64-bit code, gcc 4.3.4 on linux:

perft(11) 1665861398 nodes, 45.35 sec, 36731 kN/s, nobulk
perft(9) 1216917193 nodes, 29.75 sec, 40901 kN/s, nobulk
perft(15) 346184885 nodes, 12.09 sec, 28627 kN/s, nobulk

perft(11) 1665861398 nodes, 21.89 sec, 76100 kN/s, bulk
perft(9) 1216917193 nodes, 13.55 sec, 89823 kN/s, bulk
perft(15) 346184885 nodes, 7.01 sec, 49388 kN/s, bulk

So if you are around 140 MN/s , this would imply you are twice as fast as Harm.
Even when you correct for a faster processor and higher speed, this is still remarkable.
Could you share the result (maybe including position 2 and 3, see the perft blog)?
Maybe you could post in the perft section, so we have a new yardstick to focus on...

Bert

[MichelG]

Michel, your perft score is extremely fast ( i assume it is for an 11 ply search).
So far (if my memory is right) Harm was record holder. See below.
So if you are around 140 MN/s , this would imply you are twice as fast as Harm.
Even when you correct for a faster processor and higher speed, this is still remarkable.
Could you share the result (maybe including position 2 and 3, see the perft blog)?
Maybe you could post in the perft section, so we have a new yardstick to focus on...

Bert

I was a bit surprised myself with the result. I am still finishing the implementation, there are some 'missing features' in the king-capture function, and there are still some optimisations to be chosen.

But writing a fast perft is not my goal. I'll try to make it as fast as possibly for alfa-beta search.

Some features of my move generator:
- 3 bitfields (white, black, kings) with gaps (6 or 7 bits for each row)
- produces new boards rather than moves
- seperate white to move and black to move code.
- no global variables eases parallel implementation
- no duplication removal

[Rein Halbersma]

I was a bit surprised myself with the result. I am still finishing the implementation, there are some 'missing features' in the king-capture function, and there are still some optimisations to be chosen.

But writing a fast perft is not my goal. I'll try to make it as fast as possibly for alfa-beta search.

According to http://www.cpubenchmark.net/ the i7-980 is almost exactly twice as fast per core as the Core2 E7200. So not so shocking after all.

Some features of my move generator:
- 3 bitfields (white, black, kings) with gaps (6 or 7 bits for each row)
- produces new boards rather than moves
- seperate white to move and black to move code.
- no global variables eases parallel implementation
- no duplication removal

I have a C++ template on color so after the compiler is done also white / black move instances.

The duplication removal is extremely cheap with bitboards (and you only need to do it if number of captured pieces >= 4 and number of captures so far >= 1, so it rarely happens). If you don't do capture duplication removal, how large is your pre-allocated successor array? As Ed has shown with the 2nd perft position, the number of capture paths can run in the 500s, with an unknown theoretical upper bound, so your program could crash... Or do you dynamically allocate that array?

[MichelG]

According to http://www.cpubenchmark.net/ the i7-980 is almost exactly twice as fast per core as the Core2 E7200. So not so shocking after all.

I have a C++ template on color so after the compiler is done also white / black move instances.

The duplication removal is extremely cheap with bitboards (and you only need to do it if number of captured pieces >= 4 and number of captures so far >= 1, so it rarely happens). If you don't do capture duplication removal, how large is your pre-allocated successor array? As Ed has shown with the 2nd perft position, the number of capture paths can run in the 500s, with an unknown theoretical upper bound, so your program could crash... Or do you dynamically allocate that array?

I think you are right about the i980 being much faster than the e7200. Next wednesday or so i can do a test on a quad core 6600 like you tested.

For now, dragon has about the same timings as bert reported, but on my 2.13 ghz laptop instead of berts 2.5 Ghz machine.

I'll also test with move duplication removal. (500 moves is only 8 KB so that's not a problem [just allocate 1 MB per thread and it is fine], but i agree removing duplicates is better)

[BertTuyt]

Michel, the table shown in my previous post was based on the results of Harm Jetten (who if I remember well had the fastest perft).
My (record) 11-Ply Perft for the initial position on a i7-940 2.93 GHz processor is 22.79 sec.
I assume your perft is then around 11 - 12 seconds?
Right?

Bert

[Piet Bouma]

Table and applets now on Toernooibase. Direct link: http://toernooibase.kndb.nl/opvraag/sta ... 3&afko=&r=

Next year live on Internet?

[Rein Halbersma]

I'll also test with move duplication removal. (500 moves is only 8 KB so that's not a problem [just allocate 1 MB per thread and it is fine], but i agree removing duplicates is better)

"B:W6,K8,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24"

Just for the record: without capture duplication removal, can your program handle this position without crashing?
Hint: with removal it's only 17 moves for black, but without it, the number goes up to 530.
The difference between this position and the 2nd 10x01 draughts perft position, is a white king on square 8.

[MichelG]

"B:W6,K8,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24"

Just for the record: without capture duplication removal, can your program handle this position without crashing?
Hint: with removal it's only 17 moves for black, but without it, the number goes up to 530.
The difference between this position and the 2nd 10x01 draughts perft position, is a white king on square 8.

My old move generator could not. But it has little to do with duplication.

The old code had a table movelist[64 ply][128 moves]
Ofcourse i could increase 128 to 1024, but then you have 1024*64 moves per thread=lots of memory usage.

The new generator puts the moves on a stack, so now i got movelist[4096] (for each thread). The 530 moves will be still be placed on the stack temporarily.

I have added the duplication removal, so after placing the 530 on the stack, it will be condensed to 17 at the finish of movelist(). That means you just need to reserve space for only 513 extra moves on the stack.

Using a stack also has the advantage of keeping the moves at local to the cpu as possible.

You don't have make reservations for 500 moves for each depth; it is extremely unlikely that you can find a position where consecutive moves have that many moves (since it will involve captures that clear large part of the board). That's why you can get away with using a small memory footprint.

[Rein Halbersma]

I have added the duplication removal, so after placing the 530 on the stack, it will be condensed to 17 at the finish of movelist(). That means you just need to reserve space for only 513 extra moves on the stack.

Using a stack also has the advantage of keeping the moves at local to the cpu as possible.

You don't have make reservations for 500 moves for each depth; it is extremely unlikely that you can find a position where consecutive moves have that many moves (since it will involve captures that clear large part of the board). That's why you can get away with using a small memory footprint.

Hi Michel,

My movelist never expands to more than N+1 entries when there are N unique legal moves. After adding a new capture, I check if the last capture was already present in the list generated so far. If so, I remove it immediately. I only do this if the movelist was not empty (because the first capture is by definition unique), and if the number of captured pieces is at least 4 (otherwise you can't capture in a circle). IIRC, this restricts the checking for duplicates to less than 0.1% of all captures (because large captures are very rare).

Rein

[MichelG]

Hi Michel,

My movelist never expands to more than N+1 entries when there are N unique legal moves. After adding a new capture, I check if the last capture was already present in the list generated so far. If so, I remove it immediately. I only do this if the movelist was not empty (because the first capture is by definition unique), and if the number of captured pieces is at least 4 (otherwise you can't capture in a circle). IIRC, this restricts the checking for duplicates to less than 0.1% of all captures (because large captures are very rare).

Rein

I think that is a good technique as well. In my movegen, it would however probably give a very minor performance drop, because it at every capture it would introduce a check to see if there are more than 4 captures. Now i do only 1 such a check.

For now, i am pretty much done with the movegenerator, even though i am sure there can be more improvements.

[BertTuyt]

I also check at the end of every capture, if i need to include the move or not...
See below code:

Code: Select all

		if ( rpts->iklmx < 4 || rpts->ipbx == 1 || !Duplicate_Move64(rpts, rlsp) )
			rpts->NextMove	= rlsp + 1 ;
		else
			--rpts->ipbx ;

rlsp is a pointer to the PLOOK stack, which contains all move structures.
This stack is allocated at the start of the program 4096 entries for every thread.
I never test if the stack grows beyond this limit, maybe a wise idea to test this, especially as my search-depth is extremely growing , and i still face (now and then) some weird search-results.

Bert

[MichelG]

I got a new beta version available on http://mdgsoft.home.xs4all.nl/draughts/beta4.1.html This is almost equal to the version used in the tournament, with some last bugs fixed.

It also includes my new move generator for testing purposes. If you want a direct compare of the movegen speed to your own, you can do the following:
1. Set up a position on the board
2. Open the console by clicking window->console
3. Type 'perftbulk3 11' into the console. (with 11 indicating the maximum plydepth)

Alternatively, you can just start dragon64r.exe from the application directory and type 'pt'. It will then run a perft for 3 positions that have been mentioned in different threads.

[Krzychumag]

I got a new beta version available on http://mdgsoft.home.xs4all.nl/draughts/beta4.1.html This is almost equal to the version used in the tournament, with some last bugs fixed.

It also includes my new move generator for testing purposes. If you want a direct compare of the movegen speed to your own, you can do the following:
1. Set up a position on the board
2. Open the console by clicking window->console
3. Type 'perftbulk3 11' into the console. (with 11 indicating the maximum plydepth)

Alternatively, you can just start dragon64r.exe from the application directory and type 'pt'. It will then run a perft for 3 positions that have been mentioned in different threads.

I thank MichelG.