Zobrist Collisions?

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
hgm
Posts: 27808
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Zobrist Collisions?

Post by hgm »

Sven Schüle wrote:3) If the previous position had an e.p. square set then XOR this (resp. the old e.p. file) to the hashkey

4) In addition to 3), if the new position has an e.p. square set then XOR this (resp. the new e.p. file) to the hashkey.

Think of the special case where both sides make a pawn double step and create an e.p. target square with their move => e.p. square is not *cleared* but *changed* with the second move. For this reason I do steps 3) and 4) independently.
This assumes that you update the hash key incrementally for the e.p. key, which in generally does not make any sense for a transient contribution, because it is both less efficient and more bug prone. When you put down a piece somewhere it makes sense to make that change to the incremental key, because the alternative would be to XOR that piece into the key for many future positions, as the piece is likely to stay there for a long time. So a one-time XOR into the incremental key saves a lot of work. But XORing the e.p. rights into the incremental key only causes that you have to XOR it out again on the next move. So you have actually doubled the work, compared to just XORing it into the actual (as opposed to the incremental) key...

so in my engines I calculate the key as

actualKey = incrementalKey ^ stmKey[stm] ^ castlingKey[castlingRights] ^ epKey[epRights];

where the final term is done in a conditional code section only executed when the move is an e.p. capture (which was needed anyway to displace the capture-square from the to-square).

I also do not treat the castling rights incrementally, despite the fact that they are quite persistent and not volatile like e.p. rights. But there are too many conditions that could change them to make incremental update competative, also because a single move can change rights for both sides (e.g. Ra1xa8). By having the castlingRights flags in the low-order 4 bits of an int, I can simply use its value as an index in the castlingKey table of 16 keys, one for each possible combination of castling rights. MakeMove then only has to worry about updating the rights (by clearing bits from a 'spoiler' table: castlingRights &= spoiler[piece] & spoiler[victim]).

For the side to move it really does not matter if you do it incrementally or when you need it, as in changes on every move, so in both cases you always have to do it once in each node. But in fact I realize now you can get rid of this XOR completely (but none of my enginesis that smart):

The incremental update (for the non-special part of the move) does

incrementalKey ^= zobrist[piece][fromSqr] ^ zobrist[piece][toSqr] ^ zobrist[victim][captSqr]

where usually captSqr =toSqr, and for non-captures victim = 0 (or whatever code you use for EMPTY squares). To have a branch-less implementation I actually do have a board full of Zobrist keys for empty squares, all initialized to 0, so that in non-captures this term is effectively absent. But I could have initialized it to the stm key! In that case the non-captures would automatically handle the stm key. To also have captures handle the stm key, in theory we would have to XOR all Zobrist keys for all pieces also with the stmkey. This contribution would cancel in the part that moves the pieces, because both the from- and to-part would both contain it. In practice, of course, you don't even have to do that, as XORing a table of random values with a constant value does not make it any less random.
User avatar
stevemulligan
Posts: 117
Joined: Wed Jul 20, 2011 2:54 pm
Location: Ottawa, Canada

Re: Zobrist Collisions?

Post by stevemulligan »

actualKey = incrementalKey ^ stmKey[stm] ^ castlingKey[castlingRights] ^ epKey[epRights];
That is the method that I went with. I found it easier that doing everything in Make/UnMake.

This fixed my fen/zobrist mis-matches. The hashes are now 100% unique in the board I'm searching.

I have a new problem now. I can't figure out how to implement transposition tables. They look easy enough on paper but there is something I'm missing because I get a different best move when I turn on TT's using a fixed search depth (5 ply).

What I'm doing is very similar to this page. My engine uses fail-hard also so I expected this to just work.

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    int hashf = hashfALPHA;
 
    if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN)
        return val;
    if (depth == 0) {
        val = Evaluate();
        RecordHash(depth, val, hashfEXACT);
        return val;
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta) {
            RecordHash(depth, beta, hashfBETA);
            return beta;
        }
        if (val > alpha) {
            hashf = hashfEXACT;
            alpha = val;
        }
    }
    RecordHash(depth, alpha, hashf);
    return alpha;
}
The only difference is that I call qsearch at depth 0 instead of a board evaluation. Is storing the result from qsearch the right way to do it?
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Zobrist Collisions?

Post by Desperado »

stevemulligan wrote:
actualKey = incrementalKey ^ stmKey[stm] ^ castlingKey[castlingRights] ^ epKey[epRights];
That is the method that I went with. I found it easier that doing everything in Make/UnMake.

This fixed my fen/zobrist mis-matches. The hashes are now 100% unique in the board I'm searching.

