博弈复杂度

来自testwiki
跳转到导航 跳转到搜索

Template:NoteTA Template:Roughtranslation 博弈复杂度（Template:Lang-en）可以用许多方法加以衡量。本条目讲述其中的5種方法：状态空间复杂度（Template:Lang）、博弈树的大小（Template:Lang）、策略复杂度（Template:Lang）、博弈树复杂度（Template:Lang）與计算复杂度（Template:Lang）。

博弈复杂度的衡量

状态空间复杂度

状态空间复杂度指的是从博弈最开始的状态可以变化出的符合规则的状态的数量。[1]

当这太难以计算时，常常通过包含一些不符合规则的状态或不可能在博弈中出现的状态, 从而计算出一个上界限。

博弈树的大小

博弈树的大小指的是博弈可以进行的总次数：从博弈树最初的根节点开始延伸出的叶子节点的数量.

博弈树通常比状态空间要大得多，因为同一个状态可以由不同的行为顺序形成。（例如，在一回合井字棋游戏中，面板上有两个X和一个O，这个状态可能由两个不同的方式形成，具体的形成过程由第一个X的下子位置所决定）。一个博弈树的大小的最大值有时可以这么计算：通过仅增大博弈树的方式，简化博弈的过程（例如，允许一些本来不符合规则的行为），直到博弈树的大小变得易于计算。

不过，对于一些没有行为上限的博弈（比如说没棋盘大小的界限，或者有一个可以重复博弈状态的规则），博弈树的大小将会是无限的。

决策树

之后的两种方案用到了决策树的方法。一个决策树是博弈树的子树。决策树的状态会被标记上「玩家A获胜」、「玩家B获胜」或者「平手」；如果有那个状态可以被证明具有一个标记（假设双方都作出了最好的决策），并且光从其它状态就可以得出结论.。（终端的状态可以直接标记；如果现在该A行动：如果下一个状态标志着A的胜利，那么现在的状态可以被标记为「玩家A获胜」；如果下一个状态标志着B的胜利，那么现在的状态可以被标记为「玩家B获胜」；或者可以被标记为「平手」，如果下一个状态是平局或者B胜利。相应的对于现在该B行动也是一样。）

决策复杂度

一个博弈的决策复杂度指的是在构成初始状态取值的最小的决策树中，叶子节点的数量。

博弈树复杂度

一个博弈的「博弈树复杂度」指的是在构成初始状态取值的最小「整个」决策树中，叶子节点的数量。[1] 整个决策树包含树中所有深度的节点。

这是一个为了尝试决定初始状态取值，所做出的对于需要考虑的节点数量的一个极小化极大算法（Minimax）。

就算是去估量博弈树复杂度，那也十分困难。不过对于一些博弈，一个合理的下界限可以由底数为博弈的平均分支因子，指数为博弈的Template:Link-en的幂得出，即可以表示为：

GTC≥bd

计算复杂度

一个博弈的計算複雜性理論描述对博弈进行渐近分析的难度，随着它变得过于巨大，用大O符号表示，或者用复杂性类的成员关系表示。这个概念并不应用于特定的博弈，而是用于Template:Link-en，它们会变得非常大，通常在一个n宽n高的面板上玩弄它们。（从计算复杂度的角度来看，一个在有限面板上进行的博弈是一个有限问题，可以通过计算O(1)解决。例如遍历从方案到最佳的移动方案的所有方案。）

例子: 井字棋

Template:Seealso

以井字棋而言，一个简单的状态空间大小的上界限是39 = 19,683。（ 每一个格子中有3种状态,，有9个格子）这样计算包含了许多不合规则的状态，比如有5个X却没有0的状态，或者两方玩家都有形成一字的状态。一个更精细的计算，除去了这些不合规则的状态之后，留下5,478个状态。然后，如果把旋转或翻转后会得到相同结果的状态算作同一个的状态话，那么就可以得出765个真正本质上不同的状态。

一个简单的博弈树大小的上界限是9! = 362,880。（一开始有9个格子可以下子,，第二回合变为8个，以此类推）这包括了一方玩家获胜后继续下子的不符合规则的情况。一个更精细的计算得出的是255,168种博弈过程。如果把旋转或翻转后会得到相同结果的状态当作相同的话，那么就仅有26,830种博弈过程。

井字棋的计算复杂度取决与它如何广义化。一种自然的广义化是将其变为m,n,k型博弈：在一个宽"m"高"n"的棋盘上，第一个将"k"个子连成一线的玩家获胜。很容易就可以发现，这个博弈可以通过查找整个博弈树，解DSPACE(mn)，得出结果。这将它归类到了重要的复杂性类PSPACE里面。稍微再花点功夫，可以将它变换为Template:Link-en。[2]

一些知名博弈的复杂度

由于博弈复杂度非常巨大，下面表中一些数据只显示了以10为底数的指数部分。下面的表中的数值都需要小心对待：在博弈中，一个看起来很微小的规则变换会引起结果的巨大变化（通常依然会被粗略地估计），可能实际情况会比数值估计的结果要大得多。

博弈 棋盘大小

(格数)

状态空间复杂度

(以10为底数的指数部分)

博弈树复杂度

(以10为底数的指数部分)

平均博弈长度

(Template:Link-en)

