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

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

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

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

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

AI Showdown【Turing Complete編】

2023年9月12日

AI Showdownステージ

NAK 02は優秀なAIエンジニアロボットですが、時には悪党になって氾濫を扇動しようとします。今度は管制室を占拠して、船長を人質に取りました。

彼の唯一の弱点はギャンブルです。我々は彼をあなたとのカードゲームに誘い、あなたが勝ったら彼が落ち着くことを約束させました。あなたはギャンブルに勝たなければなりません。あなたが唯一の希望なのです。

ゲームのルール

テーブルには12枚のカードがあり、各プレイヤーは順番に1~3枚のカードを取らなければなりません。

あなたから開始し、最後のカードを取ったプレイヤーが負けになります。

入力から現在のカードの数がわかります。1,2,3を出力すると、その数分だけカードが取ったことになります。

対戦相手のNAK 02は即座に反応します。そのため、出力したら、すぐに入力を読み取り、次の出力をしても構いません。

※ゲームの設定では12枚のカードとしていますが、カードの数だけに注目すればよいので、カードではなく石でも同じ議論になります。

ゲームの必勝法を考える

最初に12枚からスタートしますが、12という数字は小さいので、全パターンを考えてみます。おそらくその過程で規則性や必勝法を見いだせるはずです。

あなたの番のカード数勝敗
1負けあなたが最後の1枚を取るため。
2勝ち1枚取る。
3勝ち2枚取る。
4勝ち3枚取る。
5負け1~3枚取れば、NAK 02は1枚を残すように調整できる。
6勝ち1枚取る。NAK 02の番で5枚。5枚の時点で負け確定。つまりNAK 02の負け。
7勝ち2枚取る。NAK 02の番で5枚。
8勝ち3枚取る。NAK 02の番で5枚。
9負け1~3枚取れば、NAK 02の番で6~8枚になる。6~8枚の時点で勝ち確定。
10勝ち1枚取る。NAK 02の番で9枚。
11勝ち2枚取る。NAK 02の番で9枚。
12勝ち3枚取る。NAK 02の番で9枚。

自分の番で1枚、5枚、9枚、・・・になっていると負け確定とわかりました。逆にいえば、それ以外の枚数なら、適切な枚数を取れば、勝ち確定となります。

※4で割って3余る枚数からスタートすれば先手必負、それ以外の枚数からスタートすれば先手必勝です。

今回のゲームは12枚からスタートし、あなたが先手です。自分の番で12枚ということは、正しい枚数を取っていけば、必ず勝てます。

では、その正しい枚数の決め方を考察しましょう。

上記の考察から、次の規則性でカードを取ればよいことがわかります。

[1]4mの形、すなわち4で割りきれるなら、3枚取る。

[2]4m+3の形、すなわち4で割って3余るなら、2枚取る。

[3]4m+2の形、すなわち4で割って2余るなら、1枚取る。

[4]4m+1の形、すなわち4で割って1余るなら、1枚取る。この場合は本来負け確定だが、相手がミスをすることを願い、もっともカードを残すように1枚だけ取る

LEGアーキテクチャーの拡張

シフト演算を追加する

Shiftステージをクリアして、シフト演算のコンポーネントがアンロック済みです。回路に組み込まれていないので、この時点で組み込んでおきます。演算系の処理になるので、XOR演算の下のスペースに回路を組むことにします。回路自体は単純です。左シフトをxy00 0110b、右シフトをxy00 0111bに割り当てることにします(詳細は後述する命令表を参照)。

シフト演算回路を組み込んだ

過去ステージのテストを実施して、少なくともデグレードしてないことを確認しておきます。

Condition系の命令を即値に対応させる

これまでは、0と比較するためだけに、0を格納したレジストリーを使ってきました。0という即値を扱えた方が便利に違いありません。

即値と判定したらマルチプレクサーで回線を切り替えます。Calculation系の命令と同等の回路を設ければよさそうです。

※スペースが空いていなかったので、既存の回路をちょっとずらしました。

※上から3番目のLess(unsigned)コンポネントの入力は、2番目の入力と逆であることに注意してください。

Condition系の命令を作ったプログラムを即値を使用するように書き換えて、テストが通るかを確認します。

