足跡を辿ろう

リミットサイクル

コード 13.1 はコード 12.6 の再掲です (話の都合上 12.6 で割愛した AvoidMode の宣言と、Init() 関数も書いています)。 障害物に当たったらとにかく右に旋回して左回りをしようとします。

次の軌跡はマップ a25x70_level11.txt で動かしてみた時の様子です。

相手のスタート位置にはたどりつけていますが、 そこから自分のスタート位置に戻れなくなっています。 なぜこういうことが起きたのでしょうか。 少し順を追って考えてみましょう。

まずは帰る途中です。 現在の目標 (自分のスタート位置) が前方にあるので前進します。

もう一回前進すると目標が前でなくなりました。 ルールに基づき右旋回します。

右旋回して前進すると前に障害物が出てきます。

もう一度右旋回して、一歩進むとまた前に障害物が出てきます。 このロボットの位置姿勢はとても大事です。 そこでこれを状態 S1 と呼びましょう。

状態 S1 は前に障害物があったので右旋回します (S2)。 前方は開け、かつ目標は前にあるので前進できます。

一歩進みました (S3)。 この状態 S3 でも目標は前なのでさらに一つ前進できます。

さらに一歩進みました (S4)。 目標が後ろになってしまいました。 右旋回せざるを得ません。

右旋回して (S5)、

さらに右旋回して (S6)、

さらに右旋回して初めて目標は前方に現れます (S7)。

一歩進んでもまだ目標は前方にあるのでさらに前進できます (S8)。

しかしさらに一つ前進した先は前方が障害物です。 目標が後方にあると言ってもいいです (S9)。 いずれにせよこういった場合は右旋回するというルールですから ロボットは右旋回します。

右旋回しても、まだ前方に障害物があります (S10)。 さらに右旋回せざるを得ません。

さらに右旋回しても、まだ前方に障害物があります (S11)。 仕方が無いのでもう一度右旋回するのですが、 よくみると今の状態は S1 と同じです。 ということは、この後 S2〜S15 を延々と繰り返すことになります。 このように同じ状態を繰り返してしまうことをリミットサイクルと呼びます。 一度リミットサイクルに入ってしまうと、 外的要因 (相手ロボットの介在) が無ければ抜け出すことが出来ません。

来た道を辿る方法

マップ a25x70_level11.txt でリミットサイクルに陥ったのは帰路です。 ちゃんと相手のスタート位置までたどり着けたのにそこから戻ることができませんでした。 童話「ヘンゼルとグレーテル」では、グレーテルは白い石を目印にして帰り道を確保しました。 当シミュレータでは周辺情報を知る配列 gSurTiles[] と FOOTPRINT との AND を取ると、自分が何ターン目にそのタイルを通ったか取得できます。 これをグレーテルの白い石のように活用すれば、 自分のスタート位置まで戻ることができるはずです。

コード 13.2 はそういうことをするプログラムです。 コード 13.1 に対して追加した部分を黄色くしています。 新しく追加した変数 ReturnTrip は往路か復路か判別するための変数です。 Init() で 0 にした後、Loop() 内でそれを監視し、1 なら復路モードとして ReturnModeStep() を実行します。 この ReturnMode を 1 にする部分は、NormalModeStep() の最後です。 真正面が目標だったら 次のステップで前進 (NaviCmd(1,0)) してゴールに到達するはずなので、 復路モードに変えているのです。

復路モードの動きは ReturnModeStep() で作っています。 OldestBreadcrumbDir() という関数は 周囲 6 タイルのうち、一番昔に通過した番号を探すものです。 一番昔に通過したということは、それだけ次のゴール (すなわちスタート位置) に 近いはずです。 0 番のタイルなら前進、1, 2, 3 番なら右旋回, 4, 5 番なら左旋回させます。

さて OldestBreadcrumbDir() 関数の中身について説明します。 まず n を 0 にしています。 原則ここで代入する値はなんでもいいのですが、 最悪を想定すると n に何も代入されないまま return n に行きつくので、 その場合はとりあえず前に進ませたいので 0 にしています。 続いて scr を 0x7fff にしています。 この 0x7fff とは 16 進法で 7fff という意味です。 これは 10 進法で 32767 なので scr = 32767 と書いても構いません。 同じ意味です。 この 32767 (0x7fff) という値ですが、 今は「とても大きな数」という認識でかまいません。

