程序间博弈研究：有限状态机竞争、进化与不同游戏策略分析

Stephen Wolfram相关信息

有关于Stephen Wolfram的Writings等相关链接，包括ABOUT、WRITINGS、PUBLICATIONS、MEDIA、SCRAPBOOK、CONTACT等，还有其在X、Facebook、LinkedIn、SoundCloud、Twitch等平台的链接。同时有文章分类，如人工智能、宏观视角、生物学等众多类别。

目录

包含顶部、基本设置、有限状态机策略、可能的有限状态机空间、获胜的复杂性、不同规模机器之间的竞争、有限状态机的自适应进化、囚徒困境呢、所有可能游戏的空间、元胞自动机策略、元胞自动机与有限状态机、元胞自动机策略的自适应进化、图灵机策略、讨论、历史与个人笔记、致谢等内容。

程序间的博弈：竞争的规则学

2026年6月4日发布此研究。无论是在生物学、经济学、政治学等众多领域，常遇到可建模为两个主体反复相互竞争的情况。每一步中，每个主体从一组特定行动中选其一，按博弈论方式，主体根据自己和对手行动获固定“收益”。主体靠特定固定程序即“策略”决策，决策输入是主体和对手过去行动序列。长期以来好奇系统考虑所有可能策略会怎样，可应用规则学方法解决。假设每步主体有两种行动，用特定图标表示，采用“匹配或不匹配”游戏收益规则。绘制不同策略下主体累积收益，将一定步数后累积收益最大主体视为“获胜主体”，以此对不同程序排名，探索竞争的规则学。可用多路图表示所有可能行动序列，每个主体在“匹配或不匹配”游戏中有累积收益，特定策略会在多路图中定义特定路径。思考获胜策略基于的程序是复杂还是简单，竞争会导致复杂性还是简单性。研究生物进化和机器学习最小模型发现，自适应进化常使简单目标以复杂方式实现，探讨目标是战胜其他主体时，潜在开放性竞争是否会导致更复杂行为或程序。

有限状态机策略

有限状态机可视为定义简单的程序，研究由其定义的策略。给出一个3个状态的有限状态机示例，用对手行动序列在有限状态机图中定义路径，根据到达状态颜色确定下一个行动。有时将有限状态机状态排列在一条线方便，可总结使用特定输入所采取的路径。两个有限状态机相互竞争时，一个机器输出成为另一个机器输入。使用“匹配或不匹配”游戏收益规则，可得出机器累积收益，最终认为主体2获胜。这里设置是确定性的，与博弈论中常研究的设置不同。

可能的有限状态机空间

具有s个状态的有限状态机可能图数量为(2 s²) s，但部分图对应机器行为相同，不同机器数量更少。

2状态机器

2状态情况下有22个不同机器，用数字标识。给出这些机器两两竞争示例及平均收益，在所有有限状态机两两竞争中，行动序列最终会周期性，周期最多等于机器状态数乘积。显示22个2状态机器相互竞争结果，评估“总体获胜者”可查看机器与其他机器竞争平均收益，获胜者是机器26，还给出其与其他2状态机器竞争平均收益及实际行为。列出所有不同机器按平均收益排名情况，让排名前三亚军机器与所有机器竞争。可总结机器行为，竞争步数会影响结果，2状态机器最大周期为4步，最大瞬态为3步，实际平均收益随总步数变化，前几步排名会变化，但此情况确定最终获胜者不需要太多步数。还有关于“平均”含义的补充说明，若用中位数代替平均值，表现突出的获胜机器是机器1172。

3状态机器

对于956个3状态不同机器，给出“竞争数组”、每台机器平均收益及分布。在“匹配或不匹配”游戏中，排名靠前机器情况，排名第一的机器1164与所有3状态机器竞争平均收益，可能极限平均收益分布，最常见行为形式。两台3状态机器竞争最大可能周期为9，机器1164最大周期为7，有792对3状态机器会产生周期为9的行为，3状态机器最大瞬态结果为8。

补充说明：“平均”的含义

讨论一台机器与其他机器竞争“平均”表现，之前将“平均”定义为与每台其他机器竞争收益平均值，若用中位数，表现突出获胜机器是机器1172，给出此情况下平均收益及其分布，中位数“异常高”原因是该机器所有平均收益中恰好有1/2为 +1，相应平均值因平均收益分布“左尾”被拉低。

获胜的复杂性

查看每个2状态有限状态机与其他2状态机器竞争实际行为并按平均收益排序，平均收益为0时行为简单，其他平均收益时行为更复杂。通过查看压缩大小了解复杂性，956个3状态机器结果显示平均收益与行为复杂性估计无强相关性，平均收益最高机器中行为复杂程度差异大，说明获胜机器行为特征非特别复杂或简单，详细结构决定哪些机器获胜。

不同规模机器之间的竞争

探讨状态数更多的有限状态机是否比状态数少的机器表现更好。2状态机器与其他2状态机器竞争最佳平均收益约为0.151，3状态机器与2状态机器竞争最佳平均收益为0.593，3状态机器平均收益分布更宽，因其可能数量更多，似乎能更好“智取”2状态机器。在与2状态机器竞争中表现最佳的3状态机器是机器1234，虽不总能确定获胜，但多数情况能获胜，它能表现得和许多2状态机器一样，与它们“产生共鸣”。4状态机器中在与2状态机器竞争表现最佳的是机器109828，在22个2状态机器中只有6种情况收益小于 +1，可认为它成功“涵盖”大多数2状态机器行为。

有限状态机的自适应进化

思考能否用有限状态机建立最小模型模拟竞争主体进化情况。研究所有可能有限状态机空间，探讨通过自适应进化找到的机器序列。对有限状态机进行连续突变，顶点突变反转颜色，边突变反转颜色或重新路由。假设对手是3状态机器1165，用4状态机器进行自适应进化，从随机4状态机器开始，对其进行连续随机突变，若不降低平均收益就接受，得到典型“适应度曲线”，最终收益达到最大值 +1，各种“突破”收敛到“完美解决方案”，不同随机突变“适应度曲线”总体形式相同。绘制自适应进化过程如何“在规则空间中移动机器”。4状态机器与所有2状态机器竞争时，适应度增加但未达到 +1，最佳机器仍会输给一些2状态机器，最终平均收益约为0.62。10个状态机器可自适应进化出对每个2状态机器极限收益都为 +1的机器，可看作“通用获胜者”，能针对不同对手有不同“专门部分”，对956个3状态机器作为对手时表现良好，平均收益 +0.603，但有一些机器未获胜。若机器和对手都进行自适应进化，交替对机器及其对手突变，保留不降低平均收益的突变。两台最初相同的4状态机器平均收益进化情况，有时一台机器获胜，有时对手获胜，通过自适应进化找到的机器很快忘记最初状态，状态数更多的机器获胜交替情况通常更少。

囚徒困境呢

之前基于“匹配或不匹配”游戏，现在考虑“囚徒困境”游戏，给出该游戏收益情况，通常将特定图标解释为“背叛”和“合作”。可基于有限状态机为囚徒困境游戏定义策略，给出2状态机器之间迭代游戏例子，收益由囚徒困境游戏决定。