主题
Search

康威博弈

康威博弈由 J. H. 康威于 1976 年提出，旨在为分析满足特定要求的博弈提供正式的结构

1. 有两位玩家，左方和右方（L 和 R），他们轮流行动。

2. 先行无法移动的玩家输掉游戏。

3. 双方玩家都拥有关于游戏状态的完整信息。

4. 没有运气的成分。

例如，尼姆博弈是康威博弈，但国际象棋不是（因为可能出现平局和僵局）。 请注意，康威的“生命游戏”（有点令人困惑地）不是康威博弈。

一个康威博弈要么是

1. 零博弈，表示为 0 或 {|}，或者

2. 形式为 {G^L|G^R} 的对象（有序对），其中 G^L 和 G^R 是康威博弈的集合。

G^L 和 G^R 的元素分别称为左方和右方选项，是左方和右方可用的移动。 例如，在博弈 {{a,b}|{}} 中，如果是 L 的回合，他可以移动到 a 或 b，而如果是 R 的回合，他没有选项并立即输掉。

在每个位置双方玩家都拥有相同移动的游戏称为无偏博弈。 玩家拥有不同选项的游戏称为偏博弈。 只有有限个位置的游戏称为短博弈。 可能返回起始位置的游戏称为循环博弈。

理论中经常出现的一些简单博弈有缩写名称

1. *={0|0}

2. 1={0|}

3. n={n-1|} 对于任何正整数 n

4. 1/2={0|1}

5. ^={0|*}

6. v={*|0}

递归构造过程可用于生成所有短博弈。 过程中的步骤称为天，在第 n 天首次出现（诞生）的博弈集合表示为 G(n)。 第零天是 G(0)={0}。 后续天是 G(n)= union {{L|R}}，其中 L 和 R 的范围涵盖 G(n-1) 的所有元素。 第 1 天有四个元素，G(1)={0,*,1,-1}，G(n) 中 n=0, 1, ... 的元素数量分别是 1, 4, 22, 1474, ... (OEIS A065401)。 D. Hickerson 和 R. Li 在 1974 年找到了 G(3)，但没有其他项是已知的。

以下配对表显示了 G(2) 及其左方和右方选项

*{*,0}-101
1{1|*}{1|{0,*}}{1|-1}{1|0}1*
0^v*{0|-1}*1/2
*0v{*|-1}v0
-10-1/2-1*-1/20
{*,0}^*2{{0,*}|-1}^*1/2

所有康威博弈的集合在以下运算下构成一个阿贝尔群

G+H={(G^L+H) union (G+H^L)|(G^R+H) union (G+H^R)}

-G={-G^R|-G^L}

这里，GL+H 形式的表达式表示所有 g+H 形式的表达式的集合，其中 g 在 G^L 中。

所有康威博弈的集合在比较运算下构成一个偏序集

1. G=H。 如果在博弈 G-H 中后行动的玩家可以获胜（G 和 H 相等）。

2. G||H。 如果在博弈 G-H 中先行动的玩家可以获胜（G 和 H 是模糊的）。

3. G>H。 如果左方可以在博弈 G-H 中获胜，无论他先行动还是后行动（G 大于 H）。

4. G<H。 如果右方可以在博弈 G-H 中获胜，无论他先行动还是后行动（G 小于 H）。

我们用 G-H 表示 G+(-H)。 G>=H 将表示 G=H 或 G>H，<= 同理。 例如，我们有 1>0、*=* 和 *||0。

每个 G(n) 都是关于关系 < 的偏序集。

一个基本定理表明，所有博弈都可以放入规范形式，这允许轻松测试相等性。 规范形式取决于两种类型的简化

1. 移除支配选项：如果 G={{L_1,L_2,...}|G^R} 且 L_2>=L_1，则 G={{L_2,...}|G^R}； 如果 G={G^L|{R_1,R_2,...}} 且 R_1>=R_2，则 G={G^L|{R_2,...}}。

2. 替换可逆移动：如果 G={{{A^L|{A^(R_1),A^(R_2),...}},G^(L_2),...}|G^R} 且 A^(R_1)<=G，则 G={{{A^(R_1^L)},G^(L_2),...}|G^R}。

如果 G 没有支配选项或可逆移动，则称 G 为规范形式。 如果 G 和 H 都处于规范形式，则它们都具有相同的左方和右方选项集，因此相等。

另请参阅

占领游戏, 博弈论, 海肯布什, 尼姆博弈, 超现实数

本条目由 Keith Briggs 贡献

使用 Wolfram|Alpha 探索

参考文献

Berlekamp, E. R.; Conway, J. H.; and Guy, R. K. Winning Ways for Your Mathematical Plays. Wellesley, MA: A K Peters, 2004.Calistrate, D.; Paulhus, M; and Wolfe, D. "On the Lattice Structure of Finite Games." In More Games of No Chance (Ed. R. J. Nowakowski). Cambridge, England: Cambridge University Press, pp. 25-30, 2002.Conway, J. H. On Numbers and Games. Wellesley, MA: A K Peters, 2000.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 283-284, 1996.Fraser, W.; Hirshberg, S.; and Wolfe, D. "The Structure of the Distributive Lattice of Games Born by Day n." http://homepages.gac.edu/~wolfe/papers/dayn/structure.pdf.Gonshor, H. An Introduction to Surreal Numbers. Cambridge, England: Cambridge University Press, 1986.Knuth, D. Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. Reading, MA: Addison-Wesley, 1974. http://www-cs-faculty.stanford.edu/~knuth/sn.html.Schleicher, D. and Stoll, M. "An Introduction to Conway's Numbers and Games." http://arxiv.org/abs/math.CO/0410026.Siegel, A. N. "Loopy Games and Computation." Ph.D. thesis. Berkeley, CA: University of California Berkeley, 2005.Sloane, N. J. A. Sequence A065401 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

康威博弈

请引用为

Briggs, Keith. “康威博弈。” 来自 MathWorld--Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/ConwayGame.html

主题分类