まえがき |
人間の知的遊戯とゲームの分類 |
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 |