I'm currently developing a bitboard-based chess engine for fun and can generate around 5.5 million positions per second on perft tests. I ran the same tests on Stockfish, which can do around 130 million positions per second. What is it that makes Stockfish (and other engines) so much faster?
5
-
1Probably wrong here. It is best to ask this at talkchess (talkchess.com/forum3/index.php), it is a regular chess coders forum, there some good ones are hanging around and they like to answer that. Consider posting some source code from you, otherwise really nobody knows what you really want.– user27863Commented May 28, 2021 at 8:09
-
1Might be interesting for you: Parallel processing for Stockfish link.springer.com/chapter/10.1007/978-3-319-93713-7_40– Hauke ReddmannCommented May 28, 2021 at 18:37
-
7Other than following @adrasthea advice of posting this question in talkchess, you should try to improve it. In which language have you written your engine? What's your level of expertise at this language? Are you sure its move generator is bug free? Are you testing both engines under the same conditions? (it doesn't make sense to compare no parallelized and parallelized engines) Can you show your code?– emdioCommented May 29, 2021 at 8:10
-
Classical bitboard implementations involving linear scanning are a far cry from Magic bitboards. It's a looong rabbit hole. Have you read for example rhysre.net/fast-chess-move-generation-with-magic-bitboards.html?– BaseZenCommented May 29, 2021 at 21:51
-
Do you use bulk counting? I.e. do you make and unmake the "leaf" moves? I would guess Stockfish does not in perft, which makes it a lot faster than one might otherwise expect. (so for the last ply of perft it is enough to count the number of generated moves, you don't necessarily need to make and unmake each one)– koedemCommented Sep 12, 2023 at 19:18
Add a comment
|
3 Answers
There are a number of reasons. The Main one is its aggressive Alpha Beta pruning and late move reductions.
To explain a bit further. AB Pruning is a search algorithm which basically cuts out the number of nodes in its search tree. How it works is it stops evaluating when it determines and proves the move to be worse than another examined moves.
Late move reduction is a slightly harder concept but it again searches the "tree" more efficiently. It does this by effectively diving down a "algorithmically" more probably tree.
If I remember the release paper correctly the elo for Stockfish 14 is 3350 +/-5% and that was based off a 4 threaded CPU.
In short there are the implementation of mathematically proven formulae to do with pruning infinite possibilities to the most correct, whilst also searching deeper down the most probably correct line.
-
4This seems to be an answer for a different question. The question was, how Stockfish achieves such a fast move generator and consequently perft speed, not how it reaches such a big depth.– koedemCommented Sep 12, 2023 at 19:13
-
Programmatically you could return all legal moves in a fraction of a second and wouldn't need an engine at all. You need to stop and think about the function of a engine. Its role IS to determine the BEST result as FAST as possible. This is done by AB Pruning , late move reduction. Both are critical for how Stockfish returns accurate results so fast...not just its "depth"– DheebsCommented Sep 15, 2023 at 7:02
-
That is not what the question asks though. The question does not ask how Stockfish is so strong, it asks for how its move generator is so fast. How its search or evaluation works is completely irrelevant for that question. The question even gives exact numbers of perft speeds to specify that the question really is only about the move generator and the make_move function, there's no ambiguity there.– koedemCommented Sep 15, 2023 at 7:40
Perft speed can be affected by:
- Coding language - for example, compiled vs interpreted.
- Bulk counting - whether you un-make leaf nodes - I believe SF doesn't do this, which makes it significantly faster.
- How your move generator works - for example, whether it performs legality checks on the generated moves.
- Whether you're using CPU or GPU for move generation.
- CPU speed/frequency.
- CPU multi-processing - for example, whether your perft is single-threaded or multi-threaded.
- CPU cache size.
- Which position you're using for perft.
Without knowing these variables, it's hard to say whether your perft numbers are reasonable or not.
As an example, my single-threaded C# magic bitboard code does perft from the standard starting position at around 100 million nodes per second on a single core of a Ryzen 5950X processor.
5.5 million moves per seconds is very decent I would say. Enough to make a 2700 or 2800 rating engine with a good evaluation function. I made a bot without any bitboard and got to around 2.5-3.5 knps and managed to beat 2300-2400 bots on chess.com with a mediocre evaluation function. 130 million positions per second is 100% for multi threading bots. No way you can achieve that with only one core. I knew an a version of minmax with multithreading but I don't really suggest implementing it since it quite hard to get it right.
-
1I agree that 5.5 MN/s is a decent search speed, however, the question was about perft specifically, which only measures the speed of your move generator (and first and foremost its correctness) without any evaluation or other search "overhead". For that 130 million moves generated per second does sound possible on one core.– koedemCommented Sep 12, 2023 at 19:16