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

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

紙版発売
電子版発売

B5変形判／280ページ

定価2,992円（本体2,720円＋税10%）

ISBN 978-4-297-13360-3

電子版

→学校・法人一括購入ご検討の皆様へ

書籍の概要

この本の概要

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

こんな方におすすめ

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

この書籍に関連する記事があります！

ゲームAI／最適化を支える探索アルゴリズム
ゲームAIの技術要素には大きく「ルール」「探索」「機械学習」の3つがあります。本書は，このうち探索技術にフォーカスを当てた入門書です。ゲームAIを題材に，さまざまな探索アルゴリズムのしくみと実装のポイント，よりよい探索のためのテクニックをわかりやすく丁寧に解説します。

本書のサンプル

本書の紙面イメージは次のとおりです。画像をクリックすることで拡大して確認することができます。

サンプル画像1

サンプル画像2

サンプル画像3

サンプル画像4

サンプル画像5

目次

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

著者プロフィール

青木栄太（あおきえいた）

1990年生まれ。2019年2月にHEROZ株式会社に入社後，ゲームAI開発に従事。プログラミングコンテストでは「thunder」として活躍。年に一度開催される国際学会「IEEE Conference on Games」にて開催されるゲームAIコンペティションにて7回優勝。その中でも特に，Fighting Game AI Competitionにて四連覇を達成。Qiitaに本書の前身である「世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門」記事を執筆するなど，探索アルゴリズムの普及活動にも取り組んでいる。