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

このスクラップは?
ゲームAI開発におけるアルゴリズムを知るための書籍やWebサイトのメモです。
このスクラップのスコープ
- 「強いゲームAIを作るためのアルゴリズム」を主な関心とします
- ゲーム開発一般の要素技術のことは書きません
- 古典的かつ現在も基礎として有用なものを扱います
- 深層学習を扱いません
- 基本的な再帰全探索などは書ける読者を想定して超入門は省きます

いろんな手法
記事「世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門」
サンダーさんの書籍化元記事。
ヒューリスティックやゲームAIの典型手法が一通り紹介されている。より深く知りたくなったら書籍へ。
書籍「ゲームで学ぶ探索アルゴリズム実践入門~木探索とメタヒューリスティクス」
焼きなまし、ビームサーチ、Chokudaiサーチ、αβ探索、MCTSなど、メタヒューリスティック手法やゲーム木探索を一通りコードレベルで理解できて使えるようになる本。
Tuhunderサーチ、DUCTや、高速化や多様性確保のテクニックも満載で、どのレベルの人が読んでもとても学びがあると思う。
書籍「ゲーム計算メカニズム」
単にαβ法の紹介にとどまらない高度な話題が豊富。
絶版で入手困難だけど、大学図書館などにあればオススメ。
書籍「パズルで鍛えるアルゴリズム力」
ゲームAIに固有の手法というよりは、DFSやDPを実際のパズルに適用する本。
反復深化A*や二部マッチングなど高度めな話題もある。
記事「コドゲ常設コンペ(BOTプログラミング)紹介」
実際の対戦系のゲームAIコンペでどんな手法が使われているか分かる。
記事「CodinGame 最適化ゲームの紹介」
実際の一人用最適化ゲーム(一人プレイ用のゲームをAIにプレイさせてハイスコアを競うジャンルのコンペ)でどんな手法が使われているか分かる。

αβ探索系
「オセロAIの教科書」を読みながらコドゲのオセロをやるのがとっつきやすい。
記事「オセロAIの教科書」
nyanyanさんによる神記事。
αβ法を使った先読み、盤面評価、定石、高速なボードの実装など、初学者が知りたいことが全て書いてある。
スライド「ビットボード解説」(東大マイコンクラブ)
オセロのビットボードについてはこれが一番易しいと思う。
記事「Egaroucid 技術解説」
にゃにゃんさんによる神記事2。
より高度な議論が書いてある。

MCTS系
基本的に、既に紹介したサンダー本がコードレベルで十分分かりやすいので、これを読んだら適当にコドゲで実践(自分はUltimate Tic-Tac-Toeにした)でよさそう。
かなり参考にした記事や論文があり、以前別スクラップにまとめた。

特定のゲームの本とか読み物とか
あるゲームに特化したヒューリスティックや、昔考察されていた手法など、読んでみると新鮮。
書籍「コンピュータ囲碁 ―モンテカルロ法の理論と実践―」
2012年(AlphaGo以前)に書かれた、囲碁のMCTS法の本。技術寄り。
書籍「最強囲碁AI アルファ碁 解体新書 増補改訂版 アルファ碁ゼロ対応 深層学習、モンテカルロ木探索、強化学習から見たその仕組み」
こちらは2018年の本なので、アルファ碁ゼロまで扱っている。
書籍「ゲームプログラミング」
1998年に書かれた最新情報。チェス、将棋、囲碁、五目並べ、チェッカー、ブリッジ、詰将棋、倉庫番、箱詰めパズルなど、題材が豊富。
書籍「コンピュータ将棋の進歩」①~⑥
歴史を感じられる。
その時々のトップ開発者やAI研究者による論文集のような形で、普通に強いAI以外にも「詰将棋専門エンジン」「手加減をするAI」「特定プレイヤーの指し手を模倣するAI」など様々な話が載っている。