次の for 文で i を 0, 1, 2, 3, 4, 5 と変化させてループしています。 6 近傍のうち、どこが一番早い時期に通ったか確認しているのです。 各タイルに対し、過去にそこを通ったターン数を取得して s に入れてます。 通ったことが無いと s は 0 になるので、まず s > 0 で過去に通ったことがあるかどうか確認し、 確認できたらそれが今まで調べたよりも昔に通ったかを s < scr で判定しています。 これによりこの for 文を抜けると、変数 n の中に一番昔に通ったタイル番号が入っています。

リミットサイクルを判定して動きを変える方法

コード 13.2 は一見良い戦略かもしれませんが マップ a25x70_level11.txt に特化しています。 あのマップは復路でリミットサイクルになる地図だったので 復路は来た道を辿るという戦略が上手くいったのです。 往路にあったらどうしようもありません。

往路でもなんとかする方法として リミットサイクルにハマったことを判別し、 今までと違う戦略を取ることで脱出を図るというやり方が考えられます。

リミットサイクルと一口に言ってもパターンは様々です。 今回は前述の 3 マスを往復するパターンを検出してみましょう。 具体的には「6 ターン以内に目の前のタイルを通過した形跡」があるかを調べます。 下の図では 7 ターン目に目の前に 1 ターン目に残した足跡があるので、7-1 で 6 ターンということになります。

ただ、これだけじゃいけません。 目の前のタイルへは、さっきも現在のタイルから来たという確証が必要です。 その確証は、目の前のタイルの 6 近傍のうち、現在のタイルを除く 5 近傍が、さらにその 6 ターン以内に通過してないことで得ることができます。

それでは、コードを見て見ましょう。 現在のターン数は gTurn という変数で得ることができます。 そのため

と書けば目の前のタイルが 6 ターン以内に通過したかどうかわかります (s<=gTurn がなぜ要るかは後で説明します)。 一方、目の前のタイルの 5 近傍は 1, 5, 6, 7, 17 です。 それらが目の前のタイルより 6 ターン以内に通過したかも検討し、そうならばいつもと違う動き −前進して左旋回− をさせてみましょう。

コード 13.1 の中の NormalModeStep() を少し改造し、 そのようにしてみたコードを次に示します (なお GetMyFootprint() は、コード 13.2 より借用してます)。

無事、リミットサイクルを抜けてゴールにたどり着くようになりました。

足跡の上書き

実はコード 13.2 は相手ロボットが存在すると上手く動作しない場合があります。 コード 13.3 も、相手の出方次第では上手く動きません。 これは先ほど後で説明するといった s<=gTurn に絡んでいます。 足跡の機能は、実際の足跡、もしくはアリのフェロモンみたいなものを想定しています。 相手が通過すると、「相手が過去通ったことがある」という情報で上書きされます。 相手が通過したターン数は特定できません。

相手が通ったという情報は「32767 ターン目に通った」という形で記録されます。 通常 2000 ターン程動かしても勝負がつかない場合にはゲーム終了となりますので、 32767 ターンというのは非常に大きい値です。 s<=gTurn において、s は目の前のタイルを通過したターン数が入ってます。 それが現ターンより小さいことは、相手が通過した以外ありえません。 この条件式は、「相手が通過した」という情報を無視するために入れたのです。

コード 13.3 では 1, 5, 6, 7, 17 番目のタイルを通過したターンが、 目の前のタイル (0 番目のタイル) よりも 6 以上小さくなければリミットサイクルと 判定しません。 相手がそれらのタイルを通過した場合、「6 ターン未満」という条件が満たされず、リミットサイクルに陥ったと判定されず、延々と同じ動きをして続けてしまいます。 これを防ぐには、32767 かどうか、もしくは現ターンよりも大きいかを判定し、 その場合には情報を無視するなどの条件式を加えればいいでしょう。