pacosako
pacosako copied to clipboard
kreibaum
Design a faster algorithm for threat detection
This isn't necessarily something I need for anything soon, but I have been thinking about this for a while. Whenever I find a tricky situation that I want this algorithm to be tested with, I can add it to this tracking ticket.
The current algorithm basically looks at the tree of all "threat moves" and then can determine the set of threatened tiles.
There is the idea to instead start with the king and then work backwards. This has the potential to be a lot faster in situations where the king is relatively protected. Even if the king is somewhat exposed, this may eliminate large sections of the tree.
It will be really hard to get this right though, Felix posted a particularly tricky case which makes for a good unit test: https://pacoplay.com/editor?fen=r4rk1/pp1O1p1p/2p5/4e2e/3P1O2/4E1Pw/PPP2AF1/4RRK1%20w%200%20AHah%20-%20-
Here the path from a pair to the king only gets opened by moving g3>Nf4.
Here is one that currently doesn't even get a reply back from the wasm worker and which used to crash the server before the fix in 6208656859d6c66a8f57a220f34201ff2ee142c9
https://pacoplay.com/editor?fen=N1S1s1Ss/SpS1P1Sp/S1sp1SP1/ppS1S3/1H1S1S2/1pHPHs1s/KDpppppp/2sSSSSk%20w%200%20ahah%20-%20-
I have build the core of the new algorithm and it gives correct looking results. Right now I have only used it to try and speed up some Julia code. But I can extend it to cover more cases and also use it to make move generation / legal move determination faster.
This second commit also makes it work in situation where a piece is currently in the chain. This has seen drastic improvements to the performance. (10x for the lunalearn.jl script)
This has been working for more than half a year now and is documented at https://blog.kreibaum.dev/speeding-up-sako-detection-with-amazons as well, I think I just forgot to close the issue.
Looking at https://blog.kreibaum.dev/speeding-up-sako-detection-with-amazons I see that castling is supposed to make use of the Amazon Algorithm. It doesn't right now.
Algorithm would set down the king again and then look at squares threatened by the opponent.