Spacial Invasion【Turing Complete編】

2023年9月12日

Spacial Invasionステージ

「貨物船に宇宙ネズミが住み着いている。君のコンピューターを我々の先進的なロボットに接続し、レーザーで宇宙ネズミを撃つようにプログラムしたい。レーザーが発射できるのは、他のレーザー光線が飛んでいないときだけであることに注意して欲しい」という要請です。

Spacial Invasion（宇宙戦争）ステージは、ロボットを制御して宇宙ネズミにレーザーを発射するプログラムを組むことです。

ロボットのマニュアル

ロボットを扱ううえでマニュアルが提供されています。これを参考にしてプログラムを組むことになります。

※アセンブリーエディターのLevel Screen下の"Robot controls"からも、マニュアルを開けます。

アセンブリーエディターを開くと、Level Screenがスペースインベーダー風のゲームになっています。

宇宙ネズミの集まりが左右に移動するので、レーザーを使って退治していきます。

※labelやconstの使い方がサンプルとして表示されています。今回はconstを使って定数を定義してみます。

ロボットを制御するには、CPUからバイトデータを出力します。

バイトデータでロボットの動きが制御するわけです、どのデータがどういった動きに対応するかは、次の通りです。

※ロボットのマニュアルに記載があります。

例えば、CPUが5を出力すれば、ロボットはレーザーを撃ちます。

このゲームの特徴を以下の列挙します。

・宇宙ネズミは規則的な動きをしているので、一度プログラムが完成すれば十分である。

・宇宙ネズミは16匹（＝4×4）いて、全滅させればクリア。

・ロボットは前後左右に動ける。ただし、カニ歩きはできず、移動方向を向いたうえで前進することになる。「向く」という行為で1ターン、「進む」という行為で1ターン消費する。

・逆方向を向くためには、2回向きを変える必要がある。「右を向く」⇒「右を向く」（あるいは「左を向く」⇒「左を向く」）とする。

・レーザーは連射不可。レーザー光が画面上に存在すれば、追加のレーザー光を発射できない。

・箱を押して前進できる。ただし、箱を残り超えることはできない。レーザーで破壊すればその上を通過できる。

・宇宙ネズミは左右どちらかに移動し続け、壁にぶつかると一段下がって、逆方向に移動する。スペースインベーダーを想像するとわかりやすいだろう。

・宇宙ネズミが下の箱に到達するか（荷物が奪われる）、ロボットに接触するか（ロボットが破壊される）とゲームオーバー。

ただし、箱を中央方向に押し、その箱に宇宙ネズミが触れてもゲームオーバーにはならず、宇宙ネズミは貫通する。

実際にゲームをテストプレイすると、仕様をすぐに把握できるはずです。

テストプレイするには、アセンブリエディターを開いた状態（あるいはキャンバス上のLevel Screenを開いた状態）でキーを入力します。

矢印キーで向きを変えたり、前進できたりします。[Enter]キーで待機し、[Tab]キーでレーザーを撃ちます。ゲームオーバーになった場合、[Enter]キーで再スタートできます。

※[Space]キーを押すと、キャンバスに戻ってLevel Screenが回転してしまうので、注意してください。

Spacial Invationステージを解く

1：アセンブリエディターから古い命令の定義を削除する

add以外の命令をすべて削除します。

2：ロボット制御のための数値を定数化する

「+」を押して、新しいプログラムファイル（ここでは"new_program"）を準備します。

constを使って、ロボットの制御用のバイトデータを定数化しておきます。

3：ロボットに指示を出すexecute命令を定義する

ロボットを指示を出すためにはCPUからアウトプットに出力する必要があります。

ここでは、REG 0から出力する命令を"execute"という名前で定義します。

※過去の命令でいえばreg0_to_outやOUTがexecuteそのものになります。

事前にREG 0にロボットの制御用データ（0～5）を保持したうえで、execute命令を実行すれば、ロボットは指示通りに動くというわけです。

4：ロボットの操作をテストする

定数のみを書くと、Immediateモードで即値として扱われREG 0に保存されます。

「定数」「execute」という2行をセットで使えば、ロボットは定数に対応する行動を取ることになります。

壁を迂回するコードを入力してみます。

[Next]ボタンや[Run]ボタンを押して、ロボットの動作を確認します。executeを実行するタイミングでロボットが行動しています。

5：試行錯誤してコードを完成させる

宇宙ネズミの動きは決まっていますので、ごり押しのアプローチですべてを退治できるはずです。

何度も試行錯誤して次のコードを完成させました。

※これは悪いコードの例になります。無理矢理クリアするコードを書いたら、行数がとても多くなってしまいました。

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

