More than 25% faster performance for certain perft positions. Arround 10% overall. New bit-board based pinned piece algorithm.

[roy-debabrata]

I developed a new algorithm for Bitboard based method for fast pinned piece detection that's more than 25% faster than Stockfish in perft for certain positions. And I developed it in Java so it's potentially much faster in C++.

I had developed the algorithm a couple of years ago and published it as a MIT Licensed application. I also made a post on chess.stackexchange.com about this. Unfortunately turns out nobody took notice, but I have been working on refining it.

I originally wanted to complete my own chess engine and complete in TCEC so I didn't publicize it much either. But I have reasons to suspect a closed source project has copied my algorithm and has been quickly gaining in performance. So I want it out and useful for everyone.

Performance comparison between my program and Stockfish (my program boot straps JVM for every run):

Position FEN	Depth	Spot (My Program)	Stockfish	Difference	Percentage
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1	7	0m10.980s	0m12.420s	-1440ms	11.59%
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - -	6	0m25.303s	0m27.341s	-2038ms	7.45%
8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -	8	0m13.438s	0m17.923s	-4485ms	25.02%
r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1	6	0m3.044s	0m2.517s	527ms	-20.94%
rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8	5	0m1.244s	0m0.373s	871ms	-233.51%
r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10	6	0m19.263s	0m21.537s	-2274ms	10.56%

As you can see the performance gains are significant. I suspect this will bring the end to pseudo legal move generation. You should notice the only position in which my application is slower are ones that run in seconds. That is because JVM warmup doesn't allow me to beat Stockfish in those positions. But without warmup even those positions run much faster than Stockfish.

I have temporarily turned my project private because I was pissed about people copying my work without attribution. So, what's the algorithm and why am I positing this? Lets answer the second question first:

1. I just want credit for the algorithm (unless it's already known but no one uses it, can't imagine why that would be).
2. As a Java developer I find it difficult to understand sophisticated C++ code in Stockfish, so I need someone to help me port my algorithm to Stockfish.
3. If anyone of you has experience publishing papers, I hope you can be a co-author with me and so we can publish my algorithm and findings.

As for the algorithm. I can post it in the discussion thread if you guys are interested.

[vondele]

My 2cents,

1. I you want credit, you keep the project open with the original history intact. If you want visibility, showing it outperforms what we have in SF, in game play (not perft), is a good thing to do. Showing the code here, is probably a first step.
2. Probably nobody in the community here would go look at a closed project, but an open project with a pointer to the sources will get some traction. If the Java code looks convincing somebody might try to implement it in C++. There is a fairly large community in our discord that have done these things multiple times... try to reach out.

[roy-debabrata]

