Advice on optimizing my move generation

[spirch]

Kind of surprised anybody (other than ratings list folk) bother to download my engine at all. But not surprised the old version gave that number. I didn't have a 64-bit computer back then and was too lazy to do perft tests that would go past 32 bits. Hell, the biggest number in my perft test is still <1B nodes.

I'm curious and I like to find new stuff or see by myself how thing are running
when you said about 3 minutes for you and my result was a little bit over 5 minutes, i wanted to see what result i would get

my engine is in c# and when i think about it i don't really have any "real" speudo move generation code, all my code are doing actual legal move (funny thing is one of the method is called speudomove... it's not)

I'm not sure if that is a good thing or a bad thing in the end

I do have a big one dimensional boolean array that can tell me if a piece can move from X to Y on an empty board but i don't think this can described as pseudo move?

in any case, right now I'm not going any alpha/beta / or any kind of ai code because doing it on my current engine would be a waste if I finally decide to go bitboard

[spirch]

to come back to OP

profling is always key, every time I take a long break and come back and make another profiling run, I always find a new thing to optimize. just now the KiwiPete depth 6, you can see earlier today how long it was taking vs now

Code: Select all

Time Taken       : 296,939ms
Moves per second : 27,048,140

that is around 7.5% improvement and when i think about it, i should have seen the issue by myself and somehow I didnt

profiling don't, generally, lie

[pedrojdm2021]

My engine is in C# Too. My move generator does your perft test in ~700ms

to boost your move generator i recommend:
1) use bitboards + magicbitboards
( if you don't know how to do this, i highly recommend the youtube channel of @maksimKorzh aka "Chess programming" in youtube, he has a playlist of Making an engine in C where he explaints it and a lot more very well)

2) you need a pseudo legal move generator, generating all the "legal moves" on the fly can be very expensive if you are not very experienced in this world, some people uses "pin rays" for pinned pieces for example, but if you don't know how to do that in a optimal way your performance will end up worse than just generating pseudo legal moves and inside make move check if the movemeny is legal or not (basically an "in check" in the code, if he move ends up with your king in check, it was illegal, so you undo your move and then return false)

3) try to avoid heavy data structure for each move, for example in my move generator i only use 18 bytes for each move
(6: square from, 6 square to, 4 promotion, 1 is_castling, 1 is_capture) = 18
a move is en-passant if your pawn target square is equals to your en-passant square in your board.

4) try to avoid sub-classes in your classes, boxing, and unboxing are evil.

5) Jagged arrays (int[][]) are faster than multi-dimensional arrays (int[,])

6) be careful with static data, that stuff in C# can lead you to memory leaks, so be careful with that. C# static data are NOT deleted by garbage collector.

7) try to avoid as much as you can complex math operations, for example to store your players indexes, do that with 0 and 1, so you can easily swap players using the xor (^) operator.

[spirch]

by the way, my perft 4 for kiwipete is about 150ms

you can see that it's all over the place depending on the implementation / person

at the end of the day, like other have previously said, move generator is not the key for high rating but accuracy is a must, when you are happy with what you have, you can move to the next step

[mvanthoor]

Kind of surprised anybody (other than ratings list folk) bother to download my engine at all.

I download and test other people's engines if I think they are interesting at some way, but I don't want to have to go and hunt for the code and/or the binaries. Put some links in your sig, that'll help.

===

To OP: Also take into account that incrementally keeping data, when the pieces move, slows down perft.

At first, I added all the PST-values from scratch in the evaluation function, but that is slow. I moved to calculating the initial values at startup, and then keep them incrementally as the pieces move. (Same for the Zobrist keys by the way.) Perft doesn't need either the incremental evals, or the zobrist keys.

The next version of my engine is going to have a tapered evaluation, so I'm going to keep a second set of PST's, also incrementally The first set took about 4 million nodes/sec off my perft speed (40 Mnps -> 36 Mnps). I expect that the next set will also take 4 miillion nodes off (32 Mnps), and I'll lose some speed due to also keeping the game phase (maybe drop down to 31 or 30 Mnps).

I could take those out (or write seperate functions for perft) to raise perft speed... but it doens't do anything for the chess engine. The important thing is that keeping the values incrementally lightens the evaluation function tremendously; this is important, because it's the most called function in the engine in the end. (It's called for all the leaf nodes for each depth.)

I also don't take them out because I can run my engine in debug mode, and then check if the incremental values that are kept during the movement of the pieces, are the same as values created from scratch. That way, I can assure I have no bugs in my incremental updates. (For Zobrist, MG PST tables, EG PST tables, and the game phase.)

Before you proceed with the rest of the engine, get perft correct. Then get the naked speed (keeping nothing incrementally) as high as possible to optimize your move generator and make/unmake functions. Then, let it be... expect perft speed to drop as soon as you start keeping things incrementally during piece movement. "Naked" perft speed is important, because it tests the efficiency of your move generator, make/unmake functions, and, even more importantly, their correctness. Beyond that, perft becomes either a debugging tool, or a tool to ensure that your engine is working correctly. (Eric Madsen goes to the extreme end by having perft actually use his search function. That will cause a very slow perft, but a very high confidence of search correctness.)