組み合わせゲーム理論

組合せゲーム理論は数学と理論計算機科学の一分野であり、典型的には完全情報を伴うシーケンシャルゲームを研究する。研究は主に、プレイヤーが定められた勝利条件を達成するために定められた方法で交代でポジションを変えたり、移動したりする2人用ゲームに限定されてきた。組合せゲーム理論は伝統的に偶然のゲームや不完全または不完全な情報を使用するゲームを研究しておらず、ゲームの状態と利用可能な移動のセットが常に両方のプレイヤーに知られている完全情報を提供するゲームを好んでいる。 ^[1]しかし、数学的手法が進歩するにつれて、数学的に分析できるゲームの種類が拡大し、したがってこの分野の境界は常に変化している。^[2]学者は通常、論文の冒頭で「ゲーム」の意味を定義しますが、これらの定義は分析対象のゲームに固有のものであり、この分野の全範囲を表すものではないため、変化することが多い。

組み合わせゲームには、チェス、チェッカー、囲碁などのよく知られたゲームが含まれます。これらは非自明であると見なされており、三目並べは「簡単に解ける」という意味で自明であると見なされています。組み合わせゲームの中には、無限チェスのようにプレイエリアが無制限のものもあります。組み合わせゲーム理論では、これらのゲームやその他のゲームの動きはゲームツリーとして表現されます。

組み合わせゲームには、数独などの1人用組み合わせパズルや、コンウェイのライフゲームなどのプレイヤーがいないオートマトンも含まれます（ただし、最も厳密な定義では、「ゲーム」には複数の参加者が必要であると言えるため、「パズル」や「オートマトン」という呼称が使われます。^[3]）。

ゲーム理論には一般に、偶然のゲーム、不完全な知識のゲーム、プレイヤーが同時に行動できるゲームが含まれ、現実の意思決定状況を表す傾向があります。

組合せゲーム理論は、「伝統的」または「経済的」ゲーム理論とは異なる重点を置いている。伝統的ゲーム理論は当初、単純な組合せ構造を持ちながら偶然の要素を持つゲームを研究するために開発された（ただし、連続した動きも考慮する。拡張形式ゲームを参照）。本質的に、組合せゲーム理論は、すべての2人用完全情報ゲームのサブクラスである超実数を使用するなど、ゲームツリーを分析するための新しい方法に貢献してきた。 ^{[3]組合せゲーム理論で研究されるタイプのゲームは、}人工知能、特に自動計画およびスケジューリングにおいても興味深い。組合せゲーム理論では、実用的な探索アルゴリズム（ほとんどの人工知能の教科書に含まれているアルファ-ベータ剪定ヒューリスティックなど）の改良にはあまり重点が置かれておらず、むしろ記述的な理論的結果（ゲームの複雑さの尺度や、戦略窃盗の議論などのアルゴリズムを必ずしも指定しない最適解の存在の証明など）に重点が置かれている。

組合せゲーム理論における重要な概念は、解かれたゲームの概念である。例えば、三目並べは、両方のプレイヤーが最適にプレイすればどんなゲームでも引き分けになることが証明できるため、解かれたゲームであると考えられる。組合せ構造が豊富なゲームについて同様の結果を導くことは困難である。例えば、2007年にチェッカーは弱く解かれたことが発表された— 双方が最適にプレイしても引き分けになる — が、この結果はコンピュータ支援による証明であった。^[4]他の現実世界のゲームのほとんどは今日では完全に分析するには複雑すぎるが、この理論は囲碁の終盤の分析で最近いくつかの成功を収めている。組合せゲーム理論をある局面に適用すると、ゲームが終了するまで両方のプレイヤーにとって最適な一連の動きを求め、そうすることでどの局面でも最適な動きを見つけようとする。実際には、ゲームが非常に単純でない限り、このプロセスは苦痛を伴うほど難しい。

数学者や科学者が熟考したり解いたりするために主に関心を持つ組み合わせの「数学ゲーム」と、娯楽や競争の一形態として一般大衆が関心を持つ組み合わせの「プレイゲーム」を区別することは有用である。^[5]しかし、多くのゲームは両方のカテゴリに分類される。 たとえば、 Nimは組み合わせゲーム理論の基礎となるプレイゲームであり、最初のコンピュータ化されたゲームの1つである。^[6]三目並べは、今でもコンピュータサイエンスの学生にゲームAI設計の基本原理を教えるために使用されている。^[7]

