Dancing Machine【Turing Complete編】
はじめに
いつもブログをご覧いただきありがとうございます。
コーストFIRE中のIPUSIRONです😀
Dancing Machineステージ
クルーたちはダンスフロアでロボットが動く様子が好きだといいます。だからこそ、ロボットにダンスチームを率いたいと思っています。しかし、ロボットにオリジナルのダンスを考えさせるという問題があります。
決定論的なロジックから、どのように創造性のあるダンスを生み出せますか？
その答えは疑似乱数生成器を使うことです。
本ステージ用の疑似乱数生成器
本ステージでは1つだけ入力を与えられます。これを初期シードと呼びます。
初期シードをもとにして、次の疑似乱数生成アルゴリズム（8ビットのxorshift）を経て、疑似乱数を生成します。
なお、「shr 1」は左に1回シフト、「shl 2」は左に2回シフト、「shr 1」は右に1回シフトすることを意味します。
temp1 = seed xor (seed shr 1)
temp2 = temp1 xor (temp1 shl 1)
next_seed = temp2 xor (temp2 shr 2)next_seedを計算したら、next_seed mod 4（next_seedを4で割った余り）を出力します。
次に、next_seed（mod 4しない値）をseedとして、次のnext_seedを計算します。
これを繰り返します。
一連の処理を通じて、次々と疑似乱数を出力していきます。
※初期シードが0になることはありません。
ダンスルームでのロボットの制御
ロボットの制御は従来通りです。
Level screenにダンスルームが映し出されています。我々が制御すべきなのは、中央のロボットになります。
Dancing Machineステージを解く
1：プログラムを実装する
LEGアーキテクチャーの回路には、シフト演算の回路を組み込み済みです。本ステージのテストで、組み込んだ回路をチェックできます。
今回のプログラムのコアとなるのは、疑似乱数生成アルゴリズムです。これは何度も使うのでサブルーチン化します。
REG 0を通じてseedを渡し、計算結果であるnext_seedはREG 1で取得するものとします。
出力値はnext_seed mod 4なので、除算用のサブルーチンを用意します。除算アルゴリズムについてはDivideステージで解説済みです。
https://akademeia.info/?p=31516完成したプログラムは次の通りです。
const SEED REG1
const NEXT_SEED REG2
# 初期シードを受け取る.
ADDi INPUT 0 SEED
label main
CALL generate_random_value _ _
# 疑似乱数（nextseed mod 4）を出力.
ADDi NEXT_SEED 0 REG1 # REG 1←next_seed.
ADDii 4 0 REG2
CALL divide _ _
ADDi REG4 0 OUTPUT
ADDi REG1 0 SEED # seed←next_seed(今はREG 1に入っている).
IF_EQ REG0 REG0 main # 強制ジャンプ.
# メイン処理終了.
# xorshiftで疑似乱数生成.
# REG 1【入力】：シード
# REG 2【出力】：疑似乱数
# REG 0,3,4：計算のために使う（破壊）.
label generate_random_value
SHRi SEED 1 REG0
XOR SEED REG0 REG3 # REG 3=temp1.
SHLi REG3 1 REG0
XOR REG3 REG0 REG4 # REG 4=temp2.
SHRi REG4 2 REG0
XOR REG4 REG0 NEXT_SEED
RET _ _ _
# 除算サブルーチン.
# REG 1【入力】：被除数
# REG 2【入力】：除数
# REG 3【出力】：商
# REG 4【出力】：余り
# REG 0：計算のために使う（破壊）.
label divide
XOR REG0 REG0 REG0
ADDi REG1 0 REG4
ADDi REG2 0 REG3
label loop
IF_LESS REG4 REG3 end
SUB REG4 REG3 REG4
ADDi REG0 1 REG0
IF_EQ REG0 REG0 loop
label end
ADDi REG0 0 REG3
RET _ _ _
2：テストする
テストが実行すると、ダンスホールにてカラフルな照明がともり、音が鳴るたびにロボットが動きます。
下に疑似乱数の計算過程が表示されるので、エラーが発生したらデバッグに活用にしてください。
[Run faster]ボタンを押して高速処理すれば、ロボットが音楽に合わせてテンポよくダンスする様子をはっきりととらえられます。
テストにパスすると、ステージクリアになります。
