Noob question on Zobrist Hashing and TT

[maksimKorzh]

Hi Guys!

I'm going to implement the very first transposition table in my life basing on this tutorial by Bruce Moreland:
https://web.archive.org/web/20071031100 ... ashing.htm

I don't want to be distracted by incrementally hashing whatever is changing within a position and just hash the position from scratch every time.
(I know it's weird and slows down the performance)

I've been walking through HGM's post "data structures choice for TT" and was really impressed by this quote

In practice the randomness of the Zobrist keys doesn't have to be very good; Zobrist hashing is a very forgiving scheme. People even have tried deriving the keys from just 12 truly random numbers (for the piece types), and derive the keys from those by making 64 bit-rotated versions of those for the squares. This seems to work fine too, even though rotating a bit pattern can hardly be called a good random generator.

So as far as the hashing would be running from scratch I want to make it as fast as possible, so here's a draft of my hashing function:
(assuming bitboard board representation)

Code: Select all

// generate position key
static inline U64 identify_position()
{
    // position key
    U64 position_key = 0ULL;
    
    // hash bitboards
    for (int bb_piece = P; bb_piece <= k; bb_piece++)
        position_key ^= bitboards[bb_piece];
    
    // hash occupancies
    position_key ^= occupancies[white];
    position_key ^= occupancies[black];
    position_key ^= occupancies[both];
    
    // hash side
    position_key ^= side;
    
    // hash enpassant
    position_key ^= enpassant;
    
    // hash castling
    position_key ^= castling;
    
    return position_key;
}

My questions are:
1. Is this gonna work?
2. What would be the limitations?

THANKS IN ADVANCE!

[hgm]

This is not going to work at all. XORing the bitboards of all piece types together just gives you the occupancy. XORing black and white occupancy to that then makes the entire exercise a cumbersome method to generate zero. You end up with something that is the XOR of total occopancy and stm and rights, totally blind to piece type.

[mkchan]

You need to hash random numbers that map to each piece-color-square, to the side to move, to the enpassant square (or file or whatever encoding you use) and to the castling rights (distinct key for each of the 4 possible castling types among KQkq).

Example code:
https://github.com/Mk-Chan/libchess/blo ... #L173-L191
https://github.com/Mk-Chan/libchess/blo ... /Zobrist.h

[mvanthoor]

And, with regard to not wanting to hash incrementally... really bad idea.

I have a function called "checkup()" in my playmove module that creates a hash from scratch and compares to the has currently in the board. They should be the same, or one or more of the incremental updates doesn't work. I use this function for checking and debugging if I change something that could influence the hash calculation.

On my computer, the engine runs perft at about 41 million moves/second, including:
- Incremental hashing
- incremental piece-on-square list
- incremental material count

When I calculate the hash from scratch, performance drops to about 14 million moves/second. That's not trivial; it's a performance drop of almost 67 percent. If you know that an engine (and especially the ones starting out) lose about 80 ELO for each 50% performance drop, your engine will start at a 100 ELO disadvantage against any other engine, because of speed, all other things being equal.

As the Zobrist-scheme is designed to be used incrementally, PRECISELY so you don't have to calculate everything from scratch all the time, I'd just do it incrementally... you are already moving your pieces, setting EP-squares, etc.... just put the Zobrist calculations in there.

[maksimKorzh]

Thanks for all 3 replies!
All are very valuable for me.
This was a noob question remember)

An idea of having checkup() to compare incrementally updated hashes with newly generated is awesome - thanks for sharing!
Now I got a lot of work to do.

[mvanthoor]

checkup() checks everything that is incrementally updated.

At this point:
- Zobrist hash
- Piece lists
- Material count

It just calls init_zobrist(), init_piece_list(), init_material_count() on the board after each move, and then compares the outcome with the incrementally updated values that are in the board. They should be the same.

You should have such a function, because making mistakes in the zobrist hashing is very easy. Just forget an update somewhere, and you're in for it. You won't actually notice it at first, but when you're going to use the Zobrist-keys for transposition tables, your results would be... weird.

That is the reason why I tested the Zobrist keys and the transposition table in the perft function. This function moves through the move tree, and generates known good move counts. If your move generator, make_move and unmake_move are bug free, the numbers should match:

