ゲームで学ぶ探索アルゴリズム実践入門〜木探索とメタヒューリスティクス
書籍情報
発売日 : 2023年02月18日
著者／編集 : 青木 栄太
出版社 : 技術評論社
発行形態 : 単行本
書籍説明
内容紹介
ゲームＡＩや最適化を支える技術探索アルゴリズムを基礎からしっかり解説！アルゴリズムのしくみと実装のポイントがわかる！
目次
■第1章 ゲームと探索の世界
1.1 ゲームAIと探索
- 1.1.1 ゲームにおけるAIと探索
- 1.1.2 ゲームの種類と探索アルゴリズム
1.2 ゲームにおける探索の魅力
- 1.2.1 個人ゲーム開発にこそ探索！
- 1.2.2 大規模商業ゲーム開発にも探索！
- 1.2.3 多様化するプログラミングコンテストの武器に！
■第2章 開発環境の準備
2.1 Windows Subsystem for Linux［WSL］のインストール
- 2.1.1 WSLの起動確認
- 2.1.2 CPUの仮想化機能の確認
- 2.1.3 BIOS/UEFIで仮想化機能を有効化
- 2.1.4 ディストリビューションの導入
- 2.1.5 パッケージの更新
- 2.1.6 C++開発環境のインストール
■第3章 文脈のある一人ゲームに使いたい探索アルゴリズム
3.1 サンプルゲーム紹介～数字集め迷路
- 3.1.1 数字集め迷路とは
- 3.1.2 数字集め迷路の実装
3.2 貪欲法［Greedy］
- 3.2.1 貪欲法の特徴と動作～全ての探索アルゴリズムの基礎！ これさえあれば戦える！～
- 3.2.2 貪欲法の実装
3.3 ビームサーチ
- 3.3.1 ビームサーチの特徴と動作～探索空間を見極めろ！ コンテスト上級者も愛用する探索！
- 3.3.2 ビームサーチの実装
3.4 Chokudaiサーチ
- 3.4.1 Chokudaiサーチの特徴と動作～多様性を自動で確保！ お手軽で初心者にオススメ！
- 3.4.2 Chokudaiサーチの実装
■第4章 文脈のない一人ゲームに使いたい探索アルゴリズム
4.1 サンプルゲーム紹介～オート数字集め迷路
- 4.1.1 オート数字集め迷路とは
- 4.1.2 オート数字集め迷路の実装
4.2 山登り法
- 4.2.1 山登り法の特徴と動作～着実によい解を探索する！ シンプルで安定感のあるアルゴリズム！
- 4.2.2 山登り法の実装
4.3 焼きなまし法
- 4.3.1 焼きなまし法の特徴と動作～局所解を抜け出せ！ マラソンマッチでおなじみのアルゴリズム！
- 4.3.2 焼きなまし法の実装
■第5章 交互着手二人ゲームに使いたい探索アルゴリズム
5.1 サンプルゲーム紹介～交互着手数字集め迷路
- 5.1.1 交互着手数字集め迷路とは
- 5.1.2 交互着手数字集め迷路の実装
5.2 MiniMax法
- 5.2.1 MiniMax法の特徴と動作～「神の一手」が打てます。そう、この手法ならね
- 5.2.2 MiniMax法の実装
5.3 AlphaBeta法
- 5.3.1 AlphaBeta法の特徴と動作～無駄は許さない！ MiniMax法の正統進化！
- 5.3.2 AlphaBeta法の実装
5.4 反復深化［Iterative Deepening］
- 5.4.1 反復深化の特徴と動作～時間を無駄にしない！ 最適な木の深さを見つけよう！
- 5.4.2 反復深化の実装
5.5 原始モンテカルロ法
- 5.5.1 原始モンテカルロ法の特徴と動作～盤面評価不要！ 勝率のよい手を選べ！
- 5.5.2 原始モンテカルロ法の実装
5.6 MCTS［モンテカルロ木探索］
- 5.6.1 MCTSの特徴と動作～敵を侮るな！ 強者同士の勝負をシミュレーション！
- 5.6.2 MCTSの実装
5.7 Thunderサーチ
- 5.7.1 Thunderサーチの特徴と動作～筆者考案！ 盤面評価を利用して有益なノードを探索！
- 5.7.2 Thunderサーチの実装
■第6章 同時着手二人ゲームに使いたい探索アルゴリズム
6.1 サンプルゲーム紹介～同時着手数字集め迷路
- 6.1.1 同時着手数字集め迷路とは
- 6.1.2 同時着手数字集め迷路の実装
6.2 交互着手用アルゴリズムの適用
- 6.2.1 原始モンテカルロ法の実装
- 6.2.2 MCTSの実装
6.3 DUCT［Decoupled Upper Confidence Tree］
- 6.3.1 DUCTの特徴と動作～コンテストで大注目！ 同時着手ならこれ！
- 6.3.2 DUCTの実装
■第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.4 高速化
- 7.4.1 複数のビット列で盤面を表現
- 7.4.2 複数のビット列で盤面を表現する実装
- 7.4.3 単一のビット列で盤面を表現
- 7.4.4 単一のビット列で盤面を表現する実装
- 7.4.5 コピー回数の抑制
- 7.4.6 参照カウント方式によるコピー回数抑制の実装
■第8章 実際のゲームへの応用
8.1 コネクトフォーをプレイするAIの実装
- 8.1.1 サンプルゲーム紹介～コネクトフォーとは
- 8.1.2 コネクトフォーの実装
- 8.1.3 盤面のビットボード化による高速化
- 8.1.4 コネクトフォーにビット演算を適用する実装
1.1 ゲームAIと探索
- 1.1.1 ゲームにおけるAIと探索
- 1.1.2 ゲームの種類と探索アルゴリズム
1.2 ゲームにおける探索の魅力
- 1.2.1 個人ゲーム開発にこそ探索！
- 1.2.2 大規模商業ゲーム開発にも探索！
- 1.2.3 多様化するプログラミングコンテストの武器に！
■第2章 開発環境の準備
2.1 Windows Subsystem for Linux［WSL］のインストール
- 2.1.1 WSLの起動確認
- 2.1.2 CPUの仮想化機能の確認
- 2.1.3 BIOS/UEFIで仮想化機能を有効化
- 2.1.4 ディストリビューションの導入
- 2.1.5 パッケージの更新
- 2.1.6 C++開発環境のインストール
■第3章 文脈のある一人ゲームに使いたい探索アルゴリズム
3.1 サンプルゲーム紹介～数字集め迷路
- 3.1.1 数字集め迷路とは
- 3.1.2 数字集め迷路の実装
3.2 貪欲法［Greedy］
- 3.2.1 貪欲法の特徴と動作～全ての探索アルゴリズムの基礎！ これさえあれば戦える！～
- 3.2.2 貪欲法の実装
3.3 ビームサーチ
- 3.3.1 ビームサーチの特徴と動作～探索空間を見極めろ！ コンテスト上級者も愛用する探索！
- 3.3.2 ビームサーチの実装
3.4 Chokudaiサーチ
- 3.4.1 Chokudaiサーチの特徴と動作～多様性を自動で確保！ お手軽で初心者にオススメ！
- 3.4.2 Chokudaiサーチの実装
■第4章 文脈のない一人ゲームに使いたい探索アルゴリズム
4.1 サンプルゲーム紹介～オート数字集め迷路
- 4.1.1 オート数字集め迷路とは
- 4.1.2 オート数字集め迷路の実装
4.2 山登り法
- 4.2.1 山登り法の特徴と動作～着実によい解を探索する！ シンプルで安定感のあるアルゴリズム！
- 4.2.2 山登り法の実装
4.3 焼きなまし法
- 4.3.1 焼きなまし法の特徴と動作～局所解を抜け出せ！ マラソンマッチでおなじみのアルゴリズム！
- 4.3.2 焼きなまし法の実装
■第5章 交互着手二人ゲームに使いたい探索アルゴリズム
5.1 サンプルゲーム紹介～交互着手数字集め迷路
- 5.1.1 交互着手数字集め迷路とは
- 5.1.2 交互着手数字集め迷路の実装
5.2 MiniMax法
- 5.2.1 MiniMax法の特徴と動作～「神の一手」が打てます。そう、この手法ならね
- 5.2.2 MiniMax法の実装
5.3 AlphaBeta法
- 5.3.1 AlphaBeta法の特徴と動作～無駄は許さない！ MiniMax法の正統進化！
- 5.3.2 AlphaBeta法の実装
5.4 反復深化［Iterative Deepening］
- 5.4.1 反復深化の特徴と動作～時間を無駄にしない！ 最適な木の深さを見つけよう！
- 5.4.2 反復深化の実装
5.5 原始モンテカルロ法
- 5.5.1 原始モンテカルロ法の特徴と動作～盤面評価不要！ 勝率のよい手を選べ！
- 5.5.2 原始モンテカルロ法の実装
5.6 MCTS［モンテカルロ木探索］
- 5.6.1 MCTSの特徴と動作～敵を侮るな！ 強者同士の勝負をシミュレーション！
- 5.6.2 MCTSの実装
5.7 Thunderサーチ
- 5.7.1 Thunderサーチの特徴と動作～筆者考案！ 盤面評価を利用して有益なノードを探索！
- 5.7.2 Thunderサーチの実装
■第6章 同時着手二人ゲームに使いたい探索アルゴリズム
6.1 サンプルゲーム紹介～同時着手数字集め迷路
- 6.1.1 同時着手数字集め迷路とは
- 6.1.2 同時着手数字集め迷路の実装
6.2 交互着手用アルゴリズムの適用
- 6.2.1 原始モンテカルロ法の実装
- 6.2.2 MCTSの実装
6.3 DUCT［Decoupled Upper Confidence Tree］
- 6.3.1 DUCTの特徴と動作～コンテストで大注目！ 同時着手ならこれ！
- 6.3.2 DUCTの実装
■第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.4 高速化
- 7.4.1 複数のビット列で盤面を表現
- 7.4.2 複数のビット列で盤面を表現する実装
- 7.4.3 単一のビット列で盤面を表現
- 7.4.4 単一のビット列で盤面を表現する実装
- 7.4.5 コピー回数の抑制
- 7.4.6 参照カウント方式によるコピー回数抑制の実装
■第8章 実際のゲームへの応用
8.1 コネクトフォーをプレイするAIの実装
- 8.1.1 サンプルゲーム紹介～コネクトフォーとは
- 8.1.2 コネクトフォーの実装
- 8.1.3 盤面のビットボード化による高速化
- 8.1.4 コネクトフォーにビット演算を適用する実装
著者情報
青木 栄太
1990年生まれ。2019年2月にHEROZ株式会社に入社後、ゲームAI開発に従事。プログラミングコンテストでは「thunder」として活躍。年に一度開催される国際学会「IEEE Conference on Games」にて開催されるゲームAIコンペティションにて7回優勝。その中でも特に、Fighting Game AI Competitionにて四連覇を達成。Qiitaに本書の前身である「世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門」記事を執筆するなど、探索アルゴリズムの普及活動にも取り組んでいる。
青木, 栄太, 1990-
