thunderさんが探索アルゴリズムの入門書を執筆されたそうでご恵贈いただいた。

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

本書は、貪欲法、焼きなましのような競技プログラミングでよく出てくるアルゴリズムから、将棋や囲碁のAIでもよく出てくるMinimax、AlphaBeta、MCTSを解説している。あとは同時着手型のゲームでよくお世話になるDUCTも解説がある。この手のゲームの探索部を書いたことのない人にとっては非常に良い入門書だと思う。

秋葉さんも絶賛。

2/18発売の書籍「ゲームで学ぶ探索アルゴリズム実践入門」を頂き拝読しました。これはメチャお勧め！

図やコードも多く初心者でもサクサク読めます。一方で、世界的コンテストで確固たる実績がある著者だけあって、強ぇAIプログラムを作るための今どきな実用的技術が厳選されていて、素晴らしい密度！ pic.twitter.com/68WaZYU3La

— Takuya Akiba (@iwiwi) February 13, 2023

個人的に気になったところを一つだけ挙げておく。

「AlphaBeta法は、MiniMax法に工夫を加えることで、MiniMax法と同じ性能を持ちながら計算時間を減らすことのできる手法」(P.113)とあるのだが、計算時間が減っているなら同じ性能とは言わない。ここの「性能」という言葉の用法がおかしい。ここは、「同じ性能を持ちながら」ではなく、「同じ探索結果でありながら」と書くべき。

ただし、「同じ探索結果」であることはそんなに重要ではないと思う。

なぜなら、普通は、AlphaBeta探索で書いたあと、(現実的なゲームAIのプログラミングでは)各種枝刈りを導入するので、実際の運用において「MiniMaxと同等の探索結果をもたらす」とはなかなか言い難いし、それゆえ、このような説明はどこか嘘くさい。

正確に書くなら「naiveな(alpha-beta以外の各種枝刈りがなく)AlphaBeta探索の実装なら、MiniMaxと同じ探索結果になる(ただし普通はそのような実装のまま放置はしない)」とすべきだ。

あと、AlphaBeta探索は、各種枝刈りを導入してこそ価値があるので、各種枝刈りもついでに説明してほしかったな…。まあ、しかし入門書なら、これくらいの匙加減でいいのかもしれない。

なんにせよ、最近競技プログラミングでもマラソンマッチと呼ばれる長期間に亘って開催されるコンテストがわりと目立つようになってきたが、そういう時にも大活躍しそうな本書、わりとお勧めできる。