Winboard Forum

Hello,

for computing trans map hash codes, Zobrist keys seem to be the best available to map a position to a 64 bit number. There is a small propability that two positions during the search map to the same number, but it seems one has to accept that.

For the pawn hash, obviously injective mappings from the set of all pawn structures to 64 bit numbers exist. Is it also possible to define an injective mapping that can be computed easily and/or incrementally, just like Zobrist keys?

(Note that for the trans map, the small propability of hash errors makes a legality check on the trans move necessary to avoid crashed due to the searching of illegal moves. Similar disadvantages might hold for a pawn hash that is not provably injective.)

Onno

Just use the Zobrist scheme, ignoring all non-pawns. If you have implemented the Zobrist randoms as int **Zobrist, rather than as int Zobrist[NPIECE][NSQR], you can set up an int *(PawnZobrist[]) pointing into the same table of random values as Zobrist[] for the pawns, and to a (shared) area of 64 zeros for all other pieces.

Likely you have an area like that in the ordinary ZobristTable anyway, for the encoding of empty squares (when they are 'captured').

You could of course also simply declare a second 2-dimensional array, containing mostly zeros, but that would be an uneccessary burden on your L1 cache. I don't like the size of this table of randoms anyway, so in uMax I shrunk it to ~1KB.

Thank you for your hints on implementing pawn hash with Zobrist keys. I had planned, if I would implement Zobrist keys, then use the obvious approach to test if the piece is a pawn, and do no update of pawn key if not.

Have you chosen your approach for code simplicity or for execution speed?

My original question was however how to avoid hash errors (different pawn structures with same 64-bit codes). Such errors might crash the program, for example if one stores the passers in the pawn hash table, retrive an entry that belongs to a different pawn structure, then evaluate the passers and find no pawn on the square where it is supposed to be. Do you check for such errors? (If the answer is no, my next question is if you check legality of the trans move.)

Onno Garms wrote:My original question was however how to avoid hash errors (different pawn structures with same 64-bit codes). Such errors might crash the program, for example if one stores the passers in the pawn hash table, retrive an entry that belongs to a different pawn structure, then evaluate the passers and find no pawn on the square where it is supposed to be. Do you check for such errors?

I don't.

(If the answer is no, my next question is if you check legality of the trans move.)

I do, but only because I don't lock the hash table or take any other measures to prevent two search threads from writing to the same hash entry simultaneously. With a single thread, skipping legality checking of the transposition table is in practise 100% safe when you use 64-bit hash keys. The probability of an illegal move from the transposition table is vanishingly small.

For the pawn hash table, you are even safer, because the number of pawn structures you see in a typical search is tiny compared to the number of positions. You could probably run your program for millions of years on the fastest currently available hardware without a single error (this is just an intuitive guess, and I am too lazy to verify this claim right now - I could be wrong).

If the pawn hash table claimed there was a passed pawn on a square where no pawn is found, my program would crash, too. It's never happened.

Tord

Onno Garms wrote:Have you chosen your approach for code simplicity or for execution speed?

For speed, and to minimize size of memory footprint (which translates to speed).

Having zero entries in the table allows you to always apply the value, without testing if it is needed. That saves branches, and branches that aren't there can't be mispredicted.

So I always XOR with the Zobrist value for the captured piece, even on non-captures: the victim for non-captures is an empty square, and all Zobrist randoms for empty squares are defined as zero.

I only use 32-bit hash lock in the TT. This would make Joker crash if the FROM square was empty. I had foreseen that, so I checked for it, and it would still crash due to castlings, if there were piieces inbetween K and R. So now I also check for that. Joker has no Pawn hash.

In crafty I use the same set of Zobrist randoms, since I already have some for pawns to update the actual hash signature, I just use the same pawn values for a separate incrementally-updated pawn hash key. I do not update this key unless a pawn moves or is captured or promotes, so I don't do a lot of "null-updating". I think the branches are much less important than the effect of doing random memory reads that might well not be in L1 or even in L2.

My MakeMove() function already has separate blocks for each type of piece, so only updating the pawn signature for pawn moves has zero mis-predicted branches in my code anyway...

Onno Garms wrote:For the pawn hash, obviously injective mappings from the set of all pawn structures to 64 bit numbers exist.

Hi Onno,

