Hash move ordering vs. Hash cuts: savings in number of nodes visited

[mvanthoor]

I made a little experiment...

Thanks for this post It seems that my 166 Elo gain in the hash table is within the expected margin. The difference with your 183 Elo gain could be due to the engines, opening books, and time controls used.

Your second test also shows that there is a huge compound effect of features in a chess engine: the hash table has a greater impact if your move ordering is better, and if you have lots of pruning. Thus, my gains when adding Killers/History, and Aspriation Window/PVS, are going to be larger, as compared to adding them without a hash table. If I had done it the other way around, with K / H and A / PVS first, their gains would have been smaller and the one with the hash table would be larger.

So you're also right with your last statement: if a feature doesn't do much, it could be an option to set it aside and implement it again later, because at that point, it could possibly work in concert with a different feature that you didn't have before, and cause lots of gains. Lithander had this compound effect with QSearch / PST's: both had a respectable gain on their own (somewhere between 100-200 Elo), but together, the gain was over 500 points.

[lithander]

The explanation for this two different behaviours resides in the differences between Dumb and Dumber. Dumber uses plain alphabeta, whereas Dumb uses PVS and aspiration windows, ie Dumb practices a lot of re-researches of the same tree, making hash cutoffs more frequent. Move ordering is also improved in Dumb with killers and history tables. Finally Dumb uses a lot of prunings, extensions and reductions that produces deeper searches were transpositions are more likely to occur. All this render the hashtable more efficient in Dumb than in Dumber.

That's really an interesting result! Your findings that hash cutoffs don't provide much benefit in a simple engine but start to really shine in combination with other more advanced search techniques reminds me of the Quiescence Search doesn't improve strength thread.

If you're building your first engine from the bottom up and not start from a rather fully featured engine like yours and make it dumber it's quite tricky to find the combination of features that together will make a significant enough difference in playing strength that they should go into the next release. QSearch & PSTs and MVV-LVA move ordering was the last package I added and it was a game changer. But I'm still experimenting to figure out what's going into version 0.4.

To keep my first chess programming project doable and fun I pledged to make just a very simple, easy to understand engine. By now I think I think I've made it actually harder for me in a way: Now I'm stuck with a slow move generator (albeit nice and easy to understand) and by deciding to skip "complicated" optimization like hash tables I guess it's harder to reach the goal of an engine that plays decent chess, knows how to convert won endgames and so on.

Sometimes I just want to call this project done and start from scratch to optimize for speed and strength like everybody else.
For now I feel bound by my original pledge to be "minimal" and so I always try to look for features that give a lot of strength with only a few lines of hopefully intuitive code. Finding those gold nuggets get's harder and harder though!

[mvanthoor]

Sometimes I just want to call this project done and start from scratch to optimize for speed and strength like everybody else.

Do It!

For now I feel bound by my original pledge to be "minimal" and so I always try to look for features that give a lot of strength with only a few lines of hopefully intuitive code. Finding those gold nuggets get's harder and harder though!

You have everything a minimal chess engine needs. The only two "obvious things" you're missing, are Killer Moves and History Heuristic. Add those. Then you have MVV-LVA, PST's, Best move First, Killer Moves, and History Heuristic. Add 5 sets of PST's to it, with the option of choosing them as a UCI option (with the strongest set as the default), and call it 1.0.

It will be in the lower 1600 range, and it's minimal, with only the basic features, stable, and very usable in that range. That is an accomplishment on its own. To top it off, it's not written in C.

Don't torture yourself any longer. Repeat after me.

"Killers, Heuristics, and Personality is version 1.0 and it will be done." Repeat 10 times. Make 2-3 video's to go along with adding QSearch, PST's, and the Killer/Heuristics, and wrap it up. Everything after this, is already Basics++ (TT, Aspriation windows, PVS), and everything after that is getting into the advanced things already.

Do it and start with the engine you feel you now _really_ want to write, or this will keep nagging every time you write a line of code in MinimalChess.

[Mike Sherwin]

