レビュー:探索アルゴリズム実践入門

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


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

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

秋葉さんも絶賛。

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

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

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

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

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

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

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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です