ポケモンGO攻略にルート最適化（巡回セールスマン問題）は活用できるか

ゲームの世界に効率化を持ち込んでみよう

先日、日本で公開されたポケモンGOは、世間の話題をかっさらっています。流行りものにはのっかっておけ、ということで、（弊社内で）話題のとのルート最適化との相性について考察してみたいと思います。なお、ルート最適化については、「Google Optimization Toolsは最適化問題の救世主になるか」でも触れています。

ルート最適化は、ゲームの何を効率化する？

ルート最適化とは「複数の拠点を、いかに効率的に回るか」という問いに答えることを目的としています。

ポケモンGOの場合、ターゲットになる拠点は「ポケストップ」でしょう。これを、短時間でできるだけ多く回ることが、アイテム収集の面でも、経験値稼ぎの面でも重要な意味を持ちます。

ということで、目指すべき解は「定められた時間内で、どれだけ多くのポケストップを回るか」ということになります。

制約条件もある

しかしながら、ポケストップをタップ＆スワイプで、アイテムを集めて回るだけならそれで良いのですが、残念ながら、ゲームそのものには、もっと複雑な目的（制約条件）があります。

1. ポケモンと遭遇すると、1-2分程度の滞在が発生する
2. ルアーモジュールがかかっていると、ポケモンとの遭遇率が上がる
3. ポケストップは、5分経過すると、再度回すことができる
4. 新しい場所に行かないと、新しいポケモンに出会うことができない

このうち、1は、完全にランダムだと理解すると、どのルートだとしても同じですので、制約条件には含めなくても良いと思います。２は、ルアーモジュールがかかる可能性をランダムであると考えるか、それが多く発生する場所があると考えるかで制約条件が変わりそうです。３・４については、どちらに重きを置くか、という問題が発生します。３を重視するのであれば、ルートにおいて、同じ拠点を複数回訪問することも含めて、一定時間内に訪問ポケストップが最大となるように計算を行うことになります。４を重視するのであれば、一般的な「巡回セールス問題」と近くなります。（つまり、設定された拠点全てを、1回ずつ回る際の最適ルートを計算する、ということです。）

その他にも、自分の陣営（赤、青、黄色）のジムにまわりたい、などの要望もあるでしょう。

ルート最適化の限界

上記を踏まえて、ルート最適化に取り組みたいところですが、ひとつ大きな問題があります。

それは「リアルタイム処理にするかどうか」というところです。技術的な話だけを考えると、リアルタイム処理にすることも可能なのですが、今回の場合は、インプット情報を得る手段が難しいので断念せざるを得ないでしょう。

今回、考慮したい要素と、そのリアルタイムでの変化状況を挙げると

• ポケストップの位置：変化しない
• ルアーモジュールの有無：変化する
• ジムの所属陣営：変化する

ということになります。

最も重要な要素であるポケストップが変化しないので、リアルタイム処理である必要は低いです。（つまり、最低限という観点なら、事前計算で十分）

そして、ルアーモジュールの有無や、ジムの所属陣営は大きく変わるわけですが、反対に「変わったこと」を取得する術がありません。（API公開されているなら話は別ですが、それを取得して、食わせて、再計算するのはかなり困難です。ルアーモジュールは30分で切れますし、ジムは短いと数分単位で入れ替わります）

シンプルな「巡回セールスマン問題」として解くべき

それらを踏まえると、このポケモンGOの巡回ルートは、素直に「巡回セールスマン問題」として解くべきだと言えるでしょう。

インプットとしては「ポケストップの拠点情報」を使います。そして、限られた時間内で、どれだけ沢山のポケストップを回ることができるか、を命題として設定することになります。

但し、一般的な巡回セールスマン問題では、「定められた拠点をいかに効率的に回るか」という問いになりますので、この場合は、「トラックの積載量を定義して」「その荷物を下ろしていく」という問いだと考えたほうが良さそうです。（Vehicle Routing Problem ですね）

これらの前提を踏まえて、Google Optimization Tools を用いて（実際にできる部分だけでも）トライしてみましょう。（続く）