if statement and calculation faster than constant

[mvanthoor]

The author of that article employed some highly sophisticated algorithms including magic bitboards to achieve that, while I didn't do much beyond simple BB LUTs and clang -Ofast to similar results. The only problem is my perft(6) is 119060974...

Until you get the perft counts 100% correct, you can't make any assumption with regarding to the speed of your engine. If you don't have castling, you're omitting two calls to square_attacked(); you need to see if your king is in check, and the square next to the king is not attacked. If you don't do promotions, you omit adding four pieces to your move list; this will obviously make add_move() faster. Without castling and promotions you get less positions to perft through, so you're calling make/unmake less often, which will also mean you call even less square_attacked() less often (you need to check somehow if your move is legal; if you have less moves, you need to check less).

make(), unmake(), square_attacked(), and add_move() are the top four functions used when running perft. Not generating all the possible moves gives you a huge speed advantage.

My advice would be to first finish your move generator and THEN compare with other engines or perft tools.

Oh, and perft needs to be checked in other positions than only in the starting position... search for 'perftsuite.epd' on the internet, and look at this as well: https://www.chessprogramming.org/Perft_Results

Especially the "kiwipete" position catches a lot of mistakes in move generation. I thought my move generation and make/unmake were perfect at the beginning, and I _STILL_ forgot one edge case (one that I have never seen in an over the board game played by myself), which thus gave wrong perft results.

And make no mistake; if your perft results aren't perfect, your engine might very well, at some point, make an illegal move in an engine match and then the GUI will kill it and award the win to your opponent.

[leanchess]

So yes, I'm using 'clang', in the sense that both Rust (rustc) and C (clang) compile to LLVM.

Silly me. Of course it's LLVM.

In that case, I believe Rust's having comparable performance should hardly come as a surprise (unless you have some performance-impacting features like exceptions enabled).

Yes. My perft 7 runtime is now down to 86.xx seconds on my system (i7-6700K), and this is:

- Without hash/transposition table
- Without bulk counting of leaf nodes (full make/unmake)
- Without special "in check" move generators and such

- WITH full chess implementation (promotions, castling)
- WITH incremental Zobrist hash updates
- WITH incremental piece list updates (location of each piece on the board)
- WITH incremental material balance update (material count for each side)

Now I am impressed, although I fail to see the reason for updating Zobrist keys when hashing is disabled.

[Terje]

Now I am impressed, although I fail to see the reason for updating Zobrist keys when hashing is disabled.

He isn't trying to make a perft software, but a chess engine, so he wants the fastest perft (movegen+make/unmake) that still lets his engine actually search when he gets to implementing that part

I've looked at your makemove/takemove code. (Second time I actually looked into another chess engine after FabChess.)

First time after implementing the move list pool, it was almost, but not quite, a direct copy of FabChess' implementation (without me ever having seen it before).

Now, your makemove/takemove, and my make/unmake functions are basically twins, allowing for differences because of mine being Rust and yours being C. Our programming style and even naming seems to be the same as well.

If I have both functions open in VSCode, it's actually possible for me to be looking at yours and it'll take a few seconds for me to realize it :X

If the rest of your engine is as readable as takemove/makemove, then I congratulate you on a job well done. I hope you will take a look at Rustic Alpa 1 when it comes out. It'll be the base-line version; weak, feature-deprived, barely able to play, but written and commented like a literary work. (I hope... because I'm not the one judging this.)

Thank you, I've put a lot of effort into cleaning up the code. I will definitely be taking a look at Rustic when it releases

[mvanthoor]

Now I am impressed...

Thanks I'm rather pleased to be able to optimize the move generator, make/unmake and square_attacked() to this point.

It's my first chess engine*, and my first non-trivial piece of software in Rust.

(Actually, second... but the first was like 25 years ago written when I was a teenager, in Turbo Pascal. It played legal chess... eh... most of the time, slightly better level than completely random moves. It only had a text interface. And then I was stuck, because no internet, and no books on subjects like this in my local library. Writing a *real* chess engine has been on my bucket list since then, and I actually started in August 2018. I wrote the FEN-string parser, and then life happened. I only seriously picked it up again somewhere in the first week of Febuary.)

... although I fail to see the reason for updating Zobrist keys when hashing is disabled.

Perft is not only a tool to see how fast the bare engine runs in a brute force search. It is mainly a diagnostic tool. First and foremost, the visited number of leaf nodes has to be 100% correct or everything else you do is useless, because in that case, you're playing games under the constant threat of making an illegal move. Second, perfting runs the engine through a lot of positions. So, you can have it incrementally update stuff in makemove:

- Piece lists
- Material count
- Zobrist hashing

All of those things need an initial state. When you start the engine, you have a function called create_piece_list(), create_material_count(), create_zobrist_key(). They create those things from scratch for the pieces in the starting position, and you can verify BY HAND that the creation is correct.

Now, when running the perft function, you do the incremental updates throughout make_move(), and at the very end of make_move(), you call those create_* functions, doing the calculation from scratch (for the position that is the result of make_move()). If you did your incremental updates correctly, each of the values that are now in your board should be the same as the values you just created.

This way, you can verify that your incremental updates are working, and you take those create_* functions out of make_move() again.

Every time you change ANYTHING in either your move generator or in make_move() or unmake_move(), or in your board representation or lists, you'll have to run perft and the check for the incremental updates again on many positions to verify that everything is still correct. If you don't, you can just as well do nothing at all, IMHO.

