Noob question on Zobrist Hashing and TT

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Mike Sherwin
Posts: 43
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Noob question on Zobrist Hashing and TT

Post by Mike Sherwin » Thu Sep 10, 2020 6:53 pm

I get the intent of the endeavor and it is a noble intent. But, poor performance is sort of a drag. Take TSCP for example, many have initially learned chess programming as it is open source. It does not have many features and is a snail when it comes to performance. Yet it serves it's purpose. However, there are enhanced versions of TSCP by others that Tom has put on his website. In 2004/5 I sent him a simple bitboard move generator version. Someone added a hash table and null move version. And other versions also. Maybe take a look at a few of the various versions and plan your engine from those.

No4b
Posts: 23
Joined: Thu Jun 18, 2020 1:21 pm
Location: Moscow
Full name: Alexander Litov

Re: Noob question on Zobrist Hashing and TT

Post by No4b » Thu Sep 10, 2020 8:25 pm

maksimKorzh wrote:
Thu Sep 10, 2020 10:12 am
mvanthoor wrote:
Thu Sep 10, 2020 9:32 am
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.
As far as i remember, when i did Debug of the hashtable for my chess variant engine, even not incrementally updated table grant you some speedup, althought very minor.
At the same time although i understand that you want mostly to introduce ideas to your audience,
IMHO one of the most basic concepts of a chess engine is that speed is matters VERY much (like you can get +50-100 elo just from reordering
operators in the code).
Even if you adamant on the writing hashtable without incremental updates, I think it would be a good idea to revisit this part in the later video
both to show importance of speed for the chess engine and to show one of the easiest ways to do it.

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Noob question on Zobrist Hashing and TT

Post by maksimKorzh » Thu Sep 10, 2020 8:28 pm

Ok guys. You're right.
I will learn to incrementaly update zobrist keys and then try to implement basic TT.

Please forgive me my approach but that's the only accetable way to learn for me. I wish I could catch the gist from one take straight ahead like you do.

Well at least I can say that depth 6 was the highest available for me for years - I was so dumb that couldn't understand how to improve it (copyasting wouldn't make any sense). Now I hit depth of 9 for 2-3 seconds only thanks to the approach so many people giving critics to.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

User avatar
mvanthoor
Posts: 319
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Noob question on Zobrist Hashing and TT

Post by mvanthoor » Thu Sep 10, 2020 10:28 pm

maksimKorzh wrote:
Thu Sep 10, 2020 8:28 pm
Please forgive me my approach but that's the only accetable way to learn for me. I wish I could catch the gist from one take straight ahead like you do.
Oh no... that's not true. Most people writing chess engines are not geniuses and don't "get it" by just looking at some code.

I've written my own chess engine in the 90's, using a book that only explained concepts and had pseudo-code in it. (Actually, I gave it to a second hand book store just a few months ago.) The program that came from that endeavor only reached depth 3 or 4 on the computers of the day. It got clobbered by my old table top dedicated computer... which, nowadays, gets clobbered by *me* on its strongest tournament level. And I'm not THAT great of a player.

Since the 90's I've been thinking about writing my own chess program from scratch, but there was always something else to do... so I postponed it... again and again. When I discovered Rust, I liked the language enough to try and write something in it... and so the chess program popped up again.

I've been at this stuff for over a year now, writing code, testing, concluding that my engine is SLOW compared to other bitboard engines... so back to finding bottlenecks, rewriting some function here and there, then updating Rust and rewriting more stuff to take advantage of new features in the programming language.

Because I also have a job and a normal life, this is done in bursts; mainly july-august 2019, febuary-april of 2020, then in May it became too difficult next to my job because of the cataract, and now I'm slowly resuming development again. First order of business was to get to know my code again, and clean up and re-order some stuff. Along the way I hit a snag with Rust having a huge performance regression in version 1.45.2 due to different handling of some construct I wrote... so I had to change it.

That is done now, and the engine is now close to as clean and fast as I can get it. The next thing will be to reactivate its console interface, so I can have an interface to put moves into, and see output; then I need to write the search, uci interface, and an evaluation.

Therefore, don't think that people on here just get this stuff on the first take. I certainly didn't. Some people on here have been programming chess engines for FIFTY YEARS; some of them got a Ph.D. for developing techniques we now take for granted. You can't just 'get that' in a few weeks if you're starting out from scratch.

You have a one up on me: one of your engines is already playing. It may not be fast, or strong, but it plays. Mine doesn't. We're taking different paths. Your path obviously is to write an engine, then write a better one, and an even better one. My path is to write a single engine, and I keep chipping at the functions bit by bit until they are as clean and fast as I can get them, before I move on to the next one. (And I might even go back to improve the code further.)