https://www.chessprogramming.org/Perft_Results

If your Zobrist hashing is bug free and you're using a hash table, you should see a huge speed gain, and the numbers perft move counts should still match. If they don't, you have errors in either your Zobrist hashing updates, or in the transposition table functions.

[maksimKorzh]

And, with regard to not wanting to hash incrementally... really bad idea.

I have a function called "checkup()" in my playmove module that creates a hash from scratch and compares to the has currently in the board. They should be the same, or one or more of the incremental updates doesn't work. I use this function for checking and debugging if I change something that could influence the hash calculation.

On my computer, the engine runs perft at about 41 million moves/second, including:
- Incremental hashing
- incremental piece-on-square list
- incremental material count

When I calculate the hash from scratch, performance drops to about 14 million moves/second. That's not trivial; it's a performance drop of almost 67 percent. If you know that an engine (and especially the ones starting out) lose about 80 ELO for each 50% performance drop, your engine will start at a 100 ELO disadvantage against any other engine, because of speed, all other things being equal.

As the Zobrist-scheme is designed to be used incrementally, PRECISELY so you don't have to calculate everything from scratch all the time, I'd just do it incrementally... you are already moving your pieces, setting EP-squares, etc.... just put the Zobrist calculations in there.

Your proofs are unarguable but let me ask one more clarification question:
So if we call your checkup() NOT EVERY move within a movegen but ON DEMAND.
Let's consider this code By Bruce Moreland:

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;
}

int ProbeHash(int depth, int alpha, int beta)
{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

    if (phashe->key == ZobristKey()) {
        if (phashe->depth >= depth) {
            if (phashe->flags == hashfEXACT)
                return phashe->val;

            if ((phashe->flags == hashfALPHA) &&
                (phashe->val <= alpha))

                return alpha;
            if ((phashe->flags == hashfBETA) &&
                (phashe->val >= beta))

                return beta;
        }

        RememberBestMove();
    }

    return valUNKNOWN;
}

void RecordHash(int depth, int val, int hashf)
{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

    phashe->key = ZobristKey();
    phashe->best = BestMove();
    phashe->val = val;
    phashe->hashf = hashf;
    phashe->depth = depth;
}

Now assuming good move ordering and LOTS of nodes reduced we will have say 100 000 nodes to traverse on depth 7
So 100 000 is MUCH LESS compared to the number of nodes traversed in PERFT for depth 8
So we call checkup() (or ZobristKey() according to Bruce Moreland) only 100 000 instead of 100 000 000 000 times
This would be slower, but would it be 60% slower? Please clarify.

Now please let me explain why do I want to avoid incremental updates (I know nobody cares but still):
I'm writing a didactic bitboard chess engine and covering it on youtube for novice auditory.
Now incremental updates of hash keys (even though I have a general idea on how to do this based on VICE implementation) might lead to bugs if not careful and I'm trying to AVOID all the possible pitfalls where it is possible so the viewers can catch the gist but not getting bothered with implementation details.

Now if my engine would give some ELO point handicap to other SAME engines but with incremental updates THIS IS GOOD
because it gives my viewers a prospect to improve engine on their own. So what I'm trying to do can be described as:
THE MINIMAL WORKING IMPLEMENTATION PROVING THE CONCEPT OR IDEA.

And I do sacrifice performance slightly from time to time just to make the code EASIER TO UNDERSTAND and POINTING TO THE GIST of the technique WITHOUT GETTING DISTRACTED on IMPLEMENTATION DETAILS.

I wish I could have an engine fitting the goals described above to learn from it because open source engines we have relying on particular implementation SO MUCH that implementation itself distracts from the gist of techniques.
As far as I didn't yet see an engine that would be as described I decided to make my own so the NOOBS LIKE ME who has BIG ISSUES with UNDERSTANDING "best practices" of implementation ACTUALLY BECOME ABLE to pick up COMPLICATED TOPICS from scratch, so later on they can come here with reasonable questions (not this like noob questions I ask) so you guys can the help them to IMPLEMENT THINGS THE RIGHT WAY.

[RubiChess]

And, with regard to not wanting to hash incrementally... really bad idea.

I have a function called "checkup()" in my playmove module that creates a hash from scratch and compares to the has currently in the board. They should be the same, or one or more of the incremental updates doesn't work. I use this function for checking and debugging if I change something that could influence the hash calculation.

