Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old May 26th 04, 08:34 AM
pd42
 
Posts: n/a
Default 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   Report Post  
Old May 26th 04, 03:15 PM
Robert Hyatt
 
Posts: n/a
Default 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) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #3   Report Post  
Old May 26th 04, 05:47 PM
Tord Kallqvist Romstad
 
Posts: n/a
Default Which pawn positions go into a pawn hash table?

(pd42) writes:

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?


I have a function which studies the pawn structure on the board and
computes a lot of information, including the squares of all passed,
isolated, doubled and backward pawns for both sides, the number of
pawns on black/white squares for both sides, the number of *blocked*
pawns on black/white squares, a classification of the central pawn
structure (open, closed, semi-closed, unresolved, and a few other
possibilities), some kingside pawn strom terms for use in positions
with castling in opposite directions, and much more.

Computing all of this is very time-consuming, and if I had to call
this function at all nodes, it would slow me down a lot. Fortunately,
this isn't necessary. All the information is stored in a pawn
structure hash table. Because the number of pawn structures which
occur in a search is usually tiny compared to the number of nodes
searched, you will almost always find the pawn structure on the board
in the pawn hash table. This means that you can do extremely
complicated pawn structure calculations almost for free.

Normal Zobrist hashing (considering only pawns, not pieces, of course)
works fine for generating hash keys. 32-bit keys are probably good
enough for the pawn hash table.

--
Tord Romstad
  #4   Report Post  
Old May 27th 04, 04:59 AM
Vincent Diepeveen
 
Posts: n/a
Default 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
&(entries-1) , 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   Report Post  
Old May 27th 04, 09:26 AM
pd42
 
Posts: n/a
Default 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   Report Post  
Old May 27th 04, 09:59 AM
Tord Kallqvist Romstad
 
Posts: n/a
Default 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 32-bit 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 32-bit *and* a 64-bit
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 &(entries-1) , 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   Report Post  
Old May 27th 04, 02:26 PM
David Richerby
 
Posts: n/a
Default 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 32-bit 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 32-bit *and* a 64-bit
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 32-bit 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   Report Post  
Old May 27th 04, 06:59 PM
pd42
 
Posts: n/a
Default 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 32-bit 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 32-bit *and* a 64-bit
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 32-bit 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 32-bit if you already have 64-bitat 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   Report Post  
Old May 27th 04, 07:20 PM
Robert Hyatt
 
Posts: n/a
Default 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 32-bit 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 32-bit *and* a 64-bit
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 32-bit 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 32-bit if you already have 64-bitat 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) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #10   Report Post  
Old June 1st 04, 05:21 PM
Vincent Diepeveen
 
Posts: n/a
Default 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 32-bit 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 32-bit *and* a 64-bit
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 32-bit 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 32-bit if you already have 64-bitat 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

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
hash table collisions Paul Rushmer rec.games.chess.computer (Computer Chess) 21 April 1st 04 10:25 AM
newbie analisis question Michael C. Shultz rec.games.chess.analysis (Chess Analysis) 19 January 29th 04 06:09 AM
Kaspy vs X3D Fritz PGN NetSock rec.games.chess.computer (Computer Chess) 4 December 16th 03 01:07 PM
Chessbase engines loses so easy! kostas_1966 rec.games.chess.computer (Computer Chess) 14 November 5th 03 11:57 PM
Sick of players who INSIST on playing *BOOK* openings Scott rec.games.chess.analysis (Chess Analysis) 13 July 17th 03 10:26 PM


All times are GMT +1. The time now is 11:29 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