Home 
Search 
Today's Posts 
#1




Which pawn positions go into a pawn hash table?
If I calculated correctly, there are more than 5E25 possible pawn
structures. Clearly it's impossible to put them all in a hash table for pawn structure scoring. So the question is: which pawn structures do you put in this table, and, most importantly, how do you compute them? Example: do a search with pawn moves only (doesn't sound like a very good scheme to me, you will miss many captures that lead to doubled pawns etc), and what amount would be 'enough'? 
#2




Which pawn positions go into a pawn hash table?
pd42 wrote:
If I calculated correctly, there are more than 5E25 possible pawn structures. Clearly it's impossible to put them all in a hash table for pawn structure scoring. So the question is: which pawn structures do you put in this table, and, most importantly, how do you compute them? Example: do a search with pawn moves only (doesn't sound like a very good scheme to me, you will miss many captures that lead to doubled pawns etc), and what amount would be 'enough'? Wrong idea. As you search the normal game tree when playing, for each pawn structure you evaluate, you put _that_ into the pawn hash table. It is likely you will visit that same pawn structure many times as you shuffle pieces on the board... Doing this will typically cause you to evaluate a particular pawn structure only once for every 100 calls to evaluate one, because you have already seen the current structure previously and saved the evaluation information...  Robert M. Hyatt, Ph.D. Computer and Information Sciences University of Alabama at Birmingham (205) 9342213 136A Campbell Hall (205) 9345473 FAX Birmingham, AL 352941170 
#3




Which pawn positions go into a pawn hash table?

#4




Which pawn positions go into a pawn hash table?
hello,
I guess 5 * 10^25 is a calculation mistake. For sure it's less than roughly = 48! / 8!8!32! = 29.019.905.518.636.890 positions = 2.9 * 10^16 Just a rough estimation. Practical it's less of course as a big number of pawn positions will never happen even reality on the board. Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. that number &(entries1) , where # entries is a power of 2, at that array number in hashtable you replace the current position that's there when it is not the same. If it is the same you already have the score. Chances of it going wrong is very low, depending upon pawnhashtable size and how and what you do it's between 92%99% usually. "pd42" wrote in message om... If I calculated correctly, there are more than 5E25 possible pawn structures. Clearly it's impossible to put them all in a hash table for pawn structure scoring. So the question is: which pawn structures do you put in this table, and, most importantly, how do you compute them? Example: do a search with pawn moves only (doesn't sound like a very good scheme to me, you will miss many captures that lead to doubled pawns etc), and what amount would be 'enough'? 
#5




Which pawn positions go into a pawn hash table?
Robert Hyatt wrote in message ...
pd42 wrote: If I calculated correctly, there are more than 5E25 possible pawn structures. Clearly it's impossible to put them all in a hash table for pawn structure scoring. So the question is: which pawn structures do you put in this table, and, most importantly, how do you compute them? Example: do a search with pawn moves only (doesn't sound like a very good scheme to me, you will miss many captures that lead to doubled pawns etc), and what amount would be 'enough'? Wrong idea. As you search the normal game tree when playing, for each pawn structure you evaluate, you put _that_ into the pawn hash table. It is likely you will visit that same pawn structure many times as you shuffle pieces on the board... Doing this will typically cause you to evaluate a particular pawn structure only once for every 100 calls to evaluate one, because you have already seen the current structure previously and saved the evaluation information... Of course! Thanks. 
#6




Which pawn positions go into a pawn hash table?
Hi Vincent!
"Vincent Diepeveen" writes: Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. In my experience 32bit hash keys are good enough for pawn hash tables (unlike the main transposition table). I made an experiment once, and checked for false pawn hash hits (by storing a 32bit *and* a 64bit key in the pawn hash entries) at all nodes in the search. I think I played 100 blitz games in the experiment, and I didn't see a single false hit. that number &(entries1) , where # entries is a power of 2, at that array number in hashtable you replace the current position that's there when it is not the same. If it is the same you already have the score. Chances of it going wrong is very low, depending upon pawnhashtable size and how and what you do it's between 92%99% usually. Surprisingly, even tiny pawn hash tables give remarkable performance gains. My engine is *much* faster with a pawn hash table with two (!) entries than without a pawn hash table at all. The reason is, of course, that most moves in the search tree don't change the pawn structure. I've found that increasing the pawn hash table size beyond 256 entries gives me very little (about 3%, IIRC).  Tord Romstad 
#7




Which pawn positions go into a pawn hash table?
Tord Kallqvist Romstad wrote:
"Vincent Diepeveen" writes: Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. In my experience 32bit hash keys are good enough for pawn hash tables (unlike the main transposition table). I made an experiment once, and checked for false pawn hash hits (by storing a 32bit *and* a 64bit key in the pawn hash entries) at all nodes in the search. I think I played 100 blitz games in the experiment, and I didn't see a single false hit. The Birthday Theorem tells us that the probability of seeing two positions with the same hash exceeds a half when we've seen sqrt(number of possible keys) positions. With a 32bit hash key, this means that, when you've seen more than 66,000 positions, you have a 50/50 chance of having had a collision. I'd guess that you wouldn't see that many different pawn structures while considering moves for a single game and, even if you did, the chance of considering the two positions that collide at the same time should still be pretty low. For example, you might find deep in the end game that you consider a pawn structure that has the same hash as the initial position. But, by then, you've almost certainly overwritten the initial position's score in the hash table with something else that ended up in the same bin but with a different key. Dave.  David Richerby Dangerous Laser (TM): it's like an www.chiark.greenend.org.uk/~davidr/ intense beam of light but it could explode at any minute! 
#8