On my computer, the engine runs perft at about 41 million moves/second, including:
- Incremental hashing
- incremental piece-on-square list
- incremental material count

When I calculate the hash from scratch, performance drops to about 14 million moves/second. That's not trivial; it's a performance drop of almost 67 percent. If you know that an engine (and especially the ones starting out) lose about 80 ELO for each 50% performance drop, your engine will start at a 100 ELO disadvantage against any other engine, because of speed, all other things being equal.

As the Zobrist-scheme is designed to be used incrementally, PRECISELY so you don't have to calculate everything from scratch all the time, I'd just do it incrementally... you are already moving your pieces, setting EP-squares, etc.... just put the Zobrist calculations in there.

Your proofs are unarguable but let me ask one more clarification question:
So if we call your checkup() NOT EVERY move within a movegen but ON DEMAND.
Let's consider this code By Bruce Moreland:

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;
}

int ProbeHash(int depth, int alpha, int beta)
{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

    if (phashe->key == ZobristKey()) {
        if (phashe->depth >= depth) {
            if (phashe->flags == hashfEXACT)
                return phashe->val;

            if ((phashe->flags == hashfALPHA) &&
                (phashe->val <= alpha))

                return alpha;
            if ((phashe->flags == hashfBETA) &&
                (phashe->val >= beta))

                return beta;
        }

        RememberBestMove();
    }

    return valUNKNOWN;
}

void RecordHash(int depth, int val, int hashf)
{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

    phashe->key = ZobristKey();
    phashe->best = BestMove();
    phashe->val = val;
    phashe->hashf = hashf;
    phashe->depth = depth;
}

Now assuming good move ordering and LOTS of nodes reduced we will have say 100 000 nodes to traverse on depth 7
So 100 000 is MUCH LESS compared to the number of nodes traversed in PERFT for depth 8
So we call checkup() (or ZobristKey() according to Bruce Moreland) only 100 000 instead of 100 000 000 000 times
This would be slower, but would it be 60% slower? Please clarify.

Why do you compare 100000 position in an alphabeta depth 7 search with 100000000000 positions in a perft test when arguing about incremental or full hash calculation? perft is only for testing the move generator for correctness and there you don't need the hash so you _could_ leave out even incremental hash calculation completely for a (little) faster perft.

But in alphabeta search you probably do a TT lookup for every of your 100000 position (see the call to ProbeHash at the beginning of your AlphaBeta). So the hash needs to be correct for every position. So your "ON DEMAND" is in fact "EVERY MOVE" (you make). And 100000 incremental hash updates are faster than 100000 full hash calculations, that's for sure.

Incremental updates are quite trivial, only for castle moves, en passant captures and double pawn pushes you have to be careful.

Regards, Andreas

[mvanthoor]

Your proofs are unarguable but let me ask one more clarification question:
So if we call your checkup() NOT EVERY move within a movegen but ON DEMAND.

...

Now assuming good move ordering and LOTS of nodes reduced we will have say 100 000 nodes to traverse on depth 7
So 100 000 is MUCH LESS compared to the number of nodes traversed in PERFT for depth 8
So we call checkup() (or ZobristKey() according to Bruce Moreland) only 100 000 instead of 100 000 000 000 times
This would be slower, but would it be 60% slower? Please clarify.

As Andreas says below, you can't compare this. Obviously doing a full zobrist calculation in an alpha-beta search has less of an impact than doing this in perft, because alpha-beta does not search all positions. So overall, the engine will not become 60% slower, but there will be an impact.

This is true for anything you calculate on the fly:
- material count
- not keeping a piece list but finding each piece every time you need to move it
- pawn locations, even...

Now please let me explain why do I want to avoid incremental updates (I know nobody cares but still):
I'm writing a didactic bitboard chess engine and covering it on youtube for novice auditory.
Now incremental updates of hash keys (even though I have a general idea on how to do this based on VICE implementation) might lead to bugs if not careful and I'm trying to AVOID all the possible pitfalls where it is possible so the viewers can catch the gist but not getting bothered with implementation details.

In my honest opinion, creating a chess engine is one huge implementation detail; get ONE thing wrong, and it either doesn't work at all, it plays poorly, or incorrectly.

