Move generator advice

[RedBedHed]

Christian,

Can't wait! I'll be so proud if I can just get it to beat me lol.

[RedBedHed]

I can definitely see how knowing the stack frame would help with debugging...

[RedBedHed]

I figured out how to do the .gitignore, Jost. Thanks for that tip.

[RedBedHed]

Henk,

Interesting! I was taught that depth is one of the most important factors... I definitely need to read more about this.

[JVMerlino]

John, I'll admit I was very nervous trying these positions. I thought I had a new bug for a second, but it turned out that my definition of the en passant square isn't quite Forsyth's definition lol. I adjusted my FEN parser, and I am very, very happy to say that the move generator passed every one of these test positions !

Excellent! Yes, getting your engine compliant with various "standards" is important if you want to formally and thoroughly test your engine. If you haven't implemented the UCI or XBoard communication protocol yet, you will need to do so eventually.

Congratulations on an absolutely 100% correct move generator!

[JVMerlino]

Christian,

Can't wait! I'll be so proud if I can just get it to beat me lol.

That is the first great moment for all of us. Of course, it helps to be a terrible chess player. Good Luck!

[Henk]

Only need to implement alpha beta algorithm + material count + small random value and it will be able to beat a 1600 player.

O wait you need to implement quiescence search as well. I don't know.

[RedBedHed]

John,

Thank you! I will look into UCI as soon as possible. It won't be too hard then haha.

Henk,

It would probably take a 4-ply alpha-beta search to beat me.

[RedBedHed]

I learned a second ago how to use intrinsics (built-in hardware instructions) for bit scan forward (a hot function). For clang and gcc (__GNUC__) the specific intrinsic is "__builtin_ctzll()." By controlling the flow of compilation with macros to use this intrinsic (which works with my compiler+machine), another 0.1 second was shaved off of the initial perft(6).

These are the updated initial perft results for my i5 machine:

perft(1) - 0.000 seconds - 20 nodes visited.
perft(2) - 0.000 seconds - 400 nodes visited.
perft(3) - 0.000 seconds - 8902 nodes visited.
perft(4) - 0.000 seconds - 197281 nodes visited.
perft(5) - 0.016 seconds - 4865609 nodes visited.
perft(6) - 0.406 seconds - 119060324 nodes visited.

I'm updating the github repository now

[lithander]

I don't know how extensive your set of perft test positions is already but I remember that the testsuite from
http://www.rocechess.ch/perft.html uncovered a few last issues with my move generator when I thought I had it bugfree already.

In chess programming it's quite easy to introduce subtle bugs and inefficiencies that do not complete break your engine but just make it play slightly worse and these bugs are hard to fix because you don't even suspect them to be in there.

So I found using testsets really useful to test all the assumptions I'm making about my code and what it should do.

For example if you have min-max-search implemented and you want to do the next step and implement alpha-beta then, if correctly implemented, the result of your search should be always exactly the same. But you should have to visit far less nodes. That's the assumption and you can make sure that your program meets it: With a set of test positions, if you search them to a fixed depth with both versions of the program the principal variation should stay the same on each position while the number of visited nodes goes down significantly. Sometimes your assumptions were wrong, sometimes your code was buggy - but in both cases you get to correct something and are better off than before! And if your assumptions were met you are rewarded by a feeling of security that you have indeed made another step forward!

If you can come up with a way to test something for correctness outside of actual play (which is the ultimate test of course, play thousands of games against a variety of other engines. But it takes... so... much... time.) it's probably always worth the extra mile to implement that test.