Robot Racing【Turing Complete編】

2023年9月12日2023年10月19日

1 はじめに
2 Robot Racingステージ
3 Fastbotの制御
4 テスト操縦してみよう
5 Robot Racingステージを解く

はじめに

いつもブログをご覧いただきありがとうございます。

コーストFIRE中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

Robot Racingステージ

Robot Racingステージのゴールは、ロボットレースに勝利することです。

ロボットレースは宇宙船で人気のスポーツです。さまざまにプログラミングされたロボットが障害物コースを完走します。コースを完走したロボットの中で、プログラムがもっとも小さいロボットが勝者となります。

よって、ロボットをトラック内で移動させる、できるだけ小さいプログラムを作らなければなりません。

Fastbotの制御

我々はFastbotというロボットを操作して、ゴールを目指します。

Fastbotは赤くて派手なランニングシューズを履いています。

制御するための値	動作
0	右に行く。
1	下に行く。
2	左に行く。
3	上に行く。

テスト操縦してみよう

アセンブリーエディターを開きます。

右上にLevel Screenがあり、ロボットレースの様子が映し出されています。

左下からスタート地点、右下がゴールです。

手動でFastbotを操作して、ゴールを目指してみてください。矢印キーで操作できます。

手動で操作してゴールに到達しても何も起きませんが、プログラムでゴールに到達するとクリアになると想像できます。

※過去に制御したロボットは目の前の物体を識別できましたが、今回のFastbotにはそういった機能について言及がされていないので、備わっていなさそうです。

Robot Racingステージを解く

1：プログラムからFastbotを動かしてみる

これ以上Fastbotについて仕様が明らかになっていません。実際に短いテストプログラムを書いてみます。

アセンブリエディターを開きます。4つの制御値（0～4）をconstで定数化しておきます。この制御値を出力すれば、おそらくFastbotは動き出すでしょう。

マップ上の左下からスタートしています。次は上に1マス移動できます。

そこで、次のプログラムを入力し、[Run]ボタンを押して実行してください。定数を出力させるために、ADDiiを代用しています。ADDiiであれば即値同士を足し合わせられます。今回は制御値と0を加算して、その計算結果を出力端子から出力させました。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

ADDii UP 0 OUTPUT

Fastbotが1個上に移動しました！期待通りの動きです。

続けて「右⇒下⇒右」と動かしてみます。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT

どうやら1マスずつ動くようです。

続けて、Fastbotの右側が空いてい、進めるはずです。一度右に進んだら、こちらが「右に移動せよ」と命令しなくても、1tickごとに自動で右に進む可能性があります。それをプログラムで確かめてみます。

そのためには、内部的に1tick進むような処理を追加すればよいだけです。レジスターのゼロクリア処理で代用します。

※従来のアセンブリー言語でいうとNOP命令のようなものです。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
XOR REG1 REG1 REG1
XOR REG1 REG1 REG1
XOR REG1 REG1 REG1

残念ながらFastbotはその場から移動していません。つまり、明確にこちらが命令しない限り、向いた方向に自動で動いたりはしないということです。よって、1マスずつ命令しなければならないわけです。

ところで、プログラムを実行させたまま放置すると、最初の行から処理がまた実行されます。これはProgramコンポーネントにマシン語が記述されており、プログラムカウンターで順に実行しています。何も記述がないところは00hを実行しており、最後のアドレスの処理が終われば、プログラムカウンターは00hに戻ります。つまり、プログラム全体を無限ループするわけです。

シミュレーターのメイン画面で[Run]ボタンから実行すると、Programコンポーネントのどこのアドレスを読み込んでいるのかがわかります。ずっと見ていると、機械語が入力されていない部分も読み込んでいることがわかります。そのまま見ていると、最後のアドレスに到達した後に、最初のアドレスに戻っています。

2：プログラムの設計方針を考察する

Fastbotの操作する方法はわかりました。次にプログラムの設計方針について考える段階にきました。

しかし、Fastbotは目の前の物体の認識機能がないようです。もしその機能を備えていれば、The Mazeステージのように迷路と見なして、右手法でゴールに到達できるはずです。

ところで、Level Screenの下を見ると"Test: 1/1″となっています。つまり、テストパターンは1つしかないということです。表示されているこのマップでゴールに到達すればよいだけです。

