Increase performance of make move, unmake move and move generation functions

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Post Reply
eligolf
Posts: 114
Joined: Sat Nov 14, 2020 12:49 pm
Full name: Elias Nilsson

Increase performance of make move, unmake move and move generation functions

Post by eligolf »

Hi,

I am creating my own C# bitboard engine from scratch and it is going pretty good so far, much thanks to this forum and other helpful resources.

Since C# is not my main language I would like some advice on how to speed things up in the base of the code, that is the move generation, make and unmake move functions.

Currently I have optimized the logic as far as I could and have gone from around 500 k nodes/s to 1.5 M nodes/s. My questions are:

1. I have the relevant code including bit operation code here: https://onecompiler.com/csharp/3zsymc4eh. I know it is a lot to ask, I would highly appreciate if you had the time to take a rough look at it to see if I make any obvious mistakes that could slow the performance down.

2. Is 1.5 M nodes/s okay for a C# engine for move generation, make and unmake move? I have no reference to what good values are for this langauge.

Thank you so much in advance, and hope I am not asking for too much or it breaks some rule in this forum :)
okidoki
Posts: 17
Joined: Thu Jun 30, 2022 12:46 pm
Full name: Kabir Kumar

Re: Increase performance of make move, unmake move and move generation functions

Post by okidoki »

eligolf wrote: Thu Nov 09, 2023 12:36 pm 2. Is 1.5 M nodes/s okay for a C# engine for move generation, make and unmake move? I have no reference to what good values are for this langauge.
Is this speed of perft? If yes, then it is slow. From preliminary view, it seems that there are few unnecessary conditionals in make and unmake moves.
Also suggest to use struct if the object is compact and has all value types.

I will take another look at this later today if update.
eligolf
Posts: 114
Joined: Sat Nov 14, 2020 12:49 pm
Full name: Elias Nilsson

Re: Increase performance of make move, unmake move and move generation functions

Post by eligolf »

okidoki wrote: Thu Nov 09, 2023 6:18 pm
eligolf wrote: Thu Nov 09, 2023 12:36 pm 2. Is 1.5 M nodes/s okay for a C# engine for move generation, make and unmake move? I have no reference to what good values are for this langauge.
Is this speed of perft? If yes, then it is slow. From preliminary view, it seems that there are few unnecessary conditionals in make and unmake moves.
Also suggest to use struct if the object is compact and has all value types.

I will take another look at this later today if update.
Yes it is perft, in game it is around 800k-1M. Thank you :)
User avatar
lithander
Posts: 881
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Increase performance of make move, unmake move and move generation functions

Post by lithander »

eligolf wrote: Thu Nov 09, 2023 12:36 pm Is 1.5 M nodes/s okay for a C# engine for move generation, make and unmake move?
With perft it's important that you don't compare apples with oranges. Legal movegens are faster than pseudolegal because they can just count the number of legal moves at the leaf nodes without playing them. To further increase the speed you can use transpositon tables, or even multithreading and claim amazing perft speeds.