組合せゲーム理論は、公平なゲームの理論との関連で生まれました。公平なゲームでは、一方のプレイヤーが利用できるプレイは、もう一方のプレイヤーも利用できるものでなければなりません。そのようなゲームの 1 つがNimで、完全に解くことができます。Nim は 2 人のプレイヤーが参加する公平なゲームで、通常のプレイ条件が適用されます。つまり、動けないプレイヤーは負けます。1930 年代に、Sprague–Grundy の定理により、すべての公平なゲームは Nim のヒープと同等であることが示され、組み合わせレベルで考えた場合、報酬だけでなく詳細な戦略が重要になるゲームでは、大きな統一が可能であることが示されました。

1960年代に、エルウィン・R・バーレカンプ、ジョン・H・コンウェイ、リチャード・K・ガイは共同で、片方のプレイヤーが利用できるプレイが両方のプレイヤーが利用できるという要件を緩和した、パルチザンゲームの理論を提唱した。彼らの研究結果は、1982年に著書『数学的プレイに勝つ方法』で発表された。しかし、この主題について最初に発表された研究は、コンウェイの1976年の著書『数とゲームについて』 (ONAGとしても知られる)であり、超実数の概念とゲームへの一般化を紹介した。『数とゲームについて』も、バーレカンプ、コンウェイ、ガイの共同研究の成果であった。

組み合わせゲームは、慣例により、一方のプレイヤーがもう一方のプレイヤーに動きが残っていない場合に勝利する形式にするのが一般的です。結果が 2 つしかない有限ゲームは、この慣例が適用される同等のゲームに簡単に変換できます。組み合わせゲームの理論で最も重要な概念の 1 つは、 2 つのゲームの合計の概念です。これは、各プレイヤーがゲームのどの時点でも 1 つのゲームかもう 1 つのゲームのいずれかで動くことを選択でき、対戦相手がどちらのゲームでも動きが残っていない場合にプレイヤーが勝利するゲームです。ゲームをこのように組み合わせると、豊かで強力な数学的構造が生まれます。

コンウェイは『数とゲームについて』の中で、パルチザンゲームの理論の着想は囲碁の終盤のプレイの観察に基づいていると述べている。終盤は、盤上の異なる部分で互いに分離されたより単純な終盤の合計に分解できることが多い。

入門書『Winning Ways』では多数のゲームが紹介されていますが、入門理論の動機付けとなる例として次のゲームが使用されました。

• ブルー・レッド・ハッケンブッシュ- 有限レベルでは、この党派的な組み合わせゲームにより、値が二項有理数であるゲームの構築が可能になります。無限レベルでは、すべての実数値と、超実数のクラスに含まれる多くの無限値を構築できます。
• 青・赤・緑のハッケンブッシュ -星など、従来の意味での数字ではない追加のゲーム値を許可します。
• Toads and Frogs - さまざまなゲーム値を許可します。他のほとんどのゲームとは異なり、位置は短い文字列で簡単に表されます。
• ドミニアリング- ドミニアリングでは、動く動機がある場合とない場合があるため、ホットゲームなどのさまざまな興味深いゲームがポジションとして表示されます。これにより、ゲームの温度について議論できます。
• ニム-公平なゲーム。これにより、ニムバーの構築が可能になります。(青赤緑ハッケンブッシュの緑のみの特別なケースと見ることもできます。)

古典的なゲームである囲碁は、初期の組み合わせゲーム理論に影響を与え、その後、ベルレカンプとウルフは囲碁の終盤理論と温度理論を開発しました (参考文献を参照)。この理論を活用して、彼らは囲碁の終盤の妥当なポジションを構築し、熟練した囲碁プレイヤーに選択肢を与え、どちらにしても勝つことができるようにしました。

組合せゲーム理論の文脈で研究されている別のゲームはチェスである。1953年にアラン・チューリングはこのゲームについて「計算の仕方を、必要であれば数学記号を使って英語で明確に説明できれば、記憶容量が十分であれば、どんなデジタルコンピュータでもその計算をするようにプログラムすることは常に可能である」と書いている。^[8] 1950年の論文で、クロード・シャノンはチェスのゲームツリーの複雑さの下限を10の¹²⁰乗と推定し、今日ではこれはシャノン数と呼ばれている。^[9]チェスは未解決のままであるが、スーパーコンピュータの使用を含む広範な研究により、7個以下の駒によるすべてのエンドゲームで完璧なプレイの結果を示すチェスのエンドゲーム表ベースが作成された。無限チェスはチェスよりもさらに大きな組合せ複雑性を持つ（限られたエンドゲームのみ、または少数の駒による合成ポジションのみが研究されている場合を除き）。

