程序之间的博弈：竞争的Ruliology

# 程序之间的博弈：竞争的规则学 来源：https://writings.stephenwolfram.com/2026/06/games-between-programs-the-ruliology-of-competition/ 程序之间的博弈：竞争的规则学 ## 基本设定 无论是在生物学、经济学、政治学还是其他许多领域，我们经常会遇到可以建模为两个主体反复相互竞争的场景。想象每个步骤中每个主体可以从一组动作中选择一个，然后——以经典的博弈论方式——每个主体（或“玩家”）根据自己和对手采取的动作获得某个固定的“收益”。但主体如何决定采取什么动作？我们假设每个主体有一个固定的程序——或“策略”——来做出决策。并且我们假设这些决策的输入是主体及其对手在过去采取的动作序列。 近一个世纪以来，对于特定策略的选择已经有了大量研究。但我一直好奇的是，如果我们系统地考虑所有可能的策略，会发生什么。如果我们把策略看作程序，这就成了一个我们可以立即应用规则学方法的问题。这就是我在这里要做的事情。 为了更具体地说明这个设定，让我们假设在每个步骤中，每个主体采取两种可能动作之一，用 和 表示。暂时让我们采用经典的“匹配或不匹配”（“猜硬币”）游戏的收益——其中玩家1在匹配时获得更大收益，而玩家2在不匹配时获得更大收益： 那么，当主体反复进行这个游戏时会发生什么？嗯，这取决于他们的策略。以下是几个不同策略选择的例子： 绘制这两种主体的累积收益（用 和 表示）在每个案例中，我们得到： 通常我们会认为“获胜主体”是在一定步数后累积收益数值最大（即在这些图中最终位于顶部）的主体。根据这样的标准，我们就能对不同程序进行排名，并总体上探索竞争的规则学。 在我们使用的基本设定下，我们可以用多路图表示所有可能的动作序列： 对于任何给定的动作序列，在我们的匹配或不匹配游戏中，每个主体都有一个累积收益： 如果每个主体采用特定策略，这将定义多路图中的一条特定路径。对于上面例子中使用的策略，路径如下： 要拥有一个获胜策略需要什么？在接下来的内容中，我们将考虑基于几种不同类型程序的策略。但我们始终可以问的一个基本问题是，最终获胜的策略往往是基于更复杂还是更简单的程序，或者表现出更复杂还是更简单的行为。 换句话说，如果你想赢，你是应该试图构建一些复杂的东西？还是应该期望能够找到一个能“破解游戏”的“简单技巧”，并且（至少通常）让你获胜？实际上，我们是在问竞争是否倾向于导致复杂或简单。 我最近研究了生物进化与机器学习的最小模型，在这些模型中，程序通过自适应进化来最大化某个外部施加的适应度函数。我发现的是，即使使用的适应度函数很简单，最大化它的程序的行为通常也相当复杂。换句话说，自适应进化往往会以一种复杂的方式实现一个简单、固定的目标。 那么，如果我们的目标不是一个固定的、外部强加的目标，而只是广泛地要战胜其他主体呢？这种潜在的开放式竞争是否会引导我们走向更复杂的行为（或更复杂的程序），还是不会？这正是我们通过研究竞争的规则学能够探索的问题。 ## 来自有限状态机的策略 有限状态机可以被认为是定义了极其简单的程序（可能建模生物学中的通路、经济学中的决策过程等）。为了开始我们对竞争规则学的研究，我们将考察由有限状态机定义的策略。 一个典型的有限状态机（这里是有3个状态）的例子是： 我们将使用这个有限状态机来定义主体的策略。为了理解其工作原理，假设主体对手采取的动作序列为： 我们的想法是使用这个动作序列在有限状态机图中定义一条路径，然后根据所到达状态的颜色确定下一个动作。我们从带有输入箭头的顶点开始，然后依次沿着颜色与对手下一步动作匹配的边前进： 在这个过程结束时，我们将到达图中的某个顶点（即有限状态机中的某个状态）。在所示的特定情况下，我们到达的状态是 。然后我们取策略的输出——即主体要采取的下一个动作——为 。 有时将有限状态机的状态排列在一条线上会很方便： 然后我们可以用给定输入总结所采取的路径，显示连续达到的状态： 那么，如果两个有限状态机竞争会发生什么？基本想法是，一个机器的连续输出成为另一个机器的连续输入，反之亦然。如果我们的第二个机器是 那么我们可以通过以下方式表示机器的行为： 如果我们使用的收益是匹配或不匹配游戏的收益，那么这些机器的累积值为 所以最终主体2可以被视为获胜者。 这里需要注意的是，在我们使用的设定中，一切都是确定性的：在每个步骤中，每个主体采取的动作都是根据其策略从过去移动的历史中确定性地计算出来的。这与博弈论中最常研究的不同设定不同，在博弈论中每个移动在效果上被视为独立，但不同动作可以有概率（“混合策略”）——并且最终对“不同骰子投掷结果”进行平均。 ## 可能的有限状态机空间 具有*s*个状态的有限状态机的可能图数量为(2*s*2)*s*。但其中一些图对应行为相同的机器——因此不同机器的数量更少： ### 2-状态机 在2-状态的情况下，22个不同的机器是 其中我们通过编号识别每个机器。 那么，如果这些机器成对竞争会发生什么？这里有几个例子，每个例子中我们识别平均收益（这里是匹配或不匹配游戏10轮的收益）： （在所有有限状态机之间的竞争中，移动序列最终必须变为周期性的——周期最多等于每个机器中状态数的乘积。） 如果22个不同的2-状态机中的每一个都与所有其他机器竞争，会发生什么？我们可以通过显示每对机器的平均（长期）收益来总结结果（收益是每个机器“作为主体1”进行游戏时的收益；在匹配或不匹配中，如果“作为主体2”进行游戏，收益取反）： 那么哪个机器是“总体赢家”？评估这一点的一种方法是看给定机器与所有其他（不同）机器竞争时所获得的平均收益的均值： 按此度量，赢家是机器26： 将这个机器与所有（不同的）2-状态机竞争，我们得到以下平均收益： 每种情况的实际行为——本身不依赖于收益，只依赖于涉及的机器——是： 获胜机器的“亚军”有哪些？以下是所有不同的机器，按它们的平均收益排序： 如果我们让前三名亚军与所有机器竞争，结果如下： 我们可以通过显示机器在与所有其他机器竞争时的行为历史（实际上，是通过将上面图片中的第一列放在一起）来总结机器的行为。以下是所有机器的结果（15步），按平均得分从高到低排序： （再次说明，这些图片完全由涉及的机器决定；只有匹配或不匹配游戏中的收益决定它们的排序。） 这里要补充一点，与我们之前所说的有关：我们让机器进行多少步竞争。对于所有有限状态机，行为最终必须变为周期性——对于2-状态机，最大周期是4步，最大瞬态是3步。但实际的平均收益均值随着考虑的总步数变化： 值得注意的是，至少在最初几步，排序会变化： 但在这个例子中，不需要太多步就能看清最终的赢家（稍后我们会看到需要更长时间的示例）。 （还有其他微妙之处。其中之一是我们通过让每个机器与所有其他不同机器进行游戏来计算平均收益。原则上我们也可以包括其他等效机器——这会略微改变我们平均值的权重。但由于我们真正关心的是策略，而不是机器本身，我们使用的方案似乎更合适。） ### 3-状态机 对于具有*s*= 3个状态的956个不同机器，相应的“竞争阵列”（1000步后）为： 每个机器的平均收益均值（即“竞争阵列”中每行的平均值）为 而这些平均收益均值的分布为： 对于匹配或不匹配游戏，排名靠前的几个机器是： 将排名最高的机器（*s*= 3 机器1164）与所有（不同的）3-状态机竞争，我们得到以下平均收益： 这里可能的极限平均收益分布为： 最常见的观察行为形式为： 两个3-状态机之间竞争的最大可能周期是9。机器1164从未完全达到这一点；它与机器2546和2755竞争时出现最大周期7（两者均给出极限平均收益–1）： 如果查看所有可能的3-状态机对，结果发现有792对产生周期9的行为，例如： （这些没有瞬态；3-状态机的最大瞬态为8。） ### 旁注：我们所说的“平均”是什么意思？ 我们讨论了机器在与所有其他（不同）机器竞争时“平均”表现如何。但“平均”是什么意思？到目前为止，我们取“平均”为与每个其他机器竞争所得的收益的平均值（而这些收益本身是连续步骤的平均值）。但是如果我们使用中位数而不是平均值呢？以下是每个机器与其他所有机器运行1000步后的中位数收益： 这里引人注目的获胜机器是机器1172： 这种情况下的平均收益及其分布为： 中位数“异常高”，因为对于这个机器，恰好一半的平均收益是+1。（相应的平均值被平均收益分布中的“左尾”拉低了。） ## 获胜的复杂性 让我们（基本上如上所述）查看每个不同的2-状态有限状态机在与所有其他2-状态机竞争时的实际行为，按平均收益均值从小到大排序： 平均收益均值为0的情况看起来很简单的行为。但对于其他平均收益均值，给定机器与所有其他机器竞争的行为似乎更复杂。 我们可以通过查看上面所示行为数组的压缩大小（通过Compress获得）来部分了解这种复杂性： 以下是956个不同3-状态机的相应结果——显示平均收益均值与我们估计的行为复杂性之间没有强相关性： 实际上，在平均收益均值最高的机器中，行为复杂性的水平仍然相当多样化 所指示机器的“行为轨迹”为 和 换句话说，至少在这种情况下，我们不能说获胜机器的特点是行为特别复杂或是特别简单。看来是详细的结构，而不是整体特征，决定了哪些机器会获胜。 ## 不同大小机器之间的竞争 拥有更多状态的有限状态机是否能够系统性地比状态数更少的机器做得更好（即获得更大的收益）？任何2-状态机在与所有其他2-状态机竞争时能实现的最佳平均收益均值约为0.151。但例如，如果我们考虑3-状态机与2-状态机竞争（1000轮），最佳平均收益均值则为0.593： 查看可能的平均收益均值的分布，我们看到3-状态机的平均收益均值分布比2-状态机更宽——这一事实至少部分是由于可能的3-状态机比2-状态机多得多： 但值得注意的是，最宽的分布是3-状态机与2-状态机竞争时的分布：实际上，凭借其更大范围的可能策略，3-状态机似乎能够更好地“智胜”2-状态机。 在对抗2-状态机时整体表现最好的3-状态机是机器1234： 它并不总是决定性地获胜（平均收益+1），但大多数情况下如此： 它是如何做到这一点的？基本上，对于许多不同的2-状态机，这个特定的3-状态机能够表现得就像它们一样： 从某种意义上说，这个3-状态机的某些方面与许多2-状态机“共鸣”： 那么4-状态机呢？在对抗2-状态机时整体表现最好的4-状态机是机器109828： 在22个2-状态机中，它仅在6种情况下获得小于+1的收益： 以下是所有22种情况的行为： 再一次，我们可以把这个4-状态机视为成功地“覆盖”了大多数2-状态行为： ## 有限状态机的自适应进化 在许多实际竞争场景中，竞争主体有办法进化。那么，我们能否使用有限状态机构建一个最小模型？ 到目前为止，我们所做的一直是在所有可能的有限状态机的空间中观察。但通过自适应进化找到的机器序列呢？例如，是否存在一种方式自适应地