I have a new problem now. I can't figure out how to implement transposition tables. They look easy enough on paper but there is something I'm missing because I get a different best move when I turn on TT's using a fixed search depth (5 ply).

What I'm doing is very similar to this page. My engine uses fail-hard also so I expected this to just work.

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    int hashf = hashfALPHA;
 
    if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN)
        return val;
    if (depth == 0) {
        val = Evaluate();
        RecordHash(depth, val, hashfEXACT);
        return val;
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta) {
            RecordHash(depth, beta, hashfBETA);
            return beta;
        }
        if (val > alpha) {
            hashf = hashfEXACT;
            alpha = val;
        }
    }
    RecordHash(depth, alpha, hashf);
    return alpha;
}
The only difference is that I call qsearch at depth 0 instead of a board evaluation. Is storing the result from qsearch the right way to do it?
Hi Steve,

assuming your technical stuff works proper, you dont have to worry
about different bestMoves/bestScores when enable/disable the TT.

The reason is the virtual depth. Think of this example (fixDepth 4):

line: 1.e4 e5 2.Nf3 Nc6 0.20 -> store into TT
line: 1.e3 e6 2. e4 e5 -> lookup TT 0.20 (3.Nf3 Nc6)

With TT the second line gets the score from 2 virtual additional moves,
although we are at ply 4. So the score may differ which can lead
finally to another score (because of different decisions in the tree), or
even to another move and pv. Most of the time (not always) the
quality of the move,pv will be better than without TT because of the
virtual depth.

Michael
User avatar
lucasart
Posts: 3232
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Zobrist Collisions?

Post by lucasart »

stevemulligan wrote:I've taken "no piece" out of the code. Not sure why I had that in there to begin with. And the random numbers have been regenerated and look much better now. Must have been a Perl bug.

Still getting about 27% of my lookups that do not have matching fen strings. That's a bit better. I will take a look at how Polyglot does it.


old random # generation in Perl (always creates even numbers, very odd! :))

Code: Select all

for &#40;my $i = 0; $i < 2; $i++)
&#123;
 for &#40;my $j = 0; $j < 7; $j++)
 &#123;
   for &#40;my $k = 0; $k < 64; $k++)
   &#123;
   my $x = int&#40;rand&#40;18446744073709551615 ));
   print $x . "\n";
   &#125;
 &#125;
&#125;

Updated to python, these look better:

Code: Select all

import random

for i in range&#40;2&#41;&#58;
 for j in range&#40;6&#41;&#58;
  for k in range&#40;64&#41;&#58;
   print random.randint&#40;0, 18446744073709551615&#41;
Here's what I use:

Code: Select all

U64 rand64&#40;)
// 64 bit LCG, constants from Donald Knuth
&#123;
	static U64 seed = 0ULL;
	return seed = seed * 6364136223846793005ULL + 1442695040888963407ULL;