要するに、移動ルートを全部指定するような強引なプログラムでも本ステージをクリアできるということです。ここでは、強引なプログラムでクリアを目指してみます。その後でもう少し効率的なプログラムを紹介します。

3：プログラムを実装する

プログラムに数行を記述しては、Fastbotの挙動を確認します。それを地道に続けて、ゴールを目指しましょう。

完成したプログラムは次の通りです。

マップ全体を左下、左上、右下、右上の4等分にして、それぞれにコメントを入れました。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

# 左下.
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT # 4等分マップ間移動.

# 左上.
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT # 4等分マップ間移動.

# 右上.
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT # 4等分マップ間移動.

# 右下.
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT # ゴール.
#ADDii DOWN 0 OUTPUT # ゴールから出る.実際には不要.

4：テストする

テストにパスすると、ステージクリアになります。

※ゴールに到達してもクリアダイアログが表示されない場合は、[Run faster]ボタンを押してみてください。

4等分のマップを解く処理をサブルーチン化する【別解】

強引なプログラムでステージクリアできましたが、実はギリギリな状態でした。何がギリギリだったのかというと、Programコンポーネントのメモリー容量です。

プログラムの最終行の右側を見ると248となっています。これはこのコードの先頭アドレスが248dであり、そして直前のコードの最後が247dということです。最後の4バイト命令の分を加えると、全体で251（＝247＋4）バイトということです。

我々のLEGアーキテクチャーでは、Programコンポーネントのメモリー容量が256バイト（0スタートなので最終アドレスは255）でした。本当にギリギリだったことがわかります。

※もしゴールから出るコードが必要だったとすると、さらに4バイトを追加する必要があります。ちょうど256バイトのプログラムになります。

1：規則性を見抜く

用意されたトラックは一見すると迷路に見えます。しかしながら、じっくり見ると複雑ながらも何らかの規則性を持っていると気づくかもしれません。

先ほどは強引な手法でプログラムを実装しましたが、その過程で規則性に気づきことも多いでしょう。

規則性があれば、その処理を共通化できそうです。

我々のLEGアーキテクチャーではサブルーチンの仕組みを組み込み済みですので、サブルーチンで処理を共通化しましょう。

・左上マップと右上マップ･･･同一経路。ただし、最後の動きは調整が必要。

・左下マップと右下マップ･･･線対称、すなわち180度回転すると重なる。右下マップはゴールから移動しなくてよい。

以上より、4等分したマップの始点と終点のルートを共通化し、マップ間の移動については個別に処理させた方がよさそうです。

2：左上マップと右上マップを攻略する

左上マップ（右上マップと同一）を解くコードをSOLVE1というサブルーチンにします。このサブルーチンを使ったプログラムに書き換えると次のようになります。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

# 左下.
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT # 4等分マップ間移動.

# 左上.
CALL SOLVE1 _ _
ADDii RIGHT 0 OUTPUT # 4等分マップ間移動.

# 右上.
CALL SOLVE1 _ _
ADDii DOWN 0 OUTPUT # 4等分マップ間移動.

# 右下.
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT # ゴール.

label SOLVE1
# 左上マップ（右上マップ）を解く.
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
RET _ _ _

※サブルーチンはコードの最後に持ってきます。

次のステップに進む前に、この時点でテストをパスすることを確認します。

3：左下マップと右下マップを攻略する

左下マップを解くコードと右下マップを解くコードの部分を抜粋します。

# 左下.
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT # 4等分マップ間移動.

# 右下.
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT # ゴール.

ちょっとわかりにくいので、定数を止めてあえて10進数値で表記してみます。

# 左下.
ADDii 3 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 1 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 3 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 3 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 3 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 1 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 3 0 OUTPUT

ADDii 3 0 OUTPUT # 4等分マップ間移動.

# 右下.
ADDii 1 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 3 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 1 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 1 0 OUTPUT
ADDii 2 0 OUTPUT
ADDii 1 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 3 0 OUTPUT
ADDii 0 0 OUTPUT
ADDii 1 0 OUTPUT # ゴール.

規則性は見えてきましたか？　2バイト目の数値の変化に注目してください。それ以外は共通です。

次のような対応が見られます。

左下マップ用のコード	右下マップ用のコード
0	2
1	3
2	0
3	1

つまり、左下マップの値に2を足して、4で割った余りが右下マップの値になっています。

右下マップの値＝左下マップの値＋2 mod 4