No.アドレス1バイト目2バイト目3バイト目4バイト目処理内容
100h(=0d)0100 0000b(=64d)
※ADDかつImmediateモード
0000 0111b(=7d)
※入力端子
0000 0000b(=0d)
※即値
0000 0001b(=1d)
※REG 1
入力端子からくるバイトデータをREG 1に保存する。
※ADD命令で代用している。
204h(=4d)0110 0000b(=96d)
※IF_EQUALかつImmediateモード
0000 0001b(=1d)
※REG 1
0000 0000b(=0d)
※即値
0001 0000b(=16d)
※アドレス10h
REG 1と0を比較して、一致したら指定アドレスにジャンプする。
308h(=8d)0001 0010b(=18d)
※PUSH
0000 0001b(=1d)
※REG 1
1111 1111b(=255d)
※未使用
1111 1111b(=255d)
※未使用
REG 1をスタックにPUSHする。
40Ch(=12d)0010 0000b(=32d)
※IF_EQUAL
0000 0011b(=3d)
※REG 3
0000 0011b(=3d)
※REG 3
0000 0000b(=0d)
※アドレス00h
指定アドレスに無条件ジャンプ。
※IF_EQUALで代用している。
510h(=16d)0001 0011b(=19d)
※POP
1111 1111b(=255d)
※未使用
1111 1111b(=255d)
※未使用
0000 0111b(=7d)
※出力端子
スタックからPOPして、出力端子に送る。
614h(=20d)0010 0000b(=32d)
※IF_EQUAL
0000 0011b(=3d)
※REG 3
0000 0011b(=3d)
※REG 3
0000 0000b(=0d)
※アドレス00h
指定アドレスに無条件ジャンプ。
作成したプログラム
64 7 0 1
96 1 0 16
18 1 255 255
32 3 3 0
19 255 255 7
32 3 3 0

LEGアーキテクチャーの命令表

LEG32アーキテクチャーは4バイト命令を解釈するため、32ビットCPUといえます。

これまではハンドアセンブルしてきましたが、本ステージからはアセンブリー言語のまま記述できるようにします。そのためには、各オペコードにニーモニックを割り当てます。ここでいうニーモニックとは、プログラムを実行するための機械語(数字の羅列)を、プログラミングしやすくするために簡略記号化したものになります。

レジスター群

バイナリ値10進数値転送元 or 転送先割り当てた文字列
0000 0000b0REG 0REG0
0000 0001b1REG 1REG1
0000 0010b2REG 2REG2
0000 0011b3REG 3REG3
0000 0100b4REG 4REG4
0000 0101b5REG 5 ※RAMにLOAD/SAVEするとき、REG 5にアドレスを指定する。RAM
0000 0110b6プログラムカウンターPC
0000 0111b7入力端子 ※転送元用INPUT
0000 0111b7出力端子 ※転送先用OUTPUT

各命令のニーモニック

ニーモックに"i"がついているのは即値を扱うことを意味します。例えば、"ADDi"は第2引数が即値、"ADDii"は第1引数と第2引数が即値です。

命令フォーマットの"reg"はレジスター群(上記で定義)、"value"は即値、"address"はアドレス値、"_"は指定なし(1111 1111b)、"label"はラベルの記述直後のアドレス値を意味します。

OPCODE
バイナリ値
OPCODE
10進数値
命令の系統ニーモック
割り当てた文字列
命令フォーマット備考
0000 0000b0Calculation/ADDADDADD reg reg reg
0100 0000b64Calculation/ADDADDiADDi reg value regコピーとしても使える。
「ADDi REG0 0 REG1」とすれば、「REG1←REG0」
「ADDi INPUT 0 REG1」とすれば、「REG 1←INPUT」
「ADDi REG1 0 OUTPUT」とすれば、「OUTPUT←REG 1」
1100 0000b192Calculation/ADDADDiiADDii value value reg
0000 0001b1Calculation/SUBSUBSUB reg reg reg
0100 0001b65Calculation/SUBSUBiSUBi reg value reg
1100 0001b193Calculation/SUBSUBiiSUBii value value reg
0000 0010b2Calculation/ANDANDAND reg reg regマスクビットにより、マスク部の情報のみを取り出せる。
0100 0010b66Calculation/ANDANDiAND reg value reg
0000 0011b3Calculation/OROROR reg reg reg
0100 0011b67Calculation/ORORiOR reg value reg
0000 0100b4Calculation/NOTNOTNOT reg _ reg
0000 0101b5Calculation/XORXORXOR reg reg regゼロクリアに使える。
0100 0101b69Calculation/XORXORiXOR reg value reg
0000 0110b6Calculation/SHLSHLSHL reg reg reg左(Left)シフト。
0100 0110b70Calculation/SHLSHLiSHLi reg value reg
0000 0111b7Calculation/RHLSHRSHR reg reg reg右(Right)シフト。
0100 0111b71Calculation/RHLSHRiSHRi reg value reg
0001 0000b16RAM/LOAD_RAMLOADLOAD _ _ regREG 5内のデータを指定アドレスとして、RAMにロードする。転送先はreg。
0001 0001b17RAM/SAVE_RAMSAVESAVE reg _ _REG 5内のデータを指定アドレスとして、RAMにセーブする。セーブするデータ元はreg。
0001 0010b18RAM/PUSHPUSHPUSH reg _ _スタックにPUSHする。
0001 0011b19RAM/POPPOPPOP _ _ regスタックからPOPする。
0001 0100b20RAM/CALLCALLCALL label _ _labelという名のサブルーチンを呼び出す。
0001 0101b21RAM/RETRETRET _ _ _
0010 0000b32Condition/IF_EQUALIF_EQIF_EQ reg reg address「reg1=reg2」の判定。
無条件ジャンプに使うなら、「IF_EQ reg0 reg0 address」や「EF_EQ _ _ address」とする。
0110 0000b96Condition/IF_EQUALIF_EQiIF_EQ reg value address
0010 0001b33Condition/IF_NOT_EQUALIF_NOT_EQIF_NOT_EQ reg reg address「reg1≠reg2」の判定。
0110 0001b97Condition/IF_NOT_EQUALIF_NOT_EQiIF_NOT_EQi reg value address
0010 0010b34Condition/IF_LESSIF_LESSIF_LESS reg reg address「reg1<reg2」の判定。
0110 0010b98Condition/IF_LESSIF_LESSiIF_LESSi reg value address
0010 0011b35Condition/IF_LESS_OR_EQUALIF_LESS_EQIF_LESS_EQ reg reg address「reg1≦reg2」の判定。
0110 0011b99Condition/IF_LESS_OR_EQUALIF_LESS_EQiIF_LESS_EQi reg value address
0010 0100b36Condition/IF_GREATERIF_GTIF_GT reg reg address「reg1>reg2」の判定。
0110 0100b100Condition/IF_GREATERIF_GTiIF_GTi reg value address
0010 0101b37Condition/IF_GREATER_OR_EQUALIF_GT_EQIF_GT_EQ reg reg address「reg1≧reg2」の判定。
0110 0101b101Condition/IF_GREATER_OR_EQUALIF_GT_EQiIF_GT_EQi reg value address

