search

niklasf / shakmaty

A Rust library for chess and chess variant rules and operations
https://docs.rs/shakmaty
GNU General Public License v3.0
210 stars 41 forks source link

Implementation of insufficient material for Horde #44

Closed stevepapazis closed 3 years ago

stevepapazis commented 3 years ago

Hey, there

This pull request implements the insufficient material method for Horde.

First we need to determine the horde checkmating patterns that use the least amount of material. That is fairly easy to do in positions where white has queens, rooks and pawns or when white has more than three pieces; for example a queen and any other white piece mate the black king, pawns promote to queens or knights, etc.

Positions with minor pieces are a bit trickier, since they're more of them and a bishop and a knight can deliver a double check. But even those can be worked out by hand. Then we can use a brute force approach to validate that we haven't missed out any of them, similarly to how endgame tablebases are generated.

We quantify those patterns into conditions that can be used to check any given position against at run time.

Here is a little more information on horde checkmating patterns and generation of test positions.

niklasf commented 3 years ago

Thanks again! I downsampled the test suite a bit more before merging, to avoid getting near crate upload limits.