ゲーム計算メカニズム - 将棋・囲碁・オセロ・チェスのプログラムはどう動く -
本書はどうすればコンピュータにゲームをプレーさせられるかについて書かれた本である。ここでゲームとは,頭を使って戦う思考ゲームのことである。本書ではその中でも中心的な分野である二人・完全情報・確定的・零和ゲームを扱う。
- ジャンル
- 発行年月日
- 2010/02/26
- 判型
- A5
- ページ数
- 204ページ
- ISBN
- 978-4-339-02540-8
- 内容紹介
- 目次
- レビュー
本書はどうすればコンピュータにゲームをプレーさせられるかについて書かれた本である。ここでゲームとは,頭を使って戦う思考ゲームのことである。本書ではその中でも中心的な分野である二人・完全情報・確定的・零和ゲームを扱う。
まえがき
人間の知的遊戯とゲームの分類
1.1 ゲームとはなにか
1.2 ゲームの分類
1.2.1 0人ゲーム,1人ゲーム,2人ゲーム,3人以上のゲーム
1.2.2 完全情報ゲームと不完全情報ゲーム
1.2.3 確定的ゲームと非確定的ゲーム
1.2.4 零和ゲームと非零和ゲーム
1.3 2人完全情報確定零和ゲーム
1.4 思考ゲームの社会的意味
演習問題
休憩室:衝立将棋
2人ゲームとゲーム木の先読み
2.1 ゲームのプログラミングとは
2.2 ゲームのためのデータ
2.3 ゲームのための手続き
2.4 静的評価と通常のゲーム木探索
演習問題
休憩室:ヘックス
ゲーム木探索メカニズム
3.1 β値の導入
3.2 α値の導入
3.3 順序付け
3.4 反復深化
3.5 ランダム探索木の作成方法
演習問題
休憩室:ゲーム木の複雑さ
評価値計算とゲームプログラムの基礎
4.1 評価関数
4.2 ゲームプログラムを作る
4.3 データ構造や計算の工夫
4.3.1 局面のデータ構造
4.3.2 付加的データ
4.3.3 データの詰め込み方
4.3.4 インクリメンタルな計算
4.3.5 関数値の表による計算
演習問題
休憩室:アマゾン
ゲーム木拡張
5.1 前向き枝刈り
5.2 捕獲探索
5.3 シンギュラー拡張
5.4 小数点拡張
5.5 実現確率探索
5.6 探索アルゴリズムへの組み込み
演習問題
休憩室:ゲームの解
トランスポジションテーブル
6.1 同一局面とはなにか
6.2 どんなときに局面が同一になるか
6.3 どんな情報を保存するか
6.4 データ構造
6.5 インデックスの衝突の(不)処理
6.6 トランスポジションテーブル利用のアルゴリズム
6.7 ハッシュ関数の構成法
6.8 他の状況でのハッシュテーブル
6.9 トランスポジションテーブルの有効性
演習問題
休憩室:将棋のバリエーション
ウィンドウ探索
7.1 ウィンドウ探索の基本とアスピレーション探索
7.2 ヌルウィンドウ探索
7.3 ネガスカウト
7.4 MTD
7.4.1 MTDアルゴリズム
7.4.2 MTDの種類と動作
演習問題
探索領域の制御
8.1 ProbCut
8.2 実現確率探索
演習問題
休憩室:ダブルストーン
並列探索
9.1 動機
9.2 コンピュータのモデル
9.3 並列探索のオーバヘッド
9.4 並列アスピレーション探索
9.5 YBWCアルゴリズム
9.5.1 基本的な考え方
9.5.2 Jamboreeアルゴリズム ― YBWCアルゴリズムを利用した例
9.5.3 YBWCアルゴリズムの改良
9.6 ワークスティーリングによる仕事のスケジューリング
9.7 分散メモリ環境における並列探索
9.7.1 トランスポジションテーブル共有に関する問題
9.7.2 探索空間がDAGの場合の問題
9.7.3 TDSアルゴリズムによる仕事のスケジューリング
演習問題
AND/OR木と証明数探索
10.1 はじめに
10.2 定義
10.3 証明数と反証数
10.4 証明数探索
10.5 証明数探索の改良
10.5.1 先端ノードの証明数・反証数の初期化
10.5.2 内部ノードにおける探索の効率化
演習問題
休憩室:詰将棋のルール
深さ優先探索を用いた証明数探索と性能向上手法
11.1 深さ優先探索に変換する意義
11.2 脊尾のアルゴリズム
11.2.1 証明数を用いた反復深化法
11.2.2 トランスポジションテーブルの利用
11.2.3 多重反復深化法
11.2.4 脊尾のアルゴリズムの擬似コード
11.3 df-pnアルゴリズム
11.3.1 基本的な考え方
11.3.2 df-pnアルゴリズムの擬似コード
11.3.3 df-pnアルゴリズムと証明数探索の性能比較
11.3.4 df-pnアルゴリズムの改良
11.4 シミュレーション
11.4.1 基本的な考え方
11.4.2 シミュレーションの擬似コード
11.5 トランスポジションテーブルの効率的な利用法
11.6 探索空間がDAGの場合に生じる問題
演習問題
サイクル空間におけるAND/OR木探索
12.1 はじめに
12.2 GHI問題
12.3 GHI問題への単純な解決策
12.3.1 探索空間が木であると考える
12.3.2 不可逆な指し手と可逆な指し手に分割する
12.4 岸本・Mu245DllerのGHI解決索
12.4.1 基本的な考え方
12.4.2 トランスポジションテーブルの改良
12.4.3 シミュレーションの利用
12.4.4 GHI解決策を付加したdf-pnアルゴリズムの擬似コード
12.4.5 その他の問題について
12.5 サイクル空間でのdf-pnアルゴリズムの無限ループ問題
12.6 最小距離法
12.6.1 基本的な考え方
12.6.2 最小距離の更新
12.6.3 最小距離法の擬似コード
12.6.4 最小距離法の問題点
演習問題
休憩室:小さな将棋
モンテカルロ法による探索
13.1 囲碁でモンテカルロ法が成果を挙げる
13.2 モンテカルロ法の基本的な考え方
13.3 UCT
13.4 モンテカルロ法の現在
演習問題
ゲームにおける学習1:強化学習
14.1 予言学習問題と学習アルゴリズム
14.2 最小平均二乗法
14.3 最小平均二乗法の学習例:4×3の世界
14.4 TD法
14.5 TD(λ)の学習例:4×3の世界
14.6 Q学習
14.7 いくつかの学習事例
演習問題
休憩室:ブロックスデュオ
ゲームにおける学習2:ニューラルネットワーク
15.1 ニューラルネットワークと神経細胞
15.2 ニューラルネットワークの計算
15.3 ニューラルネットワークの学習方法
15.4 学習における問題
15.5 いくつかの学習事例
演習問題
休憩室:ゲームの部分計算
あとがき
引用・参考文献
演習問題解答
索引