回路的には第1引数が即値の処理もできますが、ニーモニックは定義しません。
なぜなら、「第1引数のみが即値」と「2引数のみが即値」が同等の演算ばかりのためです。例えば、加算では「即値+レジスター値」と「レジスター値+即値」でどちらも結果は同じです。
扱いやすさを考えると、第2引数を即値のほうが都合のよい演算がいくつかあります。例えば、シフト演算であれば、レジスター値を2ビット分左シフトといったように、2ビットという指定が即値のほうが扱いやすくなります。

即値同士のビット演算はほとんど使わないはずので、用意しません。
つまり、ANDii、ORiiなどのニーモックは用意しません。
用意するのは簡単ですが、命令一覧表が大きくなって読みにくくなる弊害のほうが大きいと感じました。
※もし必要だと感じたら追加しましょう。

命令表の表記については、次の記事を参考にしました。

命令コードを定義する

上記で定義したレジスター群と命令をすべて、命令コードとして定義します。

AI Showdownステージを解く

1:プログラムを設計する

ゲームで取るべき手順はすでに解説しましたので、これをプログラムで実現しましょう。

4で割った余りを計算する必要があります。そこで、除算についてはDivideステージでソフトウェアで実現しました。そのプログラムを参考にして、今回はサブルーチン化して活用することにします。今回は余りしか使いませんが、せっかくですので商と余りをレジスター経由で返すようにします。

プログラムのざっくりした流れは次の通りです。

①入力端子からカード数を読み込む。

②除算サブルーチンで余りを特定する。

③余りが0なら、出力端子から3を出力する。

④余りが3なら、出力端子から2を出力する。

⑤それ以外なら、出力端子から1を出力する。

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

アセンブリーエディター上でプログラムを実装していきます。

label main
ADDi INPUT 0 REG1
ADDii 0 4 REG2
CALL DIVIDE _ _
IF_EQi REG4 0 output_3 #REG4は余り.
IF_EQi REG4 3 output_2
# それ以外のときは1を出力.
ADDii 0 1 OUTPUT
IF_EQ REG0 REG0 main

label output_3
ADDii 0 3 OUTPUT
IF_EQ REG0 REG0 main

label output_2
ADDii 0 2 OUTPUT
IF_EQ REG0 REG0 main

# 除算サブルーチン.
# 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 _ _ _

3:テストする

9パターンのテストが実施されます。

テストにパスすると、"YOU WIN!"と表示されて、ステージクリアになります。

エラーが発生する際には、ニーモニックが正しいスペルになっていることに注意してください。例えば、即値を使っているのに接尾語’i’をつけ忘れている、即値を2つ使っているのに接尾語が"ii"になっていないなどです。

また、(コメント、ラベル、空行を除く)すべての行が4つの文字列を指定する必要があります。例えば、"CALL DIVIDE"は二つの文字列しかありません。正しくは"CALL DIVIDE _ _"になります。同様にRETについても、"RET _ _ _"と書くようにしてください。