RIGHT
execute
FORWARD
execute
FORWARD
execute
LEFT
execute
FORWARD
execute
FORWARD
execute
FORWARD
execute
FORWARD
execute
SHOOT
execute
FORWARD
execute
RIGHT
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
# 赤い宇宙ネズミ4匹退治完了.

LEFT
execute
SHOOT
execute
LEFT
execute
SHOOT
execute
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
# 緑の宇宙ネズミ4匹退治完了.

RIGHT
execute
ENJOY
execute
SHOOT
execute
SHOOT
execute
RIGHT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
# 青い宇宙ネズミ4匹退治完了.

LEFT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
ENJOY
execute
LEFT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
SHOOT
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
ENJOY
execute
# 黄色い宇宙ネズミ4匹退治完了.

4：テストする

[Run]ボタンを押します。ロボットがすべての宇宙ネズミを倒すと、このステージをクリアできます。

Conditionモードを利用する【別解】

先に示したコードは戦術などなく、汎用性もまったくないものでした。もう少しエレガントなコードを考えてみましょう。

ロボットはaction（数値は4に対応）という行動で、目の前の物体を検知できます。物体がなければ0が入力として得られ、それ以外なら0以外が得られます。

※具体的にいえば、箱だと40、宇宙ネズミだと33、壁だと1になります。

我々のCPUにはCondtionモードが用意されており、0か否かを識別できます。Conditionモードでは、REG 3の内容が条件式を満たすかどうかを判定し、満たせばREG 0の番地に処理がジャンプします。

Turing Complete【Turing Complete編】

Turing Completeステージ Turing CompleteステージはCPU ARCHITECTUREセクションの最終ステージであり ...

 https://akademeia.info/?p=30019

よって、物体に対応する値を入力として受け取ったら、REG 3に格納します。ジャンプ先をREG 0にセットしたうえで、その都度Conditionモードで判定すればよさそうです。

ジャンプ先については、labelから取得できます。labelの位置に相当する番地は、そのラベル名を記述すれば即値としてREG 0にセットされて好都合です。

1：宇宙ネズミを全滅させるための戦略を考える

シンプルな戦略の一例として次が挙げられます。

①目の前の箱をレーザーで破壊する。

②一歩前進する。

③目の前の物体を検知し続けて、何もない（入力が0）なら待機し続ける（ループ処理）。

0以外ならレーザーを発射する。これを4回繰り返す。

※このロボットの動きだと、0以外になるのは宇宙ネズミが目の前を横切るときしかありえません。

※4匹連続で横切るため、4回レーザーを連射します。発射した途端宇宙ネズミに当たって、レーザー光は消えるので連射できます。

この戦略が優れているのは、宇宙ネズミが目の前を通り過ぎるタイミングを狙っていることです。これによりロボットの向きを変える必要がありません。その分だけコードが短くなるし、挙動がわかりやすいといえます。

さらに、移動距離も最小限で、宇宙ネズミが目の前に来るまで待ち続けるためループ処理に入ります。それだけコードが短くなります。

目の前にいるときにレーザーを撃つことで、すぐに敵に当たります。結果的にレーザーを連打できるのです。

試しにこの戦術を採用して、テストプレイしてみてください。うまくいくはずです。

2：非ゼロの判定に使用する命令群を定義する

execute命令は出力用の命令に相当します。REG 0の内容を出力しているからです。

逆に入力用の命令を定義しておきます。10 110 000bというInstructionビット列に対して"IN"と命名します。これはCopyモードで、Input端子からきたバイトデータをREG 0に記憶する命令です。

Conditionモードの処理ではREG 3を対象に判定します。そのため、REG0の内容をREG3にコピーする処理が必要です。

REG 3の内容がゼロなら（REG 0の内容を番地として）ジャンプするJZE命令（Jump Zero Equal）を定義します。

常にジャンプするJMP命令も追加します。これはレーザーを発射した後に、同じ処理を繰り返すために用います。

3：コーディングする

コードの設計はできているので、実際にコーディングします。

ポイントは次に列挙します。

・定義した命令を組み合わせる。

・labelを活用して、Conditionモードでのジャンプ先を指定する。

実際のコードを見ればlabelの使い方がなんとなくわかるはずです。

※従来のアセンブリー言語とちょっと異なるので戸惑うかもしれませんが、慣れだと思います。コツは複数の命令でモードにおける1つの処理を実現しているということです。

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

SHOOT
execute
FORWARD
execute
# 待機場所に到達.

# 宇宙ネズミを探す.
label SEARCH_FOR_LATS
ACTION
execute
IN
reg0_to_reg3
SEARCH_FOR_LATS
JZE
# 4匹連続でくるので4連打する.
SHOOT
execute
SHOOT
execute
SHOOT
execute
SHOOT
execute
SEARCH_FOR_LATS
JMP

4：テストする

すべての宇宙ネズミを全滅できました。