1. My project still has the MIT licensee I just made it private temporarily, I can make it public again. I am just weary of people copying my idea without credit. I don't have the resources to prosecute bad actors. As I mentioned, I suspect it has already happened once.
2. If I make it open source but if someone implements it for Stockfish, after me making my changes public again, I suspect no one will bother adding me to the authors page (since I won't be the author and it would make sense). So in this case what are my options?

[Disservin]

FYI SF isnt particularly optimized for perft, it also has bulk counting for perft and for search it uses pseudo legal movegen. There are probably many engines in the wild which will beat Stockfish in a h2h perft comparison.

[roy-debabrata]

My project is in MIT license, If I code it for Stockfish I can publish it under any license as I want including GPL. The real question, and everyone seems to keep missing here, if your legal move generation algorithm was ~10% faster than it is on the average case and ~25% faster in cases there are lots of pins in the position, would you still need to use the pseudo legal move generation? Does it really give you a base 10% performance gain? Even with cutoffs let's not pretend there aren't overheads with pseudo legal moves.

[PGG106]

The impact of movegen on search speed is far more complex than you are assuming, not only there are cutoffs, there's also staged movegen, and sf tries a ridicolously small amount of moves per node, 2 or 3 on average.
There are a lot of movegen implementations that are faster than sf when you stare at the perft and none of them are used for stockfish, it's not as clear cut as you think it is.
It doesn't mean it isn't worth a test but keep in mind you might make your super secret public for a test that fails, consider that as a real possible option before deciding on how to proceed

[bftjoe]

You can speculate about your own future actions all you want. Once you actually license it under GPL, then other people might be more interested in doing the leg work for you. But a movegen speedup may or may not translate to actual elo gain under Stockfish testing conditions.

[Disservin]

Even if this were to pass, I highly doubt that Stockfish will switch to some of the core files to be licensed under MIT instead of GPL. Good luck!

That is not entirely true, see the tablebase code the initial core code was distributed as This file may be redistributed and/or modified without restrictions.
https://github.com/syzygy1/tb/blob/master/interface/tbcore.c
MIT is in a similar state

to deal in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software

So that is fine, some of the more challenging question is whether porting the java code to c++ would still keep the original license intact.

[vondele]

most challenging question, would there be a gain in game play...
Easiest solution for copyright question, the author of the code makes PR and contributes it ...

[roy-debabrata]

Know that sf tests are public, so there's a scenario where your idea becomes public for everyone to see and fails the test, and you end up with no secret and no glory and recognition.

I have tests too. I run the same perfts and much faster than stockfish. And even it it turns out my idea doesn't cut it, so what? I didn't do this for some fake notion of "secret glory" the pile of discarded ideas that took months for me to work out is already quite long. This would just become part of that pile. But I do very thorough tests on my engine. Testing out changes for days. I have very good reason to believe this is a genuine breakthrough.

[Disservin]

Now 600 elo from movegen speed improvements alone ? That sounds hardly believable

[PGG106]

That's definitely outside the realm of possibility, i don't think going from naive for loops to state of the art movegen is even near that figure, going by 100 elo per doubling of speed, 600 elo would mean 64x speed improvement lol, definitely not possible.
But again, this doesn't mean that a movegen change can't gain elo, it's just nowhere near close to that figure.

[roy-debabrata]

I cannot prove it without de compiling their code base and I won't go name names because there is a real possibility that I might be wrong.

[PGG106]

There is a 100% possibility you are wrong frankly, they might've gotten some elo from improving their movegen, possibly using your code as a source, but movegen alone doesn't account for even a fraction of those 600 elo, the math simply isn't there.

[roy-debabrata]

I am not an elo expert so you might be right.

[roy-debabrata]

https://github.com/Gigantua/Gigantua achieves 2B nps, is this applicable to Stockfish ? Not really. Perft speed alone isnt everything and certainly being faster than Stockfish is no major "breakthrough"

Okay. Guess I am wasting my time then. Thank you for your comments.

[PGG106]

None of the comments are trying to imply your change is worthless or that it will 100% not work, if we were sure it wouldn't work there would be no need to test the change.
What everyone is pointing out is there's no guarantee the change is good, but that doesn't make it not test worthy.

[roy-debabrata]

Exactly what I have been saying. Quoting from my original post:

• I just want credit for the algorithm (unless it's already known but no one uses it, can't imagine why that would be).
  

• As a Java developer I find it difficult to understand sophisticated C++ code in Stockfish, so I need someone to help me port my algorithm to Stockfish.
  

• If anyone of you has experience publishing papers, I hope you can be a co-author with me and so we can publish my algorithm and findings.
  

Everyone here seems to be pessimistic about the prospect. Quoting myself again:

• As for the algorithm. I can post it in the discussion thread if you guys are interested.

So far no one has even asked me what my algorithm actually even does. I am not even trying to keep it a secret but I am being told that by making my idea public I open myself up to the possibility of ridicule. I have also been told in a lot of different ways that it is unlikely that perft performance will translate.

Anyways, seems like everyone here is interested in discussing right about everything else under the sun to the point that no one even wants to discuss the algorithm. Tells me more than I need to really.

[PGG106]

Considering the amount of useful information you recieved about movegen speed, search speed, elo and testing, you aren't really greateful lmao. Good luck finding a c++ coder for your test.

[gab8192]

Please explain your idea, and I (or someone else) will try implementing it on stockfish

[roy-debabrata]

https://github.com/roy-debabrata/SpotChess
Made the repository public.

https://github.com/roy-debabrata/SpotChess/blob/master/src/main/java/com/debabrata/spotchess/logic/MoveProcessor.java
Check out the processPinnedPieceMethod.

[roy-debabrata]

So the idea is pretty simple. So you know how we use store moves pre-calculated by using magic hash? We can do the same thing for pinned piece as well.

So, imagine for e5 we have the following piece combination for rook attacks.
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

We usually store:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 0 1 1 1
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

What I do is also store:
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0

So I just store the nearest pair of pieces. Since we don't consider the edge of the board consider this:

1. If only piece at the edge of the board, we store nothing.
2. If one piece not on the edge, we store that one piece and the edge.
3. If more pieces than the two nearest.

We can use the same magic number for both move and pin storage because so we can multiply twice. Once for bishop check check and once for rook check check. And use the same indexes to also get the pinned pieces.

Now that we have done all of that we just need to divide up the set by pairs and for each pair check if one piece is a enemy bishop/rook and one piece is our piece. Of course, we don't include checkers in this because we will call the checker a pinned piece!

That's about it. This way we can quickly get a list of all pinned pieces and a list of bishop/enemy types checking us all for the cost of two hash calculations and 4 hash table look ups.

Now, the existing magic numbers that are used by Stockfish might not work because there will be more unique pin combinations than move combinations. But any magic number that works for the pinned piece lookup will necessarily also work for the move table lookup.

That's it. That's the idea.

[Sopel97]

I'm confused by your attitude. Considering that you took the code down from github and never mentioned anything regarding the algorithm it's only right to assume that you're waiting for someone to work with you in secret. If you want the discussion to be about the algorithm instead then maybe start talking about the algorithm.

[roy-debabrata]

I didn't want to do it in secret. I just wanted assurance that in case it works well I will get the attribution (even though someone else might translate the code to C++ for Stockfish). In any case I made it public. I am just spooked because I believe someone copied by code without attribution and I don't have the resources to correct it.

[roy-debabrata]

https://github.com/roy-debabrata/SpotChess
Made the repository public.

https://github.com/roy-debabrata/SpotChess/blob/master/src/main/java/com/debabrata/spotchess/logic/MoveProcessor.java
Check out the processPinnedPiece method.

[ddobbelaere]

Show us the code!

Make your Java repository public (of your tool called Spot), so that everyone can see for themselves.
By your own chosen MIT license, there is an automatic need for acknowledgement anyway, so no worries.

[roy-debabrata]

https://github.com/roy-debabrata/SpotChess
Made the repository public.

https://github.com/roy-debabrata/SpotChess/blob/master/src/main/java/com/debabrata/spotchess/logic/MoveProcessor.java
Check out the processPinnedPiece method.

[MrBrain295]

Fantastic claims require fantastic evidence.

[roy-debabrata]

https://github.com/roy-debabrata/SpotChess
Made the repository public.

https://github.com/roy-debabrata/SpotChess/blob/master/src/main/java/com/debabrata/spotchess/logic/MoveProcessor.java
Check out the processPinnedPiece method.

Run the perft yourself.

[Disservin]

You didnt have to send the same message 4 times..

[roy-debabrata]

I was replying to different people. Didn't realize people would get notification for every reply. Sorry.