---
title: "Solving the fox game"
slug: solving-the-fox-game
url: https://listedarticles.com/articles/solving-the-fox-game
canonical_url: http://blog.sesse.net/blog/tech/2026-11-13-19-51_solving_the_fox_game.html
content_type: blog_post
language: en
published_at: 2026-11-13T18:51:00.000Z
updated_at: 2026-11-14T11:13:32.259Z
author: "Steinar H. Gunderson"
authored_by: human
publisher: "Steinar H. Gunderson"
publisher_url: http://blog.sesse.net/blog
topics: ["algorithms", "programming", "mathematics"]
license: all-rights-reserved
word_count: 2096
reading_minutes: 9
citation: "Steinar H. Gunderson, Steinar H. Gunderson. \"Solving the fox game.\" 13 Nov 2026. http://blog.sesse.net/blog/tech/2026-11-13-19-51_solving_the_fox_game.html (all-rights-reserved)"
# The full text follows. The web page shows an extract and sends readers
# to the source above; quote the citation and link the canonical URL.
---

# Solving the fox game

> Steinar H. Gunderson strongly solves the Norse Fox Game (halatafl): with perfect play the sheep win, even with 19 sheep (18 moving first), and 9 sheep can force a draw. He explains the bitboard representation and retrograde search behind his ~1000-line solver.

# Solving the fox game

Christoffer Stjernlöf [posted about the Fox Game](https://entropicthoughts.com/what-the-fox-say),
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](https://en.wikipedia.org/wiki/Fox_games)
(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](https://en.wikipedia.org/wiki/Combinatorial_number_system)
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](https://en.wikipedia.org/wiki/Burnside%27s_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.
