組合せゲーム理論
CGTとも呼ばれる組合せゲーム理論は、組合せゲームを研究する応用数学・理論計算機科学の一分野であり、「伝統的な」ゲーム理論や「経済的な」ゲーム理論とは区別されている。CGTは、公平なゲーム、特にNimの2人用ゲームの理論に関連して生まれたもので、ある種の組合せゲームを「解く」ことに重点を置いています。
ゲームはコンビナトリアルゲームであるためには、いくつかの条件を満たさなければなりません。これらは以下の通りです。
- ゲームには最低でも2人のプレイヤーが必要です。
- ゲームはシーケンシャルでなければなりません。
- ゲームは完璧な情報を持っていなければならない（つまり、ポーカーのように情報が隠されていない）。
- ゲームは決定論的でなければならない（すなわち、ノンチャンス）。運はゲームの一部ではない。
- ゲームは、可能な手の量が決まっていなければなりません。
- 最終的にはゲームは終了しなければなりません。
- 1人のプレイヤーが動けなくなった時点でゲームは終了しなければなりません。
組合せゲーム理論は、主に2つのプレイヤー、有限であり、勝者と敗者（すなわち、ドローで終了しない）を持っている組合せゲームのサブセットの研究に限定されています。
これらの組み合わせゲームは木で表現することができ、各頂点は木の上で直下のゲームの特定の手の結果として生じるゲームである。これらの対局には対局値を割り当てることができる．これらのゲームの値を見つけることは、ゲーム加算の理論的概念と同様に、CG理論家にとって大きな関心事である。2つの対局の合計とは、手番の各プレイヤーが2つの対局のうち1つの対局だけに手を出さなければならない対局のことで、他の対局はそのままにしておくことができます。
エルウィン・ベルレカンプ、ジョン・コンウェイ、リチャード・ガイがこの理論の創始者です。彼らは1960年代に一緒に仕事をしていました。彼らの出版した作品は『Winning Ways for Your Mathematical Plays』と呼ばれています。
定義
理論上、左と右と呼ばれる二人のプレイヤーがいます。ゲームというのは、左右が他のゲームに手を出すことができるものです。例えば、チェスのゲームでは、通常のスタートの段取りがあります。しかし、チェスのゲームは、最初の一手目が終わった後に、別のゲーム、別の設定のゲームと考えることもできます。このように、それぞれの手番をゲームと呼ぶこともあります。
ゲームは {L|R} という表記法を用いる。L {\displaystyle L
}は、左の人ができるゲーム。R {displaystyle R
}は、右のプレイヤーが手を出せるゲームだ。チェスの表記法を知っていれば、通常のチェスの設定は
| a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } }♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ |
ドットの「...」は、多くの手があることを意味しているので、すべてが表示されているわけではありません。
チェスはとても複雑です。もっと簡単なゲームを考えた方がいいです。例えば、ニムはもっと簡単に考えることができます。ニムはこんな感じで遊ばれています。
- カウンターの山は0個以上あります。
- ターンに、プレイヤーは１枚の山から好きなだけカウンターを取ることができます。
- 手を打てない選手が負ける。
一番簡単なニムのゲームは、カウンターが全くない状態から始まります。この場合、どちらのプレイヤーも動くことができません。これは{|}と表示されます。どちらのプレイヤーも動けないので、両サイドは空っぽになります。最初に行った人が動けないので、負けてしまいます。CGTでは、{|}を記号0（ゼロ）と書くことが多いです。
最も簡単な次のゲームは、1つの山と1つのカウンターしかありません。左のプレイヤーが先に手を出した場合、そのプレイヤーはカウンターを取らなければならず、右のプレイヤーは何も手を出せません({|}, または0)。代わりに右が先手を打った場合、左はそれ以上の手を打つことができません。つまり、左も右も0に手を出すことができるので、{{|}|{|}}または{0|0}となります。最初に手を出した人が勝ちです。0|0}に等しいゲームは非常に重要です。これは、* (星)という記号で書かれています。
質問と回答
Q:組合せゲーム理論とは何ですか?
A: 組合せゲーム理論(Combinatorial Game Theory)とは、組合せゲームを研究する応用数学および理論計算機科学の一分野であり、「伝統的」または「経済的」ゲーム理論とは区別されるものである。
Q:組合せゲームとみなされるためには、どのような条件を満たす必要がありますか?
A: 組合せゲームとみなされるためには、少なくとも2人のプレーヤーがいること、プレーヤーが交互に交代すること、完全情報があること、決定論的であること（偶然性がない）、運が絡まないこと、可能な手の数が決まっていること、ゲームが最終的に終わること、プレーヤーが動かなくなったらゲームが終了することが必要である。
Q: 組み合わせゲーム理論では、どのようなゲームを研究しているのですか?
A: 組合せゲーム理論では、主に勝者と敗者が存在する（引き分けに終わらない）二人用の有限ゲームを扱う。
Q: このようなゲームはどのように表現されるのですか?
A: この種のゲームは木で表現することができます。各頂点は、木におけるその直下の特定の手から得られるゲームの結果を表します。
Q: CG理論家の目標は何ですか?
A: CG理論家の目標は、これらのタイプのゲームの値を見つけることと、各プレイヤーが2つの異なるゲームで1手だけを打ち、もう一方は手番中に変更しない「ゲーム加算」の概念を理解することです。
Q:CGTの設立者は誰ですか?
A: エルウィン・バーレカンプ、ジョン・コンウェイ、リチャード・ガイの3人が、1960年代に出版した「Winning Ways for Your Mathematical Plays」という著作で、CGTの創設者としてクレジットされています。
