Christoffer Stjernlöf posted about the Fox Game, an old Norse asymmetric board game (seemingly also called “halatafl”) where twenty sheep try to outsmart two foxes and get to the other side. His AI uncovered some interesting insights, but left the question open as of whether the foxes or the sheep actually win with perfect play (the general sentiment in his family was that winning with the foxes was easy). This was too tempting for me to leave on the table, so I set out to make a strong solve.

Since I don't know this game myself, I've stayed with the rules he describes even when they differ from e.g. Wikipedia (in particular, I do not use forced fox jumps, or multi-jumps); the only real change is that I don't have a 40-move draw rule, any position that is a forced win for one of the sides would be a win no matter how long it would take. (I consider this just an implementation detail in his AI, although morally, I consider a draw a loss for the sheep.) You might want to read his post to get the full rules, because I'm not going to repeat them here.

The results first: The sheep win with perfect play, even with only 19 sheep (remove one on the flank), or 18 if they are allowed to go first. Even with only 9 sheep (the minimum possible that isn't an instant win for the foxes), the sheep can force a draw right from the start. With one fox, 11 sheep suffice for a forced win. (The draw margin is seemingly so large because one fox can just camp in the last spot in the pen, and it's hard to force it away without getting harassed by the other fox, unless you have lots of sheep.)

The rest is about the implementation. I'll skip over a lot of wrong turns, and unsurprisingly, there were a lot of bugs to iron out, but hopefully, it got to a good place in the end. :-) I started out trying to make something very simple, and it worked for the first few cases, but then things got more complicated than I would have liked in the end. Still only at ~1000 lines of code, though, with no dependencies.

Board representation

The board has 33 squares. I tried a few different ways of represent the state of the game, and ended up on a simple bitboard representation: There's a 64-bit bitmap representing where there are sheep, and another bitmap representing where there are foxes. Since there's plenty of room in there, I use a spare bit to represent side-to-move. This is compact (which mattered a lot earlier on, but not as much later), easy to iterate over, and has little redundancy, so it's easy to keep valid. You need fast 64-bit population count and bit-scan instructions, but a) that's common now everywhere, and b) I decided fairly early that I wanted to require BMI2 anyway.

The bit order mostly doesn't matter; I just started at top-left and went from there. All it really influences is square iteration order. There's a small tweak in that I store the right half of the board mirrored (reverse x order) for symmetry purposes; more on that below.

Move generation

I just typed in every possible move from every square into an array, then verified by generating some SVGs that I hadn't made any typos (I had). In retrospect, I should have done something more automated; it would have been less painful.

The moves for sheep are just “you can go to X, Y or Z”. The moves for foxes are “you can go to X or Y, or you can go to Z if there's a sheep at W (which will be eaten)”. The move generator mostly just looks up the source square and tests every move. For the sheep, I make an easy test using bitboards; for the foxes, I could probably do something similar, but the jump moves proved a bit tricky (even with PEXT/PDEP) and I didn't end up using it.

This is the part that really determines the geometry of the board (apart from debugging display). Everything else is pretty much geometry-agnostic.

Result storage

There's a little over 2^41 possible board states (this includes some illegal positions as well as some situations that could never arise during actual gameplay, such as a fox being stuck at C1 with a row of sheep ahead of it), and I want to remember all of them. With that many positions, I figured I needed a fairly compact representation. I needed to store that a position could be sheep win, fox win or a draw, and then there was a fourth “invalid” state that was useful for internal reasons, so that maps exactly to two bits per position. (A tablebase intended for distribution could be compressed to less using the usual tricks of entropy coding, skipping half of the positions, or similar.)

This means we need to give a number to every possible position, ideally one with no collisions and no holes. I learned about combinatorial number systems which fit the bill exactly; given e.g. “we have 33 squares and 15 pieces”, it gives a dense mapping of positions from board to ID (ranking) and the opposite (unranking). (I made some fairly fast ranking and unranking algorithms, which may or may not have been novel, but it turned out I didn't actually need fast unranking after some other optimizations.) There are some extra complications in that there are two types of pieces, but you can solve them in a number of ways.

On a macro level, I store everything with 9 sheep and 1 fox first, then 9 sheep and 2 foxes, 10 sheep and 1 fox, and so on. 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).

mmap is almost never the right answer, but again, I was trying to go for simplicity. It certainly brought me pain, though, and perhaps some more explicit I/O would have been better.

Symmetry

The board is left-right symmetric (with an odd number of columns, so that there is a middle column that is neither “left” nor “right”). I had hoped to just ignore this, but eventually the gains became too important to ignore, so I conceded.

