組合せゲーム理論の世界
数学で解き明かす必勝法
著：安福 智明
著：坂井 公
著：末續 鴻輝
内容紹介
組合せゲーム理論について基本的な内容から最先端の研究まで幅広く解説。
組合せゲーム理論とは、運の要素や伏せられた情報がないゲームに潜む数学的な構造を探る理論であり、ゲームという身近で楽しい題材を取り扱いつつ、深い数学的な構造を含んでいる非常に興味深い理論である。近年では、他の数学分野との繋がりが調べられたり、競技プログラミングの問題として取り上げられたりするなど、組合せゲーム理論に関心を持つ人が増えている。
本書では、組合せゲーム理論に興味のあるすべての人が読み進められるように、可能な限り、定理などの主張の証明は詳細に述べた。また、基礎的な概念をできるだけ網羅しつつ、そこからどのような展開がなされているのかを紹介し、さらなる勉強の助けとなることを目指した。各章末には演習問題を用意し、巻末に解答例をまとめているため、独学にも適している。
目次
第1章 組合せゲーム
1.1 組合せゲームとは
1.2 コラム1：組合せゲーム理論の研究集会
第2章 ニムとグランディ数
2.1 ニム
2.2 不偏ゲーム
2.3 ニムの必勝者判定
2.3.1 2山以下のニム
2.3.2 3山以上のニム
2.4 グランディ数
2.5 ターニング・タートルズ
2.6 コラム2：ニム積
2.7 コラム3：直和以外のゲームの和
2.7.1 ゲームの結合和
2.7.2 ゲームの選択和
2.7.3 ゲームの皇帝和
第3章 様々な不偏ゲーム
3.1 制限ニム
3.2 All-but ニム
3.3 8進ニム
3.4 Max ニムと Min ニム
3.4.1 Max ニム
3.4.2 Min ニム
3.5 Wythoffのニムとその変種
3.5.1 Wythoffのニムの一般化
3.6 Mooreのニム
3.7 コラム4：佐藤・ウェルターゲーム
3.8 コラム5：表現論とのつながり
第4章 非不偏ゲームの性質
4.1 非不偏ゲームの定義
4.2 非不偏ゲームの直和と代数構造
4.3 ゲームの大小関係
4.4 局面の標準形
4.5 コラム6：計算複雑性の話
第5章 様々な局面の値
5.1 整数
5.2 局面の値とは
5.3 2進有理数
5.4 *k（スターk）
5.5 ↑（アップ）と↓（ダウン）
5.6 ⧾（タイニー）と⧿（マイニー）
5.7 2進有理数とほかの値の関係
5.8 転換ゲーム
5.9 特徴的な局面
5.10 コラム7：局面の値が常に2進有理数になるルールセット
5.11 コラム8：全象ルールの話
第6章 超現実数とゲームの終局値
6.1 超限ゲームの基本的な性質
6.2 超現実数の定義と基本的な性質
6.3 ゲームの終局値
6.4 コラム9：超現実数の構造
6.5 コラム10：ゲームの温度
6.6 コラム11：不偏超限ゲームとグランディ数
6.6.1 超限ニム
6.6.2 超限佐藤・ウェルターゲーム
第7章 発展的な話題
7.1 ルーピーゲーム
7.1.1 不偏ルーピーゲーム
7.1.2 不偏ルーピーゲームの値
7.2 逆形ゲーム
7.2.1 逆形不偏ゲーム
7.2.2 逆形商
7.3 得点付きゲーム
7.3.1 得点付きゲームの定義
7.3.2 保証された得点付きゲーム
7.3.3 正規形非不偏ゲームとの関係
7.3.4 得点駒あり一般化コナネ
7.3.5 ゲームの宇宙
7.4 コラム12：非不偏ルーピーゲーム
7.5 コラム13：逆形ケイレスの逆形商
7.6 コラム14：逆形非不偏ゲーム
7.6.1 停滞ゲームの宇宙
7.6.2 双葉ゲームの宇宙
7.6.3 交互ゲームの宇宙
解答例
関連図書
索引
