Newbie chess program - Hansel

[okidoki]

Dear All,
I am a newbie chess programmer and not so expert in programming as well. (Most of my programming is in web technologies)
I am trying to write a chess program to understand how to code using techniques which efficiently increases the performance.
I have about 5 years of coding experience in C# .NET and I am writing the chess engine in C# as well.

Currently I have written a chess program and in that I have tried to implement known ideas.
As of now it provides correct perft results and when compiled in release mode, it provides about 14-15M nps.

I don't know where but there are .NET chess engines which do much better than this and are about 40-50M nps.
I profiled my code (Instrumentation profiling) and didn't find much, or not able to read the report correctly. One thing for sure realized, inlining everything decreases the performance.

I have used structs as data structure for Move with an intention of having the memory allocated on stack rather than heap.

I would like to request the community to share with me, what is wrongly being done in my code base which is resulting in the gap.

Please find the link to my code base here : https://github.com/frankcastle64/Hansel ... tialCommit

Thanks and have a great day ahead.

[algerbrex]

Hi, and welcome to the chess programming community!

I’m not very familiar with C#, and at the moment I could only manage a quick glance through your code base, but one thing I noticed was a lot of branching logic, depending on the color. I found this kind of branching slowed down my engine quite a bit when I first begin writing it, and using a more color agnostic approach is was not only faster, but made the code shorter and cleaner.

Most of the color agnosticness was achieved by flipping a color bit between 0 and 1, and using it to index different arrays that stored information for white and black at the 0th or 1st index.

Not always possible to avoid color specific logic, but I’ve found in many places it is.

And again, I don’t know C# well but there might be some hidden overhead with creating a move struct versus using just a single integer to store all your move information, including the score.

I’ll try to have more of a look later. In the meantime, good luck!

[okidoki]

Hi, and welcome to the chess programming community!

I’m not very familiar with C#, and at the moment I could only manage a quick glance through your code base, but one thing I noticed was a lot of branching logic, depending on the color. I found this kind of branching slowed down my engine quite a bit when I first begin writing it, and using a more color agnostic approach is was not only faster, but made the code shorter and cleaner.

Most of the color agnosticness was achieved by flipping a color bit between 0 and 1, and using it to index different arrays that stored information for white and black at the 0th or 1st index.

Not always possible to avoid color specific logic, but I’ve found in many places it is.

And again, I don’t know C# well but there might be some hidden overhead with creating a move struct versus using just a single integer to store all your move information, including the score.

I’ll try to have more of a look later. In the meantime, good luck!

Thanks for the reply. To provide more information,

Basically, I am running the fen
[fen]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1[/fen]
at depth of 5 and with current code implementation, I am getting about 14-15 Mnps.

I tried to reduce the conditionals, but to my expectations, it didn't help.
When I profiled the code, it is not conditional statements which is slowing down, but simple assignments and conditionals which are taking time in MakeMove


I find it very surprising for something like this, how can one prevent this?
My hardware is CPU i3-3rd gen and 8GB RAM.
336ms for int sqFrom = (int)(move & MoveEncodingMasks.SQ_FROM_MASK); seems very slow.

[zenpawn]

I would be very happy to achieve a 15m nps perft.

[lithander]

My engine is also written in C# and I have mostly stopped using the Visual Studio profiler because it doesn't deal well with the recursive nature of the search implementation. Instead I basically do a bunch of A/B testing: When in doubt compile two versions and stick with the faster one!

[okidoki]

I would be very happy to achieve a 15m nps perft.

Thanks for the reply @zenpawn, but is it my misconception that higher the raw speed would mean it can efficiently crunch more nodes?
My thought is if I write same evaluation for two engines, then the winning chance for faster engine is higher. Simply put higher NPS, more depth or more time can be spent in the evaluation (where more rules can be parsed).

My engine is also written in C# and I have mostly stopped using the Visual Studio profiler because it doesn't deal well with the recursive nature of the search implementation. Instead I basically do a bunch of A/B testing: When in doubt compile two versions and stick with the faster one!

Thanks for the reply @lithander, I did go through your code and it gets around 30-35 Mnps on my machine.(Pretty impressive)
I cannot find where my implementation has gone slow to give me half the speed than your implementation, especially for instance-based calls( https://github.com/frankcastle64/Hansel ... StaticImpl
).

May I request you to please check my git hub link for quick code-review where this can be optimized.

I have tried the aspects which I could think of like
1. Removal of conditional logic as much as possible. (This didn't speed up at all, verified by profiler.)
2. Converting multidimensional array to jagged array. https://github.com/frankcastle64/Hansel ... dArrayImpl
3. Removing static and making all calls instance based: https://github.com/frankcastle64/Hansel ... StaticImpl

Thanks.

[Chessnut1071]

My engine is also written in C# and I have mostly stopped using the Visual Studio profiler because it doesn't deal well with the recursive nature of the search implementation. Instead I basically do a bunch of A/B testing: When in doubt compile two versions and stick with the faster one!

? are you using a recursive search because it's more convenient or because it's more time efficient. If it's the latter, how much more efficient is it? I'm . toying with the idea

[lithander]

My engine is also written in C# and I have mostly stopped using the Visual Studio profiler because it doesn't deal well with the recursive nature of the search implementation. Instead I basically do a bunch of A/B testing: When in doubt compile two versions and stick with the faster one!

? are you using a recursive search because it's more convenient or because it's more time efficient. If it's the latter, how much more efficient is it? I'm . toying with the idea

If you are dealing with tree data structures the algorithms are usually recursive. So I don't think my choice is uncommon or odd..

A non-recursive implementation is possible where you maintain your own stack and that might be even more efficient in the end. But to me that's less intuitive.

[okidoki]

My engine is also written in C# and I have mostly stopped using the Visual Studio profiler because it doesn't deal well with the recursive nature of the search implementation. Instead I basically do a bunch of A/B testing: When in doubt compile two versions and stick with the faster one!

? are you using a recursive search because it's more convenient or because it's more time efficient. If it's the latter, how much more efficient is it? I'm . toying with the idea

If you are dealing with tree data structures the algorithms are usually recursive. So I don't think my choice is uncommon or odd..

A non-recursive implementation is possible where you maintain your own stack and that might be even more efficient in the end. But to me that's less intuitive.

.
In general the repetitive logic like divide-and-conquer is handled in form of recursion.
Similar to that the tree structure is further divided and is done in recursion, because for all the nodes are part of a tree.
A sub-tree can be part of the bigger tree without losing the structure. Thus recursion seems to be a better idea here and is convenient, well a trade-off for memory overhead, more over the compiler would optimize the code (IMO)

[hgm]

A tree is by nature a recursive (fractal) structure: each node has zero or more children, which each again are a tree.