主題
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 貢獻

使用 探索

參考文獻

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."

在 中被引用

康威博弈

請引用為

Briggs, Keith. “康威博弈。” 來自 Web 資源，由 Eric W. Weisstein 建立。 https://mathworld.tw/ConwayGame.html

主題分類