Author: Michel Langeveld
Date: 14:58:11 06/22/99
Go up one level in this thread
On June 22, 1999 at 12:20:20, Dann Corbit wrote:
>On June 22, 1999 at 12:11:54, Michel Langeveld wrote:
>
>>Hello Chess World!!
>>
>>the complete table becomes:
>>
>>Ply(0) Nodes= 1
>>Ply(1) Nodes= 20 = 20,00x ply(0)
>>Ply(2) Nodes= 400 = 20,00x ply(1)
>>Ply(3) Nodes= 8902 = 22,26x ply(2)
>>Ply(4) Nodes= 197281 = 22,16x ply(3)
>>Ply(5) Nodes= 4865609 = 24,66x ply(4)
>>Ply(6) Nodes= 119060324 = 24,47x ply(5)
>>Ply(7) Nodes= 3195901860 = 26,84x ply(6)
>>Ply(8) Nodes= 84998978956 = 26,60x ply(7)
>>Ply(9) Nodes= 2439530234167 = 28,70x ply(8)
>>
>>Ply 9 is interesting because white-promotions and white long castling is added
>>for the first time.
>>
>>Volunteers for doing ply 10 or verify ply 9 :-P ? Maybe we can calculate this
>>distributedly...
>How many of those positions are unique?
>;-)
I haven't calculated the exact number but at least 2214046243735 seems to be
doubles. But this number doesn't make sense because the number of doubles is
much higher. I guess 99% doubles is not strange.
Some background information:
I have a bet with 2 other guys (total = 3) who can make the best chessprogram.
That's why I started to write this program. 17 November is the deadline of our
program's. Each program has to play 6 games of 30 minutes against each other.
The winner is who has the highest total score.
After the bet we have both 3 much knowledge about writing a chessprogram and
have plans to combine ideas together to one hugh program. If the program is
strong enough we will maybe join some event (like WCCCM) but this is just all
future.
I wrote the program using Microsoft Visual C++ 6.0. I started just a few weeks
ago and are still much improving every day. We both 3 share numbers about
positions to ensure our movegenerators are correct and fast!! That's why I
started to calculate the beginning position.
I made some optimizations to calculate nodecounts in positions. For example it's
not nessecary to do all moves on the lowest level off the search tree.
Just knowing HOW much moves are possible is enough. nodecount +=
movelist.number; Doing moves on higher levels in the tree is ofcourse nessecary.
Further more I used a hashtable of 100MB. I use a 64bit hash value for each
position. I used the random generator of Crafty except I added an cast to _int64
to the last statement of Random64 to ensure 64bit values are used. I'm not sure
this is right in Crafty. I have to check this before yelling, but it seems only
32 bit numbers are generated. first 32 bits are zeros. But again i'm not sure
about this. Can comebody check if Crafty is using real 64 bit values on Windows
platform?? Just print them out to screen with printf("%I64u", value) or
something.
In my hash I use 3 values:
-hashValue (_int64)
-nodeCounter (_int64)
-ply (char)
this gives a total of 17 bytes which is rounded by VC to 24 byte.
I have a table of 2**22 records (4194304) of each 24 bytes which give a total
hashtable just above 100Mb. I use to last bits (and with 1 << 22 - 1)
to store the key.
This can be optimized more because not the entire hashkey has to be stored
only the former 64-22 = 42 bits. Als maybe the nodecounter can stored a little
bit shorter only about 41 bits are nececarry to store a number of
2.xxx.xxx.xxx.xxx. Further in VC 6.0 it's possible to not alias struct so the
real number of bytes are used to store the struct.
The first 8 ply I could generated in 1 hour. Strange enough the 9 ply test costs
me 36 hours. Maybe 100Mb is infact to small for this test. I got much
collisions. I experimented by only replace when the notecount is higher but this
worked slower. The best replacement algorithm for counting nodes seems to be
only storing a record when the number of ply searched IS GREATER OR _EQUAL_ to
the record in the hashtable.
Further more I build in release mode and made almost all functions __forced
inline. (This give a lot of performance increase).
I shall recheck my results with BTM to ensure no double 64bit hashvalues or used
for different positions. But this likely to be not true.
Up to ply 10!!!
Michel Langeveld
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.