AI Showdown【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
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バイト目 | 処理内容 |
|---|---|---|---|---|---|---|
| 1 | 00h（＝0d） | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0111b（＝7d） ※入力端子 | 0000 0000b（＝0d） ※即値 | 0000 0001b（＝1d） ※REG 1 | 入力端子からくるバイトデータをREG 1に保存する。 ※ADD命令で代用している。 |
| 2 | 04h（＝4d） | 0110 0000b（=96d） ※IF_EQUALかつImmediateモード | 0000 0001b（＝1d） ※REG 1 | 0000 0000b（＝0d） ※即値 | 0001 0000b（＝16d） ※アドレス10h | REG 1と0を比較して、一致したら指定アドレスにジャンプする。 |
| 3 | 08h（＝8d） | 0001 0010b（＝18d） ※PUSH | 0000 0001b（＝1d） ※REG 1 | 1111 1111b（＝255d） ※未使用 | 1111 1111b（＝255d） ※未使用 | REG 1をスタックにPUSHする。 |
| 4 | 0Ch（＝12d） | 0010 0000b（=32d） ※IF_EQUAL | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 0000 0000b（＝0d） ※アドレス00h | 指定アドレスに無条件ジャンプ。 ※IF_EQUALで代用している。 |
| 5 | 10h（＝16d） | 0001 0011b（＝19d） ※POP | 1111 1111b（＝255d） ※未使用 | 1111 1111b（＝255d） ※未使用 | 0000 0111b（＝7d） ※出力端子 | スタックからPOPして、出力端子に送る。 |
| 6 | 14h（＝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 0000b | 0 | REG 0 | REG0 |
| 0000 0001b | 1 | REG 1 | REG1 |
| 0000 0010b | 2 | REG 2 | REG2 |
| 0000 0011b | 3 | REG 3 | REG3 |
| 0000 0100b | 4 | REG 4 | REG4 |
| 0000 0101b | 5 | REG 5 ※RAMにLOAD/SAVEするとき、REG 5にアドレスを指定する。 | RAM |
| 0000 0110b | 6 | プログラムカウンター | PC |
| 0000 0111b | 7 | 入力端子 ※転送元用 | INPUT |
| 0000 0111b | 7 | 出力端子 ※転送先用 | OUTPUT |
各命令のニーモニック
ニーモックに"i"がついているのは即値を扱うことを意味します。例えば、"ADDi"は第2引数が即値、"ADDii"は第1引数と第2引数が即値です。
命令フォーマットの"reg"はレジスター群（上記で定義）、"value"は即値、"address"はアドレス値、"_"は指定なし（1111 1111b）、"label"はラベルの記述直後のアドレス値を意味します。
| OPCODE バイナリ値 | OPCODE 10進数値 | 命令の系統 | ニーモック 割り当てた文字列 | 命令フォーマット | 備考 |
|---|---|---|---|---|---|
| 0000 0000b | 0 | Calculation/ADD | ADD | ADD reg reg reg | |
| 0100 0000b | 64 | Calculation/ADD | ADDi | ADDi reg value reg | コピーとしても使える。 「ADDi REG0 0 REG1」とすれば、「REG1←REG0」 「ADDi INPUT 0 REG1」とすれば、「REG 1←INPUT」 「ADDi REG1 0 OUTPUT」とすれば、「OUTPUT←REG 1」 |
| 1100 0000b | 192 | Calculation/ADD | ADDii | ADDii value value reg | |
| 0000 0001b | 1 | Calculation/SUB | SUB | SUB reg reg reg | |
| 0100 0001b | 65 | Calculation/SUB | SUBi | SUBi reg value reg | |
| 1100 0001b | 193 | Calculation/SUB | SUBii | SUBii value value reg | |
| 0000 0010b | 2 | Calculation/AND | AND | AND reg reg reg | マスクビットにより、マスク部の情報のみを取り出せる。 |
| 0100 0010b | 66 | Calculation/AND | ANDi | AND reg value reg | |
| 0000 0011b | 3 | Calculation/OR | OR | OR reg reg reg | |
| 0100 0011b | 67 | Calculation/OR | ORi | OR reg value reg | |
| 0000 0100b | 4 | Calculation/NOT | NOT | NOT reg _ reg | |
| 0000 0101b | 5 | Calculation/XOR | XOR | XOR reg reg reg | ゼロクリアに使える。 |
| 0100 0101b | 69 | Calculation/XOR | XORi | XOR reg value reg | |
| 0000 0110b | 6 | Calculation/SHL | SHL | SHL reg reg reg | 左（Left）シフト。 |
| 0100 0110b | 70 | Calculation/SHL | SHLi | SHLi reg value reg | |
| 0000 0111b | 7 | Calculation/RHL | SHR | SHR reg reg reg | 右（Right）シフト。 |
| 0100 0111b | 71 | Calculation/RHL | SHRi | SHRi reg value reg | |
| 0001 0000b | 16 | RAM/LOAD_RAM | LOAD | LOAD _ _ reg | REG 5内のデータを指定アドレスとして、RAMにロードする。転送先はreg。 |
| 0001 0001b | 17 | RAM/SAVE_RAM | SAVE | SAVE reg _ _ | REG 5内のデータを指定アドレスとして、RAMにセーブする。セーブするデータ元はreg。 |
| 0001 0010b | 18 | RAM/PUSH | PUSH | PUSH reg _ _ | スタックにPUSHする。 |
| 0001 0011b | 19 | RAM/POP | POP | POP _ _ reg | スタックからPOPする。 |
| 0001 0100b | 20 | RAM/CALL | CALL | CALL label _ _ | labelという名のサブルーチンを呼び出す。 |
| 0001 0101b | 21 | RAM/RET | RET | RET _ _ _ | |
| 0010 0000b | 32 | Condition/IF_EQUAL | IF_EQ | IF_EQ reg reg address | 「reg1＝reg2」の判定。 無条件ジャンプに使うなら、「IF_EQ reg0 reg0 address」や「EF_EQ _ _ address」とする。 |
| 0110 0000b | 96 | Condition/IF_EQUAL | IF_EQi | IF_EQ reg value address | |
| 0010 0001b | 33 | Condition/IF_NOT_EQUAL | IF_NOT_EQ | IF_NOT_EQ reg reg address | 「reg1≠reg2」の判定。 |
| 0110 0001b | 97 | Condition/IF_NOT_EQUAL | IF_NOT_EQi | IF_NOT_EQi reg value address | |
| 0010 0010b | 34 | Condition/IF_LESS | IF_LESS | IF_LESS reg reg address | 「reg1＜reg2」の判定。 |
| 0110 0010b | 98 | Condition/IF_LESS | IF_LESSi | IF_LESSi reg value address | |
| 0010 0011b | 35 | Condition/IF_LESS_OR_EQUAL | IF_LESS_EQ | IF_LESS_EQ reg reg address | 「reg1≦reg2」の判定。 |
| 0110 0011b | 99 | Condition/IF_LESS_OR_EQUAL | IF_LESS_EQi | IF_LESS_EQi reg value address | |
| 0010 0100b | 36 | Condition/IF_GREATER | IF_GT | IF_GT reg reg address | 「reg1＞reg2」の判定。 |
| 0110 0100b | 100 | Condition/IF_GREATER | IF_GTi | IF_GTi reg value address | |
| 0010 0101b | 37 | Condition/IF_GREATER_OR_EQUAL | IF_GT_EQ | IF_GT_EQ reg reg address | 「reg1≧reg2」の判定。 |
| 0110 0101b | 101 | Condition/IF_GREATER_OR_EQUAL | IF_GT_EQi | IF_GT_EQi reg value address |
回路的には第1引数が即値の処理もできますが、ニーモニックは定義しません。
なぜなら、「第1引数のみが即値」と「2引数のみが即値」が同等の演算ばかりのためです。例えば、加算では「即値＋レジスター値」と「レジスター値＋即値」でどちらも結果は同じです。
扱いやすさを考えると、第2引数を即値のほうが都合のよい演算がいくつかあります。例えば、シフト演算であれば、レジスター値を2ビット分左シフトといったように、2ビットという指定が即値のほうが扱いやすくなります。
即値同士のビット演算はほとんど使わないはずので、用意しません。
つまり、ANDii、ORiiなどのニーモックは用意しません。
用意するのは簡単ですが、命令一覧表が大きくなって読みにくくなる弊害のほうが大きいと感じました。
※もし必要だと感じたら追加しましょう。
命令表の表記については、次の記事を参考にしました。
https://steamcommunity.com/sharedfiles/filedetails/?id=26251...命令コードを定義する
上記で定義したレジスター群と命令をすべて、命令コードとして定義します。
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 _ _ _"と書くようにしてください。