Which is the better way? Both are the best way.

Some people want to have their own engine play, and as quickly as possible, so they just write the code and if it works it works. If the engine isn't fast or strong, that's no problem; they just write a new one that's better. That's you.

Other people start writing an engine, and start testing as soon as possible. They discover that the engine is slower in perft than other engines using similar techniques, and they're disappointed. Then they start optimizing until the engine is as fast or faster as the ones they're testing against, and the code is as clean as it gets. That's me.

In the end, we probably go through the same iterations and the same learning process, and it will probably take a similar amount of man hours with regard to writing code. In the end, will probably end up with one engine you like enough to call "your" engine and develop that further and further, and abandon the earlier attempts. The amount of code I have reverted or just deleted is probably just as much as all of your previous engines put together.
Well at least I can say that depth 6 was the highest available for me for years - I was so dumb that couldn't understand how to improve it (copyasting wouldn't make any sense). Now I hit depth of 9 for 2-3 seconds only thanks to the approach so many people giving critics to.
As you can see, you're improving. If you can write a chess engine, you're not stupid. It's not trivial, even if all the information is out there, and it's lots of work. You're not stupid: you're just not very experienced yet. (My own experience also only spans a year, but I get the impression that I've been programming much longer than you are; so it may make writing fast and more maintainable programs easier, not chess programming itself.)

Be prepared for the fact that this stuff is addicting, and that your engine is never good enough. I know mine won't be. Even Stockfish isn't good enough, as it has just improved by about 80 ELO :P

===

By the way: is your engine Wukong able to run Perft from the command-line? I may run it on my computer to compare with my own engine. If you wish, you can compile and run Rustic if you have Rust version 1.46 installed. (Latest stable version.) The Github repo is here:

https://github.com/mvanthoor/rustic

You can compile the engine with:
cargo build --release

(This won't compile for your specific CPU. I'd need to know the exact CPU model to give you the correct flags.)

You can run Perft as follows:
./rustic -p 7

(Perft depth 7 on the starting position.)

Or:
./rustic --fen "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -p 6

(Perft 6 on what you call the "tricky position"; also known as "Kiwipete" from the CPW.)

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Noob question on Zobrist Hashing and TT

Post by maksimKorzh » Sat Sep 12, 2020 7:49 am

mvanthoor wrote:
Thu Sep 10, 2020 10:28 pm
maksimKorzh wrote:
Thu Sep 10, 2020 8:28 pm
Please forgive me my approach but that's the only accetable way to learn for me. I wish I could catch the gist from one take straight ahead like you do.
Oh no... that's not true. Most people writing chess engines are not geniuses and don't "get it" by just looking at some code.

I've written my own chess engine in the 90's, using a book that only explained concepts and had pseudo-code in it. (Actually, I gave it to a second hand book store just a few months ago.) The program that came from that endeavor only reached depth 3 or 4 on the computers of the day. It got clobbered by my old table top dedicated computer... which, nowadays, gets clobbered by *me* on its strongest tournament level. And I'm not THAT great of a player.

Since the 90's I've been thinking about writing my own chess program from scratch, but there was always something else to do... so I postponed it... again and again. When I discovered Rust, I liked the language enough to try and write something in it... and so the chess program popped up again.

I've been at this stuff for over a year now, writing code, testing, concluding that my engine is SLOW compared to other bitboard engines... so back to finding bottlenecks, rewriting some function here and there, then updating Rust and rewriting more stuff to take advantage of new features in the programming language.

Because I also have a job and a normal life, this is done in bursts; mainly july-august 2019, febuary-april of 2020, then in May it became too difficult next to my job because of the cataract, and now I'm slowly resuming development again. First order of business was to get to know my code again, and clean up and re-order some stuff. Along the way I hit a snag with Rust having a huge performance regression in version 1.45.2 due to different handling of some construct I wrote... so I had to change it.

That is done now, and the engine is now close to as clean and fast as I can get it. The next thing will be to reactivate its console interface, so I can have an interface to put moves into, and see output; then I need to write the search, uci interface, and an evaluation.

Therefore, don't think that people on here just get this stuff on the first take. I certainly didn't. Some people on here have been programming chess engines for FIFTY YEARS; some of them got a Ph.D. for developing techniques we now take for granted. You can't just 'get that' in a few weeks if you're starting out from scratch.

You have a one up on me: one of your engines is already playing. It may not be fast, or strong, but it plays. Mine doesn't. We're taking different paths. Your path obviously is to write an engine, then write a better one, and an even better one. My path is to write a single engine, and I keep chipping at the functions bit by bit until they are as clean and fast as I can get them, before I move on to the next one. (And I might even go back to improve the code further.)

Which is the better way? Both are the best way.

Some people want to have their own engine play, and as quickly as possible, so they just write the code and if it works it works. If the engine isn't fast or strong, that's no problem; they just write a new one that's better. That's you.

Other people start writing an engine, and start testing as soon as possible. They discover that the engine is slower in perft than other engines using similar techniques, and they're disappointed. Then they start optimizing until the engine is as fast or faster as the ones they're testing against, and the code is as clean as it gets. That's me.

In the end, we probably go through the same iterations and the same learning process, and it will probably take a similar amount of man hours with regard to writing code. In the end, will probably end up with one engine you like enough to call "your" engine and develop that further and further, and abandon the earlier attempts. The amount of code I have reverted or just deleted is probably just as much as all of your previous engines put together.
Well at least I can say that depth 6 was the highest available for me for years - I was so dumb that couldn't understand how to improve it (copyasting wouldn't make any sense). Now I hit depth of 9 for 2-3 seconds only thanks to the approach so many people giving critics to.
As you can see, you're improving. If you can write a chess engine, you're not stupid. It's not trivial, even if all the information is out there, and it's lots of work. You're not stupid: you're just not very experienced yet. (My own experience also only spans a year, but I get the impression that I've been programming much longer than you are; so it may make writing fast and more maintainable programs easier, not chess programming itself.)

Be prepared for the fact that this stuff is addicting, and that your engine is never good enough. I know mine won't be. Even Stockfish isn't good enough, as it has just improved by about 80 ELO :P

===

By the way: is your engine Wukong able to run Perft from the command-line? I may run it on my computer to compare with my own engine. If you wish, you can compile and run Rustic if you have Rust version 1.46 installed. (Latest stable version.) The Github repo is here:

https://github.com/mvanthoor/rustic

You can compile the engine with:
cargo build --release

(This won't compile for your specific CPU. I'd need to know the exact CPU model to give you the correct flags.)

You can run Perft as follows:
./rustic -p 7

(Perft depth 7 on the starting position.)

Or:
./rustic --fen "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -p 6

(Perft 6 on what you call the "tricky position"; also known as "Kiwipete" from the CPW.)
Sorry for late reply.
I've been re-reading this post many times already. It's very inspiring. Thank you so much for being so heart-opened.
Some people want to have their own engine play, and as quickly as possible, so they just write the code and if it works it works. If the engine isn't fast or strong, that's no problem; they just write a new one that's better. That's you.
Yup, that was me for years but after starting chess programming youtube channel something has changed. I mean when starting sharing your experience with others it opens a highway for your own growth e.g. I've just discovered what everybody does - stealing... ahh, sorry, getting inspired by the ideas from the open source engines and this is completely a new level for me because for years all of my attempts were doomed to no more 1500 ELO points while now I'm starting to understand how things work (at least regarding search). So if I can teach people to UNDERSTAND ideas from other engines and embedd them into their own this would already be good. And quite a fun thing that with this new "skill" I now feel that I can change/improve literally any part of my current engine. I was starting new engine evry time just because couldn't maintain the previous, couldn't change it much and also when I just started I was more addicted to various board representations and movegeneration techniques rather than search & eval.

Code: Select all

By the way: is your engine Wukong able to run Perft from the command-line?
No it doesn't and I wouldn't call it a chess engine as well because even though it's capable of playing versus other engines still there's a great lack of standard functionality.

Perft results:
Wukong runs perft depth 6 with optimization flags for about 21 second
BBC(my current, covered on youtube): runs perft 6 with optimization flags for about 7 seconds.
Both use exactly the same make move function, the only difference is that BBC uses pre-calculated attack tables and magic bitboards for sliding pieces, so pure lookup, no calculations. But anywat there're LOTS of things to improve which I would probably be covering on youtube after the initial release so that people could see not only the process of initial implementation of an engine but also the development progress. I would still keep it as didactic as possible, with global variables everywhere it's possible and modularity (so you can likely take away a single part, say move ordering and replace it with a more effective one WITHOUT touching move generator or search). After I've started researching open source chess engine's code (my new cool skill!) I've realized that even though there're LOTS of engines ther're only a few PATTERNS the are following and within a single patters there might be only a couple of unique ideas. So as far as new engines are doomed to clone those patterns I would at least like follow some GUIDELINES to make it TRULY DIDACTIC and MODULAR. At least I have not yet seen an engine doing implementing the approach I'm promoting, I'll be happy to find one like that some day)
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

User avatar
mvanthoor
Posts: 319
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Noob question on Zobrist Hashing and TT

Post by mvanthoor » Sat Sep 12, 2020 12:34 pm

maksimKorzh wrote:
Sat Sep 12, 2020 7:49 am
Sorry for late reply.
I've been re-reading this post many times already. It's very inspiring. Thank you so much for being so heart-opened.
Thanks :) No problem; I have quite some experience in programming (studied computer science and I'm a software engineer by profession), but with regard to actual chess programming, my experience is limited to about a year.
Yup, that was me for years but after starting chess programming youtube channel something has changed. I mean when starting sharing your experience with others it opens a highway for your own growth e.g. I've just discovered what everybody does - stealing... ahh, sorry, getting inspired by the ideas from the open source engines and this is completely a new level for me because for years all of my attempts were doomed to no more 1500 ELO points while now I'm starting to understand how things work (at least regarding search).
We (at least, most of us, I think) don't "steal" code; but we do learn from open source engines and implement idea's from other engines. You can't have missed how fast the NNUE networks have spread from the first tentative implementation in a Shogi engine, to chess engines, and now even to Stockfish.
So if I can teach people to UNDERSTAND ideas from other engines and embedd them into their own this would already be good. And quite a fun thing that with this new "skill" I now feel that I can change/improve literally any part of my current engine. I was starting new engine evry time just because couldn't maintain the previous, couldn't change it much and also when I just started I was more addicted to various board representations and movegeneration techniques rather than search & eval.
Starting new engines is good in the beginning, to get a feel for what you want to do, and you learn from the mistakes you make. At some point however, you'll have to decide on an approach (mailbox, bitboard, etc...) and stick with it, because otherwise, you'll be doing work over and over and over again. There's a point where you're experienced enough to implement a good move generator, so all your implementations will be good. Making one after the other becomes a waste of time from then on. It gets more productive to keep improving the engine you have.

(I actually decided to not go forward with the VICE-like mailbox engine I started with, but turn it into a magic bitboard engine from the get-go. So I started writing the bitboard move generator, and at some point, the engine was actually half mailbox and half magic bitboard...)
Perft results:
Wukong runs perft depth 6 with optimization flags for about 21 second
BBC(my current, covered on youtube): runs perft 6 with optimization flags for about 7 seconds.
Rustic runs perft 6 on the starting position in 2.96 seconds, on an Intel i7-6700K, single-threaded, with no hash and no perft-only move generator tricks such as bulk-counting. (But there are many engines that are still faster...)
Both use exactly the same make move function, the only difference is that BBC uses pre-calculated attack tables and magic bitboards for sliding pieces, so pure lookup, no calculations. But anywat there're LOTS of things to improve which I would probably be covering on youtube after the initial release so that people could see not only the process of initial implementation of an engine but also the development progress.
I look forward to that :) After the first version of my engine is finished, I'll have book to write...
I would still keep it as didactic as possible, with global variables everywhere it's possible and modularity (so you can likely take away a single part, say move ordering and replace it with a more effective one WITHOUT touching move generator or search).
You're going to get into problems if you keep using global variables, and very long functions with many indentations. My recommendation would be to keep variables as local as possible, and make functions as small as possible.

