| まえがき |
| 人間の知的遊戯とゲームの分類 |
| 1.1 ゲームとはなにか 1 |
| 1.2 ゲームの分類 2 |
| 1.2.1 0人ゲーム，1人ゲーム，2人ゲーム，3人以上のゲーム 2 |
| 1.2.2 完全情報ゲームと不完全情報ゲーム 4 |
| 1.2.3 確定的ゲームと非確定的ゲーム 5 |
| 1.2.4 零和ゲームと非零和ゲーム 5 |
| 1.3 2人完全情報確定零和ゲーム 6 |
| 1.4 思考ゲームの社会的意味 7 |
| 演習問題 8 |
| 休憩室：衝立将棋 8 |
| 2人ゲームとゲーム木の先読み |
| 2.1 ゲームのプログラミングとは 9 |
| 2.2 ゲームのためのデータ 10 |
| 2.3 ゲームのための手続き 14 |
| 2.4 静的評価と通常のゲーム木探索 17 |
| 演習問題 20 |
| 休憩室：ヘックス 21 |
| ゲーム木探索メカニズム |
| 3.1 β値の導入 23 |
| 3.2 α値の導入 25 |
| 3.3 順序付け 26 |
| 3.4 反復深化 28 |
| 3.5 ランダム探索木の作成方法 29 |
| 演習問題 30 |
| 休憩室：ゲーム木の複雑さ 31 |
| 評価値計算とゲームプログラムの基礎 |
| 4.1 評価関数 32 |
| 4.2 ゲームプログラムを作る 34 |
| 4.3 データ構造や計算の工夫 35 |
| 4.3.1 局面のデータ構造 35 |
| 4.3.2 付加的データ 36 |
| 4.3.3 データの詰め込み方 36 |
| 4.3.4 インクリメンタルな計算 36 |
| 4.3.5 関数値の表による計算 37 |
| 演習問題 37 |
| 休憩室：アマゾン 38 |
| ゲーム木拡張 |
| 5.1 前向き枝刈り 39 |
| 5.2 捕獲探索 40 |
| 5.3 シンギュラー拡張 40 |
| 5.4 小数点拡張 41 |
| 5.5 実現確率探索 41 |
| 5.6 探索アルゴリズムへの組み込み 42 |
| 演習問題 42 |
| 休憩室：ゲームの解 43 |
| トランスポジションテーブル |
| 6.1 同一局面とはなにか 44 |
| 6.2 どんなときに局面が同一になるか 45 |
| 6.3 どんな情報を保存するか 46 |
| 6.4 データ構造 48 |
| 6.5 インデックスの衝突の（不）処理 48 |
| 6.6 トランスポジションテーブル利用のアルゴリズム 50 |
| 6.7 ハッシュ関数の構成法 51 |
| 6.8 他の状況でのハッシュテーブル 52 |
| 6.9 トランスポジションテーブルの有効性 53 |
| 演習問題 54 |
| 休憩室：将棋のバリエーション 54 |
| ウィンドウ探索 |
| 7.1 ウィンドウ探索の基本とアスピレーション探索 55 |
| 7.2 ヌルウィンドウ探索 56 |
| 7.3 ネガスカウト 57 |
| 7.4 MTD 58 |
| 7.4.1 MTDアルゴリズム 59 |
| 7.4.2 MTDの種類と動作 65 |
| 演習問題 67 |
| 探索領域の制御 |
| 8.1 ProbCut 68 |
| 8.2 実現確率探索 72 |
| 演習問題 74 |
| 休憩室：ダブルストーン 74 |
| 並列探索 |
| 9.1 動機 75 |
| 9.2 コンピュータのモデル 76 |
| 9.3 並列探索のオーバヘッド 77 |
| 9.4 並列アスピレーション探索 80 |
| 9.5 YBWCアルゴリズム 81 |
| 9.5.1 基本的な考え方 81 |
| 9.5.2 Jamboreeアルゴリズム―YBWCアルゴリズムを利用した例 82 |
| 9.5.3 YBWCアルゴリズムの改良 84 |
| 9.6 ワークスティーリングによる仕事のスケジューリング 85 |
| 9.7 分散メモリ環境における並列探索 86 |
| 9.7.1 トランスポジションテーブル共有に関する問題 86 |
| 9.7.2 探索空間がDAGの場合の問題 90 |
| 9.7.3 TDSアルゴリズムによる仕事のスケジューリング 91 |
| 演習問題 93 |
| AND/OR木と証明数探索 |
| 10.1 はじめに 94 |
| 10.2 定義 96 |
| 10.3 証明数と反証数 99 |
| 10.4 証明数探索 101 |
| 10.5 証明数探索の改良 103 |
| 10.5.1 先端ノードの証明数・反証数の初期化 103 |
| 10.5.2 内部ノードにおける探索の効率化 104 |
| 演習問題 104 |
| 休憩室：詰将棋のルール 105 |
| 深さ優先探索を用いた証明数探索と性能向上手法 |
| 11.1 深さ優先探索に変換する意義 106 |
| 11.2 脊尾のアルゴリズム 107 |
| 11.2.1 証明数を用いた反復深化法 107 |
| 11.2.2 トランスポジションテーブルの利用 110 |
| 11.2.3 多重反復深化法 110 |
| 11.2.4 脊尾のアルゴリズムの擬似コード 111 |
| 11.3 df-pnアルゴリズム 113 |
| 11.3.1 基本的な考え方 113 |
| 11.3.2 df-pnアルゴリズムの擬似コード 117 |
| 11.3.3 df-pnアルゴリズムと証明数探索の性能比較 119 |
| 11.3.4 df-pnアルゴリズムの改良 120 |
| 11.4 シミュレーション 120 |
| 11.4.1 基本的な考え方 120 |
| 11.4.2 シミュレーションの擬似コード 122 |
| 11.5 トランスポジションテーブルの効率的な利用法 124 |
| 11.6 探索空間がDAGの場合に生じる問題 125 |
| 演習問題 126 |
| サイクル空間におけるAND/OR木探索 |
| 12.1 はじめに 127 |
| 12.2 GHI問題 128 |
| 12.3 GHI問題への単純な解決策 129 |
| 12.3.1 探索空間が木であると考える 129 |
| 12.3.2 不可逆な指し手と可逆な指し手に分割する 130 |
| 12.4 岸本・Mu・245D・llerのGHI解決索 130 |
| 12.4.1 基本的な考え方 130 |
| 12.4.2 トランスポジションテーブルの改良 131 |
| 12.4.3 シミュレーションの利用 133 |
| 12.4.4 GHI解決策を付加したdf-pnアルゴリズムの擬似コード 133 |
| 12.4.5 その他の問題について 135 |
| 12.5 サイクル空間でのdf-pnアルゴリズムの無限ループ問題 137 |
| 12.6 最小距離法 139 |
| 12.6.1 基本的な考え方 139 |
| 12.6.2 最小距離の更新 141 |
| 12.6.3 最小距離法の擬似コード 142 |
| 12.6.4 最小距離法の問題点 143 |
| 演習問題 143 |
| 休憩室：小さな将棋 144 |
| モンテカルロ法による探索 |
| 13.1 囲碁でモンテカルロ法が成果を挙げる 145 |
| 13.2 モンテカルロ法の基本的な考え方 146 |
| 13.3 UCT 149 |
| 13.4 モンテカルロ法の現在 154 |
| 演習問題 155 |
| ゲームにおける学習1：強化学習 |
| 14.1 予言学習問題と学習アルゴリズム 156 |
| 14.2 最小平均二乗法 157 |
| 14.3 最小平均二乗法の学習例：4×3の世界 158 |
| 14.4 TD法 161 |
| 14.5 TD(λ)の学習例：4×3の世界 163 |
| 14.6 Q学習 165 |
| 14.7 いくつかの学習事例 166 |
| 演習問題 167 |
| 休憩室：ブロックスデュオ 168 |
| ゲームにおける学習2：ニューラルネットワーク |
| 15.1 ニューラルネットワークと神経細胞 170 |
| 15.2 ニューラルネットワークの計算 171 |
| 15.3 ニューラルネットワークの学習方法 173 |
| 15.4 学習における問題 176 |
| 15.5 いくつかの学習事例 177 |
| 演習問題 178 |
| 休憩室：ゲームの部分計算 178 |
| あとがき 179 |
| 引用・参考文献 180 |
| 演習問題解答 1486 |
| 索引 187 |
| まえがき |
| 人間の知的遊戯とゲームの分類 |
| 1.1 ゲームとはなにか 1 |
| 1.2 ゲームの分類 2 |
| 1.2.1 0人ゲーム，1人ゲーム，2人ゲーム，3人以上のゲーム 2 |
| 1.2.2 完全情報ゲームと不完全情報ゲーム 4 |
