What the Fox Say?

There is an old Norse board game, which in Sweden is played under the name Starve the Fox, or just the Fox Game. According to Wikipedia, Fox and Geese is a simplified version of it played in English speaking countries.

In Starve the Fox, one player plays as the foxes, and one player plays as the sheep. The rules are asymmetric, and obviously the game is almost always won by the fox player …

This is what the board looks like in its starting position.

The orange circles with the letter F in them are the two pieces the fox player starts with. The white circles with the letter S in them are the 20 pieces the sheep player starts with. Green circles represent empty locations pieces can move into. The fox and the sheep players take turns moving one piece of their own. Pieces can only move one step at a time, along the lines on the board, and cannot pass through each other or occupy the same location.

After that, though, rules are asymmetric. First, the rules for the sheep player:

The fox player moves first at the start of the game.11 Though my analysis indicates that the first-move advantage is very small in this game, so it probably doesn’t matter too much who wins. Its rules are:

It doesn’t take much to realise that this is a loopy game, meaning it can get into positions where the best moves for both players are to shuffle their pieces back and forth, repeating previous positions over and over and not making any progress. I have only heard rules explained in the presence of children, and they don’t specify what happens in such situations. In the analysis below, I’ve considered the game a draw after a stretch of 40 moves with no progress. Progress is easily measured in terms of sheep rank, since sheep cannot go backward.

I don’t remember playing this game when I was young, but it was a favourite of my wife’s late grandfather, and that half of her family knows it well. It is common wisdom in her family that the fox player needs to blunder badly for the sheep to win. Her entire family believes the game is heavily tilted in favour of the fox. I have played the game a few times, and indeed it has been easier for me to win when playing as fox.

I have an unhealthy relationship with strategy games like these. I simply must put them through computer analysis to figure them out. I don’t know why. It’s just something that happens. I used to write tree search algorithms manually, but I have realised that OpenSpiel provides a generic tree search supporting most of the things I’ve ever found myself needing to support, so I can write the game rules in Python and hook into OpenSpiel to analyse it.

Well, consider the rules above. How often do you think the fox wins, between two equal players? Write down your guess, and you’ll learn how good your sense of this is.

The first stop for a problem like this is plain Monte Carlo tree search (mcts) with random rollouts to the end for leaf scoring. In un-optimised Python, this managed to perform about 1,000 search iterations per second when playing Starve the Fox. I gave this algorithm a thinking budget of just under a second, and played against it, both as the fox player and the sheep player. In those games, it seemed clear that the fox would win most of the time.22 Unless the sheep forced a draw, which they can do as long as there’s enough of them, thanks to the loopy nature of the game. The algorithm playing itself got a similar result: around 85 % of games were won by the foxen.

With so much corroborating evidence, I was close to calling the experiment finished. I didn’t expect deeper search to improve things by much, because the branching factor is relatively low, in part thanks to the constraints on sheep movement.

But then just to be sure, I tried one last game. I played as fox, and the computer played sheep with a search budget of 8,000 iterations. Although it still didn’t play particularly well, it managed to exploit two of my blunders, and actually get into a winning position. With the sheep! That caught my interest, and it meant the experiment wasn’t over at all, but might actually need deeper search to more accurately reflect the strategy possible.

I didn’t realise it right away, but what happened in that high search budget game was that we learned something about the nature of Starve the Fox.

The sheep side requires deeper thinking than the fox side to play well. Since the sheep, in isolated conflicts with foxes, are so underpowered, they must move the mass of the entire flock in coordination to beat the foxes, and with one movement per turn, that requires strategising over many turns.33 In fact, the sheep player isn’t really moving sheep as much as they’re moving the holes in the flock to make sure the holes stay away from the sheep closest to the foxen. This is a fantastic property of the game, because it (a) is thematically smashing, and (b) means a child can play an adult and both still have fun; the child gets to play the fox side and the adult just has to think harder.

However, I didn’t want to wait for 16,000 iterations or whatever’s needed for the plain mcts to play a very strong game. One of the more expensive parts of that search algorithm are the random rollouts to score leaves in the search tree. A trick to make leaf scoring faster is to cut off the rollouts well before the game ends44 The depth at which to truncate rollouts depends on both the complexity of the game and the quality of the rollout policy. For completely random rollouts, it may even be desirable to cut them off at depth zero – i.e. not perform any random moves at all, because they make the scored state less representative of the end state than the earlier leaf node was. In the case of Starve the Fox, stopping the rollout after 8 plies seemed to yield the best results with the first draft of the heuristic function, but it’s possible with a stronger heuristic function shorter rollouts would be even better, because they buy time for more tree search at the cost of not evaluating as far into the future., and then use a heuristic function to score the positions in games that haven’t yet terminated when the rollout is truncated. The heuristic value is scaled to be smaller in magnitude than the score given to a terminated game, so that the tree search will prioritise the win/loss signal over the heuristic when it can see both.