Which pawn positions go into a pawn hash table?
David Richerby wrote in message ...
Tord Kallqvist Romstad wrote: "Vincent Diepeveen" writes: Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. In my experience 32bit hash keys are good enough for pawn hash tables (unlike the main transposition table). I made an experiment once, and checked for false pawn hash hits (by storing a 32bit *and* a 64bit key in the pawn hash entries) at all nodes in the search. I think I played 100 blitz games in the experiment, and I didn't see a single false hit. The Birthday Theorem tells us that the probability of seeing two positions with the same hash exceeds a half when we've seen sqrt(number of possible keys) positions. With a 32bit hash key, this means that, when you've seen more than 66,000 positions, you have a 50/50 chance of having had a collision. I'd guess that you wouldn't see that many different pawn structures while considering moves for a single game and, even if you did, the chance of considering the two positions that collide at the same time should still be pretty low. For example, you might find deep in the end game that you consider a pawn structure that has the same hash as the initial position. But, by then, you've almost certainly overwritten the initial position's score in the hash table with something else that ended up in the same bin but with a different key. Dave. Why use 32bit if you already have 64bitat hand for the main hash table???Surely not to save memory as I understand the pawn hash table doesn't need to be very large anyway (kb's rather than mb's).... 
#9




Which pawn positions go into a pawn hash table?
pd42 wrote:
David Richerby wrote in message ... Tord Kallqvist Romstad wrote: "Vincent Diepeveen" writes: Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. In my experience 32bit hash keys are good enough for pawn hash tables (unlike the main transposition table). I made an experiment once, and checked for false pawn hash hits (by storing a 32bit *and* a 64bit key in the pawn hash entries) at all nodes in the search. I think I played 100 blitz games in the experiment, and I didn't see a single false hit. The Birthday Theorem tells us that the probability of seeing two positions with the same hash exceeds a half when we've seen sqrt(number of possible keys) positions. With a 32bit hash key, this means that, when you've seen more than 66,000 positions, you have a 50/50 chance of having had a collision. I'd guess that you wouldn't see that many different pawn structures while considering moves for a single game and, even if you did, the chance of considering the two positions that collide at the same time should still be pretty low. For example, you might find deep in the end game that you consider a pawn structure that has the same hash as the initial position. But, by then, you've almost certainly overwritten the initial position's score in the hash table with something else that ended up in the same bin but with a different key. Dave. Why use 32bit if you already have 64bitat hand for the main hash table???Surely not to save memory as I understand the pawn hash table doesn't need to be very large anyway (kb's rather than mb's).... Note that the normal hash signature is not useful for pawns. It has pieces included which means that a second signature needs to be maintained. Doing it in 32 bits would be cheaper until run on a real 64 bit architecture which will be the "norm" in a few more years... I have two signatures, one with everything, one with just pawns, both are 64 bit values...  Robert M. Hyatt, Ph.D. Computer and Information Sciences University of Alabama at Birmingham (205) 9342213 136A Campbell Hall (205) 9345473 FAX Birmingham, AL 352941170 
#10




Which pawn positions go into a pawn hash table?
I wouldn't know either why there is a 32 bits need when already having more
than that. In diep there are 2 values. 1 value for the pieces (excluding pawns) and 1 value for the pawns. Note that storing 32 bits key in pawnhashtable and using the rest as a lookup shouldn't cause any problems. There aren't many pawn positions at all. "pd42" wrote in message om... David Richerby wrote in message ... Tord Kallqvist Romstad wrote: "Vincent Diepeveen" writes: Yet pawnhashtables use replacing strategies, so they just keep a number of positions. you hash to a big number using 64 bits variables. In my experience 32bit hash keys are good enough for pawn hash tables (unlike the main transposition table). I made an experiment once, and checked for false pawn hash hits (by storing a 32bit *and* a 64bit key in the pawn hash entries) at all nodes in the search. I think I played 100 blitz games in the experiment, and I didn't see a single false hit. The Birthday Theorem tells us that the probability of seeing two positions with the same hash exceeds a half when we've seen sqrt(number of possible keys) positions. With a 32bit hash key, this means that, when you've seen more than 66,000 positions, you have a 50/50 chance of having had a collision. I'd guess that you wouldn't see that many different pawn structures while considering moves for a single game and, even if you did, the chance of considering the two positions that collide at the same time should still be pretty low. For example, you might find deep in the end game that you consider a pawn structure that has the same hash as the initial position. But, by then, you've almost certainly overwritten the initial position's score in the hash table with something else that ended up in the same bin but with a different key. Dave. Why use 32bit if you already have 64bitat hand for the main hash table???Surely not to save memory as I understand the pawn hash table doesn't need to be very large anyway (kb's rather than mb's).... 
Reply 
Thread Tools  
Display Modes  


Similar Threads  
Thread  Forum  
hash table collisions  rec.games.chess.computer (Computer Chess)  
newbie analisis question  rec.games.chess.analysis (Chess Analysis)  
Kaspy vs X3D Fritz PGN  rec.games.chess.computer (Computer Chess)  
Chessbase engines loses so easy!  rec.games.chess.computer (Computer Chess)  
Sick of players who INSIST on playing *BOOK* openings  rec.games.chess.analysis (Chess Analysis) 