&#125;
I don't think anything more complicated is useful (perhaps it would be for statistics, but not for zobrist hashing).
I don't know about PERL or Python, but you will need an unsigned int 64 type for computations (you need to do multiplications and additions modulo 2^64).
Also, it's good because it is portable and doesn't rely on what the compiler implementation of "rand" actually does (some are good some aren't, but they are rarely 2^64 periodic)
User avatar
Zach Wegner
Posts: 1922
Joined: Thu Mar 09, 2006 12:51 am
Location: Earth

Re: Zobrist Collisions?

Post by Zach Wegner »

They're all divisible by 65536, in fact. Moral of the story: perl sucks.
User avatar
stevemulligan
Posts: 117
Joined: Wed Jul 20, 2011 2:54 pm
Location: Ottawa, Canada

Re: Zobrist Collisions?

Post by stevemulligan »

Michael Hoffmann wrote: assuming your technical stuff works proper, you dont have to worry
about different bestMoves/bestScores when enable/disable the TT.
Ok, assuming my QS is working then I guess this ok.

[d]3q1rk1/p4pp1/2pb3p/3p4/6Pr/1PNQ4/P1PB1PP1/4RRK1 b - - bm Bh2+; id "WAC.009";

Without TT my best lines look like this:
1 -256 3 38 h4g4
2 -308 14 985 h4g4 f2f3
3 -250 70 4031 d6h2 g1h1 h2f4 h1g1
4 -250 227 14289 d6h2 g1h1 h2f4 h1g1
5 -242 2071 155096 d8f6 f2f3 d6c5 d2e3 d5d4
With TT I get a slightly better score (although my result is still not the "best move" according to the wac.epd)
1 -256 2 38 h4g4
2 -308 14 985 h4g4 f2f3
3 -250 104 7349 d6h2 g1h1 h2f4 h1g1
4 -250 288 17010 d6h2 g1h1 h2f4
5 -233 5350 502722 d8c7 f2f4 h4h1 g1h1 d5d4

I was storing PV in a triangular array so I guess my PV is totally broken now but that should only affect move ordering, not my final score. Judging from some of the posts here retrieving the true PV is going to be tricky.
Zach Wegner wrote: They're all divisible by 65536, in fact. Moral of the story: perl sucks.
Yes, it's my crutch. I should should know better than to do anything math related with it.
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Zobrist Collisions?

Post by Desperado »

It looks like that there is really sth. going wrong collecting your pv.
If you playout the second line you will see that h4h1 would be a blunder.

But on the other hand, after f2f4 the score really maybe about -250.
So indeed, you may have a look on you pv collection code.
Ohterwise such lines are very confusing because you wont know
what is going wrong (the line/moves are broken or the score is
wrong for the line/moves printed)

Michael
User avatar
stevemulligan
Posts: 117
Joined: Wed Jul 20, 2011 2:54 pm
Location: Ottawa, Canada

Re: Zobrist Collisions?

Post by stevemulligan »

If you playout the second line you will see that h4h1 would be a blunder.
I changed my code to pull the PV from the TT (actually I have a 2nd hash just for Exact nodes) I still get the h4h1 blunder.

If it's working fine without the TT code, is it safe to say my TT implementation is broken?

Edit: Should I be storing leaf nodes? My guess is yes, it would save a call to the board eval sometimes, but when I ignore leaf nodes I get the same line as without the TT enabled? Could I have the wrong sign when I store the score for leaf nodes?
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Zobrist Collisions?

Post by Desperado »

How does your pv-collection code works/looks like ?
User avatar
stevemulligan
Posts: 117
Joined: Wed Jul 20, 2011 2:54 pm
Location: Ottawa, Canada

Re: Zobrist Collisions?

Post by stevemulligan »

Before the TT I was collecting during search (when value > alpha)

Code: Select all

triangularArray&#91;rd2&#93;&#91;rd2&#93; = move;
triangularArray&#91;rd2&#93;&#91;rd2&#93;.Score = value;
for &#40;int j = rd2 + 1; j < triangularLength&#91;rd2 + 1&#93;; j++)
&#123;
   triangularArray&#91;rd2&#93;&#91;j&#93; = triangularArray&#91;rd2 + 1&#93;&#91;j&#93;; 
&#125;
triangularLength&#91;rd2&#93; = triangularLength&#91;rd2 + 1&#93;;

After the TT was added, I pull out all the Exact nodes after each iteration of search completes. ( I know I'm missing a check for repetition here but I don't think it's causing problems yet)

Code: Select all

while &#40;true&#41;
&#123;
   if &#40;PVTable.ContainsKey&#40;examineBoard.currentZob&#41;)
   &#123;
      PVTableEntry pv = PVTable&#91;examineBoard.currentZob&#93;;
      Position p = new Position&#40;);
      p.src = pv.src;
      p.dest = pv.dest;
      p.promoteType = pv.promoteType;

      lastLine&#91;lastLineLength&#93; = p;
      lastLineLength++;

      examineBoard.MakeMoveAI&#40;pv.src,pv.dest,pv.promoteType&#41;;
      examineBoard.FindValidMovesAI&#40;);
   &#125;
   else
   &#123;
       break;
   &#125;
&#125;



Storing in the TT is done with this method:

Code: Select all

public static void RecordEntry&#40;ulong key, int score, byte depth, TransTableType type, Position pos&#41;
        &#123;
            TransTableEntry e = new TransTableEntry&#40;);
            e.zob = key;
            e.depth = depth;
            e.score = score;
            e.type = type;

            if &#40;type == TransTableType.Exact&#41;
            &#123;
                if &#40;PVTable.ContainsKey&#40;key&#41;)
                &#123;
                    int omgreplace = 1; //fixme
                &#125;
                PVTableEntry pv = new PVTableEntry&#40;);
                pv.depth = depth;
                pv.score = score;
                pv.src = pos.src;
                pv.promoteType = pos.promoteType;
                pv.dest = pos.dest;
                PVTable&#91;key&#93; = pv;
            &#125;
            
            TransTableEntry o = TransTable&#91;key % TransTableSize&#93;;
            if &#40;o.type != TransTableType.Null&#41;
                if &#40;depth >= o.depth&#41;
                    TransTable&#91;key % TransTableSize&#93; = e;
            else
                TransTable&#91;key % TransTableSize&#93; = e;
        &#125;