I played this as a kid! except we called them wolves instead of foxes.
My mom used to say that the sheep are guaranteed to win if they play perfectly though I don't know where she got this from (in our rules if game got stuck in a loop, the wolf had to break it iirc, which might have influenced this). Allegedly her grandma always won with sheep.
Anyway, the game seems small enough to be bruteforceable no? If my quick maths's right they are less than 2^40 different game states. This might nerdsnipe me into giving it a try.
Hmm I was hoping there was a link to play the game against the computer. But the only link to a playable version seems to be https://xkqr.org/fox-game-puzzles/ which presents pre-arranged game states as puzzles to solve.
Excellent read nonetheless. I like how the asymmetry makes it a good game to play with kids.
Unfortunately I only have a debugging interface for playing against the computer in the terminal. It wouldn't be too hard to get something on the web, though, I just didn't expect there to be any interest. I'll see if I can take the time.
The puzzles certainly have been buggy in the past, but I haven't found any actual bugs in a good while. Any time I run across something I think is a bug now, it's just because I didn't read the situation out fully.
The check is never for a specific fox to eat a sheep. If the puzzle doesn't accept a solution using one of the foxes, it is because doing so would have one of the following consequences:
The sheep can then fill the pen and win;
The fox can be trapped; or
The solution doesn't actually lead to eating a sheep at all, because all sheep can survive a few turns.
One such situation is when one of the foxes occupies the last non-sheep point in the pen. Often the sheep can fill that location quickly once the fox moves away from it, so that fox must not move.
The next time you find a buggy solution, it would be helpful if you sent the id of that puzzle so I can check!
It is true that the wrong solution in 798be409 allows sheep to trap one fox in one move, but then the planning horizon is not clear from the text on the page… Maybe reword it as «eat a sheep within X moves without losing a fox or leaving a one-move win to sheep»?
ETA: 8048ba2b has one solution that does not instantly lose, and it says that tree search prefers d3-c3 in a real game. But am I right that the situation after the solution is still a forced win for foxes by moving the bottom fox left until it is possible to move up?
PS. I guess it would be nice to know how to load a puzzle by ID…
ETA: d73c67ea comment is in a sense buggy! «A tree search prefers f3-e3 in a real game.» but f3-e3 is a loss one move faster than the solution.
Is the "loopy game" terminology indicative of the fact that you've read about combinatorial game theory? It's been ages since I thought about that stuff, but I always thought it was really neat.
Great read. I swear I read about this game somewhere, I think it was in a reader for the game theory course at TU Delft, about 9 years ago. And I think it also mentioned that while it seems easier for foxes, sheep will always win with perfect play.
Anyway, I have a similar urge to "computer analyze" games, and like someone mentioned it feels like this one should be brute-forceable... Also for computationally intensive stuff its probably worth it to switch to a compiled language?
Ah! Well it is a great looking and reading draft! I was almost nerd sniped into doing my own bot until I saw that you had gone beyond random rollouts into ML!
priner | 17 hours ago
I played this as a kid! except we called them wolves instead of foxes.
My mom used to say that the sheep are guaranteed to win if they play perfectly though I don't know where she got this from (in our rules if game got stuck in a loop, the wolf had to break it iirc, which might have influenced this). Allegedly her grandma always won with sheep.
Anyway, the game seems small enough to be bruteforceable no? If my quick maths's right they are less than 2^40 different game states. This might nerdsnipe me into giving it a try.
splitbrain | a day ago
Hmm I was hoping there was a link to play the game against the computer. But the only link to a playable version seems to be https://xkqr.org/fox-game-puzzles/ which presents pre-arranged game states as puzzles to solve.
Excellent read nonetheless. I like how the asymmetry makes it a good game to play with kids.
[OP] kqr | 20 hours ago
Unfortunately I only have a debugging interface for playing against the computer in the terminal. It wouldn't be too hard to get something on the web, though, I just didn't expect there to be any interest. I'll see if I can take the time.
k749gtnc9l3w | 22 hours ago
I think some of the puzzles are buggy? In the sense that you are told to eat a sheep, but the check is for a specific fox to eat a sheep…
[OP] kqr | 20 hours ago
The puzzles certainly have been buggy in the past, but I haven't found any actual bugs in a good while. Any time I run across something I think is a bug now, it's just because I didn't read the situation out fully.
The check is never for a specific fox to eat a sheep. If the puzzle doesn't accept a solution using one of the foxes, it is because doing so would have one of the following consequences:
One such situation is when one of the foxes occupies the last non-sheep point in the pen. Often the sheep can fill that location quickly once the fox moves away from it, so that fox must not move.
The next time you find a buggy solution, it would be helpful if you sent the id of that puzzle so I can check!
k749gtnc9l3w | 19 hours ago
It is true that the wrong solution in 798be409 allows sheep to trap one fox in one move, but then the planning horizon is not clear from the text on the page… Maybe reword it as «eat a sheep within X moves without losing a fox or leaving a one-move win to sheep»?
ETA: 8048ba2b has one solution that does not instantly lose, and it says that tree search prefers d3-c3 in a real game. But am I right that the situation after the solution is still a forced win for foxes by moving the bottom fox left until it is possible to move up?
PS. I guess it would be nice to know how to load a puzzle by ID…
ETA: d73c67ea comment is in a sense buggy! «A tree search prefers f3-e3 in a real game.» but f3-e3 is a loss one move faster than the solution.
cmcaine | 19 hours ago
bc3debbe seems wrong to me?
And puzzle b68b91c4. You can move the fox to e3 to guarantee catching two sheep. Maybe the other fox then is guaranteed trapped or something.
quasi_qua_quasi | 15 hours ago
Is the "loopy game" terminology indicative of the fact that you've read about combinatorial game theory? It's been ages since I thought about that stuff, but I always thought it was really neat.
rustybolt | 11 hours ago
Great read. I swear I read about this game somewhere, I think it was in a reader for the game theory course at TU Delft, about 9 years ago. And I think it also mentioned that while it seems easier for foxes, sheep will always win with perfect play.
Anyway, I have a similar urge to "computer analyze" games, and like someone mentioned it feels like this one should be brute-forceable... Also for computationally intensive stuff its probably worth it to switch to a compiled language?
trenchant | 18 hours ago
you may want to remove the 'draft' tag 😄
[OP] kqr | 15 hours ago
But it is a draft! It hasn't passed through final editing and I'm not happy with all parts of it yet so I'm having the community preview it.
trenchant | 13 hours ago
Ah! Well it is a great looking and reading draft! I was almost nerd sniped into doing my own bot until I saw that you had gone beyond random rollouts into ML!