What the fox say?

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

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 … … or is it? Let’s find out.

这是一款古老的北欧棋盘游戏，在瑞典被称为“饿死狐狸”（Starve the Fox），或者简称为“狐狸游戏”。据维基百科记载，“狐狸与鹅”（Fox and Geese）是该游戏在英语国家流传的简化版本。在“饿死狐狸”中，一名玩家扮演狐狸，另一名玩家扮演绵羊。游戏规则是不对称的，显然，狐狸玩家几乎总是赢家……真的是这样吗？让我们一探究竟。

Game rules 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.

游戏规则：这就是棋盘的初始状态。带有字母 F 的橙色圆圈是狐狸玩家起始的两枚棋子。带有字母 S 的白色圆圈是绵羊玩家起始的 20 枚棋子。绿色圆圈代表棋子可以移动到的空位。狐狸玩家和绵羊玩家轮流移动自己的一枚棋子。棋子每次只能沿棋盘上的线条移动一步，不能相互穿过，也不能占据同一个位置。不过，在此之后，规则便不再对称。

First, the rules for the sheep player: GoalFill the pen, which is the top-centre 3×3 square the fox starts in. The sheep player wins when nine of its pieces to occupy the box bounded by corners at c5 and e7. MovementNot backwards. In other words, moves that reduce the rank of the sheep are not legal. AttackIf the sheep player manages to trap a fox such that it cannot move at the end of the turn, that fox is removed from the board. This gives the sheep an alternate victory condition: if they manage to remove both foxes, they can no longer prevent the sheep from filling the pen, so the sheep win right away.

首先是绵羊玩家的规则：目标是填满羊圈，即狐狸起始所在的顶部中心 3×3 方格。当绵羊玩家有九枚棋子占据了以 c5 和 e7 为角的方框内时，绵羊玩家获胜。移动规则是不能后退。换句话说，任何降低绵羊排位的移动都是违规的。攻击规则是如果绵羊玩家成功困住一只狐狸，使其在回合结束时无法移动，该狐狸就会被移出棋盘。这为绵羊提供了另一种获胜条件：如果它们成功移除了两只狐狸，狐狸就无法再阻止绵羊填满羊圈，因此绵羊直接获胜。

The fox player moves first at the start of the game. 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: GoalPrevent the sheep from filling the pen. MovementAny direction. AttackThe fox can eat sheep by jumping over them. If there is an open location two steps away in a straight line from the fox, and a sheep on the location in between (i.e. this type of configuration: F—S—O), then the fox can move to the open location two steps away, and the sheep in between is removed. When fewer than nine sheep remain, they can no longer fill the pen and the fox wins.

游戏开始时，狐狸玩家先行。虽然我的分析表明该游戏中的先行优势非常小，所以谁先手可能并不重要。其规则如下：目标是阻止绵羊填满羊圈。移动规则是可以向任何方向移动。攻击规则是狐狸可以通过跳过绵羊来吃掉它们。如果狐狸直线方向两步远有一个空位，且中间位置有一只绵羊（即 F—S—O 这种配置），那么狐狸可以移动到两步远的空位，中间的绵羊被移除。当剩余绵羊少于九只时，它们就无法填满羊圈，狐狸获胜。

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.

不难发现，这是一个容易陷入循环的游戏，意味着它可能进入这样一种局面：双方玩家的最佳策略都是来回移动棋子，不断重复之前的状态，却无法取得任何进展。我只在有孩子在场时听过规则讲解，他们并没有说明在这种情况下该怎么办。在下文的分析中，我将连续 40 步没有进展的情况视为平局。进展很容易通过绵羊的排位来衡量，因为绵羊不能后退。

The foxes are assumed to be overpowered 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.

我对这类策略游戏有一种不健康的执着。我必须通过计算机分析来彻底搞懂它们。我不知道为什么，这只是自然而然发生的。我过去常手动编写树搜索算法，但我意识到 OpenSpiel 提供了一种通用的树搜索，支持我所需要的大部分功能，所以我可以用 Python 编写游戏规则并接入 OpenSpiel 进行分析。那么，考虑一下上面的规则。你认为在两名水平相当的玩家之间，狐狸获胜的概率是多少？写下你的猜测，你就会知道自己的直觉有多准了。

A somewhat strong computer opponent 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. The algorithm playing itself got a similar result: around 85 % of games were won by the foxen.

一个相当强大的计算机对手：解决这类问题的第一步是使用简单的蒙特卡洛树搜索（MCTS），并通过随机模拟到终局来进行叶节点评分。在未经优化的 Python 环境中，它在玩“饿死狐狸”时每秒能执行约 1,000 次搜索迭代。我给了这个算法不到一秒的思考时间，并分别以狐狸和绵羊的身份与它对弈。在这些对局中，很明显狐狸大部分时间都会获胜。算法自对弈的结果也类似：约 85% 的对局由狐狸获胜。

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.

有了这么多佐证，我本打算结束实验。我没指望更深层的搜索能带来多大改善，因为分支因子相对较低，部分归功于对绵羊移动的限制。但为了保险起见，我进行了最后一场对局。我扮演狐狸，计算机以 8,000 次迭代的搜索预算扮演绵羊。虽然它依然表现平平，但它成功利用了我两次失误，竟然进入了获胜局面。是用绵羊！这引起了我的兴趣，意味着实验远未结束，实际上可能需要更深层的搜索，才能更准确地反映出该游戏可能的策略。

What this says about the game 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. 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

关于这款游戏的启示：我起初并没有意识到，但在那场高搜索预算的对局中，我们了解到了“饿死狐狸”的本质。绵羊方比狐狸方需要更深层的思考才能玩好。由于绵羊在与狐狸的孤立冲突中处于劣势，它们必须协调整个羊群的移动来击败狐狸，而每回合只能移动一步，这就需要跨越多个回合进行策略规划。事实上，绵羊玩家与其说是在移动绵羊，不如说是在移动羊群中的空隙，以确保这些空隙远离最靠近狐狸的绵羊。这是该游戏的一个绝妙特性，因为……