In fact, I have just feature-gated some functionality in my engine. (It means that the feature can be disabled or enabled at compile time.) The engine contains a module called "wizardry", which has a function that can generate magic numbers; so people can see where those numbers in the move generator come from. It also has a testing-module, that runs a huge PERFT-test on 172 well-known and known-good positions.

Those features don't have to be in the final engine; they only need to be compiled if I'd change something in the move generator somewhere and I either need new magic numbers, or need to test the move generator change. See, building without and with "extra" features:

Code: Select all

$ cargo build --release
   Compiling rustic v0.1.0 (C:\Code\rustic)
    Finished release [optimized] target(s) in 9.26s

Marcel@WORKSTATION MINGW64 /c/Code/rustic
$ ./target/release/rustic.exe -w
error: Found argument '-w' which wasn't expected, or isn't valid in this context

USAGE:
    rustic.exe [OPTIONS]

For more information try --help

Marcel@WORKSTATION MINGW64 /c/Code/rustic
$ cargo build --release --features extra
   Compiling rustic v0.1.0 (C:\Code\rustic)
    Finished release [optimized] target(s) in 9.10s

Marcel@WORKSTATION MINGW64 /c/Code/rustic
$ ./target/release/rustic.exe -w

Engine: Rustic Alpha 1
Author: Marcel Vanthoor <mail@marcelvanthoor.nl>
Description: UCI Chess Engine, written in Rust
Finding magics for: Rook
a1:       324259726147719720u64 (offset:      0, end:   4095, attempts: 11340)
b1:      1170944767933030402u64 (offset:   4096, end:   6143, attempts: 56287)
c1:       468427139954245960u64 (offset:   6144, end:   8191, attempts: 44740)
d1:      1224988994322960384u64 (offset:   8192, end:  10239, attempts: 100879)
... and so on.
I can easily extend this to the "comm" modules: uci, xboard, and console. Then users can actually decide if they want to compile the engine with all the communication protocols available and then select them with "rustic -c uci" or "rustic -c xboard", or they can decide to compile only the "uci" module if they don't intend to use anything else.