The explanation for this two different behaviours resides in the differences between Dumb and Dumber. Dumber uses plain alphabeta, whereas Dumb uses PVS and aspiration windows, ie Dumb practices a lot of re-researches of the same tree, making hash cutoffs more frequent. Move ordering is also improved in Dumb with killers and history tables. Finally Dumb uses a lot of prunings, extensions and reductions that produces deeper searches were transpositions are more likely to occur. All this render the hashtable more efficient in Dumb than in Dumber.

That's really an interesting result! Your findings that hash cutoffs don't provide much benefit in a simple engine but start to really shine in combination with other more advanced search techniques reminds me of the Quiescence Search doesn't improve strength thread.

If you're building your first engine from the bottom up and not start from a rather fully featured engine like yours and make it dumber it's quite tricky to find the combination of features that together will make a significant enough difference in playing strength that they should go into the next release. QSearch & PSTs and MVV-LVA move ordering was the last package I added and it was a game changer. But I'm still experimenting to figure out what's going into version 0.4.

To keep my first chess programming project doable and fun I pledged to make just a very simple, easy to understand engine. By now I think I think I've made it actually harder for me in a way: Now I'm stuck with a slow move generator (albeit nice and easy to understand) and by deciding to skip "complicated" optimization like hash tables I guess it's harder to reach the goal of an engine that plays decent chess, knows how to convert won endgames and so on.

Sometimes I just want to call this project done and start from scratch to optimize for speed and strength like everybody else.
For now I feel bound by my original pledge to be "minimal" and so I always try to look for features that give a lot of strength with only a few lines of hopefully intuitive code. Finding those gold nuggets get's harder and harder though!

Hi Thomas, I looked at your code. This is just my opinion and nothing more. If one wants to create a toy engine then speed does not matter. If that is your goal then keep on trucking. So you made a pledge to write a "minimal" chess engine. You have tied your hands to an artificial concept. What is minimal? Minimal is one ply + SEE. Or is minimal defined as minimal a/b. Minimal seems to be a moving target depending on what side of the bed one gets up from each morning. And why can't minimal include a hash table? Just put in a minimal hash table! A hash table does not have to have multiple buckets and fancy replacement schemes. They can be one cell and always replace, i.e. minimal.

So now let's talk about your code. First you start with not the fastest of languages. That's fine really. If SF was written in C# it would still be a 3200+ elo engine. But, I do not think anyone would do that because what purpose would it serve? If you are going to downshift and take a hard left turn and start over are you going to stay with C#? That sounds sub optimal. On the other hand if there was a compiler that compiled extended C# to native code then that would make sense for chess. That compiler is Beef. Won't mention that again.

Code: Select all

        static readonly int[] KING_FILE = new int[8] { -1, 0, 1, 1, 1, 0, -1, -1 };
        static readonly int[] KING_RANK = new int[8] { -1, -1, -1, 0, 1, 1, 1, 0 };

Two pointers means two registers used. Why not one structure that would only use one pointer?

Code: Select all

