組合せゲーム理論（Combinatorial Game Theory, CGT）は、いわゆる「伝統的な」ゲーム理論や「経済学的な」ゲーム理論と区別される、応用数学・理論計算機科学の一分野です。CGT は特に公平な2人零和ゲーム（特にNimのようなゲーム）に端を発し、有限で完璧情報を持ち運の要素がないゲームの「解析（解法）」を目的とします。

組合せゲーム（combinatorial game）と見なされるには、一般に次のような条件を満たす必要があります。

  1. ゲームには最低でも2人のプレイヤーがいること。
  2. ゲームはシーケンシャル（順番に手を指す）であること。
  3. ゲームは完璧情報であること（例：ポーカーのように情報が隠されていない）。
  4. ゲームは決定論的であり、偶然要素（チャンス）が介在しないこと（すなわちノンチャンス）。運はゲームの一部ではない。
  5. 各局面での合法手の集合が有限であること（手の選択肢が無限に続かない）。
  6. ゲームは必ず有限手数で終局すること（無限ループしない）。
  7. 標準的な終局条件として、あるプレイヤーが手番で合法手を持たなくなったときにゲームが終了すること（通常は「最後に手を指した者が勝ち」＝正規化規則）。

CGT は特に「2人」「有限」「完璧情報」「決定論」「勝者と敗者が明確（引き分けを想定しない）」といった性質をもつゲーム群の理論的構造を扱います。なお、ルールを少し変えることで生じる「ミゼール（misère）ルール」（最後の手を取った者が負けとなる変形）などの解析も重要な分野です。

ゲーム木と局面の値

これらのゲームは局面（状態）と合法手の関係を示す「ゲーム木」で表現できます。各ノードは局面を表し、エッジはプレイヤーの1手を表します。CGT では局面に対して「勝てる／負ける」といった単純な分類（N 位置／P 位置）だけでなく、より細かい「局面の値（value）」を割り当てることが重要です。局面の値を扱うことで、複数のゲームを同時に行う〈ゲーム加算（disjunctive sum）〉の解析が可能になります。

ゲームの合計（和）とは、2つ以上の独立した対局を並べて行うもので、各手番でプレイヤーは合成ゲームのうち1つだけの局面に手を行い、他の局面はそのまま残る、というルールです。合成ゲームの勝敗は各成分の構造の組合せで決まり、局面値の代数的操作（ニム加算、ニム和など）が有効になります。

公平ゲーム（impartial）と非公平（partizan）

組合せゲームは大まかに2種類に分かれます。

  • 公平（impartial）ゲーム：どちらのプレイヤーも同じ合法手集合を持つ（例：Nim）。こうしたゲームにはスプレーグ–グランディ（Sprague–Grundy）定理が適用され、各局面は「グランディ数（Grundy 数あるいはニンバー）」と呼ばれる非負整数に同型化できます。グランディ数の計算は mex（minimum excludant）ルールで行い、合成ゲームでは各成分のグランディ数をビット単位の排他的論理和（xor、一般に「ニム和」）で合成します。ニム和が0なら P 位置（後手必勝）、非ゼロなら N 位置（先手必勝）です。例えばヒープが 3 と 4 の Nim の場合、3 xor 4 = 7 ≠ 0 なので先手が必勝となります。
  • 非公平（partizan）ゲーム：左右のプレイヤーが取れる手が異なるタイプのゲーム。コンウェイの理論ではこうした局面に対してより豊かな「値（例：サリュール数、簡約形、オプション集合）」を与えることができ、サリュール数（surreal numbers）や一般化されたゲーム値（ニンバー以外の値）を用いて解析します。部分ゲームの和に対する代数的性質や順序構造の研究がここに含まれます。

Sprague–Grundy と Nim の扱い（簡単な手順）

公平ゲームの局面に対して Grundy 数 g を求める基本的な手順：

  1. 終局（合法手が無い局面）には g=0 を割り当てる。
  2. ある局面の合法手で到達可能な局面の Grundy 数たちの集合を取り、その最小除外値 mex をその局面の g とする。つまり g = mex({ g(到達局面) }).
  3. 複数の独立した局面の和では、それぞれの g をビットごとの xor で合成し、合成値が 0 なら P 位置、0 でなければ N 位置。

この理論により、Nim に還元できる局面（ニム相当）を見つけることで、非常に多くの公平ゲームを効率的に「解く」ことができます。

実践上の留意点

  • 多くの CGT 的問題は理論的には解けても計算コストが高く、一般化されたゲーム解析は PSPACE 完全など高い計算複雑性を示す場合があります。
  • 部分ゲームの値は必ずしも単純な数値にならない（例えば「熱いゲーム」「冷たいゲーム」「分数的な値」などの概念がある）ため、解析はやや抽象的で代数的です。
  • ルール変更（正規ルール⇆ミゼールルールなど）により結論が大きく変わるので、ルール系を明確に定めることが重要です。

組合せゲーム理論の古典的な創始者には エルウィン・ベルレカンプ、ジョン・コンウェイ、リチャード・ガイらがいます。彼らは1960年代に共同研究を行い、その代表的な成果として書籍『Winning Ways for Your Mathematical Plays』があり、CGT の基礎と多くの応用事例をまとめています。

初学者はまず Nim の解析と Sprague–Grundy の基本（mex とニム和）を理解することを勧めます。その上で部分ゲームの値や合成ゲームの代数的性質（値の和、比較、簡約）に進むと、CGT の全体像がつかめます。