ゲームとは、簡単に言えば、左と右と呼ばれる 2 人のプレイヤーが実行できる「動き」のリストです。どの動きによっても、ゲームの位置は別のゲームと見なすことができます。ゲームを他のゲームへの可能な動きの観点から見るというこの考え方は、組み合わせゲーム理論で標準的なゲームの再帰的な数学的定義につながります。この定義では、各ゲームは{L|R}と表記されます。L は左のプレイヤーが移動できるゲームの位置の集合であり、R は右のプレイヤーが移動できるゲームの位置の集合です。L と R の各位置は、同じ表記を使用してゲームとして定義されます。

ドミニアリングを例にとると、4×4のボードの16個のマスそれぞれに、一番左上のマスをA1、上から2列目の左から3番目のマスをC2、というようにラベルを付ける。例えば、(D3, D4)は、右下隅に垂直のドミノが置かれているゲームの位置を表すために使用する。すると、初期位置は、組み合わせゲーム理論の表記法で次のように記述できる。

${\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \}.}$

標準的な Cross-Cram プレイでは、プレイヤーは交互にターンを行いますが、この交代はゲーム状態内にエンコードされるのではなく、組み合わせゲーム理論の定義によって暗黙的に処理されます。

${\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.}$

上記のゲームは、どちらのプレイヤーにも 1 つの動きしか残っておらず、どちらかのプレイヤーがその動きをすれば、そのプレイヤーが勝つというシナリオを表しています。(C3 の無関係な空きマスは図から省略されています。) 各プレイヤーの動きリスト内の {|} (動きの後に残った 1 つのマスに対応) はゼロ ゲームと呼ばれ、実際には 0 と省略できます。ゼロ ゲームでは、どちらのプレイヤーにも有効な動きはありません。したがって、ゼロ ゲームになったときの順番のプレイヤーは自動的に負けになります。

上の図のようなゲームの種類にも簡単な名前があります。これはスター ゲームと呼ばれ、∗ と省略されることもあります。スター ゲームでは、有効な動きはゼロ ゲームにのみつながります。つまり、スター ゲーム中に順番が来た人が自動的に勝利することになります。

Domineering にはないもう 1 つのタイプのゲームは、ループゲームです。ループ ゲームでは、左または右への有効な移動はゲームであり、その後最初のゲームに戻ることができます。 たとえば、チェッカーは、ピースの 1 つが昇格するとループになり、2 つ以上のマスの間を無限に循環できます。このような移動がないゲームは、ループフリーと呼ばれます。

無限の数の位置を持つ超限ゲームもあります。つまり、左と右には有限ではなく無限の動きのリストがあります。

数字は、自由に動ける回数、または特定のプレイヤーの有利な動きを表します。慣例により、正の数は左の有利さを表し、負の数は右の有利さを表します。これらは、0 を基本ケースとして再帰的に定義されます。

0 = {|}

1 = {0|}、2 = {1|}、3 = {2|}

−1 = {|0}、−2 = {|−1}、−3 = {|−2}

ゼロゲームは最初のプレイヤーの負けとなります。

数ゲームの合計は整数のように動作します。たとえば、3 + −2 = 1 です。

任意のゲーム数は超実数クラスに属します。

∗ または {0|0} と表記されるStar は、どちらかのプレイヤーが (ゲームで最初に動く場合) ゼロゲームに動かなければならず、したがって勝つため、最初のプレイヤーの勝利です。

∗ + ∗ = 0 です。最初のプレイヤーは ∗ の 1 つのコピーを 0 にし、次に他のプレイヤーは ∗ のもう 1 つのコピーも 0 にする必要があるためです。この時点で、0 + 0 では移動が認められないため、最初のプレイヤーは負けます。

ゲーム ∗ は正でも負でもありません。ゲーム ∗ と、最初のプレイヤーが勝つ他のすべてのゲーム (プレイヤーがどちらの側にいるかに関係なく) は、0 とあいまいまたは混同されていると言われます。記号的に、∗ || 0 と書きます。

Upは↑と書かれ、組合せゲーム理論における位置である。^[10]標準的な表記では、↑ = {0|∗}である。

−↑ = ↓ (下)

Up は厳密に正 (↑ > 0) ですが、無限小です。Up は、数学的プレイの勝利方法で定義されています。

↓と書かれる下は、組合せゲーム理論における位置である。^[10]標準的な表記では、↓ = {∗|0}である。

−↓ = ↑ (上)

Down は厳密に負 (↓ < 0) ですが、無限小です。Down は、Winning Ways for your Mathematical Playsで定義されています。

{1|−1} というゲームを考えてみましょう。このゲームでは、どちらの動きも、その動きをしたプレイヤーにとって有利です。そのため、このゲームは「ホット」であると言われています。つまり、-1 未満の任意の数より大きく、1 より大きい任意の数より小さく、その間の任意の数ではあいまいです。これは ±1 と表記されます。これは、予想される方法で、数値に加算したり、正の数で乗算したりできます。たとえば、4 ± 1 = {5|3} です。

