nekoTheShadow’s diary

IT業界の片隅でひっそり生きるシステムエンジニアです(´・ω・`)

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

honto.jp

競技プログラミングにはいろいろな形式があって、なかでも人気のあるもののひとつにヒューリスティックコンテストがあります。与えられた入力データに対してそのスコアの高さを競うもので、1週間から数か月という期間に何度もプログラムを改善・提出し続けることからマラソンマッチと呼ばれることがあります。自分は競技プログラミングのひとつであるアルゴリズムコンテスには取り組んでいたものの、このヒューリスティックコンテストについては未経験。アルゴリズムコンテストは入力データに対して正解を求める速さを競うというもので、その性質上、この2つのコンテストで求められる知識には違いがあります。ヒューリスティックコンテスト未経験の身として、そちらのコンテストで使う知識をどこかで触れてみたいと思っていたところ、この本をたまたま発見。すぐ購入して学習に取り組みました。

本書はいくつかのゲームのAIを作成しながら、さまざまな探索アルゴリズムを紹介していくという内容になっています。実際にコードをエディタに打ち込みながら、探索アルゴリズムの中身を見ていくつくりになっており、自分はこの形式が好みのため、本書の個人的評価は高いです。コード以外の説明部分についても、カラフルな図表を多用しており、かなり理解しやすいと感じました。文章についても簡潔でわかりやすいです。先に述べた通り、自分は探索アルゴリズムnoobでしたが、探索アルゴリズムの有名どころをおさえることができたと思います。

ただ、中身がわかりやすいとはいえ、まったくアルゴリズムの知識がないという人には厳しいかもしれません。最低限、AtCoderやyukicoderの簡単な問題が解ける、あるいはその解説を読んで内容が理解できるというレベルは必要かと思われます。また、本書のサンプルコードはC++を利用していますが、こちらについてはC++スペシャリスト以外でも理解できるレベルです。一部C++固有の内容が紹介されますが、分量的にはごくわずか。最低限C言語に似たプログラミング言語の知識があれば、大丈夫そうです。かくいう自分もC++苦手勢、よくわかんない勢のため、学習には慣れたJavaを利用しました。

github.com

分量自体は結構あるので、読み終わるまでに時間はかかってしまいましたが、個人的には今年の上半期で一番学びが多かった1冊でした。アルゴリズムに興味がある人はぜひ。