Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Which pawn positions go into a pawn hash table?

60 views
Skip to first unread message

pd42

unread,
May 26, 2004, 3:34:26 AM5/26/04
to
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'?

Robert Hyatt

unread,
May 26, 2004, 10:15:34 AM5/26/04
to

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
hy...@uab.edu University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170

Tord Kallqvist Romstad

unread,
May 26, 2004, 12:47:51 PM5/26/04
to
pd...@hotmail.com (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

Vincent Diepeveen

unread,
May 26, 2004, 11:59:13 PM5/26/04
to
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" <pd...@hotmail.com> wrote in message
news:c3a8d849.04052...@posting.google.com...

pd42

unread,
May 27, 2004, 4:26:52 AM5/27/04
to
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in message news:<c928q6$3a0$1...@crier.cis.uab.edu>...

> pd42 <pd...@hotmail.com> 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.

Tord Kallqvist Romstad

unread,
May 27, 2004, 4:59:49 AM5/27/04
to
Hi Vincent!

"Vincent Diepeveen" <di...@xs4all.nl> 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

David Richerby

unread,
May 27, 2004, 9:26:58 AM5/27/04
to
Tord Kallqvist Romstad <rom...@math.uio.no> wrote:
> "Vincent Diepeveen" <di...@xs4all.nl> 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!

pd42

unread,
May 27, 2004, 1:59:55 PM5/27/04
to
David Richerby <dav...@chiark.greenend.org.uk> wrote in message news:<YBo*OS...@news.chiark.greenend.org.uk>...

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)....

Robert Hyatt

unread,
May 27, 2004, 2:20:31 PM5/27/04
to

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...

Vincent Diepeveen

unread,
Jun 1, 2004, 12:21:59 PM6/1/04
to
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" <pd...@hotmail.com> wrote in message
news:c3a8d849.04052...@posting.google.com...

0 new messages