【レビュー】ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス

■第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　コネクトフォーにビット演算を適用する実装

ゲームAIの技術要素には大きく分けて「ルール」「探索」「機械学習」の3つがあります。近年話題になることの多い機械学習ですが、機械学習だけでは遠い将来の状況を正確に読むことは難しく、特に探索がなければ真に強いAIは生まれません。また、ゲームAIの技術を競う各種コンテストなどでは使用できるメモリ量やファイルの容量に制限が課され、機械学習を利用することが現実的ではないケースもあります。これは実務においても同様で、与えられた要件によっては今も探索技術が主要素となり得ます。本書は、この探索技術とそれを支えるアルゴリズムにフォーカスを当て、ゲームAIを題材にその重要性と魅力を楽しく学ぶための入門書です。さまざまなゲームの種別に対応した探索アルゴリズムについて、動作のしくみと実装方法を丁寧に解説します。

　・# 「ゲームで学ぶ探索アルゴリズム実践入門」のサンプルコードでAtCoderの問題を解いてみた[2023-03-03に投稿]