The basic idea is that I ranked the board twice, both as itself and mirrored (mirroring is just a couple of masks and shifts, given my representation), and picked the key that was the smaller as canonical. This reduced the number of positions I needed to look at to a bit over 50%, as expected, but it does nothing to the storage/RAM requirements; the new rank is not dense and the “illegal” (non-canonical) positions are spread out a bit all over the place (although of course near the low and high ends of values, it works much better).

As a tweak, I chose to compute all 33+281 canonical fox positions and renumbered using those placements as an assumption. This slashes ~95% of the waste, which is good enough; you can still rank a nonconical position if the foxes are symmetric about the center (or if there's only one fox and it's in the middle!), though.

You can improve on this by making the macro-splitting finer; instead of having a chunk for e.g. “10 sheep, 2 foxes”, you could have one with “5 sheep in left, 0 foxes in left, 1 sheep center, 1 fox center, 4 sheep in right, 1 fox in right” and demand that there are more sheep in left than right. However, you still get problems when the number is balanced, you'd need finer splitting etc.. The gains are small enough that I didn't see the point in doing this, and it tends to be a place where it's easy to introduce bugs.

I imagined calculating the exact number of positions up to symmetry would be an interesting exercise somehow, but I suppose it just immediately falls to Burnside's lemma as soon as you know how to count positions at all.

Searching

Now that we have positions and moves and a way to store results, we want to know how to find the result for the starting position (and ideally also all other positions).

My first attempt just did a depth-first search, caching as it went. This worked for the earlier stages but was generally a disaster; it ran out of stack easily (even with 8 GB—eight gigabytes of stack), and had problems with figuring out loops. (It didn't loop infinitely, but was prone to declaring loops where one side could break out of the loop by winning. I had a nasty hack to fix that, but it didn't really feel good.)

What I did instead was propagating results one step at a time. For each possible position:

1. If from a given position you know you can immediately win (e.g., the sheep reach the pen, or the fox eats the last relevant sheep), mark it as such.

2. If you can, in one move, reach a known-won position, mark your position as won (for the side to move). Similarly, if you can only reach known-lost positions, mark your position as lost.

3. Repeat #2 over and over again until you no longer have changes.

This was simple but still inefficient; I typically needed 40–80 passes for each chunk (where a chunk is something like “all positions with 15 sheep, 2 foxes”). However, it was super-easy to parallelize; I have 64 cores and could just hand out reasonable independent sub-chunks, you don't even need locking or atomic operations on the result set.

The correct way of doing this is retrograde analysis (replace #2 with doing backwards moves) and I assume this would have made the calculation roughly ten times as fast. But I only needed ~36 hours for the actual run (plus numerous pre-runs that failed for various reasons!), so I never got to this. After all, I wanted something simple to begin with.

Distance-to-win

Since I only store win/draw/loss (WDL) for each position (also known as a “bitbase” in chess tablebases), it's not easy to know what the fastest way to win is; just that “this move does not mess it up, the other side still can't force a draw”. However, in practice, you could just do reasonable-looking moves that don't regress the position, and take forward moves whenever you can (i.e., do sheep pushes if that still wins).

I made a simple alpha-beta searcher that tries to get win distances using the bitbase as a guide, which was a really fun challenge! It can find wins when they're perhaps ~20 ply (10 moves for each side) away, depending a bit on how narrow the win is (if there are only a few ways to win, it will obviously have to search a much smaller tree). Ultimately, though, alpha-beta for finding exact mate scores is just a losing game, since even perfect move ordering will only give you a sqrt() improvement over pure minimax.

Perhaps making DTZ (distance-to-zeroing, referring to zeroing the draw move counter in e.g. chess) bases would be possible without breaking the bank on storage space; I would assume that usually, you can force some sort of progress pretty fast, at least as the sheep.

Try it out

I made a very rudimentary interface to the database; the UI isn't very nice, and it largely relies on hovering (which doesn't work all that well on mobile) but I didn't want a polished game-player, just to know the answer. :-) You can try it out at https://sheep.sesse.net/, although I don't envision keeping it up forever. Perhaps someone can gain new insight from it and become an expert player, although strong solves are rarely very insightful in themselves due to the brute-force nature. At least we've conclusively settled (again, under this ruleset!) that the sheep win with perfect play.

Earlier, I would publish the source, but these days, the only ones who would be reading it would be the AI beast (fox?), and I'm not really so interested in that. :-) I'm definitely open to answering questions if anyone should have them; contact information at my home page as usual.