書籍概要

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

著者
発売日
更新日

概要

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

こんな方におすすめ

  • アルゴリズムに興味がある人
  • ゲームAIの仕組みに興味がある人
  • AIを機械学習以外の視点から見つめ直し，視野を広げたい人
  • ゲームAIコンテストやヒューリスティックコンテストで競うための地力をつけたい人
  • 対戦ゲームを開発してみたいが，CPU（コンピュータが操作するプレイヤー）の作り方がわからない人

サンプル

samplesamplesamplesamplesample

目次

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

サポート

ダウンロード

（2024年7月18日更新）

サンプルファイルダウンロード

本書の解説で使っているサンプルコードをダウンロードできます。ファイルはZIP形式で圧縮されていますので，展開してご利用ください。サンプルコードに含まれる内容については，本書のP.vをご覧ください。

ダウンロード
sample_code.zip

更新情報

以下のファイルの内容を更新しました。

  • 06_SimultaneousGame/03_DUCT.cpp
  • Appendix/06_DUCTWithTime.cpp
誤 
w = 1. - w; // 敵側の行動選択フェーズなので、ここは評価を反転する必要がある
double ucb1_value = w / n + (double)C * std::sqrt(2. * std::log(t) / n);
正 
// 敵側の行動選択フェーズなので、ここは評価を反転する必要がある
double ucb1_value = 1. - w / n + (double)C * std::sqrt(2. * std::log(t) / n);

（以下2023年3月2日更新）

以下のファイルの内容を更新しました。

  • Appendix/03_BeamSearchWithTime.cpp
  • Appendix/03_ChokudaiSearchWithTime.cpp
誤 
// 探索時のソート用に評価を比較する
bool operator<(const State &state_1, const State &state_2)
{
    return state_1.evaluated_score_ < state_1.evaluated_score_;
}
正 
// 探索時のソート用に評価を比較する
bool operator<(const State &state_1, const State &state_2)
{
    return state_1.evaluated_score_ < state_2.evaluated_score_;
}

（以下2023年2月9日更新）

以下のファイル名を変更しました。

変更前 Appendix/Appendixの使い方
変更後 Appendix/Appendixの使い方.txt

正誤表

本書の以下の部分に誤りがありました。ここに訂正するとともに，ご迷惑をおかけしたことを深くお詫び申し上げます。

（2024年7月18日最終更新）

P.184　本文下から2行目

誤 48行目のように評価を逆転させる点に注意
正 49行目のように評価を逆転させる点に注意

P.185　コード6.3.5の48行目

下記は削除します。

誤 
w = 1. - w;

P.185　コード6.3.5の49行目

誤 
double ucb1_value = w / n + (double)C * std::sqrt(2. * std::log(t) / n);
正 
double ucb1_value = 1. - w / n + (double)C * std::sqrt(2. * std::log(t) / n);

（以下2023年3月15日更新）

P.64　本文2行目

誤 ビームの本数＋1個の（以下略）
正 ビームの深さ＋1個の（以下略）

（以下2023年2月27日更新）

P.85　本文下から3行目（第2刷で修正済）

誤 tが高いほど遷移確率が低く、tが低いほど遷移確率が高くなります。
正 tが高いほど遷移確率が高く、tが低いほど遷移確率が低くなります。

P.103　本文下から5行目（第2刷で修正済）

誤 ノードfならAのスコアが6、
正 ノードhならAのスコアが7、

商品一覧