apart from the Zobrist key aspect which has already been discussed, I would like to know why you think that this is obvious. Your statement implies that 64 bit are sufficient to enumerate all possible pawn structures with up to 8 white and up to 8 black pawns. Could you explain your assumption?

I can imagine several ways to enumerate the set of all possible different pawn structures of a regular chess game, and to determine the number of bits required:

2x48 = 96 bit is "obvious" (two 48-bit bitboards for white/black) but there are better representations.

log2(3^48) = 77 bit is also "obvious" (each square either empty/wpawn/bpawn).

log2((22*27*31*33)^4) = 77 bit is another way of enumerating. White pawn a2 can reach 6+5+4+3+2+1 squares or be off (22), b2 can reach 5+6+5+4+3+2+1 squares or be off (27), and so on. Here you can save some combinations when two or more squares can be reached by different pawns (e.g. pawns a3 and b3 could either come from a2 and b2 or - by capturing - from b2 and a2, position is the same) but I can't see easily how much you can save here, and I feel it might be less than 13 bit in total. Also the number of captures which must have occurred before to realize a given pawn structure is limited by (15 - number of present enemy pawns), but again, I don't see how this can be computed easily without doing an expensive full enumeration, and how many bits you can save by this.

Most probably I missed something very simple. Open my eyes, please

Sven

bob wrote:In crafty I use the same set of Zobrist randoms, since I already have some for pawns to update the actual hash signature, I just use the same pawn values for a separate incrementally-updated pawn hash key. I do not update this key unless a pawn moves or is captured or promotes, so I don't do a lot of "null-updating". I think the branches are much less important than the effect of doing random memory reads that might well not be in L1 or even in L2.

My MakeMove() function already has separate blocks for each type of piece, so only updating the pawn signature for pawn moves has zero mis-predicted branches in my code anyway...

Yes, if the branches are there anyway, you just put the code where it was needed. But in Joker all pieces are handled by the same code. (Which is also good from the viewpoint of I-cache misses.)

Note that the zero updates are very unlikely to be cache misses, as all non-pawns can share the same board-image of zeros. Which is further used by the main hash-key update on any non-capture. So it is likely to be used a lot, and thus always in L1.

But I admit that the L1-residence of the Zobrist random table is one of my worries, which might be one of the reasons why Joker runs like sh*t on a Pentium 4 (with its 8KB L1). A full Zobrist table takes 2x6x64 = 678 longs = 6KB. In Joker I already reduced that by two, by making it 768 normal ints, and using the black entries for the upper half of the key as the low-order half of the white entries, and vice versa. (Unfortunately partly offset by the fact that I distinguish 8 piece types, rather than 6, so that I end up with a 4KB table.)

Perhaps I should switch to the micro-Max scheme, where I only use a table of bytes, combining them into longs by non-aligned access. This reduces the table to 1KB, allowing it to reside permanently in L1 even on a P4.

A simple Haskell program for counting the number of ways to place between 0 and 8 white pawns and between 0 and 8 black pawns on 48 possible squares:

Code: Select all

Calculate the binomial coefficient of m over n, i.e. the number of ways to
select n objects out of a collection of m equal objects:

> binom m n = div (product [m - n + 1 .. m]) (product [1..n])


Count the number of possible pawn configurations with w white pawns
and b black pawns.  Note that some of these probably cannot occur in
practise, because of the limited way pawns move.

> countPawnConfigurations (w,b) = (binom 48 w) * (binom (48 - w) b)


Count the total number of possible pawn configurations with 0..8 white
pawns and 0..8 black pawns:

> countAllPawnConfigurations =
>     sum (map countPawnConfigurations [(w,b) | w <- [0..8], b <- [0..8]])


Main function:

> main = print countAllPawnConfigurations

Running the program gives the value of 49095495585283107, which is well below 2^64.

Tord

Here is a simple way to prove that the number of pawn structures is smaller than 2^64 and to give every pawn structure different number even if you allow more than 8 pawns for one side when you only do not allow more than 16 pawns for both sides.


The idea is that there are less than 2^48 options to choose squares for the pawns when after doing it there are at most 2^16 options to choose the white pawns out of the pawns.

More formally:
Define for every square sq that can have a pawn:

number(sq)=(file(sq)-'a')*6+rank(sq)-2;

Define 48 bit number that is the sum of
2^number(sq) for all squares sq when sq has a pawn inside it.

