組合せゲームとは、二人のプレイヤーが交互に手を打つ（着手する）ゲームであり、次の二つの性質を持つものです。
（１）確定性・・・サイコロを振るなどの偶然要素を含まない。
（２）完全情報性・・・ゲームの進行やお互いの手の内が隠されていない。
例えば、将棋やチェスなどは組合せゲームですが、麻雀やトランプなどは上の性質を満たさないため、組合せゲームではありません。
この組合せゲームに対し、数学的に必勝法を与えることがこの分野の目標となります。
以下、組合せゲーム理論に登場する重要な用語・研究対象について解説します。
・正規形ゲーム
最後に着手をしたほうが勝ちとなるゲーム。
これに対し、最後の着手をしたほうが負けとなるゲームを逆形ゲームと呼ぶ。
・不偏ゲーム
プレイヤーによって可能な着手に違いのないゲーム。代表的なものとしては石取りゲーム(NIM)があり、このゲームの研究から生じたGrundy 値の理論(後述)により不偏ゲームの局面を先手必勝局面か後手必勝局面かに分類できる。
・非不偏ゲーム
プレイヤーによって可能な着手が異なることもあるゲーム。
囲碁や将棋などが含まれる。
非不偏ゲームの数学的構造も(特に正規形の場合)よく研究されており、ゲーム同士の和や大小関係などが定義できることが知られている。その大小関係から、片方のプレイヤーがどれだけ有利であるかを判定することができる。
通常、プレイヤーの片方を左、もう片方を右と呼んで区別する(Alice,Bobや黒、白といった区別もある)。
・帰結類
組合せゲームでは偶然や運に左右されないので、引き分けがないゲームならばどちらかのプレイヤーは必勝手順を持つ。
必勝者によってゲームの局面を分類した集合を帰結類と呼ぶ。
不偏ゲームでは以下の2つの帰結類がある。
P…後手番のプレイヤーが必勝手順を持つ。
N…先手番のプレイヤーが必勝手順を持つ。
非不偏ゲームでは上の二つに加えて、以下の二つの帰結類がある。
L…誰からゲームを始めるかに関わらず、左が必勝手順を持つ。
R…誰からゲームを始めるかに関わらず、右が必勝手順を持つ。
・NIM
代表的な不偏ゲーム。いくつかの石によって構成された山が数山あり、プレイヤーは交互にいずれかの山を選んで、そこから好きなだけ石を取る。最後の石を取ったほうの勝ちである。
このゲームについては、各山の石の個数の排他的論理和を取り、その値が0ならば帰結類がP、0でないならば帰結類がNであることが知られている。
・排他的論理和(ニム和)
非負の整数に対して定義される演算。数を2進表記し、各桁において2を法とした足し算を行う。
(例:4⊕7=100(2)⊕111(2)=011(2)=3)
不偏ゲームの必勝形を求めるときに利用されることも多い。
・Grundy値(ニム値、Grundy数)
不偏ゲームの局面に以下の定義で割り当てられる値。Grundy値がnである局面は一山n石のニムと同一視できる(置き換え可能である)ことが知られており、この結果とニムの必勝判定法により不偏ゲームの各局面は必勝判定できる。
具体的には、以下のように定義される。
ゲームの局面xに対して、そのGrundy値をG(x)とすると、
xが終了局面ならばG(x)=0
そうでないならばG(x)=mex({G(y)|yはxから一手で移行可能な局面})
とする。ただしmex(S)は集合Sに属さない最小の非負整数とする。
・逆形ゲーム
逆形ゲームは、正規形のルールとは違い、着手不能になったプレイヤーの勝ちというゲームである。いわゆる、負けるが勝ちのゲームである。逆形ゲームは正規形ゲームとは異なり、直和ゲームに対するGrundy値が計算できず、かなり複雑となる。そのため、近年では逆形商と呼ばれる特殊な可換モノイドとその上の準同型写像を用いて逆形ゲームの分類を行うことが主流である。ゲームの局面から逆形商への標準全射があり、それが必勝形保存準同型となるため、逆形商を決定すれば必勝判定が可能となる。また、この標準全射がGrundy値の代わりを務めるのである。
・ルーピーゲーム
ルーピーゲームは同形反復を許したゲームであり、一度現れた局面が後続局面に現れることを許可したゲームである。例えば将棋やチェスなどがそうである。Stopperと呼ばれる、お互いのプレイヤーが無限回の同形反復を行うことの無い局面に関しては、正規形の理論をある程度用いることができるが、直和ゲームに関しては無限回の同形反復を含む可能性があるため、その限りではない。ルーピーゲームは現在も未発展なゲームである。
・超限ゲーム
超限ゲームとは一般の順序数の誕生日を持つゲームである。例えば、超限ニムでは石の個数を一般の順序数へと拡張したものとなる。ニム和は超限帰納法を用いて自然に定義できる。また、ニム和をカントールノーマルフォームを用いて定義すれば、一部の超限版不偏ゲームのGrundy値は計算できることがわかっている。しかし、逆形ゲームやルーピーゲームの超限版においてはまだ研究されていない。超限ゲームもルーピーゲーム同様未発展なゲームである。