static Attacks()
        {
            long t0 = Stopwatch.GetTimestamp();

            for (int index = 0; index < 64; index++)
            {
                ...
            }    
            

Unmodified TSCP is already a minimal engine and everyone hates this approach that TSCP uses because even though TSCP is written in C it is dirt slow. So if any minimal chess engine scans the entire board for pieces it is going to be hated at least in part. As it is sounding, even by yourself. So, if I were you (and I'm not) I would do something minimal to optimize this like have u64 piece[wtm]. Each bit of piece[wtm] is a piece on the board.

Code: Select all

  u64 pieces = piece[wtm];
  do { } while (pieces);

The Attacks() function to me looks like it should be an initiation for a vector magnitude table. In which for each square, each direction there is a magnitude 0 to 7 depending on the square and piece type. There can even be a type like capture only, move only, capture or move. That would allow pawns to handled by the same code that sliders are handled by.

So with just a couple of small additions you can have a screaming fast minimal engine.

Just my two pence.

[lithander]

"Killers, Heuristics, and Personality is version 1.0 and it will be done." Repeat 10 times. Make 2-3 video's to go along with adding QSearch, PST's, and the Killer/Heuristics, and wrap it up. Everything after this, is already Basics++ (TT, Aspriation windows, PVS), and everything after that is getting into the advanced things already.

Sounds like plan! Only that instead of personalities I'm going to look into auto-tuned tapered evaluation! I hope that I can generate something comparable in strength to the PeSTO tables because these fix all my issues with converting won endgames it seems.

So you made a pledge to write a "minimal" chess engine. You have tied your hands to an artificial concept. What is minimal? Minimal is one ply + SEE. Or is minimal defined as minimal a/b. Minimal seems to be a moving target depending on what side of the bed one gets up from each morning.

Can't say I disagree with anything you said there!

My original plans where to stop at the state of the last of my videos. Fixed 4-ply depth alpha-beta search with material counting evaluation. But at that point the engine just didn't play very good chess. And my goals shifted when I joined this community and learned about engine-vs-engine ranking lists and how hard it is to find good, well maintained engines in the 1000-2000 ELO range to play against. I wondered if I couldn't just fix the most obvious blunders so that the minimal engine would still be small and simple but also play decent chess. And both version 0.2 and 0.3 are not quite there yet but they at least make good sparring partners in their respective elo range I think.

As a definition for minimal your "minimal a/b" idea isn't a bad start. 'b' would be the amount and complexity of the code and 'a' would be the strength of the engine in ELO.

If, in an attempt to be as objective as possible, I compare my engine with other C# engines through Visual Studio's "analyze code metrics" feature than I receive better scores regarding maintainability and cyclomatic complexity. They may have the stronger engine but for 50% more ELO they had to write 500% more code. Code that is also more difficult to understand.

So isn't the attempt of making an engine that plays some solid chess at ~2000 ELO (and thus can beat myself and most other human players) that is open source under a very permissive license (MIT) and implemented in a way that is relatively easy for a human mind to follow, not a worthy goal?

If anyone thinks it should be faster you can fork it and make it faster! You wouldn't even have to open source your improved version.

Code: Select all

static readonly int[] KING_FILE = new int[8] { -1, 0, 1, 1, 1, 0, -1, -1 };
static readonly int[] KING_RANK = new int[8] { -1, -1, -1, 0, 1, 1, 1, 0 };

Two pointers means two registers used. Why not one structure that would only use one pointer?

The code you're looking at is run only once at startup. So it's performance doesn't matter. It just generates a few kb of lookup tables so that I can look up for every piece and it's current square what other squares it can move to. That's exactly like your magnitude table only that I store the actual square indices so they don't have to be generated in a for-loop in the actual move generation code. I don't think magnitude tables and for loops that still have to add positions + directional offset at runtime would be faster but if you think so I may give it a try just to be sure.

The Attacks() function to me looks like it should be an initiation for a vector magnitude table.

So in summary... that's what it already is?!

Unmodified TSCP is already a minimal engine and everyone hates this approach that TSCP uses because even though TSCP is written in C it is dirt slow.

Well, I only hate it because it sometimes stalls in cutechess-cli when I play 1000 games and then I have to restart the test. I don't care about it's speed or implementation because I deliberately picked it because it plays at MinimalChess's current strength.

So, if I were you (and I'm not) I would do something minimal to optimize this like have u64 piece[wtm]. Each bit of piece[wtm] is a piece on the board.

Interesting suggestion! But how exactly would I iterate over the bits? Isn't that where you need compiler intrinsics like _BitScanForward? I guess whether it makes sense for MinimalChess depends on that detail.

But I like it because it doesn't make the board instance much fatter, wich would be bad because I have no move-undo and make new instances whenever I play a move. And it's based on a simple enough concept!

If you are going to downshift and take a hard left turn and start over are you going to stay with C#? That sounds sub optimal. On the other hand if there was a compiler that compiled extended C# to native code then that would make sense for chess. That compiler is Beef.

I'm still not really sure how much slower C# would be if I took a performance-oriented approach. So I think I would start with implementing a bitboard move generator and something like perft again to figure out how much slower C# actually is compared to C/C++. At that point it would also be interesting to see how to compile that code with Beef and how fast that would be.

Just my two pence.

Thanks for taking the time and I appreciate your critical eye!