This 48 bit number has at most 16 1's and you can define 16 bit number to decide which 1's are white.

Uri

Nice proof, Uri!

Your way of encoding the Pawn structure is actually very similar to a Huffman encoding (but permutated):

encode:
0 empty square
10 white pawn
11 black pawn

and then simply concatenate these encodings in the order af the squares they belong to. For a position with 16 pawns (and 32 empty squares of the 48 relevant squares) that requires 32+2*16 = 64 bits. With fewer pawns, fewer bits are required.

Your way of ordering the bits is actually more convenient for deriving the key in an engine that uses bitboards, as it can use the pawn bitboard directly, and only has to add the color information in the 1st and 8th rank bits.

Note that according to Shannon information theory a string of uncorrelated symbols, with frequencies 1/6, 1/6 and 2/3 (such as random permutations of 8 white pawns, 8 black pawns and 32 empty squares) has an information content of SUM p*log_2(p) = (ln 2/ ln 3) - 1/3 = 1.25 per symbol, or 60.078 for 48 symbols. So it should be possible in ~60 bits.

Making use of the fact that there are at most 8 white or black pawns reduces the number of colorations for a given set of 16 pawns from 2^16 to the binomial coefficient 16 over 8 = 12,870. The latter number is expressible in 14 bits.

H.G.Muller wrote:

bob wrote:In crafty I use the same set of Zobrist randoms, since I already have some for pawns to update the actual hash signature, I just use the same pawn values for a separate incrementally-updated pawn hash key. I do not update this key unless a pawn moves or is captured or promotes, so I don't do a lot of "null-updating". I think the branches are much less important than the effect of doing random memory reads that might well not be in L1 or even in L2.

My MakeMove() function already has separate blocks for each type of piece, so only updating the pawn signature for pawn moves has zero mis-predicted branches in my code anyway...

Yes, if the branches are there anyway, you just put the code where it was needed. But in Joker all pieces are handled by the same code. (Which is also good from the viewpoint of I-cache misses.)

Note that the zero updates are very unlikely to be cache misses, as all non-pawns can share the same board-image of zeros. Which is further used by the main hash-key update on any non-capture. So it is likely to be used a lot, and thus always in L1.

But I admit that the L1-residence of the Zobrist random table is one of my worries, which might be one of the reasons why Joker runs like sh*t on a Pentium 4 (with its 8KB L1). A full Zobrist table takes 2x6x64 = 678 longs = 6KB. In Joker I already reduced that by two, by making it 768 normal ints, and using the black entries for the upper half of the key as the low-order half of the white entries, and vice versa. (Unfortunately partly offset by the fact that I distinguish 8 piece types, rather than 6, so that I end up with a 4KB table.)

Perhaps I should switch to the micro-Max scheme, where I only use a table of bytes, combining them into longs by non-aligned access. This reduces the table to 1KB, allowing it to reside permanently in L1 even on a P4.

Nah. Joker runs like sh** on a PIV because the PIV itself is a piece of sh**. My core2 at 2.0ghz is twice as fast (single cpu) as my PIV xeon 2.8ghz. Actually even more factoring in the 64 bit operations. PIV was just a dog from the get-go, until they had time to get the core-2 right...

Well, I won't argue with your classification of the Pentium 4.

But it must be more than that, as I am talking of an equal-hardware situation, where the opponents are also having the handicap of a Pentium 4. And on that machine Joker could not compete with engines that perform ~300 ELO below it on my own Core 2 Duo.

Sven Schüle wrote:apart from the Zobrist key aspect which has already been discussed, I would like to know why you think that this is obvious. Your statement implies that 64 bit are sufficient to enumerate all possible pawn structures with up to 8 white and up to 8 black pawns. Could you explain your assumption?

Other people have already given the exact number. I just took:
- number of ways to place 8 pawns on 48 squares is 48 over 8
- to the power of 2 (for 2 colors, also counting black and white pawn on same square) gives 1,42 * 10^17
- which is less then 1% of 2^64.

EDIT:
This ignores the fact that there can be less then 8 pawns. I did not bother to do an exact calculation, but I felt confident that "there is enough room left". (In deed, the gap can be closed easily, e.g. by adding 8 "offboard squares", leading to 56 over 8.)
/EDIT

To construct a map explicitely, take white_pawns OR black_pawns, bitboard, and use the 16 bits in row 1 and 8 to mark which of the at most 16 pawns are black. However, this is not useful as a hash function.

