World Draughts Forum

It is currently Wed Dec 13, 2017 19:27

All times are UTC+01:00




Post new topic  Reply to topic  [ 247 posts ]  Go to page Previous 1 2 3 4 517 Next
Author Message
 Post subject:
PostPosted: Sun Jul 13, 2008 11:22 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject:
PostPosted: Sun Jul 13, 2008 11:29 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject:
PostPosted: Mon Jul 14, 2008 01:17 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 726
Real name: Ed Gilbert
Location: Morristown, NJ USA
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


Top
   
 Post subject:
PostPosted: Mon Jul 14, 2008 07:50 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
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?


Top
   
 Post subject:
PostPosted: Mon Jul 14, 2008 14:31 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 726
Real name: Ed Gilbert
Location: Morristown, NJ USA
Thank you Rein for spotting my error. On your test position I do get 3 moves.

-- Ed


Top
   
 Post subject:
PostPosted: Tue Jul 15, 2008 10:48 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
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


Top
   
 Post subject:
PostPosted: Tue Jul 15, 2008 14:22 
Offline
User avatar

Joined: Mon Dec 19, 2005 16:48
Posts: 306
Location: Emmen
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?


Top
   
 Post subject:
PostPosted: Tue Jul 15, 2008 17:34 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 726
Real name: Ed Gilbert
Location: Morristown, NJ USA
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:
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


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 12:33 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 13:32 
Offline
User avatar

Joined: Mon Dec 19, 2005 16:48
Posts: 306
Location: Emmen
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,


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 13:47 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 726
Real name: Ed Gilbert
Location: Morristown, NJ USA
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


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 13:51 
Offline
User avatar

Joined: Mon Dec 19, 2005 16:48
Posts: 306
Location: Emmen
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


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 14:15 
Offline
User avatar

Joined: Mon Dec 19, 2005 16:48
Posts: 306
Location: Emmen
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.


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 14:44 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
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


Top
   
 Post subject:
PostPosted: Wed Jul 16, 2008 15:13 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 247 posts ]  Go to page Previous 1 2 3 4 517 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 8 guests


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