分枝因素 引用 对应Template:Link-en的复杂性类
井字棋 9 3 5 9 4 PSPACE-complete[2]
Sim 15 3 8 14 3.7 PSPACE-complete[3]
五格骨牌 64 12 18 10 75 [4] [5] ?, but in PSPACE
美國播棋[6] 14 13 18 [4] Generalization is unclear
屏風式四子棋 42 13 21 36 4 [7] [1] ?, but in PSPACE
Domineering (8 × 8) 64 15 27 30 8 [4] ?, but in PSPACE; in P for certain dimensions[8]
馬來播棋 14 15 33 [4]
英國跳棋 32 20 or 18 31 70 2.8 [9] or [1] EXPTIME-complete[10]
西非播棋[11] 12 12 32 60 3.5 [1] Generalization is unclear
多層式四子棋 64 30 34 20 54.2 [1] PSPACE-complete[2]
迂棋 45 21 46 44 11 [12] ?, but in EXPTIME
直棋 24 10 50 50 10 [1] ?, but in EXPTIME
西洋跳棋 50 30 54 90 4 [1] EXPTIME-complete[10]
中國跳棋(2人) 121 23 [13] EXPTIME-complete [14]
中國跳棋(6人) 121 78 [13] EXPTIME-complete [14]
集結棋 64 23 64 44 29 [15] ?, but in EXPTIME
黑白棋 64 28 58 58 10 [1] PSPACE-complete[16]
OnTop (2人局) 72 88 62 31 23.77 [17]
六貫棋 121 57 98 40 280 [4] PSPACE-complete[18]
五子棋(15x15, 无禁手) 225 105 70 30 210 [1] PSPACE-complete[2]
围棋(9x9) 81 38 45 [19] [1] EXPTIME-complete[20]
國際象棋 64 47 123 80 35 [21] EXPTIME-complete (without 50-move drawing rule) [22]
連六棋 361 172 140 30 46000 [23] PSPACE-complete[24]
雙陸棋 28 20 144 50-60 250 [25] Generalization is unclear
象棋 90 40 150 95 38 [1] [26][27] ?, believed to be EXPTIME-complete
角力棋 61 25 154 87 60 [28] ?, but in EXPTIME
三寶棋 271 127 157 66 240 [4] [29] ?, but in PSPACE
韓國將棋 90 44 160 100 40 [27] ?, believed to be EXPTIME-complete
牆棋 81 42 162 91 60 [30] ?, but in PSPACE
卡卡頌(2p base game) 72 >40 195 71 55 [31] Generalization is unclear
亞馬遜棋 100 40 212 84 374 or 299[32] [33] [34] PSPACE-complete[35]
围棋(13x13) 169 79 90 [1] [19] EXPTIME-complete[20]
日本将棋 81 71 226 115 92 [26] [36] EXPTIME-complete[37]
印度鬥獸棋 64 43 402 92 17281 [38] [39] [40] ?, but in EXPTIME
围棋(19x19) 361 171 360 150 250 [19] [1] EXPTIME-complete[20]
西洋陸軍棋 92 115 535 381 21.739 [41]
Double dummy bridgeTemplate:NoteTag (52) <17 <40 52 5.6

注释

Template:NoteFoot

参考文献

Template:Reflist

外部链接

参见

Template:Div col

Template:Div col end

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 Template:Cite thesis
  2. ↑ 2.0 2.1 2.2 2.3 Template:Cite journal
  3. ↑ Wolfgang Slany: The Complexity of Graph Ramsey Games
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 Template:Cite journal
  5. ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance Template:Wayback, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf Template:Wayback.
  6. ↑ See van den Herik et al for rules.
  7. ↑ Template:Cite web
  8. ↑ Template:Cite paper
  9. ↑ Template:Cite journal
  10. ↑ 10.0 10.1 Template:Cite journal
  11. ↑ See Allis 1994 for rules
  12. ↑ Template:Cite journal
  13. ↑ 13.0 13.1 Template:Cite journal
  14. ↑ 14.0 14.1 Template:Cite journal Proves completeness of the generalization to arbitrary graphs.
  15. ↑ Template:Cite thesis
  16. ↑ Template:Cite journal
  17. ↑ Template:Cite thesis
  18. ↑ Template:Cite journal
  19. ↑ 19.0 19.1 19.2 Template:Cite webTemplate:Dead link This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
  20. ↑ 20.0 20.1 20.2 Template:Cite book
  21. ↑ The size of the state space and game tree for chess were first estimated in Template:Cite journal Shannon gave estimates of 1043 and 10120 respectively, smaller than the upper bound in the table, which is detailed in Shannon number.
  22. ↑ Template:Cite journal
  23. ↑ Template:Cite book
  24. ↑ On the fairness and complexity of generalized k-in-a-row games
  25. ↑ Template:Cite web
  26. ↑ 26.0 26.1 Template:Cite journal
  27. ↑ 27.0 27.1 Template:Cite web
  28. ↑ Template:Cite web
  29. ↑ Template:Cite web
  30. ↑ Template:Cite thesis
  31. ↑ Template:Cite thesis
  32. ↑ The lower branching factor is for the second player.
  33. ↑ Template:Cite journal
  34. ↑ Template:Cite paper
  35. ↑ Template:Cite arxiv
  36. ↑ Template:Cite journal
  37. ↑ Template:Cite journal
  38. ↑ Template:Cite web
  39. ↑ Template:Cite web
  40. ↑ Template:Cite web
  41. ↑ Template:Cite thesis
检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=博弈复杂度&oldid=8485”