World Draughts Forum

It is currently Mon Jun 26, 2017 13:17

All times are UTC+01:00




Post new topic  Reply to topic  [ 19 posts ]  Go to page 1 2 Next
Author Message
PostPosted: Fri May 20, 2011 04:31 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 69
Location: Mountain View
Inspired by some discussion on the talkchess forum, I computed the perft number of 8x8 checkers for depth 24 with the same distributed implementation I used earlier to compute depths 1 to 23. Below you see the perft breakdown per move (called "divide") from the initial position for depths 22 to 24.

Code:
move         divide(22)       divide(23)        divide(24)
----------------------------------------------------------
12-16:  243598269855110 1123463594881857  5192042148594780
11-16:  246743868125768 1131373985922218  5248615918291379
11-15:  209016678583301  984253557821317  4602138522979438
10-15:  215412869777867 1000606302770349  4643700995955222
10-14:  184865466345796  856779998157523  3988937724259353
 9-14:   213736468971938 1003310451936358  4712325943133747
 9-13:   288999100078322 1337748969176591  6263620622082081
----------------------------------------------------------
       1602372721738102 7437536860666213 34651381875296000


Top
   
PostPosted: Fri May 20, 2011 07:20 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1487
AartBik wrote:
Inspired by some discussion on the talkchess forum, I computed the perft number of 8x8 checkers for depth 24 with the same distributed implementation I used earlier to compute depths 1 to 23. Below you see the perft breakdown per move (called "divide") from the initial position for depths 22 to 24.

Code:
move         divide(22)       divide(23)        divide(24)
----------------------------------------------------------
12-16:  243598269855110 1123463594881857  5192042148594780
11-16:  246743868125768 1131373985922218  5248615918291379
11-15:  209016678583301  984253557821317  4602138522979438
10-15:  215412869777867 1000606302770349  4643700995955222
10-14:  184865466345796  856779998157523  3988937724259353
 9-14:   213736468971938 1003310451936358  4712325943133747
 9-13:   288999100078322 1337748969176591  6263620622082081
----------------------------------------------------------
       1602372721738102 7437536860666213 34651381875296000


Congratulations!

When I was computing perft(22), I wanted to surprise you before you would have bettered your own record. Someone who I had confided in wrote me: "You definitely dont want to get into a perft one-upsmanship with Aart. His company has more computing resources than the governments of most countries!" I guess the next time someone like me or Murray Cash (the one on the talkchess forum who had already confirmed perft(23))wants to improve your perft numbers, this will have to be done in absolute secrecy. ;-)

BTW, did the total runtime for this computation still qualify as a "test run"? Are you allowed to give us any additional stats at all?


Top
   
PostPosted: Fri May 20, 2011 18:10 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 69
Location: Mountain View
Rein Halbersma wrote:
I guess the next time someone like me or Murray Cash (the one on the talkchess forum who had already confirmed perft(23))wants to improve your perft numbers, this will have to be done in absolute secrecy. ;-)


Thanks Rein. I hope I did not spoil anyone's fun. I was just trying to have some fun myself :-)


Top
   
PostPosted: Mon Sep 10, 2012 21:53 
Offline

Joined: Mon Sep 10, 2012 21:48
Posts: 10
Real name: Murray Cash
Hello Aart, I can finally verify perft(24) = 34651381875296000. Although I don't have breakdown figures (I have only just added that feature).
It took 4d 10:08:37 on my laptop to compute. Next: perft(25)!

Murray


Top
   
PostPosted: Tue Sep 11, 2012 07:02 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1487
murraycash wrote:
Hello Aart, I can finally verify perft(24) = 34651381875296000. Although I don't have breakdown figures (I have only just added that feature).
It took 4d 10:08:37 on my laptop to compute. Next: perft(25)!

Murray


Congratulations, Murray. You must have upgraded your hardware because the previous perft(23) also took you 4 days, IIRC. Can you give us some details on your hardware / algorithm (hash? parallelism?) BTW, unless your perft(25) computation is nearly finished, it is generally not a good idea to announce your ambitions to Aart! Best is to present him with the counts to verify ;-)


Top
   
PostPosted: Tue Sep 11, 2012 16:01 
Offline

