Dancing Machine【Turing Complete編】

2023年9月12日

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ステージで解説済みです。

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

2：テストする

テストが実行すると、ダンスホールにてカラフルな照明がともり、音が鳴るたびにロボットが動きます。

下に疑似乱数の計算過程が表示されるので、エラーが発生したらデバッグに活用にしてください。

[Run faster]ボタンを押して高速処理すれば、ロボットが音楽に合わせてテンポよくダンスする様子をはっきりととらえられます。

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