組み合わせゲーム理論は、 ゲームの複雑さを いくつかの方法で測定します。
状態空間の複雑さ（初期状態から可能な合法的なゲーム局面の数） ゲームツリーのサイズ（可能なゲームの総数） 決定の複雑さ（初期位置を決定するための最小決定木における葉ノードの数） ゲームツリーの複雑度（初期位置における最小の全幅決定木の葉ノード数） 計算複雑性（ゲームが任意に大きくなるにつれて漸近的に高まる難易度） これらの対策には、様々なゲームシナリオにおけるゲームの状況、起こりうる結果、および計算の複雑さを理解することが含まれる。
ゲームの複雑さの尺度
状態空間の複雑性 ゲームの状態空間複雑度とは、ゲームの初期状態から到達可能な合法的なゲーム状態の数のことである。 [ 1 ]
計算が難しすぎる場合は、（一部の）不正な局面（ゲーム中に決して発生しない局面）も数えることで、上限値を算出できる場合が多い。
ゲームツリーのサイズ ゲームツリーのサイズ とは、プレイ可能なゲームの総数を指します。これは、ゲームの初期位置を根とするゲームツリー の葉ノードの数です。
ゲームツリーは通常、状態空間よりもはるかに大きくなります。これは、異なる順番で手を動かすことで、多くのゲームで同じ局面が発生する可能性があるためです（例えば、盤面にX が2つとOが1つある三目並べでは、最初のXの位置によって、この局面に到達する方法は2通り考えられます）。ゲームツリーのサイズの上限は、ゲームツリーのサイズだけが増加するような方法でゲームを単純化し（例えば、不正な手を許可するなど）、扱いやすいサイズになるまで続けることで計算できる場合があります。
手数に制限がないゲーム（例えば、盤面の大きさや、局面の繰り返しに関するルールなど）の場合、ゲームツリーは一般的に無限になります。
決定木 決定木は ゲーム木のサブツリーであり、各局面は、グラフ内の他の局面のみを調べることで、その局面が（両者が最善の手を打ったと仮定して）その値を持つことが証明できる場合、「プレイヤーAの勝ち」、「プレイヤーBの勝ち」、または「引き分け」とラベル付けされます。終端局面は直接ラベル付けできます。プレイヤーAの番の場合、後続局面のいずれかがAの勝ちであれば「プレイヤーAの勝ち」、後続局面がすべてBの勝ちであれば「プレイヤーBの勝ち」、後続局面がすべて引き分けかBの勝ちであれば「引き分け」とラベル付けできます。（プレイヤーBの番の場合、対応する局面も同様にマークされます。）
ゲームの複雑さを測定する以下の2つの方法は、決定木を使用します。
意思決定の複雑性 意思決定の複雑さとは、初期位置の値を決定する最小の決定木における葉ノードの数のことである。
ゲームツリーの複雑さ ゲームツリー複雑度 とは、初期位置の値を決定する最小の全幅決定木における葉ノードの数です。 [ 1 ] ミニマックス探索で評価する必要のある位置の数の推定値です。
ゲームツリーの複雑さを推定することさえ難しいが、いくつかのゲームについては、次のように近似することができる。G T C ≥ b d {\displaystyle GTC\geq b^{d}} b はゲームの平均分岐係数 、d プライ 数である。
計算複雑性 ゲームの計算複雑性 難しくなる度合いを表し、 ビッグオー記法または 複雑性クラス への所属として表現されます。この概念は特定のゲームに適用されるのではなく、n × n の盤面でプレイするなどして任意に大きくできるように一般化さ れたゲームに適用されます。（計算複雑性の観点から見ると、固定サイズの盤面上のゲームは有限の問題であり、例えば各局面における最善手へのルックアップテーブルを用いることで、O(1)で解くことができます。）
漸近的複雑度は、（考慮する計算リソースの 種類に関わらず）ゲームを解くための最も効率的なアルゴリズムによって定義されます。最も一般的な複雑度尺度である計算時間は 、常に漸近的状態空間複雑度の対数によって下限が定められます。これは、解法アルゴリズムがゲームのあらゆる状態に対応しなければならないためです。また、ゲーム群に対して機能する特定のアルゴリズムの複雑度によって上限が定められます。同様のことが、2番目によく使われる複雑度尺度である、計算に使用される空間 またはコンピュータメモリ の量にも当てはまります。アルゴリズムはゲームの状態を保存する必要がないため、典型的なゲームの空間複雑度に下限があることは明らかではありません。しかし、多くの興味深いゲームはPSPACE困難 であることが知られており、それらの空間複雑度も漸近的状態空間複雑度の対数によって下限が定められることになります（厳密には、この上限はこの量に関する多項式にすぎませんが、通常は線形であることが知られています）。
深さ優先 ミニマックス戦略 では、ゲームのツリーの複雑さに比例した計算時間（ツリー全体を探索する必要があるため）と、ツリーの複雑さの対数の多項式に相当する量のメモリ（アルゴリズムは常に可能な各移動深度でツリーのノードを1つ保存する必要があり、最も深い移動深度におけるノードの数はまさにツリーの複雑さであるため）が必要になります。 後方帰納法は 、考えられるすべての局面に対して正しい手を計算して記録する必要があるため、状態空間の複雑さに比例した量のメモリと時間を必要とします。
三目並べ の場合、状態空間のサイズの単純な上限は 3 9 = 19,683 です。(9 つのセルそれぞれに 3 つの状態があります。) この数には、5 つの十字がありゼロがない状態や、両方のプレイヤーが 3 つの列を持っている状態など、多くの不正な状態が含まれています。これらの不正な状態を除外してより注意深く数えると、5,478 になります。[ 2 ] [ 3 ]
ゲームツリーを制限するには、可能な初期手が9つ、可能な応答が8つなどとなるため、最大で9!、つまり合計362,880通りのゲームが存在します。しかし、ゲームは9手未満で解決する場合もあり、正確な列挙では255,168通りのゲームが存在します。局面の回転と鏡像を同じものとみなすと、可能なゲームはわずか26,830通りになります。
三目並べの計算複雑性は、どのように一般化さ れるかによって決まります。自然な一般化は、m 、n 、k ゲーム、m × nの盤面でプレイされ、最初に k 個 連続で揃えたプレイヤーが勝者となります。このゲームは、ゲームツリー全体を探索することでDSPACE ( mn ) で解くことができます。これにより、重要な複雑性クラスPSPACEに分類されます。さらに研究を進めれば、 PSPACE 完全で あることが示されます。[ 4 ]
よく知られたゲームの複雑さ ゲームの複雑さが大きいため、この表では常用対数 の上限値（つまり桁数）を示しています。以下の数値はすべて慎重に検討してください。ゲームのルールに些細な変更を加えるだけでも、数値（そもそも概算値であることが多い）は大きく変動し、示されている数値よりもはるかに大きくなる可能性があります。
注記 ↑ ダブルダミーブリッジ（つまり、コントラクトブリッジ の文脈におけるダブルダミー問題）は、正式なボードゲームではありませんが、類似したゲームツリーを持ち、コンピュータブリッジ で研究されています。ブリッジテーブルは、各プレイヤーとトリックごとにカードを置くためのスロットが1つあると見なすことができ、これはボードサイズ52に相当します。ゲームツリーの複雑さは非常に弱い上限で、合法性に関係なく、13!の4乗のプレイヤーです。状態空間の複雑さは、1つの特定のディールに対してです。同様に、合法性に関係なく、多くの転置が排除されます。最後の4プライは常に分岐係数1の強制移動です。
参考文献 1 2 3 4 5 6 7 8 9 10 11 12 Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0 。↑ 「組み合わせ論 - 三目並べの状態空間選択計算」 。Mathematics Stack Exchange 。 2020年4月8日 取得。 ↑ T、ブライアン（2018年10月20日）。 「Btsan/generate_tictactoe」 。GitHub 。 2020年4月8日 取得 。 ↑ ステファン・ライシュ (1980)。 「Gobang ist PSPACE-volllständig (Gobang は PSPACE 完全版)」。 アクタ・インフォマティカ 。 13 (1): 59–66 . 土井 : 10.1007/bf00288536 。 S2CID 21455572 。 1 2 3 4 ステファン・ライシュ (1981)。 「Hex ist PSPACE-volllständig (Hex is PSPACE-complete)」。 アクタ・インフォーム (15): 167–191 . ↑ Slany, Wolfgang (2000). "グラフラムゼイゲームの複雑性". Marsland, T. Anthony; Frank, Ian (編). Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers . Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203 . doi : 10.1007/3-540-45579-5_12 . ISBN 978-3-540-43080-3 。1 2 3 4 5 6 H. J. ファン デン ヘリク。 JWHMウイテルワイク; J. ファン ライスウェイク (2002)。 「解決されたゲーム: 現在と未来」 . 人工知能 。 134 ( 1–2 ): 277–311 . 土井 : 10.1016/S0004-3702(01)00152-7 。 ↑ Orman, Hilarie K. (1996). "ペントミノ：先手勝利" (PDF) . Nowakowski, Richard J. (編)『 Games of No Chance: Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994 』Mathematical Sciences Research Institute Publications. Vol. 29. Cambridge University Press. pp. 339–344 . ISBN 0-521-57411-0 . MR 1427975 . ↑ ジョン・トランプ (2010)。 「ジョンのコネクトフォー・プレイグラウンド」 。 ↑ Edelkamp, Stefan、および Peter Kissmann。「一般的な 2 人対戦ゲームの記号分類」。KI 2008: 人工知能の進歩、Andreas R. Dengel 他編、第 5243 巻、Springer Berlin Heidelberg、2008 年、pp. 185–92。DOI.org (Crossref)、 https://doi.org/10.1007/978-3-540-85845-4_23。 ↑ ルールについては van den Herik et al を参照してください。 ↑ Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "長方形ボード上での支配は誰が勝つか？". Nowakowski, Richard (編). More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000. Mathematical Sciences Research Institute Publications. Vol. 42. Cambridge University Press. pp. 307–315 . ISBN 0-521-80832-4 . MR 1973019 . ↑ Jonathan Schaeffer 他 (2007 年 7 月 6 日). 「チェッカー の 謎が解かれた」 . Science . 317 (5844): 1518–1522 . Bibcode : 2007Sci...317.1518S . doi : 10.1126/science.11 44079. PMID 17641166. S2CID 10274228 . ↑ Schaeffer, Jonathan (2007). "ゲームオーバー: チェッカーで黒番で引き分け" (PDF) . ICGA Journal . 30 (4): 187– 197. doi : 10.3233/ICG-2007-30402 . 2016年4月3日に オリジナル (PDF) からアーカイブ済み。 1 2 J. M. Robson (1984). "N 対 N のチェッカーは Exptime 完全である". SIAM Journal on Computing . 13 (2): 252– 267. doi : 10.1137/0213018 . ↑ 規則についてはAllis 1994を参照 ↑ Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013). 「トリックテイキングカードゲームの複雑性について」 . Rossi, Francesca (編). IJCAI 2013、第23回国際人工知能合同会議議事録、中国・北京、2013年8月3日～9日 . IJCAI/AAAI. pp. 482–488 . ↑ シャッド市警。 MHMウィナンズ。 JWHMウイテルワイク; H・J・ファン・デン・ヘリク。 MHJ ベルグスマ (2008)。 「ファノローナのベストプレーはドローにつながる」 (PDF) 。 新しい数学と自然な計算 。 4 (3): 369–387 。 土井 : 10.1142/S1793005708001124 。 ↑ Galassi, Andrea (2018). "An Upper Bound on the Complexity of Tablut" . 1 2 Bell, George I. (2009). "中国チェッカーの最短ゲームと関連問題". Integers . 9 . arXiv : 0803.1245 . Bibcode : 2008arXiv0803.1245B . doi : 10.1515/INTEG.2009.003 . S2CID 17141575 . 1 2 笠井匠、足立明夫、岩田茂樹 (1979)。「ペブルゲームのクラスと完全問題」。SIAM Journal on Computing。8 ( 4 ): 574–586。doi : 10.1137 / 0208046。MR 0573848 。 ↑ 岩田茂樹；笠井拓海（1994）。 「オセロゲーム」 n × n {\displaystyle n\times n} ボードは PSPACE完全である」。理論計算機科学 。123 （2）：329–340。doi ： 10.1016 / 0304-3975（94） 90131-7。MR 1256205 。 ↑ Robert Briesemeister (2009). ゲーム OnTop の分析と実装 (PDF) (学位論文). マーストリヒト大学、知識工学部。 ↑ Mark HM Winands (2004). Informed Search in Complex Games (PDF) (博士論文). マーストリヒト大学、マーストリヒト、オランダ 。ISBN 90-5278-429-9 。↑ チェスの状態空間とゲームツリーのサイズは、シャノン、クロード (1950) 「チェスをプレイするためのコンピュータのプログラミング」 (PDF) . Philosophical Magazine . 41 (314) で初めて推定されました。2010-07-06 に オリジナル (PDF) からアーカイブされました 。 10⁴³ と10¹²⁰ という推定値を与えたが、これは表の上限値よりも小さく、詳細はシャノン数 で説明されている。 ↑ フランケル、アヴィエズリ S. ; リヒテンシュタイン、デイヴィッド (1981)。 「完全戦略の計算 n × n {\displaystyle n\times n} n {\displaystyle n} Journal of Combinatorial Theory, Series A 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 . MR 0629595 . ↑ Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled、Candy Crush、その他のマッチ3ゲームは(NP-)困難である". 2014 IEEE Conference on Computational Intelligence and Games、CIG 2014、ドイツ、ドルトムント、2014年8月26-29 日 。IEEE。pp . 1–8。arXiv : 1403.5830。doi : 10.1109 / CIG.2014.6932866。ISBN 978-1-4799-3547-5 。↑ Diederik Wentink (2001). ゲーム Gipf の分析と実装 (PDF) (学位論文). マーストリヒト大学. ↑ Chang-Ming Xu; Ma, ZM; Jun-Jie Tao; Xin-He Xu (2009). "Connect6における証明番号検索の強化". 2009 中国制御意思決定会議 . p. 4525. doi : 10.1109/CCDC.2009.5191963 . ISBN 978-1-4244-2722-2 . S2CID 20960281 . ↑ Hsieh, Ming Yu; Tsai, Shi-Chun (2007 年 10 月 1 日). "一般化された k 列ゲームの公平性と複雑性について" . Theoretical Computer Science . 385 ( 1– 3): 88– 100. doi : 10.1016/j.tcs.2007.05.031 . ↑ Tesauro, Gerald (1992年5月1日). 「時間差学習における実際的な問題」 . Machine Learning . 8 ( 3–4 ): 257–277 . doi : 10.1007/BF00992697 . ↑ Witter, RT (2021). バックギャモンは難しい。Du, DZ.、Du, D.、Wu, C.、Xu, D. (編) 組合せ最適化と応用。COCOA 2021。Lecture Notes in Computer Science()、vol 13135。Springer、Cham。https: //doi.org/10.1007/978-3-030-92681-6_38 1 2 Shi-Jim Yen、Jr-Chang Chen、Tai-Ning Yang、Shun-Chin Hsu (2004 年 3 月)。 「コンピュータ中国将棋」 (PDF) 。International Computer Games Association Journal。27 ( 1 ): 3–18。doi : 10.3233/ICG-2004-27102。S2CID 10336286。2007 年 6月 14 日に オリジナル (PDF) からアーカイブされました 。 1 2 Donghwi Park (2015). "韓国チェスと中国チェスの空間状態複雑性". arXiv : 1507.06401 [ math.GM ]. ↑ Chorus, Pascal. 「アルファベータ法とモンテカルロ探索を用いたアバロン用コンピュータプレイヤーの実装」 （PDF） 。マーストリヒト大学知識工学部。 2012年3月29日 取得 。 ↑ Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (学位論文). Reed College. ↑ Joosten, B. 「Havannah Playing Agentの作成」 (PDF) . 2012年3月29日 取得 。 ↑ E. Bonnet; F. Jamain; A. Saffidine (2014年3月25日). "HavannahとTwixTはPSPACE完全である". arXiv : 1403.6518 [ cs.CC ]. ↑ Kevin Moesker (2009). Txixt: 理論、分析、実装 (PDF) (学位論文). マーストリヒト大学人文科学部。 ↑ グレンデニング、リサ（2005年5月）。Quoridor の習得 （PDF） 。コンピュータサイエンス（理学士論文）。 ニューメキシコ大学 。 2012年3月15日に オリジナル （PDF） からアーカイブ済み。 ↑ キャスリーン・ヘイデン (2009). カルカソンヌ用コンピュータプレイヤーの実装 (PDF) (学位論文). マーストリヒト大学、知識工学部。 ↑ 分岐係数が低いのは2人目のプレイヤーの場合です。 ↑ Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007). "The Monte-Carlo approach in Amazons" (PDF) . Computer Games Workshop、アムステルダム、オランダ、2007年6月15～17日 . pp. 185–192 . ↑ Hensgens, PPLM (2001). "A Knowledge-Based Approach of the Game of Amazons" (PDF) . Universiteit Maastricht, Institute for Knowledge and Agent Technology. ↑ RA Hearn (2005年2月2日)「AmazonsはPSPACE完全である」 arXiv : cs.CC/0502013 。 ↑ 飯田裕之;作田 誠;ジェフ・ロラソン（2002年1月）。 「コンピュータ将棋」 。 人工知能 。 134 ( 1–2 ): 121–144 . 土井 : 10.1016/S0004-3702(01)00157-6 。 ↑ 安達博、亀川博、岩田聡（1987）「n×n盤上の将棋は指数時間で完了する」 電子情報通信学会論文誌 J70-D: 1843–1852 . ↑ FC Schadd (2009). 現代ボードゲーム「ターン・アンド・タクシス」におけるモンテカルロ探索手法 （PDF） （学位論文）。マーストリヒト大学。 2021年1月14日に オリジナル （PDF） からアーカイブ済み。 ↑ ジョン・トランプ、グンナー・ファーネバック (2007)。 「囲碁の組み合わせ論」 。 N の境界 48 < log(log( N )) < 171 を導出しています。↑ トランプ、ジョン (2016)。 「合法的な囲碁の局面の数」 。 ↑ 「囲碁の対局時間に関する統計 」 ↑ JM Robson (1983). 「囲碁の複雑性」。 情報処理; IFIP会議議事録 。pp. 413–417 。 ↑ Christ-Jan Cox (2006). "Analysis and Implementation of the Game Arimaa" (PDF) . ↑ David Jian Wu (2011). "Arimaaゲームにおける動きのランキングと評価" (PDF) 。 ↑ ブライアン・ハスキン (2006) 「アリマー分岐係数の考察」 。 ↑ AFC Arts (2010). ストラテゴにおける競争的プレイ (PDF) (学位論文). マーストリヒト。 ↑ CDA Evans および Joel David Hamkins (2014). "無限チェスにおける超限ゲーム値". arXiv : 1302.4377 [ math.LO ]. ↑ ステファン・ライシュ、ジョエル・デヴィッド・ハムキンス、フィリップ・シュリヒト (2012)。 「無限チェスの配偶者問題は決定可能である」。 ヨーロッパにおけるコンピュータビリティに関する会議 : 78–88 . arXiv : 1201.5597 。 {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)↑ Alex Churchill、Stella Biderman、Austin Herrick (2020)。「マジック：ザ・ギャザリングはチューリング完全である」。arXiv : 1904.09828 [ cs.AI ] 。 {{cite arXiv}}: CS1 maint: 複数の名前: 著者リスト (リンク)↑ 「MTGの無限コンボ：試してみたい39の素晴らしいコンボ」 。 ↑ ステラ・ビダーマン (2020). 「マジック：ザ・ギャザリングは算数と同じくらい難しい」. arXiv : 2003.05119 [ cs.AI ]. ↑ Lokshtanov, Daniel; Subercaseaux, Bernardo (2022年5月14日). "WordleはNP困難である". arXiv : 2203.16713 [ cs.CC ]. 
