Open5

古典的なゲーム木探索などの書籍とか

binomialsheepbinomialsheep

このスクラップは?

ゲームAI開発におけるアルゴリズムを知るための書籍やWebサイトのメモです。

このスクラップのスコープ

  • 「強いゲームAIを作るためのアルゴリズム」を主な関心とします
    • ゲーム開発一般の要素技術のことは書きません
  • 古典的かつ現在も基礎として有用なものを扱います
    • 深層学習を扱いません
  • 基本的な再帰全探索などは書ける読者を想定して超入門は省きます
binomialsheepbinomialsheep

いろんな手法

記事「世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門」

https://qiita.com/thun-c/items/058743a25c37c87b8aa4

サンダーさんの書籍化元記事。
ヒューリスティックやゲームAIの典型手法が一通り紹介されている。より深く知りたくなったら書籍へ。

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

https://gihyo.jp/book/2023/978-4-297-13360-3
いわゆるサンダー本。
焼きなまし、ビームサーチ、Chokudaiサーチ、αβ探索、MCTSなど、メタヒューリスティック手法やゲーム木探索を一通りコードレベルで理解できて使えるようになる本。
Tuhunderサーチ、DUCTや、高速化や多様性確保のテクニックも満載で、どのレベルの人が読んでもとても学びがあると思う。

書籍「ゲーム計算メカニズム」

https://www.coronasha.co.jp/np/isbn/9784339025408/
主に二人零和有限確定完全情報ゲームに焦点を当てた本。
単にαβ法の紹介にとどまらない高度な話題が豊富。
絶版で入手困難だけど、大学図書館などにあればオススメ。

書籍「パズルで鍛えるアルゴリズム力」

https://gihyo.jp/book/2022/978-4-297-12679-7
けんちょんさん著。
ゲームAIに固有の手法というよりは、DFSやDPを実際のパズルに適用する本。
反復深化A*や二部マッチングなど高度めな話題もある。

記事「コドゲ常設コンペ(BOTプログラミング)紹介」

https://inaniwa.hatenablog.com/entry/2020/11/29/024805

実際の対戦系のゲームAIコンペでどんな手法が使われているか分かる。

記事「CodinGame 最適化ゲームの紹介」

https://valgrowth.hatenablog.com/entry/2021/03/14/231034

実際の一人用最適化ゲーム(一人プレイ用のゲームをAIにプレイさせてハイスコアを競うジャンルのコンペ)でどんな手法が使われているか分かる。

binomialsheepbinomialsheep

αβ探索系

「オセロAIの教科書」を読みながらコドゲのオセロをやるのがとっつきやすい。

記事「オセロAIの教科書」

https://note.com/nyanyan_cubetech/m/m54104c8d2f12

nyanyanさんによる神記事。
αβ法を使った先読み、盤面評価、定石、高速なボードの実装など、初学者が知りたいことが全て書いてある。

スライド「ビットボード解説」(東大マイコンクラブ)

https://speakerdeck.com/antenna_three/bitutobodojie-shuo

オセロのビットボードについてはこれが一番易しいと思う。

記事「Egaroucid 技術解説」

https://www.egaroucid.nyanyan.dev/ja/technology/explanation/

にゃにゃんさんによる神記事2。
より高度な議論が書いてある。

binomialsheepbinomialsheep

特定のゲームの本とか読み物とか

あるゲームに特化したヒューリスティックや、昔考察されていた手法など、読んでみると新鮮。

書籍「コンピュータ囲碁 ―モンテカルロ法の理論と実践―」

2012年(AlphaGo以前)に書かれた、囲碁のMCTS法の本。技術寄り。

書籍「最強囲碁AI アルファ碁 解体新書 増補改訂版 アルファ碁ゼロ対応 深層学習、モンテカルロ木探索、強化学習から見たその仕組み」

こちらは2018年の本なので、アルファ碁ゼロまで扱っている。

書籍「ゲームプログラミング」

https://www.kyoritsu-pub.co.jp/book/b10005339.html

1998年に書かれた最新情報。チェス、将棋、囲碁、五目並べ、チェッカー、ブリッジ、詰将棋、倉庫番、箱詰めパズルなど、題材が豊富。

書籍「コンピュータ将棋の進歩」①~⑥

https://www.kyoritsu-pub.co.jp/book/b10008160.html
それぞれ1996, 1998, 2000, 2003, 2005, 2012年に出版された将棋AIの本。
歴史を感じられる。
その時々のトップ開発者やAI研究者による論文集のような形で、普通に強いAI以外にも「詰将棋専門エンジン」「手加減をするAI」「特定プレイヤーの指し手を模倣するAI」など様々な話が載っている。