※余談ですが、90度回転だと+1、180度回転だと+2すればよいことにも気づきます。

左下マップを解く処理をサブルーチン化し、移動方向の違いについてはサブルーチンの呼び出し元がレジスターから指定するようにします（サブルーチンへの引数として使う）。

ただし、除算用のサブルーチンを持ち出すとプログラムサイズが大きくなってしまうので、サブルーチンの呼び出し元が4方向に対応する値を渡すようにしました。

const RIGHT 0
const DOWN 1
const LEFT 2
const UP 3

# 左下.
ADDii 0 0 REG0
ADDii 1 0 REG1
ADDii 2 0 REG2
ADDii 3 0 REG3
CALL SOLVE2 _ _
ADDii 3 0 OUTPUT # 4等分マップ間移動.

# 左上.
CALL SOLVE1 _ _
ADDii RIGHT 0 OUTPUT # 4等分マップ間移動.

# 右上.
CALL SOLVE1 _ _
ADDii DOWN 0 OUTPUT # 4等分マップ間移動.

# 右下.
ADDii 2 0 REG0
ADDii 3 0 REG1
ADDii 0 0 REG2
ADDii 1 0 REG3
CALL SOLVE2 _ _
ADDii 1 0 OUTPUT # ゴール.

label SOLVE1
# 左上マップ（右上マップ）を解く.
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii UP 0 OUTPUT
ADDii RIGHT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii LEFT 0 OUTPUT
ADDii DOWN 0 OUTPUT
ADDii RIGHT 0 OUTPUT
RET _ _ _

label SOLVE2
# REG 0～REG 3で4方向の数を指定する.
ADDi REG3 0 OUTPUT
ADDi REG0 0 OUTPUT
ADDi REG1 0 OUTPUT
ADDi REG0 0 OUTPUT
ADDi REG0 0 OUTPUT
ADDi REG3 0 OUTPUT
ADDi REG2 0 OUTPUT
ADDi REG3 0 OUTPUT
ADDi REG0 0 OUTPUT
ADDi REG3 0 OUTPUT
ADDi REG2 0 OUTPUT
ADDi REG2 0 OUTPUT
ADDi REG1 0 OUTPUT
ADDi REG2 0 OUTPUT
ADDi REG3 0 OUTPUT
RET _ _ _

完成したプログラムは192バイトでした。

再帰処理で移動する【別解2】

数学や物理学の知識があれば、トラックの経路がヒルベルト曲線になっていることに気づいたかもしれません。

ヒルベルト曲線とは、フラクタル図形の1つです。一本の線で全部のブロックを通るようにして、空間を覆い尽くす空間充填曲線の1つです。

次に紹介するサイトで、ヒルベルト曲線を作れます。スライダーの位置は画像を参考にしてください。生成したヒルベルト曲線を180度ひっくり返すと、本ステージのトラックとまったく同じになります。

ヒルベルト曲線

ヒルベルト曲線ヒルベルト曲線サイトマップ｜ホーム｜この目次ヒルベルト曲線は、フラクタル図形の ...

https://tomari.org/main/java/kyokusen/hilbert_curve.html

有名な曲線ということは、それを描くアルゴリズムの情報も見つかるはずと推測できます。

ヒルベルト曲線について速習する

Unknown Title

Unknown ...

https://www.aihara.co.jp/~taiji/lecture-2011/Hilbert_Curve-2...

解答プログラム

方向	10進数値	2進数値
右	0d	00b
下	1d	01b
左	2d	10b
上	3d	11b

再帰を活用したプログラムになります。

const ORDER 3
const DEPTH REG1
const ANGLE REG2

CALL WALK _ _

label WALK
ADDi DEPTH 1 DEPTH
IF_GTi DEPTH ORDER walk_exit
XORi ANGLE 3 ANGLE
CALL WALK _ _
XORi ANGLE 3 ANGLE
XORi ANGLE 3 OUTPUT
CALL WALK _ _
XORi ANGLE 0 OUTPUT
CALL WALK _ _
XORi ANGLE 1 OUTPUT
XORi ANGLE 1 ANGLE
CALL WALK _ _
XORi ANGLE 1 ANGLE
label walk_exit
SUBi DEPTH 1 DEPTH
RET _ _ _

再帰的な処理でコードが短くなっています。
さらに、XORi命令をうまく活用して、Fastbotの方向を変えています。

下記のプログラムを参考にしました。