And, I'm going to implement a hash table for use in the engine obviously, and therefore I need a Zobrist key. (I actually already HAVE the hash table, and I tested that in Perft as well, with 80%+ speedups. I took it out for the very first baseline version of the engine. It'll be one of the first things to return again after the engine can play.)

[mvanthoor]

Also, the speed progression from the time I started up until now (with reports split over several threads in this forum, on different subjects...)

Perft 7, starting position:
277 seconds (superfluous memory allocation -> replace with move list pool)
114 seconds (start optimization rounds here..., such as replacing vectors with counter-backed struct arrays)
104 seconds (start code cleanup/optimization here)
100 seconds
94 seconds
90 seconds
86 seconds

Some of these speed gains came about through discussion in those threads, and me learning some stuff with regard to several subjects that I hadn't encountered during my research (yet).

And I also got to fix two bugs in the process with regard to the incremental updates of zobrist hashing and material table.

All of the speed gains were by replacing / changing costly code with faster options, removing as many if/else checks as possible, and re-ordering if-statements in such a way that the option that would short-circuit it the soonest comes first.

For example, if you have a very costly if-check like this:

if (... && function() && ... && test() && ... && ... && moving_piece == KING) { ... }

It could mean that the entire chain needs to be evaluated, and then it cuts short if it's not the king that's moving. If you replace it with this:

if (moving_piece == KING && ... && ... && ... && .... && ... && ... ) { ... }

the program might very well get a lot faster, because the king rarely moves during most of the game.

At least, optimizations such as these were simple, and they did work for this engine.

[leanchess]

All of those things need an initial state. When you start the engine, you have a function called create_piece_list(), create_material_count(), create_zobrist_key(). They create those things from scratch for the pieces in the starting position, and you can verify BY HAND that the creation is correct.

Now, when running the perft function, you do the incremental updates throughout make_move(), and at the very end of make_move(), you call those create_* functions, doing the calculation from scratch (for the position that is the result of make_move()). If you did your incremental updates correctly, each of the values that are now in your board should be the same as the values you just created.

This way, you can verify that your incremental updates are working, and you take those create_* functions out of make_move() again.

Thanks for the tip, I'll use it.

Now, I must say that I had a complete promotion implemented at one point, but just hated to see the execution times go up.

I'd like to share my promotion implementation idea. I'm probably reinventing the wheel here, but just in case anyone is unaware, there it goes.

I don't remove a pawn from the pawns' BB when it reaches its last rank. Instead, I AND the pawns' BB with 0x00FFFFFFFFFFFF00 during pawns' move generation, and with its complement during that of knights, rooks, bishops and queens. The same trick is performed during check detection, and perft returns 4 instead of 1 in case a previous move was a promotion.

Hopefully this helps fellow hobbyists (and doesn't introduce additional bugs to that troubled implementation of mine).

[leanchess]

P.S. I should really pay more attention to the Chessprogramming Wiki. I just implemented Kernighan's trick, and my perft(7) got down to 37 seconds with fancy promotions (no castling yet).

[leanchess]

(Magic) bitboards aren't an especially fast way to do perft.

Speaking of the devil...

[mvanthoor]

P.S. I should really pay more attention to the Chessprogramming Wiki. I just implemented Kernighan's trick, and my perft(7) got down to 37 seconds with fancy promotions (no castling yet).

I haven't looked at the Kernighan trick yet (didn't know about it). However... are you trying to write the fastest perft program possible, or a chess engine? There are many tricks one can employ to speed up perft, but which would be very detrimental in a chess engine. For example, bulk counting of leaf nodes.

If you have a legal move generator so you don't need to check move legality, you can just generate the moves at ply 1, and add all the moves at once without having to make/unmake them to check them for legality. This creates huge amounts of speedup in perft, because you are omitting a great number of make/unmake calls. To accomplish this, you need to move the legality test from perft into the move generator. You need to check for move legality somewhere, somehow. For perft, it doesn't matter if you do it in the move genrator, or in make_move(). The point of making the move generator legal, is specifically to be able to do the bulk counting and being able to omit the make/unmake call at depth 1.

This is perfect for a perft program, but detrimental for a chess engine.

The reason is that the legality check is now in the move generator. You are checking legality for EVERY move, even moves that are possibly never searched in the alpha/beta search. Let's say you generate 30 moves in a position, and the engine is searching. At the fourth move in the list it comes to the conclusion... "This is it! I don't need to search any other move!" ... and then makes it. In that case, you have wasted legality checks for 26 moves, because they're never searched.

So, a legal move generator is very good for perft, and not very good for a chess engine... and the same goes for some other 'perft tricks'. It's therefore very important to know if you're writing a perft tool, that has only one purpose; find the correct number of moves as fast as possible, or if you're writing a chess engine, that is using perft as a diagnostics/testing tool to find bugs (in incremental updates, for example), or for optimizing functions such as make() and unmake().

[Terje]

You need to check for move legality somewhere, somehow. For perft, it doesn't matter if you do it in the move genrator, or in make_move().

A third possiblity is to have a function which checks the legality of a move without making it. SF uses this in search before making the move so there is no chance it needs to be taken back immediately after making it, and the same could be used to get something closer to bulk counting. This could be a speedup of perft depending on how expensive it is to compute, and, since SF uses it, probably good for the chess engine part.