Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old April 16th 04, 12:13 PM
Tommy
 
Posts: n/a
Default Transposition tables2

I have also noticed that if I load a mate in 7 puzzle and then solve it in a
few minutes, then start a new game a play it all, then I load the mate in 7
puzzle again, the chess program still remembers the solution (from the TT)
and plays the correct move immediately.... I thought that with always
replace, after more than a billion nodes (on a much smaller TT) the TT would
not be able to retain any old value. What do you think?

Thanks,

Tommy

  #2   Report Post  
Old April 16th 04, 01:29 PM
Mikko Nummelin
 
Posts: n/a
Default Transposition tables

On Fri, 16 Apr 2004, Tommy wrote:

I have also noticed that if I load a mate in 7 puzzle and then solve it
in a few minutes, then start a new game a play it all, then I load the
mate in 7 puzzle again, the chess program still remembers the solution
(from the TT) and plays the correct move immediately.... I thought that
with always replace, after more than a billion nodes (on a much smaller
TT) the TT would not be able to retain any old value. What do you think?


First, the hashtable should be cleared when starting a new game. Second,
mate in N -nodes in hashtable should be treated differently than other
nodes. When replacing those nodes, it should no more be based on depth (as
with "normal" nodes) but mate distance so that "mate in M" will be
replaced by "mate in N" only if NM. Also one should be very careful when
calculating the distance to mate. In general, if alpha-beta search returns
+MATE-M then the value returned further should be -MATE+M+1, and similarly
if alpha-beta returns -MATE+M the value returned further should be
+MATE-M-1. Here it is assumed that

-MATE (the player on move is mated and lost)
+MATE-1 (the player on move has mate in one)
-MATE+2 (whatever the player on move moves he will be mated next move)
.... etc.

and MATE is a sufficiently large number.

An erroneous approach is to return +MATE-M or -MATE+M based on calculated
depth-until-bottom value. With hashtable that will produce weird "mate in
100+ -moves" evaluations which often include very long or even nonexistent
paths to "mate". In game situations that will appear as unnecessary
repeating of won positions.

The above is based on bugs I made when programming Needle.


Mikko Nummelin
  #3   Report Post  
Old April 16th 04, 05:09 PM
Robert Hyatt
 
Posts: n/a
Default Transposition tables2

Tommy wrote:
I have also noticed that if I load a mate in 7 puzzle and then solve it in a
few minutes, then start a new game a play it all, then I load the mate in 7
puzzle again, the chess program still remembers the solution (from the TT)
and plays the correct move immediately.... I thought that with always
replace, after more than a billion nodes (on a much smaller TT) the TT would
not be able to retain any old value. What do you think?


Thanks,


Tommy


Have you "eyeballed" your random numbers? Have you checked to see how
your probes are scattered over the table?

That sounds wrong...


--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #4   Report Post  
Old April 16th 04, 11:11 PM
Tommy
 
Posts: n/a
Default Transposition tables2


"Robert Hyatt" wrote

Have you "eyeballed" your random numbers? Have you checked to see how
your probes are scattered over the table?


I have now... I have notice that after 60 seconds there are some positions
in the hash table were mapped by as much as 40 different positions
(different zobrist key). However like 1/5 of the positions have not been
mapped at all. The average is about 6 times.

this is how I produce random numbers (but I have also tried your function
(in crafty)):

MASKU64 ChessAttacksAndMoves::My_rand64()
{
return
(MASKU64(rand())) ^
((MASKU64(rand())) 15) ^ ((MASKU64(rand())) 30) ^
((MASKU64(rand())) 45) ^ ((MASKU64(rand())) 60)
;
}

This is how I initialise the zobrist keys:

void ChessAttacksAndMoves::FillZobristKeys()
{
int piece, colour, square;
for(piece = 0; piece=KING; ++piece){
for(colour=0; colour=BLACK_PIECE; ++colour){
for(square=0; square64; ++square){
zobrist_numbers[piece][colour][square] = My_rand64();
}
}
}
zobrist_white_constant = My_rand64();
}

To calculate the zobrist key for a position i do:

zobrist_key = 0ui64;
for all the 64 squares:
zobrist_key ^= attacks_and_moves.zobrist_numbers[piece][color][square];
if player is white:
zobrist_key ^= attacks_and_moves.zobrist_white_constant

Finally to map a zobrist key to a position in the hash table I do:

zobrist_key % number_of_elements is hash.

The number of elements, just to be sure is a prime number: 1333357

That sounds wrong...


