Solving the fox game
15 points by dracarys_18
15 points by dracarys_18
I bet using some variant of proof-number search would help a ton here -- either for doing the search, or probably for finding a winning line now that you have the tablebase.
I'm always happy when I get a chance to bring up PN search -- it's not widely known, but it dramatically outperforms minimax specifically for proving position values.
Proof-number search answers one question about one position. The author has strongly solved the game (the value, and a way to play it, is known for every legal position).
This gives beautiful locality (a single move can never remove more than one sheep, and only extremely rarely more than one fox), allowing me to just mmap everything and let the kernel deal with it, even though I only had 256GB of RAM and the total set was larger (329,870,110,455 bytes after the symmetry optimizations below).
It's a huge perfect-play database of 330GB.
This game was on my mind ever since the last post, now someone did it and I don't have to anymore. Very cool to see the result.
Regarding the rule variations:
Nice to see that who has to break the loop actually doesnt matter cuz sheep win anyway
If foxes are forced to jump when they can (the variant that I used to play), then the sheep still win, cuz thats just an extra disadvantage for the foxes (it only limits his possible moves)
(although I think we played with multijump which changes things)
I wonder how long it would take to check whether optimal sheep play from the canonical original position always avoids multijump opportunities for foxes!