公平なゲームとは、ゲームのどの位置でも、両方のプレーヤーが同じ動きをすることができるゲームです。たとえば、一方のプレーヤーが取り除くことができるオブジェクトのセットは、もう一方のプレーヤーも取り除くことができるため、ニムは公平です。しかし、一方のプレーヤーはドミノを水平に置き、もう一方のプレーヤーは垂直に置くため、ドミニアリングは公平ではありません。同様に、プレーヤーがそれぞれ異なる色の駒を所有しているため、チェッカーも公平ではありません。任意の序数に対して、ニムを一般化した公平なゲームを定義できます。このゲームでは、各動きで、どちらのプレーヤーもその数を任意のより小さい序数に置き換えることができます。このように定義されたゲームは、ニンバーと呼ばれます。スプレイグ-グランディの定理によれば、通常のプレイ規約の下では、すべての公平なゲームはニンバーと同等です。

「最小の」数、つまり通常の順序付けで最も単純で最小の数、は 0 と ∗ です。

• アルファベータ剪定、ゲームツリーを探索するための最適化アルゴリズム
• 後方帰納法、最終状況から逆方向に推論すること
• 冷却と加熱（組み合わせゲーム理論）、ゲームを理論に適応させるさまざまな変換
• コネクションゲーム、プレイヤーがコネクションを確立しようとするタイプのゲーム
• エンドゲーム テーブルベース、エンドゲームの遊び方を説明するデータベース
• 期待ミニマックス木、ミニマックスゲーム木を偶然の要素のあるゲームに適応させたもの
• 拡張型ゲーム、プレイヤーが利用できる報酬と情報で強化されたゲームツリー
• ゲーム分類、ゲームを分類する方法について議論する記事
• ゲームの複雑さ、ゲームの複雑さを測定する方法を説明した記事
• グランディのゲーム、物体の山を分割する数学ゲーム
• マルチエージェントシステム、複雑な問題に取り組むためのコンピュータシステムの一種
• ポジショナルゲーム、プレイヤーが以前に獲得していないポジションを獲得するタイプのゲーム
• チェスを解く
• シルバーコイン、以前に選択した整数の非負倍数の合計ではない正の整数を選択する数学ゲーム
• ウィトフのゲーム、1つまたは2つの山からオブジェクトを取る数学ゲーム
• 位相ゲーム、位相空間で行われる数学ゲームの一種
• ツークツヴァング、不利な場合にプレーすることを義務付けられる

• アルバート、マイケル H. ; ノワコウスキー、リチャード J. ; ウルフ、デイビッド (2007)。遊びのレッスン: 組み合わせゲーム理論入門。AK ピーターズ社。ISBN 978-1-56881-277-9。
• Beck, József (2008)。組み合わせゲーム：三目並べ理論。ケンブリッジ大学出版局。ISBN 978-0-521-46100-9。
• Berlekamp, E. ; Conway, JH ; Guy, R. (1982)。数学ゲームで勝つ方法：ゲーム全般。Academic Press。ISBN 0-12-091101-9。第 2 版、AK Peters Ltd (2001–2004)、 ISBN 1-56881-130-6、ISBN 1-56881-142-X  
• Berlekamp, E.; Conway, JH; Guy , R. (1982)。数学的遊びの必勝法：特にゲーム。Academic Press。ISBN 0-12-091102-7。第 2 版、AK Peters Ltd (2001–2004)、ISBN 1-56881-143-8、ISBN 1-56881-144-6。  
• ベルレカンプ、エルウィン、ウルフ、デイヴィッド（1997）。数学の囲碁：チリングが最後のポイントを獲得。AKピーターズ社。ISBN 1-56881-032-6。
• Bewersdorff, Jörg (2021).運、論理、そして白い嘘: ゲームの数学(第2版). AK Peters/CRC Press. doi :10.1201/9781003092872. ISBN 978-1-003-09287-2。特にセクション21～26を参照してください。
• コンウェイ、ジョン・ホートン（1976年）。『数とゲームについて』。アカデミック・プレス。ISBN 0-12-186350-6。第 2 版、AK Peters Ltd (2001)、ISBN 1-56881-127-6。 
• Robert A. Hearn、Erik D. Demaine (2009)。ゲーム、パズル、計算。AK Peters, Ltd. ISBN 978-1-56881-322-6。

• David Eppsteinのホームページにある組み合わせゲーム理論のリンクの一覧
• ディルク・シュライヒャーとマイケル・ストールによるコンウェイのゲームと数への入門
• ビル・スパイトによる組み合わせゲーム理論用語の要約
• 組み合わせゲーム理論ワークショップ、バンフ国際研究ステーション、2005 年 6 月