I know.... but I cannot understand why :-(

Thanks,

Tommy

  #5   Report Post  
Old April 17th 04, 03:35 AM
Robert Hyatt
 
Posts: n/a
Default Transposition tables2

Tommy wrote:

"Robert Hyatt" wrote


Have you "eyeballed" your random numbers? Have you checked to see how
your probes are scattered over the table?


I have now... I have notice that after 60 seconds there are some positions
in the hash table were mapped by as much as 40 different positions
(different zobrist key). However like 1/5 of the positions have not been
mapped at all. The average is about 6 times.


this is how I produce random numbers (but I have also tried your function
(in crafty)):


MASKU64 ChessAttacksAndMoves::My_rand64()
{
return
(MASKU64(rand())) ^
((MASKU64(rand())) 15) ^ ((MASKU64(rand())) 30) ^
((MASKU64(rand())) 45) ^ ((MASKU64(rand())) 60)
;
}



First, the above is pretty strange. IE " 60" is pretty pointless.

Second, why are you using xor?

My RNG (Crafty) produces good numbers from experience. (It comes from
"Numerical Recipes".

This is how I initialise the zobrist keys:


void ChessAttacksAndMoves::FillZobristKeys()
{
int piece, colour, square;
for(piece = 0; piece=KING; ++piece){
for(colour=0; colour=BLACK_PIECE; ++colour){
for(square=0; square64; ++square){
zobrist_numbers[piece][colour][square] = My_rand64();
}
}
}
zobrist_white_constant = My_rand64();
}


To calculate the zobrist key for a position i do:


zobrist_key = 0ui64;
for all the 64 squares:
zobrist_key ^= attacks_and_moves.zobrist_numbers[piece][color][square];
if player is white:
zobrist_key ^= attacks_and_moves.zobrist_white_constant


Finally to map a zobrist key to a position in the hash table I do:


zobrist_key % number_of_elements is hash.


The number of elements, just to be sure is a prime number: 1333357


That sounds wrong...


I know.... but I cannot understand why :-(


Thanks,


Tommy



--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170


  #6   Report Post  
Old April 17th 04, 05:44 PM
Tommy
 
Posts: n/a
Default Transposition tables2


"Robert Hyatt" wrote

MASKU64 ChessAttacksAndMoves::My_rand64()
{
return
(MASKU64(rand())) ^
((MASKU64(rand())) 15) ^ ((MASKU64(rand())) 30) ^
((MASKU64(rand())) 45) ^ ((MASKU64(rand())) 60)
;
}


First, the above is pretty strange. IE " 60" is pretty pointless.


well, rand() returns a 15bit number, so with 4 rand()s I can fill up 60 bits
and then I need a last one for the remaining 4 bits... (discarding 11 bits
of the last rand).

Second, why are you using xor?


well, I could have used OR and it would not change anything... I just used
XOR.

My RNG (Crafty) produces good numbers from experience. (It comes from
"Numerical Recipes".


ok, i tried it, I am sure it is much better, but it does not solve the
problem.

I will try and make My_rand64() function much better, but the problem does
not seem to be here....

Thanks,

Tommy


  #7   Report Post  
Old April 17th 04, 06:34 PM
Simon Krahnke
 
Posts: n/a
Default Transposition tables2

* Robert Hyatt (04:35) schrieb:

My RNG (Crafty) produces good numbers from experience. (It comes from
"Numerical Recipes".


I calculate random numbers before build time. I have a perl script, that
produces the source code file:

,----
| open RANDOM, " /dev/urandom" or die "/dev/urandom: $!\n";
|
| sub rand64 {
| read RANDOM, $_, 8;
| my @ints = unpack "ii", $_;
| sprintf "0x%.8x%.8xL%s", $ints[0], $ints[1];
| }
`----

I just take the os'es pseudo random. I could have real random. But
producing 49216 random bits in the kernel take their time.

Is there any point in calculating keys at runtime?

mfg, simon .... l
  #8   Report Post  
Old April 18th 04, 12:24 AM
Tommy
 
Posts: n/a
Default Transposition tables2


"Simon Krahnke" wrote

Is there any point in calculating keys at runtime?


well not really, but what is the point of doing them before build time?

One way you have a smaller source code and/or you avoid having a file
containing the random numbers.
In the other way you avoid having to generate them at run-time, but they
have to be generated only once at the beginning of the program and this is
therefore not a problem.

So I guess the run-time version is more elegant and reasonable.
But I guess this is down to personal preference....

Tommy

  #9   Report Post  
Old April 18th 04, 03:25 AM
Simon Krahnke
 
Posts: n/a
Default Transposition tables2

* Tommy (01:24) schrieb:

Is there any point in calculating keys at runtime?


well not really, but what is the point of doing them before build time?


Well, I could test them. Run a lot of games, seeing if any keys clash.
or looking at the hash distribution.

One way you have a smaller source code and/or you avoid having a file
containing the random numbers.


Having 392 lines of numbers and 45 lines of script won't eat up my disk.
:-)

This way i can use real random, and don't have to care about good pseudo
random generation.

In the other way you avoid having to generate them at run-time, but they
have to be generated only once at the beginning of the program and this is
therefore not a problem.


Sure.

So I guess the run-time version is more elegant and reasonable.
But I guess this is down to personal preference....


Okay. Just wanted to find out if i am totally wrong in doing it the
other way than everybody else.

mfg, simon .... l
  #10   Report Post  
Old April 18th 04, 01:28 PM
David Richerby
 
Posts: n/a
Default Transposition tables2

Simon Krahnke wrote:
I calculate random numbers before build time. [...] Is there any point
in calculating keys at runtime?


I'm not sure it makes much difference, as long as it doesn't take too
long. For debugging, it's useful to be able to generate the same keys
every time, which you get for free with compiled-in keys.


Dave.

--
David Richerby Indelible Carnivorous T-Shirt (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a fashion statement but it's
full of teeth and it can't be erased!
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
transposition tables... Tommy rec.games.chess.computer (Computer Chess) 1 April 18th 04 12:52 PM
transposition tables Tommy rec.games.chess.computer (Computer Chess) 2 November 27th 03 12:58 AM
Using Transposition Table with Wildly Varying Score Melissa rec.games.chess.computer (Computer Chess) 2 October 17th 03 10:08 AM
Transposition tables Noah Roberts rec.games.chess.computer (Computer Chess) 2 September 13th 03 05:21 PM
Search extensions and transposition tables Delphi rec.games.chess.computer (Computer Chess) 2 August 21st 03 10:10 PM


All times are GMT +1. The time now is 10:52 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017