Joined: Mon Sep 10, 2012 21:48
Posts: 10
Real name: Murray Cash
Quote:
Congratulations, Murray. You must have upgraded your hardware because the previous perft(23) also took you 4 days, IIRC. Can you give us some details on your hardware / algorithm (hash? parallelism?) BTW, unless your perft(25) computation is nearly finished, it is generally not a good idea to announce your ambitions to Aart! Best is to present him with the counts to verify

Hi Rein, Hardware is HP EliteBook with Intel i7-M620 @ 2.67 Ghz. 4 cores, all used.
Algorithm is a parallel move generator with "lock-less" hash table of 4GB, described by Robert Hyatt and Tim Mann, see http://chessprogramming.wikispaces.com/Shared+Hash+Table

You are right, I am only motivated to do the next perft if I can complete it in 4 days!


Top
   
PostPosted: Tue Sep 11, 2012 18:25 
Offline

Joined: Wed Mar 11, 2009 01:30
Posts: 69
Location: Mountain View
murraycash wrote:
Hello Aart, I can finally verify perft(24) = 34651381875296000. Although I don't have breakdown figures (I have only just added that feature).
It took 4d 10:08:37 on my laptop to compute. Next: perft(25)!


Hi Murray,
Thanks for verifying my number, and congrats with the very impressive performance on a laptop!
Is there a not-so-hidden challenge in your posting? :-)
Aart


Top
   
PostPosted: Thu Sep 13, 2012 00:15 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
Hi Murray,

Long time no hear from you! Are you still working on Nemesis, or another checkers engine?

Mac Banks mentioned that you were building a 10-piece database. Did you finish building it?

-- Ed


Top
   
PostPosted: Thu Sep 13, 2012 07:29 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1487
murraycash wrote:
Hi Rein, Hardware is HP EliteBook with Intel i7-M620 @ 2.67 Ghz. 4 cores, all used.
Algorithm is a parallel move generator with "lock-less" hash table of 4GB, described by Robert Hyatt and Tim Mann, see http://chessprogramming.wikispaces.com/Shared+Hash+Table

You are right, I am only motivated to do the next perft if I can complete it in 4 days!


Hi Murray,

Correct me if I'm wrong, but I think that lock-less hashing is not guaranteed to be correct for perft counts. In regular searches, almost all (and rare to begin with) read/write races on individual hash entries are filtered out by the alpha-beta mechanism, but for perft any error will certainly propagate up to the root count. Nevertheless, it appears that you got away with it (I also got away with hard hash collissions with my perft(21) confirmation and perft(22) computation, but I wonder how lucky I was then). I think having a single hash table per core is the only way to guarantee correctness (barring memory errors of course).

Rein


Top
   
PostPosted: Thu Sep 13, 2012 18:42 
Offline

Joined: Mon Sep 10, 2012 21:48
Posts: 10
Real name: Murray Cash
Quote:
Correct me if I'm wrong, but I think that lock-less hashing is not guaranteed to be correct for perft counts. In regular searches, almost all (and rare to begin with) read/write races on individual hash entries are filtered out by the alpha-beta mechanism, but for perft any error will certainly propagate up to the root count. Nevertheless, it appears that you got away with it (I also got away with hard hash collissions with my perft(21) confirmation and perft(22) computation, but I wonder how lucky I was then). I think having a single hash table per core is the only way to guarantee correctness (barring memory errors of course).


Hi Rein, I am currently using hash records with 64-bit signatures but have not encountered a problematic type-1 error (key collision) yet as my figures agree with Aart. Aart said in his other post he uses collision-free hash tables, which is the better way.

But the lock-less hashing method I use does not make this situation better or worse. Type-1 collisions can happen in single threaded or multi threaded (+ lock-less hash) perft apps and can ruin the results either way.

you can avoid type-1 collisions altogether by storing the whole position in the hash table, which can be done in 96 bits without any fancy compression (97 if you need to store the side to move also).


Last edited by murraycash on Thu Sep 13, 2012 21:09, edited 1 time in total.

Top
   
PostPosted: Thu Sep 13, 2012 18:48 
Offline

