探索木によっては、盤面状態の数が大変多くなるので、深さ優先探索は、最大探索深さが前もって定まっているような場合にのみ実用的となる。経路が存在するなら、目標状態への最短経路を見つけることが保証されている。(AI)分野の初期の開拓者の多くの特徴は、いまだ解がわからない問題を解こうとしていることであった。問題を解く一般的方法は、大規模なグラフの探索問題に変換する事であった。探索を構築せよ【どんな本?】コンピュータで問題を解くには、アルゴリズムが欠かせない。いつの時代も、より速く問題を解く需要は尽きない。して単純な解き方だと、問題の規模の二乗に比例する時間がかかる。CPUもバスも速度は上がったが、最近はリアルタイム性の要求も厳しくなった。弾幕ゲームで弾数の二乗の演算時間を費やすわけにはいかない。本書では基本となる全順序集合の整列と探索に始まり、地図などの経路探索や完全情報ゲームの最善手の探索、二次元ゲームの当たり判定などに便利な空間木構造など、現代のプログラミングで必要となるアルゴリズムとデータ構造を紹介する。日本語版は2016年12月22日初版第1刷発行。単行本ソフトカバー横一段組み約415頁。8.5ポイント37字×31行×415頁=約476,005字、400字詰め原稿用紙で約1,191枚。文庫なら厚めの上下巻ぐらいの分量。「任意の点pにおいて」など、数学っぽい表現も容赦なく出てくるので、そこは覚悟しよう。サンプル・プログラムも多数収録している。わかれば、たいがい読めるだろう。各章はゆるく独立しているが、できるだけ頭から読んだ方がいい。「アルゴリズム+データ構造=プログラム」がある。コンパイラを作ってゆく。その過程で、リストやバランス木などのデータ構造や、再起呼び出しなどの手口を身に着ける本だ。辞書)なら、イマドキのプログラミング言語は処理系やライブラリが備えている。いうことで、そういった基礎的な部分は最小限にして、現代のプログラマ、特にリアルタイム性が必要なゲームの製作で求められる、二次元空間の探索などを加えたのが本書だ。サービスで扱うデータ量は桁違いに多い。同時に、使えるメモリ量もキロバイト単位からギガバイト単位に変わった。オンライン業務では、データの追加・変更・削除が頻繁に起こる。なると、探索の効率とデータの追加・削除のコストのバランスも変わってくる。そんなわけで、一応は昔ながらのバッチ処理に向くマージソートも出ているが、むしろハッシュを使ったブルームフィルタ(→Wikipedia)の方が実用的な場面が多いかも。5章までは「処理系のハッシュ使えばいいじゃん」で済む問題が多いが、6章からは「どんなデータ構造で表すか」がキモとなる問題が増えてくる。6章の最初に出てくる問題は、二次元の迷路の探索だ。表せれば、とりあえず問題は解けます...処理時間はともかく。本書では、節と辺からなるグラフとして扱ってる。分岐点と行き止まりを節、直接に行き来できる節同志を辺でつなぐ。これで問題は半分解けたようなもん。単純に深さ優先探索すると、節の数が増えるに従い演算時間が爆発するので、何かと工夫が必要だったり。AIにおける経路探索」は、ちょっと誤解を招くかも。いうのも、ここで言うAIは、今の流行りの強化学習じゃない。三目並べなど完全情報ゲームでの最善手を探るアルゴリズムを示すもの。昔ならLISPやPrologが得意とした問題分野ですね。今はチェスも強化学習になっちゃってるけど。計算幾何学」以降に入ると、二次元ゲームを作る際に突き当たる問題が山盛り。「与えられた点から最も近い点を見つける」「点の集合をすべて含む最小の凸多角形を見つける」「任意の多角形の集合の交差を全部見つける」とか、ありがちですね。この辺になると、放物線の幾何学とかの素養が必要だけど。ええ、私は読み飛ばしました。空間木構造」も、ゲーム屋必須の章。交差クエリとかは、モロに当たり判定だったり。オブジェクトが少ないうちは力任せ、すなわち全オブジェクト同士で交差判定すりゃいいけど、撃ちまくりの弾幕ゲームでそんな事やったらキリがないい=オブジェクト数の二乗で演算時間が増えていく。リアルタイム性が求められるゲームでは、1/60秒未満で処理を終える必要があるし。そこで演算時間を節約するにはどうすれば、という話。ここの基本は、「いかに無駄な判定をせずに済ますか」。考えても当たらない要素同士は、なるたけ計算せずに済ませましょう、ってこと。そのためには、n次元空間上にバラけている点の集合を、単なる配列やリストにするのではなく、k-d木や四分木など、何らかの秩序だったデータ構造にする必要があるのだ。この辺を読んでると、グレッグ・イーガンの描く派手で自由度の高いVR世界も、その末端では忙しくリストから要素を出し入れして最適化してるのかな、とか考えちゃったり。ないと、すぐに演算量が爆発しちゃうから。問題に対し、必要な演算量を見積もり、適したデータ構造とアルゴリズムを選ぶマシンなんて、本当に作れるんだろうか?と、序盤では古典的なネタで肩慣らししつつ、中盤以降は二次元以上の空間を扱い、より現代的な問題にアプローチしてゆく、今世紀に相応しいアルゴリズムとデータ構造の本だった。その分、歯ごたえも充分にあるので、覚悟して挑もう。書評:軍事/外交バックナンバー2020年2月2020年1月2019年12月2019年11月2019年10月2019年9月2019年8月2019年7月2019年6月2019年5月@niftyが提供する無料ブログはココログ!。