This can be achieved because most stuff is local to the module that uses it. The only things that are global to all modules is the stuff that needs to be global, such as piece types, square types, precalculated bitwise operations (BB_SQUARES, BB_RANKS, BB_FILES in my case); stuff that's used EVERYWHERE.
After I've started researching open source chess engine's code (my new cool skill!) I've realized that even though there're LOTS of engines ther're only a few PATTERNS the are following and within a single patters there might be only a couple of unique ideas. So as far as new engines are doomed to clone those patterns I would at least like follow some GUIDELINES to make it TRULY DIDACTIC and MODULAR. At least I have not yet seen an engine doing implementing the approach I'm promoting, I'll be happy to find one like that some day)
Yes, alpha/beta-engines have been researched for about 60 (!) years now. There have been many refinements, approaches, and implementations during that time, but at some point, the best ones obviously stick around. (There have also been many different implementations of bitboards, of which "fancy magic bitboards" are the fastest at this point. Or maybe PEXT bitboards, but they only work well on newer Intel CPU's.) It's no surprise you're finding those patterns and idea's in most engines.

With regard to modularity... my engine is already on the verge of being able to choose communication protocols while starting, and one could even decide to compile them into the engine or not. If I'd extend this approach to the board representation, move generator, and evaluation, the engine could actually choose among them when starting. (And in the case of evaluations, even switch on the fly.) I don't know if I will ever do that. But it can be done.

One of the engines that did something like this in the past (containing several bitboard implementations in a single engine) is Elephant:

https://www.chessprogramming.org/Elephant

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Noob question on Zobrist Hashing and TT

Post by maksimKorzh » Wed Sep 16, 2020 4:01 pm

Hi guys

I've implemented init & set hash key functions.
Could you please kindly look if they are error free?
NOTE: get_random_U64_number() would generate SAME numbers regardless of environment because is based on custom PRNG - the same one I used to generate magic numbers candidates for magic bitboards. Is that ok?

Code: Select all

// random piece keys [piece][square]
U64 piece_keys[12][64];

// castling keys [bits]
U64 castle_keys[16];

// enpassant keys [square]
U64 enpassant_keys[64];

// side to move keys
U64 side_keys;

// init hash keys (with random U64 numbers)
void init_hash_keys()
{
    // loop over piece codes
    for (int piece = P; piece <= k; piece++)
    {
        // loop over squares
        for (int square = 0; square < 64; square++)
        {
            // init piece keys
            piece_keys[piece][square] = get_random_U64_number();
        }
    }
    
    // init side to move keys
    side_keys = get_random_U64_number();
    
    // loop over board squares
    for (int square = 0; square < 64; square++)
        // init enpassant keys
        enpassant_keys[square] = get_random_U64_number();
    
    // loop over castling keys
    for (int index = 0; index < 16; index++)
        // init castling keys
        castle_keys[index] = get_random_U64_number();
}

// generate unique position key
U64 generate_hash_key()
{
    // final key
    U64 hash_key = 0ULL;
    
    // piece bitboard copy
    U64 bitboard;
    
    // loop over piece bitboards
    for (int piece = P; piece < k; piece++)
    {
        // init piece bitboard copy
        bitboard = bitboards[piece];
        
        // loop over bitboard pieces
        while (bitboard)
        {
            // get piece square
            int square = get_ls1b_index(bitboard);
            
            // hash pieces
            hash_key ^= piece_keys[piece][square];
            
            // reset LS1B
            pop_bit(bitboard, square);
        }
    }
    
    // hash side to move
    hash_key ^= side;

    // loop over board squares
    for (int square = 0; square < 64; square++)
        // if enpassant square available
        if (enpassant != no_sq)
            // hash enpassant square
            hash_key ^= enpassant_keys[square];
    
    // hash castling
    hash_key ^= castle_keys[castle];
    
    // return final key
    return hash_key;
}
THANKS IN ADVANCE!
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Post Reply