Joined: Mon Sep 10, 2012 21:48
Posts: 10
Real name: Murray Cash
Quote:
Long time no hear from you! Are you still working on Nemesis, or another checkers engine?

Mac Banks mentioned that you were building a 10-piece database. Did you finish building it?


Hello Ed! It's been a while! I haven't worked on a checkers engine for a long time now, since our aborted Manchester tournament. Never had time really, too busy with other things. I never finished the 10 piece DB, I was about half way through and put it on hold as it would take another 6 months of 2 computers being on 24/7. I think it could be done a lot faster now, might re-visit the project.

The perft project has been quite interesting though, seeing what can be done with limited resources, trying to squeeze every last bit out of the laptop.
Is there any serious work still ongoing on 8x8 checkers?


Top
   
PostPosted: Thu Sep 13, 2012 21:42 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1487
murraycash wrote:

But the lock-less hashing method I use does not make this situation better or worse. Type-1 collisions can happen in single threaded or multi threaded (+ lock-less hash) perft apps and can ruin the results either way.


I'm not sure if this old xor-trick (i.e. not using std::atomic_fetch_xor) is guaranteed to be portable and race-free by the C++11 Standard, or that it "only" happens to work on x86/x86-64 architectures or with a small number of threads.

Quote:
you can avoid type-1 collisions altogether by storing the whole position in the hash table, which can be done in 96 bits without any fancy compression (97 if you need to store the side to move also).


yes, I know but I use 64-bit bitboards for other reasons (avoiding even/odd row code duplication). I don't need the color bit because I use one hash table for each side to move.


Top
   
PostPosted: Thu Sep 13, 2012 22:15 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
murraycash wrote:
Hello Ed! It's been a while! I haven't worked on a checkers engine for a long time now, since our aborted Manchester tournament. Never had time really, too busy with other things. I never finished the 10 piece DB, I was about half way through and put it on hold as it would take another 6 months of 2 computers being on 24/7. I think it could be done a lot faster now, might re-visit the project.

The perft project has been quite interesting though, seeing what can be done with limited resources, trying to squeeze every last bit out of the laptop.
Is there any serious work still ongoing on 8x8 checkers?

Except for a few bug fixes I haven't worked on 8x8 checkers much at all. It seems that with large opening books and strong engines, all games are draws. For the past few years I have been working on 10x10 international draughts, which is more challenging. Opening books do not help it much, and endgame databases start helping much later in the game than in 8x8 checkers.

I agree that building the 10pc db is not now the big hurdle that it used to be. I could probably do it in 2 to 3 months now using the 2 machines that I have here (the newest one is several years old).

-- Ed


Top
   
PostPosted: Thu Sep 13, 2012 23:33 
Offline

Joined: Mon Sep 10, 2012 21:48
Posts: 10
Real name: Murray Cash
Rein Halbersma wrote:
murraycash wrote:

But the lock-less hashing method I use does not make this situation better or worse. Type-1 collisions can happen in single threaded or multi threaded (+ lock-less hash) perft apps and can ruin the results either way.


I'm not sure if this old xor-trick (i.e. not using std::atomic_fetch_xor) is guaranteed to be portable and race-free by the C++11 Standard, or that it "only" happens to work on x86/x86-64 architectures or with a small number of threads.


Rein, I stand corrected. I agree the lock-less implementation does increase the chance of perft count errors and that for a given hash table size, increasing the number of threads accessing the hash table will further increase the chances of race conditions that could cause a random hash key (key ^ data1) ^ data2 when decoded, to be a false match.
I'll try your idea of totally separate hash tables per thread and see how performance goes.


Top
   
PostPosted: Fri Sep 14, 2012 12:41 
Offline

Joined: Sat Apr 28, 2007 13:53
Posts: 725
Real name: Ed Gilbert
Location: Morristown, NJ USA
Quote:
I'll try your idea of totally separate hash tables per thread and see how performance goes.

You could also use some spinlocks for mutual exclusion with a single hashtable. A single spinlock would be bad because only one thread could access the hashtable at a time. But if you used say 100 locks, with each lock protecting 1/100th of the table nodes, then the hashtable would usually be available for every thread simultaneously.

-- Ed


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 19 posts ]  Go to page 1 2 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited