狐狸说了什么？

# 狐狸说什么？ 来源：https://entropicthoughts.com/what-the-fox-say 有一种古老的北欧棋盘游戏，在瑞典被称为"饿死狐狸"（*Starve the Fox*），或者简称"狐狸游戏"（*the Fox Game*）。根据维基百科，英语国家流行的"狐狸与鹅"（*Fox and Geese*）是它的一个简化版本。 在"饿死狐狸"中，一位玩家扮演狐狸，另一位玩家扮演绵羊。规则是非对称的，而且很明显，狐狸一方几乎总是能赢…… ……真的吗？让我们来看看。 ## 游戏规则 (https://entropicthoughts.com/what-the-fox-say#game-rules) 以下是游戏初始局面的样子。 what-the-fox-say_01.png 带有字母 F 的橙色圆圈是狐狸玩家的两枚棋子。带有字母 S 的白色圆圈是绵羊玩家的 20 枚棋子。绿色圆圈表示棋子可以移入的空位。狐狸和绵羊玩家轮流移动自己的一枚棋子。棋子每次只能沿棋盘上的线移动一步，不能穿过彼此，也不能占据同一位置。 然而，之后的规则是非对称的。首先是绵羊玩家的规则： 目标：填满围栏，即狐狸初始所在的顶部中央 3×3 方格。当绵羊玩家的九枚棋子占据了以 `c5` 和 `e7` 为角的方格时，绵羊玩家获胜。 移动：不能后退。换句话说，降低绵羊行数的走法是不合法的。 攻击：如果绵羊玩家成功困住一只狐狸，使其在回合结束时无法移动，则该狐狸被移出棋盘。这给了绵羊一个替代胜利条件：如果他们成功移除了两只狐狸，狐狸就再也不能阻止绵羊填满围栏了，所以绵羊立即获胜。 狐狸玩家在游戏开始时先走。¹ 狐狸玩家的规则是： 目标：阻止绵羊填满围栏。 移动：可以向任意方向移动。 攻击：狐狸可以通过跳过绵羊来吃掉它。如果在狐狸前方两步远的直线上有一个空位，且中间位置有一只绵羊（即这种布局：`F—S—O`），那么狐狸可以移动到两步远的空位，中间的绵羊被移除。当剩余绵羊少于九只时，它们就无法再填满围栏，狐狸获胜。 不难发现，这是一个*有循环*的游戏，意味着它可能进入一种局面：双方的最佳走法都是来回移动棋子，反复重复之前的局面而没有任何进展。我只在孩子在场时听过规则说明，他们并没有规定这种情况下的处理方式。在下面的分析中，我将连续 40 步无进展视为和棋。进展很容易用绵羊的行数来衡量，因为绵羊不能后退。 ¹ ² 虽然我的分析表明先手优势在这局游戏中非常小，所以谁先走可能并不太重要。 ## 狐狸被假定为过于强大 (https://entropicthoughts.com/what-the-fox-say#the-foxes-are-assumed-to-be-overpowered) 我不记得小时候玩过这个游戏，但它是妻子已故祖父的最爱，她那边的家族对这个游戏很熟悉。在她的家族中有一个共识：狐狸玩家必须犯严重错误，绵羊才可能赢。她的全家都认为这个游戏严重偏向狐狸一方。我自己也玩过几次，确实当我扮演狐狸时更容易赢。 我和这类策略游戏有一种不健康的关系。我*必须*用计算机分析来搞清楚它们。我不知道为什么，就是会这样。我以前手动编写树搜索算法，但后来我发现 OpenSpiel 提供了一个通用的树搜索框架（https://openspiel.readthedocs.io/en/latest/intro.html），支持我曾经需要的大部分功能，所以我可以用 Python 写游戏规则，然后接入 OpenSpiel 来分析。 那么，考虑上面的规则。你觉得在两个水平相当的玩家之间，狐狸的胜率有多高？写下你的猜测，你就能知道你对这个问题的直觉有多准。 ## 一个还算强的电脑对手 (https://entropicthoughts.com/what-the-fox-say#a-somewhat-strong-computer-opponent) 对于这类问题，第一站是朴素的蒙特卡洛树搜索（mcts），使用随机推演到终局来对叶子节点进行评分。在未经优化的 Python 中，它在玩"饿死狐狸"时每秒大约能执行 1,000 次搜索迭代。我给了这个算法不到一秒的思考时间，然后分别扮演狐狸和绵羊与它对战。在那些对局中，狐狸似乎大多数时候都能赢。² ² 除非绵羊逼出和棋，只要绵羊数量足够，由于游戏的循环特性，它们是可以做到的。 让这个算法自己和自己对弈也得到了类似的结果：大约 85% 的对局由狐狸获胜。 有了这么多佐证证据，我差点就宣布实验结束了。我并不预期更深的搜索能带来多大改善，因为分支因子相对较低，部分原因在于绵羊移动的限制。 但为了确保万无一失，我还是尝试了最后一局。我扮演狐狸，电脑扮演绵羊，搜索预算为 8,000 次迭代。虽然它的棋艺仍然不算特别高明，但它成功利用了我的两次失误，真的进入了获胜局面。用绵羊！这引起了我的兴趣，这意味着实验远未结束，可能确实需要更深的搜索才能更准确地反映可能的策略。 ## 这说明了游戏的什么特点 (https://entropicthoughts.com/what-the-fox-say#what-this-says-about-the-game) 我没有立刻意识到，但在那局高搜索预算的对局中发生的事情是：我们学到了一些关于"饿死狐狸"本质的东西。 绵羊一方要想下好，需要比狐狸一方思考得更深。由于绵羊在与狐狸的单独对抗中实力如此悬殊，*它们必须协调整个羊群的移动来击败狐狸*，而每回合只能移动一步，这就需要在很多回合上进行策略规划。³ ³ 事实上，绵羊玩家与其说是在移动绵羊，不如说是在移动羊群中的空位，以确保这些空位远离离狐狸最近的绵羊。 这是游戏的一个*绝妙*特性，因为 (a) 在主题上非常贴切，(b) 这意味着一个小孩可以和成年人对战，而且双方都还能享受乐趣；小孩玩狐狸方，而成年人只是需要想得更深一些。 ## 加速电脑对手 (https://entropicthoughts.com/what-the-fox-say#speeding-up-the-computer-opponent) 然而，我不想等待 16,000 次迭代或者纯粹 mcts 所需要的数量才能下出非常强的棋。该搜索算法中开销较大的部分之一是对搜索树中叶子节点的随机推演评分。一种加速叶子评分的技巧是在游戏结束之前就截断推演，⁴ ⁴ 截断推演的深度取决于游戏的复杂度和推演策略的质量。对于完全随机的推演，甚至可能应该在深度零截断——即完全不执行任何随机移动，因为它们使被评分的状态比之前的叶子节点更不能代表最终状态。就"饿死狐狸"而言，在启发式函数的第一版草稿中，推演进行 8 个半步（ply）后停止似乎能产生最好的结果，但如果有更强的启发式函数，更短的推演可能更好，因为它们用不评估那么远的未来为代价，换来了更多树搜索的时间。 然后使用启发式函数来对截断时尚未终止的对局中的局面进行评分。启发式值经过缩放，其幅度小于已终止对局给出的分数，这样当树搜索能够同时看到两者时，会优先考虑胜负信号而非启发式值。 但这意味着需要一个启发式函数。一个原始的启发式函数可能基于物质，比如"存活的绵羊数量"，或基于进展，比如"绵羊总共获得的行数"。一个更复杂的启发式函数可能包含这两个变量以及更多。如果我们没有计算机，我们可能最好就是选出前三个变量并等权重地加权它们（https://entropicthoughts.com/arithmetic-models-better-than-you-think）。 但我们有计算机，所以可以做得更好。我们做的是让弱树搜索⁵ 多次进行自对弈。 ⁵ 搜索预算大约每半步 0.5 秒，叶子节点通过随机推演到终局来评分。 从每局对弈中，我们随机采样一个局面⁶，记录对局结果，然后训练一个回归模型，根据这些采样局面中的游戏状态来预测对局结果。我们得到的权重通过最小化平方损失来优化，这大概正是我们想要的启发式函数。 ⁶ 只采样一个位置，以避免处理同一局对弈中连续局面之间的强相关性。 一旦我们有了这些权重，我们就可以创建新一代树搜索，使用相同的搜索预算，但采用截断推演并应用学到的启发式函数。然后让它与上一代对战以确认它确实更好，如果确实更好，它就再进行多次自对弈，我们再采样新的局面，再拟合回归。由于它比上一代下得更好，它会找到从上一代无法获胜的局面中取胜的方法。因此，启发式函数对结果的预测——假设双方都下得很好——将变得更加准确。 我们重复这个过程几次，最终得到的是一个相当强的对手，即使在较短的思考时间预算下也是如此。好吧，至少无论它扮演哪一方，都能稳定地把我打得落花流水。 ## 学到的评估函数 (https://entropicthoughts.com/what-the-fox-say#the-learned-evaluation-function) 也许训练出来的权重能告诉我们一些关于好局面是什么样子的信息，这可能也有助于我们提高游戏水平。由于我们还没有看到链接函数⁷，我们无法对这些权重的绝对值做任何分析，不过它们的相对大小本身就很有趣。 ⁷ 它是一个双曲正切函数，将原始分数（实数，无穷支撑）映射到 \[−1, +1\] 的范围，分别表示"必败"和"必胜"，和棋的值为零。但我们还需要偏置项（大约 +1）才能将其转换为最终值，这其实不完全是概率，但非常接近。 - **已被吃掉的绵羊数量**：每只绵羊为狐狸加 +0.036 - **可以被吃的绵羊数量，轮到狐狸走**：每只绵羊为狐狸加 +0.096 - **可以被吃的绵羊数量，轮到绵羊走**：每只绵羊为狐狸加 +0.035 - **狐狸玩家的候选走法数量**：每步为狐狸加 +0.021 - **绵羊总共获得的行数**：每行为绵羊加 +0.0034 - **围栏中的绵羊数量**：每只绵羊为绵羊加 +0.017 虽然很诱人，但立刻就去解释这些数字是不恰当的，因为这里训练的启发式函数还包含另一样东西。它还训练了棋盘上特定位置的权重，这回答了一个关于玩家占据棋盘上特定位置有多有价值的一般性问题。 棋盘位置的价值吸收了上面部分变量的系数。例如，上面的列表显示围栏中的绵羊价值为 0.017，但围栏中最不值钱的位置价值为 0.11，而围栏外的平均位置价值为 0.09。因此，一只绵羊在围栏中（相比在围栏外）的价值永远不会低于 0.11−0.09+0.017=0.04。平均而言是 0.08，远高于上面的列表让我们以为的数值。 以下是绵羊玩家的其余棋盘位置价值。 ``` 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 ``` 这告诉我们，`c7` 位置的绵羊价值为 0.23，其中大部分价值来自位置本身，只有一小部分来自"围栏中绵羊数量"这个变量的总体价值。以下是一些其他观察： - 第 2 行的所有位置都很差，因为那里的绵羊暴露在被吃掉的风险中，同时也对目标没有贡献。 - 位于边缘但不在角落的位置，比如 `b3`、`c3`、`c6` 和 `d7`，通常比它们的角落邻居更差，因为有被吃掉的风险。 - 像 `a5` 这样的位置很差，因为困在那里的绵羊只有一个可走的方向，而且会被 `c5` 处的狐狸封死。我猜 `a4` 差的原因类似：它没有给绵羊留下太多选择余地。（话虽如此，`a5` 有一个可取之处：它保护了 `b5` 位置上更值钱的绵羊不被吃掉。） - 除了第 2 行和第 4 行——它们都在围栏外且有较高的被吃风险——各行的价值随着距离围栏越近而越高。 - 我很惊讶 `d6` 格对绵羊来说竟然这么值钱！我不知道原因。可能与机动性有关。 这些位置价值也帮助我们解读之前的宏观层面变量： - 绵羊每获得一行的平均价值为 0.02，有利于绵羊。 - 绵羊在围栏中的平均价值（相比围栏外）为 0.08，有利于绵羊。 - 在回合开始时可以吃掉一只绵羊的平均价值为 0.20，有利于狐狸。 - 一只被吃掉的绵羊的平均价值为 0.15，有利于狐狸。 一只被吃掉的绵羊的价值是一个很好的、直观的度量尺度。我们可以用*绵羊价值*来表示其他所有数值，类似于国际象棋中用兵值来衡量一样。按照这个换算，绵羊玩家需要总共获得九行的收益才能弥补一只绵羊的损失。 牺牲一只绵羊来让另外两只绵羊进入围栏看起来可能是一笔好交易（净绵羊价值 +0.07）。然而，故意牺牲绵羊意味着把它放到狐狸能够吃掉它的位置，这比仅仅失去一只绵羊更糟。这笔交易的实际净绵羊价值为 −0.27。我不知道为什么即将到来的"喂食"比已被吃掉的绵羊对绵羊更不利，但我猜测这是因为跳跃让狐狸能够移动两个位置，从而更快地穿越棋盘。⁸ ⁸ 按照这个逻辑，我们应该得出结论：这种移动两格的能力（单独来看，不考虑伴随的吃子）平均而言值惊人的 0.2 绵羊价值！ 绵羊说够了。狐狸玩家的各个位置价值如下： ``` 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 ``` 这些位置价值在整个棋盘上更加平坦，平均值对应 2.3 绵羊价值——每只存活的狐狸价值略高于两只存活的绵羊。这里