ハイパーロボットの解法のアプリ上での実装についてのメモ2

 前の投稿の続きです。

直進パズルオンラインのシングルプレイに答えを表示させる機能を付けました。

【簡単なアルゴリズム説明】

【実装中で苦労したこと】

【他のアプリとの違い】

を残しておきます。

【簡単なアルゴリズム説明】

１．準備

まず、壁の配位、コマの配位を管理する変数(配列を)用意する。壁の配位は一回ステージが決まれば不変ですが、コマの配位は1手動かしたら変わるので、別の変数(配列)に用意しておきます。また、あるコマをある方向に一手動かし、動かした先のコマの配位を保存できるようなプログラムも作っておきます。

２．一筆書きでゴールできるか判定するプログラムを作る

ゴール対象コマを動かして、一筆書きでゴールまで到達できるかを判定するプログラムをまず作ります。ゴールの位置が決まればゴール対象コマも決まり、コマたちの初期位置C[手数=0]から考えて、ゴール対象コマが動ける方向を元に、1手動かして実現できる配位C[手数=1]が決まります。C[n]から動ける方向をそれぞれに対して探し、C[n+1]を作っていくと、(あれば)ゴールできる手順が見つかります。これだけでも体感で1/2くらいの確率でゴールできる手順が見つかります。もちろんこれが最短とは限りません。実現される配位C[n]の大きさはそこまで大きくなく、C[n]からC[n+1]は最大でも3倍にしかならないからです。というのも、まず動ける方向が原理的に4方向が最大で、壁の方向には動けない＆来た方向には戻らない、という制限があるので、C[n+1]はC[n]の2,3倍程度の大きさしかありません。例えば2手ずつ増えるとして、10手先まで計算しようとすると、2の10乗=1024程度の計算量になりますが、これはそこまで大きくなく、この一筆書きプログラムは何回も呼んでもそこまで時間はかかりません。

３．総当たりでゴールできるプログラムを作る

ゴール対象コマでやった方法を、全てのコマに対して行います。初期位置C[手数=0]から、1手動かして実現される配位C[手数=1]を作り、全て保存します。C[n]からC[n+1]を作る時も同じ方法で、おおよそ10倍くらい配位の数が増えていきます。というのも、例えば5コマある場合、1コマあたり2,3方向しか動けず、以前実現した配位はC[n+1]に入れないので、おおよそ10倍程度になります。なので、例えば10手分の配位を計算しようとすると、10の10乗となり、計算量が爆発します。なので、1手進める毎に２．の一筆書きプログラムを走らせて、ゴールできるならその手順を答えとして保存する、というアルゴリズムにしました。よくある手順としては、総当たりパートでゴール対象コマ以外のコマも含めて4手動かし、そこからはゴール対象コマを10手動かして計14手の手順、みたいな答えが見つかることが多い印象です。PCで計算してみると、総当たりパートの手順は最大でも5手くらいを用意して、一筆書きパートは最大でも15手くらいで用意しておくと、ほぼ確実に答えが見つかります。(私の観測範囲では見つからないことはなかった)ただし、unity editor上、スマホ上では総当たりパートは最大3手、一筆書きパートは最大13手くらいが現実的に待てる計算時間だと判断しました。

＜補足＞

アプリでは、答えが見つかった瞬間、総当たりプログラムを止める方針にしました。ここで見つかった答え、つまりゴールできる手順は最短手順とは限りません。というのも、総当たりパートが長くても一筆書きパートが短くて、トータルで最短手順になるような場合もあるからです。本当は総当たりパートの最大手順数は多めにとっておきたいですが、そこはスマホアプリで実装する場合は諦める必要がありました。

【実装中で苦労したこと】

１．python からC#に書き換える作業が大変だった

元々私はpythonでのcodingが得意というか楽だったので、上記プログラムを書いてみました。それはそれで後で応用できそうなので良いのですが、これをC#に書き換える作業に結構時間がかかりました。実際、前の記事で異常に時間がかかっていたように感じていたのは、書き換え作業にバグがあったからだとわかりました。だからと言って最初からC#で書いておくべきだったのか、というとそれも違うので、経験として受け入れました。

２．リワード広告の実装が意外と大変だった

バナー広告は常に表示していれば良いので楽だったのですが、リワード広告は出すタイミングなどを気にする必要があるのでちょっと苦労しました。editor上ではうまくいっても実機上ではうまくいかない、というケースがあったので、一つ一つデバッグしながらの作業でした。いちいち実機上でのテストの旅にビルドする必要があって少々時間がかかりました。

【他のアプリとの違い】

google playには、ハイパーロボット(ricochet robot)の答えを与えてくれるアプリRicochet Robot Solverは、かなり早く答えを出してくれる印象です。このアプリでは壁の位置、コマの位置も変更して色んな状況に対応できるのですが、結構入力が面倒なので、ちゃんとした比較はやっていませんが、私のアプリではこのアプリより答えを出すのに時間がかかってしまっているように見えます。今やバグは無いので、アルゴリズムに差があるとしか思えません。どうやっているんでしょうね。総当たりは一番安易な方法なので、もっとパズル的な解き方のアルゴリズムが採用されているのかもしれません。私も最初はそちらで考えましたが、ハイパーロボット自体の非可換性が問題を難しくしており、私には解けませんでした！

というわけで、念願のハイパーロボットの一般化されたパズルゲームを一定のレベルまでクォリティを上げることができました。大変うれしいです。リアルの仕事が忙しくなってきましたが、このプログラムを応用した新作パズルゲームを作りたいと考えています。