当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題のある表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

The Maze【Turing Complete編】

The Mazeステージ

The Mazeステージは、Programmingセクションの最終ステージです。

当ステージのゴールは、ロボットを迷路から脱出させることです。

CPUから数値を出力することで、ロボットを制御できます。どの数値でどういった制御ができるのかについては、Spacial Invasionステージで解説しました。

これまで学習した内容を復習する形で、迷路脱出アルゴリズムを実装します。

迷路の仕様

・迷路は固定。ランダムに生成されない。

⇒(条件分岐を使わない)ごり押しのプログラムで解ける。ただし、別の迷路になると解けなくなる。

⇒テストでは8つの迷路を解くことになる。1つ目の迷路が終わると、2つ目の迷路が現れる。

⇒あらゆる迷路にも対応したプログラムを作る必要がある。

・すべての経路を探索するわけではない。

・最短の経路を見つけるわけではない。

・ロボットのスタート位置は右下。ゴールは左上のドア。

・迷路のゲームにはコインが存在するが、今ステージではコインを取る必要はない。

※すべてのコインを拾うという条件はない。

・コインの先にゴールはないので、一種の障害物を認識しても支障はない。

・Spacial Invasionステージで登場したロボットと同じなので、レーザーを撃てる。今ステージでは不要。

・ドアは空いていない。ドアに重なることはできない。レーザーをドアを破壊できない。ドアに向かってaction(物体調査)をすればOK。

・ドアの物体コード3、壁は1、コインは8である。

左手法で迷路を攻略する

迷路を脱出するための必勝法として、左手法(左手の法則)があります[1]https://ja.wikipedia.org/wiki/%E8%BF%B7%E8%B7%AF

左手法とは、左手伝いに進めば出口にたどり着くという手法です。

左手を迷路の壁に当てながら、道に沿ってずっと進んでいきます。途中で壁にぶつかったとしても、左手を当てながら戻っていきます。

ただし、次のような特殊な迷路については、左手法では脱出できないことがあります。

  • 途中に落とし穴など進んではいけない場所がある迷路
  • ゴールが迷路の中のに存在する迷路[2]大半のマイクロマウス競技では中央にゴールのある迷路が採用されます。

左手ではなく、右手を使っても脱出できます。これを右手法といいます。

左手法の具体的な実装方針

素朴に実装するには、二方向を調べられる必要がある

左手法を素朴に実装するには、左隣(左手が触れる方向)と前方(目の方向)の状況を把握する必要があります。

ケース取るべきアクション
「左壁あり」かつ「前壁あり」右回転
「左壁あり」かつ「前壁がなし」前進
左壁なし左折(左回転して前進)

今回のロボットは前方しか調べられませんので、左隣を識別するにはそちらの方向を向く必要があります。

三方向を同時に調べらられれば、より効率的な動きができる

ロボットマウスのように前・左・右の方向にセンサーを取り付けられれば、一度に三方向を調べられます。つまり、次のように4パターンに分類でき、素早くアクションを取れます。

※Uターンができる分、効率的です。

ケース取るべきアクション
左壁なし左折(左回転して前進)
「左壁あり」かつ「前壁なし」前進
「左壁あり」かつ「前壁あり」かつ「右壁なし」右折(右回転して前進)
「左壁あり」かつ「前壁あり」かつ「右壁あり」Uターン

※前進した直後は、後ろに壁がありません。そうでなければその場所に移動不可能だからです。

The Mazeステージを解く

1:ロボットの動作に対応する数値を定数化する

プログラムの冒頭で、ロボットの動作に対応する数値を定数化しておきます。

const LEFT 0
const FORWARD 1
const RIGHT 2
const ENJOY 3
const ACTION 4
const SHOOT 5

2:ゼロであるとき、ゼロでないときにジャンプする命令を定義する

ゼロであるときにジャンプする命令を"JZE"、ゼロでないときにジャンプする命令を"JNZ"という名前で定義します。

※今回のプログラムではJZEを使いますが、JNZを使いません。

3:プログラムの実装内容を検討する

左手法を実装するのに、ヒントが役立ちます。

この方法であれば左と前方を同時にチェックできなくても、左手法を再現できています。

処理番号処理内容
前方をチェックする。
(a) 障害物なら、右を向く。①に戻る。
(b) 障害物でなければ、前進して、左を向く。①に戻る。

上記の障害物の判定処理で留意することがあります。

障害物の有無だけをチェックすると、せっかくゴールのドア手前に来ても、ドアを障害物と認識してしまいます。そこで、単純にゼロかどうかではなく、壁(物体コード1)かどうかの条件が必要になります[3]ドア(物体コード3)かどうかの条件を組み込むアプローチでもうまくいきますが、壁の有無をチェックするのが自然です。

処理番号処理内容
前方をチェックする。
(a) なら、右を向く。①に戻る。
(b) でなければ、前進して、左を向く。①に戻る。

「前方の物体コード」から1(壁の物体コード)を引いて、それが0かどうかを判定条件にします。

そのために、1を引く命令を定義します。命令名は"sub"としました。

4:プログラムを実装する

次のプログラムが完成しました。

const LEFT 0
const FORWARD 1
const RIGHT 2
const ENJOY 3
const ACTION 4
const SHOOT 5

const OBJ_WALL 1 # 壁の物体コード

label main_loop
####################################
# 前方チェック.                     #
# 前方に壁があればジャンプ.           #
####################################
ACTION
execute
IN # REG0←前方の物体コード.
reg0_to_reg1
OBJ_WALL # REG0←1(壁の物体コード).
reg0_to_reg2
sub # 計算結果はREG3へ.
wall_case # ジャンプ先を設定.
JZE # REG3に対して条件チェック.
#### 前方チェックここまで.

# 壁がないので、前進して左を向く.
FORWARD
execute
LEFT
execute
main_loop
JMP

# 壁ありなら右を向く.
label wall_case
RIGHT
execute
main_loop
JMP

5:テストする

最初の目標は1つ目の迷路を脱出することです。

※コインを拾いながら進みます。

2つ目の迷路をうまく脱出できたら、あとは放置しておきましょう。8つの迷路を脱出するまでにある程度の時間が掛かります。

※待つのが嫌な場合は、[Run faster]ボタンを左クリックしてください。指定の周波数で動作するので、高速・低速を自由に調整できます。デフォルトでは高速に動作します。右クリックすれば、周波数を変更できます。

すべての迷路を脱出することでクリアとなります。

References

References
1 https://ja.wikipedia.org/wiki/%E8%BF%B7%E8%B7%AF
2 大半のマイクロマウス競技では中央にゴールのある迷路が採用されます。
3 ドア(物体コード3)かどうかの条件を組み込むアプローチでもうまくいきますが、壁の有無をチェックするのが自然です。