Now if my engine would give some ELO point handicap to other SAME engines but with incremental updates THIS IS GOOD
because it gives my viewers a prospect to improve engine on their own. So what I'm trying to do can be described as:
THE MINIMAL WORKING IMPLEMENTATION PROVING THE CONCEPT OR IDEA.

And I do sacrifice performance slightly from time to time just to make the code EASIER TO UNDERSTAND and POINTING TO THE GIST of the technique WITHOUT GETTING DISTRACTED on IMPLEMENTATION DETAILS.

The concepts of an alpha/beta chess engine are quite easy to grasp... it's the implementation details that make creating a good chess engine difficult. Even your use of a 0x88 board is an implementation detail; you don't -need- to check for off-board squares if your move generator keeps moving off the board into account; but then you have to count squares to see if a piece hits the edge or goes over it, instead of just moving it and then noticing it's off the board.

I understand you want to keep this as simple as possible, but as Einstein said: "Make it as simple as possible... but not simpler." You can leave out things such as incremental hashing, piece lists, material count, etc, in the first versions (if you want to), but you should at least mention that it is better to have incremental updates.

I'm leaving out the transposition table in my first version. Heck... maybe I'll even leave out quiescence search. Because I don't have a transposition table, I could have even left out zobrist hashing entirely for now. But I'm of the opinion that there are two kinds of implementations:

1: implement a working routine as fast as possible, as a prototype dummy, to be replaced by 2.
2: implement a routine as best as you can.

Even "the best you can do" might not be the absolute best yet (it probably isn't in my engine), but using a sub-par implementation if that is not absolutely necessary is not the right way to go. (In my opinion.)

I wish I could have an engine fitting the goals described above to learn from it because open source engines we have relying on particular implementation SO MUCH that implementation itself distracts from the gist of techniques.

What you mean is that many open source engines implement LOTS of functions, so it gets very hard to distill the absolute basics from them. I agree. It is not trivial to read the code of an open source chess engine if you have no experience. Therefore I'm creating my engine in stages.

The very first working versions will only have these parts:
- Board (Bitboard representation)
- Move Generator (Magic Bitboard version)
- Clean Alpha/Beta search with NO features except MAYBE quiescence search
- Zobrist hashing (because it's on there already and I'm not going to remove it now)
- Time management (needed for actually playing, and not losing on time)
- UCI interface (and a simple console interface for testing)

So the one and only thing it's going to do is to play (almost) brute force chess, and it'll be very weak. But, the things it can do, are implemented in the fastest/cleanest way I know in Rust at the time of writing.

Then, with each new version, I can add a single function, and describe how it is added, and what effect it will have. That version can test against the previous version, and in a gauntlet tournament with 9 other engines. That way, I can gauge the impact of each added function.

As far as I didn't yet see an engine that would be as described I decided to make my own so the NOOBS LIKE ME who has BIG ISSUES with UNDERSTANDING "best practices" of implementation ACTUALLY BECOME ABLE to pick up COMPLICATED TOPICS from scratch, so later on they can come here with reasonable questions (not this like noob questions I ask) so you guys can the help them to IMPLEMENT THINGS THE RIGHT WAY.

I understand your idea; I try to do exactly the same thing with regard to my engine. Still I think that building an overly simple implementation is not the right thing to do, because such an engine will become very hard to maintain in the future.

One thing I've seen is that you sometimes have very big functions with lots of indentation levels; in one of your video's I noticed clashing global variables. Those things are caused by trying to keep the implementation as straightforward as possible, but in the end, they make the code harder to reason about.

[hgm]

I think it is didactically bad to ignore incremental update. It is one of the most basic techniques, and teaching how to debug it by means of comparison with the slow 'from scratch' value is fundamental too.

My engine Inferno very heavily relies on incremental techniques: not only for board, piece-square eval and Zobrist key, but (far more complex) for view-distance tables, attack maps, piece clustering, pawn walls, mobility... I have a routine to calculate all that from scratch, and compare it with the incrementally obtained values. In the debugging phase of the code I did that in every node. Which slows things down more than a factor 100. But I couldn't have made the code error-free without it. Now that I believe the code to be bug-free, I only do the comparison in the first few ply of the tree.