Donut Dodo という、画面内の小さなドーナツを全て集めて最後に大きいドーナツに触れるとステージクリアできるアクションゲームについて、ドーナツの取得する最速の順番をアルゴリズムを用いて計算してみようと思い、やってみました。
もくじ
前提
何を最適化するかによって話が違ってくるので、対象をはっきりとさせておきます。
ここではドーナツの取得順を最適化することを目的としていますが、あるドーナツから別のドーナツを取得する際の所要時間はすでに分かっているものとします。
この前提によって、巡回セールスマン問題（正確には最短ハミルトン路問題）の解法を流用して最適化することができるようになります。
プレイヤーごとに異なる結果になる可能性があります
あるドーナツから別のドーナツを取得する際の所要時間は実際にゲームをプレイして計測します。
そのため、そのデータを使った計算結果はそのプレイヤーにとっての最短時間・最短ルートであり、誰でも同じ結果になるとは限りません。
また、あるドーナツから別のドーナツを取得する際の入力操作の最適化については、ここでは扱いません。
このプログラムはまだ実績がありません
なお、この計算プログラムによってタイムが縮んだという実績はまだありません。
もしご興味あれば最短ルートを計算するのでデータを下さい。
（データを下さいと簡単に言うけど、正直なところ、データ収集はかなりの苦行）
（実績がない理由も、たぶんデータ収集が苦行だから）
おおまかな概要
私はアルゴリズムや競技プログラミングに対する知識を持っておらず、有名どころのアルゴリズムの一部の名前を知っている程度です。
なので、知っているアルゴリズム or 問題の名前で検索して情報を集め、実際の解決方法を決める方針にしました。
巡回セールスマン問題の解法を使用
ドーナツの取得順という問題自体はスタートとゴールが指定された巡回セールスマン問題と考えて、結果的に、ビット DP（ビット全探査＋動的計画法）というアルゴリズムを採用しました。
巡回セールスマン問題は最後にスタート地点に戻ってくるのですが、今回はスタート地点とゴール地点は別です。
この場合は最短ハミルトン路問題という名前があります。
| スタートとゴール | モデル名 | |
|---|---|---|
| 巡回セールスマン問題 | 最後にスタート地点に戻る | 最短ハミルトン順路問題 |
| 今回 | 最後にスタート地点に戻らない | 最短ハミルトン路問題 |
データを工夫してモデルの差異に対応
今回は巡回セールスマン問題の解法をそのまま使えるように、入力データを工夫することにしました。
あえて巡回セールスマン問題の解法をそのまま使っている理由はいくつかあって、
- 有名な問題ということもあってネット上で解法が比較的簡単に見つかるので、プログラミングの参考資料に困らない
- 入力データとその答えがネット上で比較的簡単に見つかるので、そのまま自分のプログラムの動作確認に使える
- 上記の工夫をして巡回セールスマン問題の解法をそのまま使うことで、上２つの恩恵をそのまま受けることができる
なお、入力するデータの工夫は次のような内容です。
初期案
- 実際のゴール地点を計算上のスタート地点として扱う
- 小ドーナツから実際のスタート地点に行く所要時間を無限と見なす
- 実際のゴール地点から実際のスタート地点に行く所要時間を 0 とする
改良案
今回の問題では次のような性質があるため、計算上はスタートとゴールを同じ地点だと見なすことができ、巡回セールスマン問題として扱うことができます。
- スタート地点からは他のドーナツに向かうのみで、逆にスタート地点に向かうことがない
- ゴール地点へは他のドーナツから向かうのみで、逆にゴール地点から向かうことがない
- 任意の２点間で行きと帰りとで所要時間が異なっていても対応できるプログラムである
アルゴリズムについて
今回採用したビット DP（ビット全探査＋動的計画法）というアルゴリズムについて説明します。
アルゴリズムと計算回数
そもそも「アルゴリズム」とは何か。
アルゴリズムは問題を解くための処理の手順のことで、問題の種類によって複数のアルゴリズムが存在します。
アルゴリズムの種類と処理するデータの量によっておおまかな計算回数を見積もることができ、これによっておおまかな計算時間を見積もることができます。
ここでは一般的な PC の計算回数が 1 秒あたり 10^9 回として見積もることにします。
ビット全探査
識別番号 i で識別できる N 個のモノから任意の数だけ取得する場合に、未取得か取得済みかの組み合わせをモレなく全てのパターンを網羅する場合に便利なアルゴリズムです。
2^N（2 の N 乗）を二進数で表した時に、番号 i を未取得なら i 番目のビットが 0 、取得済みなら i 番目のビットが 1 となります。
今回のケースでの計算回数の見積もり
今回のケースでは 15 個あるドーナツそれぞれに対して未取得か取得済みかの組み合わせを全パターン網羅するためにビット全探査を使っています。
15 個のドーナツを取得する順番の組み合わせは 15! ＝ 1,307,674,368,000 ≒ 1.3*10^12実際の計算ではスタートとゴールも追加されるので、 17! ＝ 355,687,428,096,000 ≒ 3.6*10^14 仮にひとつの組み合わせにつき 1 回の計算が必要だとしても、一般的な PC の計算回数は 1 秒あたり 10^9 回と言われているので、10^5 秒≒ 28 時間以上の時間が必要です。
このままでは計算に 1 日以上かかってしまい実用的ではありません。 そこで、もうひとつの配る DP というアルゴリズムと併用して計算回数の削減を行います。
動的計画法（DP）
動的計画法（DP : Dynamic Programming）というアルゴリズムがあり、動的計画法の計算方法として配る DP ともらう DP があります。
今回は配る DP を採用しています。
動的計画法
単純な問題の結果を使って複雑な問題を解く方法で、単純な問題の結果を再利用することで計算回数を減らすこともできます。
いきなりスタートからゴールまでの最短時間を求めるのは難しいです。 そこで、問題を段階的に求めることにします。
今回のケースでの計算例
スタートしてから 1 個目のドーナツを取得する場合の最短時間はすでに分かっている前提なので、答えが出ます。 2 個目のドーナツを取得するまでの最短時間は、1 個目のドーナツを取得するまでの時間+ 2 個目への所要時間で計算できます。 3 個目は、2 個目までの時 + 3 個目への所要時間。 4 個目は、3 個目までの時間 + 4 個目への所要時間。
このようにして「n 個目までの最短時間 + (n+1) 個目への所要時間」を段階的に求めることで、最終的に全てのドーナツを取得してゴールするまでの最短時間を求めることができます。
n 個目までの最短時間は前の段階で計算済みなので、その計算済みの結果を再利用することで効率的に計算を進めることができます。
今回のケースでの計算回数の見積もり
N 個のモノを並べる組み合わせは N! 通りなので、単純に全探索をするだけだと計算回数が 17! ≒ 3.6*10^14 回必要です。一般的な PC だと 1 日で計算が終わりません。
対して、動的計画法を使うと N^2 * 2^N 回の計算回数で済むようになり、今回の場合だと 17^2 * 2^17 ＝ 37,879,808 ≒ 3.8*10^7 回です。
実際にはひとつの組み合わせにつき 1 回の計算で済むとは限らないので、これよりも増える可能性がありますが、それでも 1 秒あたり 10^9 回計算できる PC で計算すると 1 秒以内に計算が終わることが期待できます。
1 日以上かかるハズだった計算が 1 秒以内に終えることができるようになる。これがアルゴリズムの効果です。
配る DP
漸化式のようにして過去→現在→未来の状態を計算する際に、過去の値を使って現在の値を計算する場合をもらう DP と言い、現在の値を使って未来の値を計算する場合を配る DP と言います。
今回の計算で配る DP を採用したのは単純な理由で、参考に見たソースコードが配る DP だったからです。
プログラミング
プログラミングの方針として、
- 既存のソースコードを参考にして、正しく計算できるプログラムを書く
- 既存の入力データを使って、正しく計算できていることを確認する
- 最短ハミルトン路問題を循環セールスマン問題の解法を利用して解く
参考にしたプログラムが最短時間のみを出力するものだったので、そのルートも出力できるように改造しました。
参考資料
2 位以下のルートも出力したい
巡回セールスマン問題にはなくて、今回の問題では無視できない要素なのが、敵の存在です。
出力されたルートを実際に通ろうとすると敵がジャマで通れない、という状況が発生することを回避できないのです。
ではどうするかというと、2 位以下のルートも出力してその中から敵のジャマに合わないものを見つける、という方向で問題を解決を図ることにしました。
最短時間の上位を出力するように改造して、その次に上位のルートも出力するように改造しました。
参考資料
計算の軽量化・計算進捗の可視化
出力する情報を増やすために途中の計算量が増え、当然ながら、計算時間も増えていきました。計算に数秒かかるようになった段階で計算がどれくらい進んだかを可視化する機能を追加しました。
進捗表示そのものも重たい処理なので、計算時間がムダに増大しないように小細工をしています。
参考資料
おまけ
RTA におけるアルゴリズムの利用例
自身の他の利用例
溶鉄のマルフーシャ
実はマルフーシャの検証をやっている時にビット全探査を使って、最適なパラメータ強化の順番を計算したことがあります。
DPS を基準にして、できるだけ早い時点でできるだけ高い DPS になるようなパラメータの強化順を計算したのです。
現時点において未公開のままですが、理由は簡単で、ランダムで出現するパラメータ強化に対して理論値を求めても実践できないからです。
また、敵の HP と与ダメの関係で、DPS が少し上昇しただけでは敵を倒す早さに影響しないため、パラメータ強化の理論値を実践する効果が非常に小さいです。
他の方の利用例
クッキークリッカー
クッキークリッカーで学ぶアルゴリズム入門
動的計画法（DP）により操作手順を最適化しています。
説明を見た感じ、もらう DP で計算していると思われます。
進め！キノピオ隊長
テレビゲームのRTAにおける最適チャート追求の部分的な理論化：「進め！キノピオ隊長」の場合
非巡回有向ネットワークに対するダイクストラ法により、ゲームを進めるために必要最低限のアイテムを収集するルートを最適化しています。
非巡回：スタート地点に戻らない、有向効ネットワーク：状態の変化が一方通行、ダイクストラ法：スタートからゴールへの最短経路を求めるアルゴリズム（巡回セールスマン問題のように全ての点を通らなくて良い）。
さいごに
アルゴリズム関連の web ページには大いにお世話になり、その中には競技プログラミングと関係のあるページも含まれています。 非常に参考になり、とても感謝しています。
私はあくまで趣味プログラマで、競技プログラミングの外にいる人です。
なので、競技プログラミングに関りのある人がプログラムを作ったと見なさないでいただけると助かります。
ちゃんとした知識と経験のあるかたなら、もっと効率の良いプログラムを作れると思っています。
0 件のコメント:
コメントを投稿