But that said 1.5M nodes is not very fast for perft even in the most basic of cases. My engine Leorik (also written in C#) computes perft with ~90M nodes per second on a i7-9700K. That's without any tricks: it generates pseudo-legal moves and checks their legality after playing them. And that happens at a rate of playing 90 million legal moves per second. There's no unmake though as I use copy/make.

https://github.com/lithander/Leorik/tre ... orik.Perft
eligolf wrote: Thu Nov 09, 2023 12:36 pm I have no reference to what good values are for this langauge.
We did a little experiment on that a while ago because the general expectation was that managed languages couldn't really compete with C/C++ performance wise. That seems to be true but the difference is much less than many would expect:

Code: Select all

C# version 1.8 with .Net 5
1361558651 Nodes, 22813ms, 59682K NPS

Java version with JDK 17
1361558651 Nodes, 28095ms, 48462K NPS

C version built with GCC via MinGW 64bit (gcc -Ofast -march=native -static)
1361558651 Nodes, 18963ms, 71800K NPS
For this measurement we implemented the exact same algorithm in C#, Java and C and enough experts of the respective languages participated so that it's safe to assume that these implementations are all highly optimized. As you can see C/C++ was only 20% faster than C# at the time of measurement. Here's the repo: https://github.com/lithander/QBB-Perft
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
mathmoi
Posts: 286
Joined: Mon Mar 13, 2006 5:23 pm
Location: Québec
Contact:

Re: Increase performance of make move, unmake move and move generation functions

Post by mathmoi »

lithander wrote: Fri Nov 10, 2023 1:10 pm We did a little experiment on that a while ago because the general expectation was that managed languages couldn't really compete with C/C++ performance wise. That seems to be true but the difference is much less than many would expect:

Code: Select all

C# version 1.8 with .Net 5
1361558651 Nodes, 22813ms, 59682K NPS

Java version with JDK 17
1361558651 Nodes, 28095ms, 48462K NPS

C version built with GCC via MinGW 64bit (gcc -Ofast -march=native -static)
1361558651 Nodes, 18963ms, 71800K NPS
This makes me want to write an engine in C#. I really like C++ and the fact that it is possible to write highly optimized code, but there is a cost in complexity which is not negligible. C# code can be made much clearer and cleaner (in my opinion) than C# code.

A 20% loss in performance is probably around 30-40 ELO. It's important when you want to be the best and compete with Stockfish, but my ambition has never been to develop the best engine. For me it's a hobby and the objective is to have fun implementing and optimizing interesting algorithms and heuristics.

Sometimes I don't enjoy working on my engines because the code becomes complex and I often have to refactor parts of it to simplify them. Although it's normal to have to refactor code, I find that it's much easier for me to write clear and maintainable code in C# (in my professional life) than in C++ (for my chess engines).
User avatar
lithander
Posts: 881
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Increase performance of make move, unmake move and move generation functions

Post by lithander »

mathmoi wrote: Fri Nov 10, 2023 6:59 pm This makes me want to write an engine in C#. I really like C++ and the fact that it is possible to write highly optimized code, but there is a cost in complexity which is not negligible. C# code can be made much clearer and cleaner (in my opinion) than C# code.

A 20% loss in performance is probably around 30-40 ELO. It's important when you want to be the best and compete with Stockfish, but my ambition has never been to develop the best engine. For me it's a hobby and the objective is to have fun implementing and optimizing interesting algorithms and heuristics.

Sometimes I don't enjoy working on my engines because the code becomes complex and I often have to refactor parts of it to simplify them. Although it's normal to have to refactor code, I find that it's much easier for me to write clear and maintainable code in C# (in my professional life) than in C++ (for my chess engines).
Definitely give it a try then, especially if you're using C# professionally! I have been using C# since 2004 and felt like I pretty much hit a ceiling until I started with chess programming. When I tried to push the nps of my chess engine to the limits I picked up quite a few new tricks.

I'm also quite happy with the code quality: Leorik is still clear and maintainable to me. But it's not trivial to make fast code in C#! The compiler will apply much less optimizations behind the scenes than in C/C++ as it is optimized for compilation-speed and a JIT environment. Arrays for example will always have bound checking, Lists and other containers have an entire abstraction layer on top of that. When you rely on the garbage collector you'll pay for it, too. So... how do you manage your data?

And there are a few other things that are inherently more expensive in C# than their C equivalent because C# has safety measures you can't just disable. So just doing literally the same thing you'd do in C++ is often not the fastest way of doing it in C#.

I personally refrain from using 'unsafe' code. But if you're okay with using unsafe you can use C# a bit more like it were C++.

...anyway, give it a try! It's fun! And the speed difference between a naive implementation that uses standard C# patterns and the optimized end result can be mindboggling. (MinimalChess is an example for the former)
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
ericlangedijk
Posts: 15
Joined: Thu Aug 08, 2013 5:13 pm

Re: Increase performance of make move, unmake move and move generation functions

Post by ericlangedijk »

A late reply on this:
I started a chess engine in C# which was reasonably fast. Using the 'new' [ConstExpected] arguments seemed to work reasonably well. But I gave up on it because of the JIT compiler (which makes first runs always slow) and the GC moving memory around, which was extremely frustrating :)
My latest try is progressing now, using Rust, and it is insanely fast. The perft is about 30 percent faster than Stockfish. Search is a long way off still...
Post Reply