Onno Garms wrote:- number of ways to place 8 pawns on 48 squares is 48 over 8
- to the power of 2 (for 2 colors, also counting black and white pawn on same square) gives 1,42 * 10^17
- which is less then 1% of 2^64.

Hi Onno and everyone else,

thanks for your answers which gave me the requested enlightenment Tord's Haskell code convinced me most - although I can't disprove Uri, and I believe he's right - because he also cares about all positions with less than 8 pawns for each color. @Onno: this is exactly what makes your answer a little bit suspicious for me, because you assume presence of all pawns. But anyway, it's solved for me now.

EDIT:
Saw your edit now!
/EDIT

Sven

In RomiChess I use only the high 32 bits for the signature and the low 32 bits for the key for both the pawn hash and main hash.

I have never noticed a problem doing it this way.

It performs no different than when I stored the full 64 bits as a signature.

So, 64 bits as a signature is overkill, but, prudent.

Code: Select all

__inline
void PawnStore(s32 val)
{
  u32 i;

  i  = pawnPtr.lo & PAWNMASK;
  pawnHash[i].sig = pawnPtr.hi;
  pawnHash[i].val = val;
}

__inline
s32 PawnLook()
{
  u32 i;

  i = pawnPtr.lo & PAWNMASK;
  if(pawnHash[i].sig == pawnPtr.hi)
    return pawnHash[i].val;
  return NOHASH;
}

Nice script! I am brushing up on my Haskell skills now; it's such a nice language. I don't care for the literate style though, probably because my typical code to comment ratio is too high.

Currently I'm creating a simple log parser using Haskell. Basically, it eats a logfile produced by Prophet after running some test suites and displays the node counts (for starters). Normally I'd do something like that in Perl, but it's a good excuse to dig a little deeper into Haskell. Next I plan to write a script to give me the match results and some stats from PGN (produced by XBoard by running an engine-engine match).

I'm not yet at the point I could write a chess program in Haskell, but I'm thinking about giving it a go one of these days...
Obviously it wouldn't be a competitive program, but it would be a lot of fun I think.

--
James

Tord Romstad wrote:With a single thread, skipping legality checking of the transposition table is in practise 100% safe when you use 64-bit hash keys. The probability of an illegal move from the transposition table is vanishingly small.

Isn't it quite large (~ 1/(2^32))? See the hashing remark in http://en.wikipedia.org/wiki/Birthday_paradox

Or am I interpreting it wrongly?

joseph tadeusz wrote:

Tord Romstad wrote:With a single thread, skipping legality checking of the transposition table is in practise 100% safe when you use 64-bit hash keys. The probability of an illegal move from the transposition table is vanishingly small.

Isn't it quite large (~ 1/(2^32))? See the hashing remark in http://en.wikipedia.org/wiki/Birthday_paradox

Or am I interpreting it wrongly?

With a 64 bit key there are, of course, 2^64 possible "buckets" a chess position can get mapped to. Assuming all mappings are equally probable, then the probability of a collision is just 1/(2^64). That's very very close to zero...

--
James

jswaff wrote:Nice script! I am brushing up on my Haskell skills now; it's such a nice language.

I have somewhat mixed feelings about it. It is very nice for writing small programs for scripting tasks and doing mathematical computations, but for bigger and more complicated programs, it rapidly becomes difficult for non-wizards to reason about the time and space requirements of the programs.

Another problem for me is that I suffer from syntactical diabetes, and therefore can't stand the Haskell syntax. Liskell looks promising, though.

Of course, even if Haskell is not the ideal language for all sorts of practical programming tasks (except for wizard programmers, again), it is a language every serious programmer should study.

I don't care for the literate style though, probably because my typical code to comment ratio is too high.

That's usually the case for me, too. I don't use the literate style very often.

Next I plan to write a script to give me the match results and some stats from PGN (produced by XBoard by running an engine-engine match).

In fact, I have already written such a program in Haskell.

I'm not yet at the point I could write a chess program in Haskell, but I'm thinking about giving it a go one of these days...
Obviously it wouldn't be a competitive program, but it would be a lot of fun I think.

There is at least one program already:

http://www.steffen-mazanek.de/blog/2007/02/haskell-chess.html

I haven't looked at it at all so far, but based on the description it seems to be extremely weak.

Tord