Development of Shen Yu

[AAce3]

Hey everyone,
I'm currently writing a chess engine called Shen Yu, written in rust. It's not open source because I haven't put in the work to document it that well (And I'm somewhat of a novice at the language ), but rest assured that when I have time I will end up doing so.

Shen Yu is currently just a legal move generator, and it sort of has built-in selective move generation already (i.e., my "Move" type has a built in capture flag, so I just decided to generate captures and quiets spearately). It hits 140 Mnps on perft 7 from starting position with bulk counting, 45 Mnps without on my old laptop.

The eventual goal is for Shen Yu to become a MCTS/Alpha-Beta hybrid engine, i.e. the expansion phase of MCTS will involve some form of alpha-beta search. I have a lot of ideas I want to try for that, but first I will need to implement the alpha-beta part.I'm not planning to release Shen Yu until after I've implemented most of the basic ideas (LMR, NMP, History, etc. etc.), the reason being that I just don't have that much time.

I'm currently a high school, and am applying for college soon, so updates and posts may be infrequent.

This thread is really just a brain dump where I can toss ideas that I want to try. I woud love any kinds of feedback and suggestions.

Huge thanks to Blunder, Rustic, Leorik, BBC, and many other wonderful open source engines for having such excellent readable code and useful comments. I have never really used C or C++, so having lots of useful comments is so helpful (And why I want to make sure my code is well document it before I make it open source ). And, huge thanks to the chess programming wiki. You all have made some really wonderful stuff.

[AAce3]

In most implementations that I've seen, the MVV-LVA 2d-matrix is indexed by the victim first, then the attacker. I'm really curious as to why that is - is there a specific reason for why this works better, or is it just for convenience?

[lithander]

The eventual goal is for Shen Yu to become a MCTS/Alpha-Beta hybrid engine, i.e. the expansion phase of MCTS will involve some form of alpha-beta search. I have a lot of ideas I want to try for that, but first I will need to implement the alpha-beta part

Sounds interesting! I'm looking forward to read your Devlog.

And I was happy to hear that you found Leorik code to be an inspiration! It's not open-source (there's no license) but you can take all ideas you like as long as you don't create a Leorik fork and make it public.

[Mike Sherwin]

In most implementations that I've seen, the MVV-LVA 2d-matrix is indexed by the victim first, then the attacker. I'm really curious as to why that is - is there a specific reason for why this works better, or is it just for convenience?

A MVV-LVA 2d-matrix is terminology that I am unaware of. Is it from the CPW or an open source engine? I guess that a 2d lookup table with precomputed values would be faster than looking up two values and then computing the difference. I can't see a reason that the order of the indices would matter. Good luck with your engine.

Does your Perft() make and unmake leaf node moves?

[AAce3]

In most implementations that I've seen, the MVV-LVA 2d-matrix is indexed by the victim first, then the attacker. I'm really curious as to why that is - is there a specific reason for why this works better, or is it just for convenience?

A MVV-LVA 2d-matrix is terminology that I am unaware of. Is it from the CPW or an open source engine? I guess that a 2d lookup table with precomputed values would be faster than looking up two values and then computing the difference.

Yeah, from what I can tell it's a somewhat common idea.

Does your Perft() make and unmake leaf node moves?

When bulk counting is on, no. Since the move generator is completely legal, I just count the length of the movelist when the depth reaches 1. The speed difference between bulk counting and no bulk counting is kind of ridiculous (roughly 0.8 seconds for perft 6 from startpos with bulk counting, 2.5 seconds without, so nearly 150 MNps versus 45 Mnps) but the bulk counting method feels kind of cheat-y. I only used it to speed up debugging. I borrowed Leorik's perft test suite and that finished in a few minutes, whereas it would take much longer without bulk counting.

[Mike Sherwin]

The reason I asked is because I do not know how to compare my Perft() to others. My Perft() uses no tricks and makes and unmakes the leaf nodes as well. It is pseudo legal so an InCheck() is needed. It only runs at 30Mnps in the starting position which seems poor compared to 45Mnps. Is this just a case of apples and oranges or is my code not as fast as I thought.

[AAce3]

The reason I asked is because I do not know how to compare my Perft() to others. My Perft() uses no tricks and makes and unmakes the leaf nodes as well. It is pseudo legal so an InCheck() is needed. It only runs at 30Mnps in the starting position which seems poor compared to 45Mnps. Is this just a case of apples and oranges or is my code not as fast as I thought.

I'm not sure. Perhaps you just need to compile it differently?

Maybe copy-make is just faster. But, the disadvantage is that during search I will probably have to deal with a more expensive task of determining which piece on square, e.g. for MVV/LVA.

[hgm]

In most implementations that I've seen, the MVV-LVA 2d-matrix is indexed by the victim first, then the attacker. I'm really curious as to why that is - is there a specific reason for why this works better, or is it just for convenience?

I never use a 2d lookup table for that. Calculating the index for such a table is already as expensive as calculating the result. I just use the piece value minus the piece (or type) number. Or, in a really fast design, I never calculate such a key at all, but use a move generator that spits out the captures in MVV/LVA order. (By looping through a piece list stored in MVV order, and extracting the attackers of each piece there from the set of its attackers in LVA order.)

The fastest way to do someting is not do it at all.

[AAce3]

In most implementations that I've seen, the MVV-LVA 2d-matrix is indexed by the victim first, then the attacker. I'm really curious as to why that is - is there a specific reason for why this works better, or is it just for convenience?

I never use a 2d lookup table for that. Calculating the index for such a table is already as expensive as calculating the result. I just use the piece value minus the piece (or type) number. Or, in a really fast design, I never calculate such a key at all, but use a move generator that spits out the captures in MVV/LVA order. (By looping through a piece list stored in MVV order, and extracting the attackers of each piece there from the set of its attackers in LVA order.)

The fastest way to do someting is not do it at all.

I suppose you are right.
To make sure mvv-lva aligns with SEE I would think that something like

Code: Select all

value[attacker] > value[victim] ? see() : value[attacker] - (value[victim] / 2);

cheap to calculate, and accounts for recaptures. At least, that's what I'm doing in Shen Yu for now. I will probably experiment with different values other than 2.

[hgm]

You would need a larger divisor than 2 to get MVV/LVA order. 8 will do. In Fairy-Max I use victim itself, instead of value[victim], because it represents pieces by type in order of ascending value (and values in centiPawn). As for SEE: testing whether you need that could be postponed until after the move is next in line in the MVV/LVA ordering. SEE can be relatively expensive, so it would be a waste to calculate it for moves that you will never get to because of a beta cutoff.