But this means a heuristic function is needed. A primitive one might be based on material, like “number of sheep alive” or based on progress, like “total rank gained by sheep”. A more sophisticated one might include both of those variables, and more. If we didn’t have computers, we’d probably be best off by picking out the top three variables and weighing them equally.

But we have computers, so we can do better. What we do is play the weak tree search55 Search budget of maybe 0.5 seconds per ply, scoring leaves by random rollouts to the end. against itself a bunch of times. From each of those games we sample one random position66 Only one position to avoid having to deal with the strong correlation between consecutive positions in the same game., record how the game ended, and then train a regression model to predict the game outcome based on the game state in those sampled positions. The weights we get out of the regression minimise square loss, which is probably what we want for a heuristic function.

Once we have those weights, we can create a new generation of the tree search using the same search budget, but with truncated rollouts and applying the learned heuristic function. This gets to play against the previous generation to confirm it is indeed better, and if it is, it plays itself a bunch of times again, and we sample new positions, and fit the regression again. Since it’s playing better than the previous generation, it will find ways to win from positions where the previous generation did not. Thus, the heuristic function’s prediction of outcome – assuming skilled play on both sides – will become more accurate.

We repeat that a few times, and what we get is a decently strong opponent, even at short thinking time budgets. Well, at least it reliably sweeps the floor with me, regardless of which side it plays.

Maybe the trained weights tells us something about what good positions look like, which might help us get better at the game, too. Since we haven’t seen the link function77 It’s a hyperbolic tangent to map the raw score (real number, infinite support) onto the range [−1, +1] indicating “sure loss” and “sure win” respectively, with a draw having value zero. But we’d also need the bias term (roughly +1) to convert it into the final value, which isn’t really a probability but almost., we can’t do anything with the absolute values of these weights, but their relative sizes are more interesting anyway.

Although it’s tempting, it would be improper to interpret these right away, because the heuristic function trained here includes one more thing. It’s also trained weights for specific locations on the board, which answers the question of how valuable it is for a player to occupy specific positions on the board, in general.

The values of the board positions absorb some of the coefficients from the variables above. For example, the list above indicates the value of a sheep in the pen as 0.017, but the least valuable pen position has value 0.11, compared to the average outside-pen position with value 0.09. Thus, the value of a sheep in the pen (compared to having it outside the pen) is never less than 0.11−0.09+0.017=0.04. On average it is 0.08, which is much higher than the list above would make us believe.

Here are the rest of the board values for the sheep player.

7 0.21 0.13 0.21 | 0.18 6 0.11 0.16 0.11 | 0.13 5 0.08 0.16 0.14 0.13 0.14 0.16 0.08 | 0.13 4 0.05 0.12 0.10 0.13 0.10 0.12 0.05 | 0.10 3 0.12 0.11 0.10 0.13 0.10 0.11 0.12 | 0.11 2 0.02 0.05 0.02 | 0.03 1 0.06 0.12 0.06 | 0.08 a b c d e f g | mean

This tells us that a sheep in the c7 position is worth 0.23, with most of the value coming from the position itself, and only a small amount coming from the general value of the number of sheep in the pen variable. Here are some other observations:

These position values also help us interpret the macro-scale variables from before:

The value of an eaten sheep is a nice, intuitive scale for these values. We can express all the others in terms of sheep value, similar to how in chess they measure things in pawn value. Under that conversion, the sheep player needs to gain a total of nine ranks to offset the loss of a sheep.

It may also seem like it is a good trade (net sheep value +0.07) to sacrifice a sheep to get two others into the pen. However, intentionally sacrificing a sheep means putting it into a position where the fox is able to eat it, which is worse than just having lost a sheep. The trade actually has net sheep value −0.27. I don’t know why an imminent feeding is worse for the sheep than an eaten sheep, but I suspect it’s because it allows the fox to jump two positions, and thus move quicker across the board.88 And logic would have us conclude that this ability to move two places (in isolation, separate from any eating that would happen as a side effect) is, on average, worth a whopping 0.2 sheep value!

Enough about sheep. The individual-position values for the fox player are

7 0.30 0.30 0.30 | 0.30 6 0.29 0.30 0.29 | 0.29 5 0.33 0.41 0.37 0.36 0.37 0.41 0.33 | 0.37 4 0.34 0.37 0.39 0.37 0.39 0.37 0.34 | 0.37 3 0.34 0.37 0.34 0.35 0.34 0.37 0.34 | 0.35 2 0.32 0.31 0.32 | 0.32 1 0.33 0.29 0.33 | 0.32 a b c d e f g | mean

These position values are flatter across the board, with an average corresponding to 2.3 sheep value – each living fox is worth j