2026 年 5 月に開催された第 7 回自作 CPU を語る会にて、自作 CPU オセロ大会が行われたため、私も自作の三進 CPU である Libra the Processor で参戦しました。ただし、実機ではハードウェア不良により動かなかったため、シミュレータでの参戦となりました。
これまでに Libra the Processor 用に作ったプログラムは、複雑なものでもトリボナッチ数列計算プログラムぐらいだったので、オセロプログラムほどの複雑なプログラムの作成は初となりました。
特に苦労したのはプログラムサイズの制限で、 Libra the Processor は命令メモリが 5 trit = 243 words しかありません。そのため、極限まで機能を削ってとりあえず合法手を返すだけに専念し、さらに 1 word でも削るためのアドホックな最適化を重ねることでなんとかサイズ制限に収めることができました。（ 241 words ）
対戦結果は以下の通りで、全敗でしたが最後までエラーなく指しきれただけで十分健闘したと言えると思います。棋譜は https://do2.rojo.jp/shogi/javascript/mania.html のサイトで再生することができます。
- 先手 Libra the Processor vs. 後手 TD4EX4-2026 (Exit さん)
23 - 41 で TD4EX4-2026 の勝利
棋譜：D3C3B3B2B1E3D2C5F3G3H3A1B4D1C1A3E1F1A5F4F5H2H1F2C2G6D6E7E2E6C4G4G5G2A2G1A4A6B5B6H4H5C6C7F6F7H6A7B7D7D8G7G8H7F8E8C8A8B8H8 - 先手 NLP-16A (ちぇりーたくあん さん) vs. 後手 Libra the Processor
46 - 18 で NLP-16A の勝利
棋譜：
D3C3C4E3F3G3F6B5D2C1A6C5H3E2F1F2D1E1B1B4A5B2A1C2F4A2D6A4G2H2H1G4F5G1B3A3H4H5G5H6B6C6E6E7G6F7A7A8B7D7C7C8G7H8B8D8H7E8F8G8
完成したプログラム
プログラムの仕様は以下のようになっています。
- 盤面を左上から順番に走査していき、最初に見つけた合法手を返すだけの最低限の AI 。
- 入出力は MMIO を介して ASCII コードで行う。
- 最初に "B" または "W" を入力して、 "B" なら先手、 "W" なら後手として動作する。
- 座標は列を A ~ H 、行を 1 ~ 8 で表し、 "A1" 、 "H4" のように表現する。パスの場合は "P" で表現する。
- 相手の指した手が合法かどうかのチェックは行わずに信用する。
- 2 連続でパスが発生すると動作を終了する。勝敗判定は行わない。
大会で使用した実際のプログラム全体を掲載します。
命令セットについてはこちらの記事を参照してください。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 |
// プロトコル: // - このプログラムが先行(黒)なら'B', 後攻(白)なら'W' を最初に1行送る. // - 入力は相手の手を1行ずつ受け取る: D3 または P // - 出力は自分の手を1行ずつ返す: D3 または P // // メモリ // 0 ~ 89 : 盤面(番兵込み) // row: 1 ~ 8, col 1 ~ 8 とし, address = row * 9 + col // row == 0, 9, col == 0 は番兵. // 0 = 空き, 1 = 白, -1 = 黒. // // 100: MyColor, 101: OppColor // 102: ApplyRes, 103: ApplyColor // 104: FlipColor // 110: OppPass // メモリ初期化 (0 ~ 120) // C = pos SUB C, A // C = 0 CLEAR: SUB A, A // A = 0 ST C // board[pos] = 0 MOV A, C // A = pos CMPI 120 JZ INIT // if (pos == 89) ADDI C, 1 // C = pos + 1 J CLEAR // 石の初期配置, 先攻後攻の決定 INIT: MOVI A, 1 STI 40 // D4 白 STI 50 // E5 白 NOT A STI 41 // E4 黒 STI 49 // D5 黒 LDI A, 121 // A = MMIO in LDI B, 121 // 改行読み飛ばし ADDI A, 35 // 'W' = -34 なら A = 1, 'B' = -55 なら A < 0 JP INIT_L1 // if (A == 'W') MOVI A, -1 // A = MyColor INIT_L1: STI 100 // MyColor = MyColor NOT A STI 101 // OppColor = ~MyColor CMPI 0 JP MY_TURN // if (OppColor == 1) // 相手の手を読み, 盤面に反映. 合法手かチェックはしない // 重要な文字値: // - 'A' = -56 なので, 列番号 = 入力 + 57 // - '1' = -72 なので, 行番号 = 入力 + 73 // - 'P' = -41 // // 遷移元: SEARCH_OK (J), INIT_L1 (thru) OPP_TURN: MOVI B, 121 LD A, B // MMIO in ADDI C, 57 // C = col ADDI A, 42 // check 'P' (A は 'A'-'G', 'P' のみなので 'P' のときだけ正になる) JP OPP_PASS LD A, B // MMIO in LD B, B // 改行読み飛ばし ADDI A, 73 // A = row CALL MAKE_POS // C = pos LDI A, 101 // A = OppColor STI 103 // ApplyColor = OppColor CALL APPLY // 相手入力は合法と仮定するので戻り値は無視する. SUB A, A // A = 0 STI 110 // OppPass J MY_TURN // 遷移元: OPP_TURN (JP) // 前提: A = 1, B = 121 OPP_PASS: STI 110 // OppPass = 1 LD C, B // 改行読み飛ばし // 合法手を探して最初に見つかったものを選ぶ // 遷移元: OPP_PASS (thru) MY_TURN: LDI A, 100 // A = MyColor STI 103 // ApplyColor = MyColor MOVI C, 10 // C = pos // pos から始めて置けるかどうか試す // 遷移元: MY_TURN (thru), SEARCH_NEXT // 前提: C = pos, ApplyColor = MyColor SEARCH: LD A, C // A = board[pos] CMPI 0 JZ SEARCH_TRY // if (board[pos] == 0) J SEARCH_NEXT // else // pos が空きなので置いてみる. // 遷移元: SEARCH (JZ) // 前提: C = pos, ApplyColor = MyColor SEARCH_TRY: CALL APPLY // C = pos LDI A, 102 // A = ApplyRes CMPI 0 JZ SEARCH_UNDO // if (ApplyRes == 0) // 置けたので出力する. // 遷移元: SEARCH_TRY (thru) // 前提: C = pos SEARCH_OK: MOV A, C // A = pos // pos = 9 * row + col から row と col を取り出す. // col は 0~8 であるが、pos の下2桁は -4~4 のためそのままは取り出せない. // pos-4 を考えると col-4 は -4~4 になり、上位3桁は row に一致する. ADDI A, -4 // A = pos - 4 SR A SR A // A = row MOV B, A // B = row SL A SL A // A = row * 9 SUB A, C // A = -col NOT A // A = col ADDI A, -57 // col を 'A'-'H' に MOVI C, 121 // C = 121 ST C // MMIO out MOV A, B // A = row ADDI A, -73 // row を '1'-'8' に ST C // MMIO out MOVI A, -111 // A = '\n' ST C // MMIO out J OPP_TURN // 置いてみた石が違法だったためキャンセル // 前提: A = 0, C = pos, ApplyColor = MyColor SEARCH_UNDO: ST C // board[pos] = 0 // 次の pos へ // 遷移元: SEARCH (JZ), SEARCH_NEXT (JZ), SEARCH_UNDO (thru) // 前提: C = pos, ApplyColor = MyColor SEARCH_NEXT: MOV A, C // A = pos CMPI 80 JZ SEARCH_END // if (pos == 80) ADDI C, 1 // C = pos + 1 MOV A, C // A = pos + 1 ANDI A, 0t###11 // A &= 0t###11 CMPI 0t###00 JZ SEARCH_NEXT // if ((pos+1) % 9 == 0) then +1 again J SEARCH // 合法手が見つからなかった // 遷移元: SEARCH_NEXT SEARCH_END: MOVI A, -41 // A = 'P' STI 121 // MMIO out MOVI A, -111 // A = '\n' STI 121 // MMIO out LDI A, 110 // A = OppPass CMPI 0 JZ OPP_TURN // if (OppPass == 0) // 相手と自分が連続でパスしたため終了 // 遷移元: SEARCH_END (thru) GAME_END: HALT // function // 入力: A = row, B /k, C = col // 出力: C = pos // // 呼び出し元: OPP_TURN MAKE_POS: SL A SL A ADD C, C RET // function // 石を置いてひっくり返す. pos は空きマスという前提. // 入力: C = pos /keep, ApplyColor, // 出力: ApplyRes = (1つも返さなかったら0) // // 呼び出し元: OPP_TURN, SEARCH APPLY: SUB A, A // A = 0 STI 102 // ApplyRes = 0 MOV A, C // A = pos MOVI C, -10 // 隣接マスが逆の色かどうか調べる // 遷移元: APPLY (thru), APPLY_NEXT_ADD1 (J) // 前提: A = pos, C = dir APPLY_DIR_FIRST: PUSH // push_1. pos ADD A, C // A = moved pos PUSH // push_2. moved pos LD A, A // A = board[moved pos] NOT B // B = ~board[moved pos] LDI A, 103 // A = ApplyColor CMP B POP B // pop_2. B = moved pos JZ APPLY_FLIP // if (~board[moved pos] == ApplyColor) // 次の方向の処理に進む // 遷移元: APPLY_DIR_FIRST (thru), APPLY_FLIP (J), APPLY_UNDO (J) // 前提: C = dir APPLY_NEXT: MOV A, C // A = dir CMPI 10 JZ APPLY_END CMPI -8 JZ APPLY_NEXT_ADD7 CMPI 1 JZ APPLY_NEXT_ADD7 J APPLY_NEXT_ADD1 APPLY_NEXT_ADD7: ADDI A, 6 // A = dir + 6 APPLY_NEXT_ADD1: ADDI C, 1 // C = (dir or dir+6) + 1 POP A // pop_1. A = pos J APPLY_DIR_FIRST // 隣接マスが逆の色だったのでひっくり返してみる. // 遷移元: APPLY_DIR_FIRST (JZ) // 前提: A = ApplyColor, B = pos, C = dir /keep APPLY_FLIP: STI 104 // FlipColor = ApplyColor CALL FLIP CMPI 0 JZ APPLY_UNDO // if (flip result == 0) STI 102 // ApplyRes = 1 or -1 J APPLY_NEXT // ひっくり返してみたがダメだったので元に戻す. 元の位置には必ず空きマスがあるはずなので, 逆向きにFlipする. // 止まったマスの1つ手前に戻ってからFLIPを実行 // 遷移元: APPLY_FLIP (JZ) // 前提: A = 0, B = stopped pos, C = dir /keep APPLY_UNDO: SUB C, C // C = ~dir MOV A, B // A = stopped pos ADD B, C // B = stopped pos - dir ; 1個戻ったマス LDI A, 103 // A = ApplyColor NOT A // A = ~ApplyColor STI 104 // FlipColor = ~ApplyColor CALL FLIP // A = 0 SUB C, C // C = dir J APPLY_NEXT // 8方向の適用が終わった. 最後に石を置く. // 遷移元: APPLY_NEXT (JZ) APPLY_END: POP C // pop_1. C = pos LDI A, 103 // A = ApplyColor ST C // board[pos] = color RET // function // 指定の方向にひっくり返していく. pos を返してから次に進む. pos はひっくり返せる前提. // FlipColor か空きマスにぶつかったら終了し、止まったマスの位置と色を返す. // // 入力: A = FlipColor, B = pos, C = dir /keep // 出力: A = result, B = stopped pos // 呼び出し元: APPLY_DIR_FIRST, APPLY_UNDO FLIP: ST B // board[pos] = FlipColor MOV A, B // A = pos ADD A, C // A = moved pos PUSH // push_3. moved pos LD A, A // A = board[moved pos] CMPI 0 JZ FLIP_END // if (board[moved pos] == 0) LDI B, 104 // B = FlipColor CMP B JZ FLIP_END // if (board[moved pos] == FlipColor) POP B // pop_3. B = moved pos NOT A // A = FlipColor J FLIP FLIP_END: POP B // pop_3. B = moved pos RET |
工夫点
ここからはこのプログラムの工夫点をトピックごとに解説していきます。
番兵を使った盤面管理
オセロは 8 x 8 の盤面で、 1 マスあたり白、黒、空きの 3 つの状態を持ちます。 3 状態を 3 進 1 桁で表せることを上手く使えないかと思いましたが、 trit 操作はプログラムサイズが増えがちなので今回は見送りました。
普通に 1 マスを 1 word で表現する場合、下図左のように連続する 64 word のメモリ領域を使うのが素朴な発想ですが、これだと境界での場合分けが必要となります。例えば、あるマスの 1 つ左のマスにアクセスしたいとき、基本はアドレスを -1 すればよいですが、 A 列の場合はそれだと H 列のマスを参照してしまいます。
このような場合分けを避けるために、図中央のようにダミーのデータを置いておく手法があり、これらのダミーは番兵と呼ばれます。オセロの場合は番兵は空きマスとして扱えば石を返せるかどうかの判定に場合分けが不要になります。
これでもいいのですが、もう一工夫加えると図右のように左右の番兵は共通化できることに気が付きます。例えば、 A2 の左と H1 の右はどちらもアドレス 18 となりますが、番兵に変わりありません。
これでメモリ量が少し減りますが、データメモリサイズには困っていません。嬉しい点はそこではなく、 1 行あたりの要素数が 9 となり、（番兵を含めて）行を 0 ~ 10 、列を 0 ~ 8 としたときにアドレスが address = row * 9 + col と表せる点です。三進数において 9 倍は左シフト 2 回で実行できるため、三進 CPU と非常に相性が良いです。
入力された手をアドレスとして解釈する処理は以下のようになっています。入力された ASCII を row と col に変換した後、シフトと加算でアドレスに変換しています。
|
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// - 'A' = -56 なので, 列番号 = 入力 + 57 // - '1' = -72 なので, 行番号 = 入力 + 73 // - 'P' = -41 // // 遷移元: SEARCH_OK (J), INIT_L1 (thru) OPP_TURN: MOVI B, 121 LD A, B // MMIO in ADDI C, 57 // C = col ADDI A, 42 // check 'P' (A は 'A'-'G', 'P' のみなので 'P' のときだけ正になる) JP OPP_PASS LD A, B // MMIO in LD B, B // 改行読み飛ばし ADDI A, 73 // A = row CALL MAKE_POS // C = pos |
|
173 174 175 176 177 |
MAKE_POS: SL A SL A ADD C, C RET |
番兵列かどうかのチェックはアドレスが 9 の倍数かどうかをチェックすればよく、これは下 2 桁が 00 かどうかで判定できます。以下にその処理を行っているコードを示します。
AND は桁ごとに最小値演算を行うため、 # (-1) と AND を取ることでその桁は # に、 1 と AND を取ることでその桁はそのままとなります。マスクをかけた後は 0 ではなく、 0t###00 と比較することに注意が必要です。
|
141 142 143 144 145 146 147 148 149 150 |
SEARCH_NEXT: MOV A, C // A = pos CMPI 80 JZ SEARCH_END // if (pos == 80) ADDI C, 1 // C = pos + 1 MOV A, C // A = pos + 1 ANDI A, 0t###11 // A &= 0t###11 CMPI 0t###00 JZ SEARCH_NEXT // if ((pos+1) % 9 == 0) then +1 again J SEARCH |
手を出力する際には、アドレスから行と列に分解するわけですが、行と列が上位3桁と下位2桁に分かれているわけではないことに注意が必要です。（一敗）
はじめの数行のアドレスを平衡三進数で表すと下図のようになります。平衡三進数では下 2 桁は 0 ~ 8 ではなく -4 ~ 4 を表すため、 3 桁目への繰り上がりが行と一致していません。
これを解決するにはアドレスを -4 ずつずらします。これによって下図のようになり、行と列の値を上位 3 桁と下位 2 桁に分離できます。
実際のコードは以下のようになっています。まず右シフトによって行を取り出し、その後左シフトで位置を戻してから元の値から引くことで列を取り出します。ここでは address - row * 9 = col を行っているので、得られた列は -4 ~ 4 ではなく 0 ~ 8 であることに注意してください。
|
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
SEARCH_OK: MOV A, C // A = pos // pos = 9 * row + col から row と col を取り出す. // col は 0~8 であるが、pos の下2桁は -4~4 のためそのままは取り出せない. // pos-4 を考えると col-4 は -4~4 になり、上位3桁は row に一致する. ADDI A, -4 // A = pos - 4 SR A SR A // A = row MOV B, A // B = row SL A SL A // A = row * 9 SUB A, C // A = -col NOT A // A = col ADDI A, -57 // col を 'A'-'H' に MOVI C, 121 // C = 121 ST C // MMIO out MOV A, B // A = row ADDI A, -73 // row を '1'-'8' に ST C // MMIO out MOVI A, -111 // A = '\n' ST C // MMIO out J OPP_TURN |
今になって思うと、列を 0 ~ 8 ではなく始めから -4 ~ 4 で扱っておけばこの処理がシンプルになりましたね。その場合番兵列の判定は下 2 桁が ## であることになりますが、どうせ定数で比較していたのでコストは変わりません。強いて欠点を言えば配列の開始アドレスが 0 でなくて -4 になって少し気持ち悪いぐらいですね。（アドレス空間は -121 ~ 121 です）
合法手判定・盤面更新
オセロ AI を普通に作ろうと思うと、まず合法手をリストアップして、それぞれの手を何らかの方法で評価して、最も評価値の高いものを選択するという流れになるかと思います。しかしこの限界オセロプログラムはとにかく何かしらの合法手を返すことに専念するので、流れが変わってきます。
盤面を走査して最初に見つけた合法手を選択するのですが、合法手かどうか判断する処理と、そのマスに石を置いて盤面を更新する処理はほとんど同じ処理です。そこで、判断の前にとりあえず石を置いて更新処理を行ってしまい、 OK であればそのままにして、 NG であればもとに戻すという方針で実装しました。
以下に示すのはこの処理の核となる部分で、指定のマスから、指定の方向に、石をひっくり返していく処理です。なおそのマスが空いていることは事前にチェック済みとします。
|
191 192 193 194 195 196 197 198 199 200 201 202 203 |
// 隣接マスが逆の色かどうか調べる // 遷移元: APPLY (thru), APPLY_NEXT_ADD1 (J) // 前提: A = pos, C = dir APPLY_DIR_FIRST: PUSH // push_1. pos ADD A, C // A = moved pos PUSH // push_2. moved pos LD A, A // A = board[moved pos] NOT B // B = ~board[moved pos] LDI A, 103 // A = ApplyColor CMP B POP B // pop_2. B = moved pos JZ APPLY_FLIP // if (~board[moved pos] == ApplyColor) |
|
224 225 226 227 228 229 230 231 232 233 |
// 隣接マスが逆の色だったのでひっくり返してみる. // 遷移元: APPLY_DIR_FIRST (JZ) // 前提: A = ApplyColor, B = pos, C = dir /keep APPLY_FLIP: STI 104 // FlipColor = ApplyColor CALL FLIP CMPI 0 JZ APPLY_UNDO // if (flip result == 0) STI 102 // ApplyRes = 1 or -1 J APPLY_NEXT |
|
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 |
// function // 指定の方向にひっくり返していく. pos を返してから次に進む. pos はひっくり返せる前提. // FlipColor か空きマスにぶつかったら終了し、止まったマスの位置と色を返す. // // 入力: A = FlipColor, B = pos, C = dir /keep // 出力: A = result, B = stopped pos // 呼び出し元: APPLY_DIR_FIRST, APPLY_UNDO FLIP: ST B // board[pos] = FlipColor MOV A, B // A = pos ADD A, C // A = moved pos PUSH // push_3. moved pos LD A, A // A = board[moved pos] CMPI 0 JZ FLIP_END // if (board[moved pos] == 0) LDI B, 104 // B = FlipColor CMP B JZ FLIP_END // if (board[moved pos] == FlipColor) POP B // pop_3. B = moved pos NOT A // A = FlipColor J FLIP FLIP_END: POP B // pop_3. B = moved pos RET |
石をひっくり返せる条件をおさらいすると、①隣接マスが相手の色であり、②（隣接マスを含めて） 1 個以上の相手の石が続き、③その後自分の色があること、となっています。また合法手であることの条件は少なくとも 1 方向で石をひっくり返せることです。
APPLY_DIR_FIRST は①の条件を判定していて、満たしていた場合 APPLY_FLIP に進み、自分の色を指定して FLIP が呼ばれます。FLIP は（反対の色を）指定された色にひっくり返していく処理を反復して、指定した色もしくは空きマスにぶつかってひっくり返せなくなったらその位置と色を返す関数になっています。
FLIP をやってみた結果、止まったマスが自分の色であればその操作は正しかったことになります。この場合、合法手であることを記録した上で、 APPLY_NEXT に進んで次の方向の処理に進みます。（後述）
一方止まったマスが空きマスだった場合（番兵に当たった場合も含む）、この操作は間違っていたことになるので元に戻さなければなりません。この処理を以下に示します。
|
235 236 237 238 239 240 241 242 243 244 245 246 247 248 |
// ひっくり返してみたがダメだったので元に戻す. 元の位置には必ず空きマスがあるはずなので, 逆向きにFlipする. // 止まったマスの1つ手前に戻ってからFLIPを実行 // 遷移元: APPLY_FLIP (JZ) // 前提: A = 0, B = stopped pos, C = dir /keep APPLY_UNDO: SUB C, C // C = ~dir MOV A, B // A = stopped pos ADD B, C // B = stopped pos - dir ; 1個戻ったマス LDI A, 103 // A = ApplyColor NOT A // A = ~ApplyColor STI 104 // FlipColor = ~ApplyColor CALL FLIP // A = 0 SUB C, C // C = dir J APPLY_NEXT |
注目すべきは、ここでも先ほどと同じ FLIP が呼ばれていることです。ただし先ほどとは開始マス、方向、色を変えています。
下の図を見てもらえると分かると思いますが、石を置こうとしているマスと止まったマスはどちらも空きマスで、その間に元々相手の石があったのを自分の色に上書きした状態になっています。したがって、止まったマスの 1 つ手前から逆向きに同じ処理を行うことで元に戻すことができるのです。
今書いてて気付きましたが、別に逆方向からやる必要はないですね。最初の FLIP と同じマス、方向で色だけ反転させれば命令が数個減ることでしょう。
いずれにせよ、同じ関数を使いまわせることで命令サイズの削減に大きく寄与しました。
方向列挙
今紹介した指定の方向にひっくり返す処理を 8 方向に対して繰り返すのですが、これを列挙するにも工夫があります。まず 8 つの方向は下図のようにアドレスの差として表現できます。
高級言語であれば
for (int row = -1; row <= 1; row++) {
for (int col = -1; col <= 1; col++) {
if (row == 0 && col == 0) continue;
int dir = row * 3 + col;
}
}とか書くのが基本かなと思うんですが、変数の読み書きやインクリメントは馬鹿にならないコストです。
次に思いつく方法としては、
int dirs[] = {-10, -9, -8, -1, 1, 8, 9, 10};
for (int i = 0; i < 8; i++) {
int dir = dirs[i];
}のような方法ですが、最初に方向リストを作成するのに即値命令をたくさん並べる必要があり、結局重たいです。
最終的に出来上がったのは次のコードです。
|
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
// 次の方向の処理に進む // 遷移元: APPLY_DIR_FIRST (thru), APPLY_FLIP (J), APPLY_UNDO (J) // 前提: C = dir APPLY_NEXT: MOV A, C // A = dir CMPI 10 JZ APPLY_END CMPI -8 JZ APPLY_NEXT_ADD7 CMPI 1 JZ APPLY_NEXT_ADD7 J APPLY_NEXT_ADD1 APPLY_NEXT_ADD7: ADDI A, 6 // A = dir + 6 APPLY_NEXT_ADD1: ADDI C, 1 // C = (dir or dir+6) + 1 POP A // pop_1. A = pos J APPLY_DIR_FIRST |
現在値が 10 だったら終了、 -8 か 1 だったら +7 、それ以外は +1 という計算です。ミソとなるのは -1 から 1 に飛ばずに 0 もそのまま計算している点です。
方向が 0 で APPLY_DIR_FIRST に進んだ場合、隣接マスが自分自身 = 空きマスと判定されるので、ひっくり返せないと判定されるだけです。無駄な計算にはなりますが、場合分けを減らすことでプログラムサイズを削減できます。
その他細かいポイントとしては、 APPLY_NEXT_ADD7 と APPLY_NEXT_ADD1 の合流のコストを下げるために APPLY_NEXT_ADD7 では +6 をして APPLY_NEXT_ADD1 にフォールスルーしています。…が以下のようにしても命令長は変わらなかったことに今気が付きました。
CMPI -8
JZ APPLY_NEXT_ADD7
CMPI 1
JZ APPLY_NEXT_ADD7
ADDI C, 1
J APPLY_NEXT_JOIN
APPLY_NEXT_ADD7:
ADDI C, 7
APPLY_NEXT_JOIN:
POP A
J APPLY_DIR_FIRST-8 と 1 はどちらも下 2 桁が 01 となることで判定できるので、以下のようにすれば少し命令が削減できると思われるかもしれませんが、これだと A レジスタの値を破壊してしまうため、得にはならないかと思います。
ANDI A, 0t###11
CMPI 0t###01
JZ APPLY_NEXT_ADD7激アドホック最適化
プログラム開発終盤、本当に 1 命令でも削りたい状況だったため、激アドホックな命令削減を行いました。
例えば初期設定で'B'と入力されたら A = -1 、'W' と入力されたら A = 1 としたい場面で、普通に書くと次のようになるかと思います。
LDI A, 121 // A = MMIO in
LDI B, 121 // 改行読み飛ばし
CMPI -34 // 'W' と比較
JZ INIT_W
MOVI A, -1 // 'B' の場合
J INIT_JOIN
INIT_W:
MOVI A, 1
INIT_JOIN:'W' = -34 かどうかを判定するために、 -34 を引いて 0 になるかを見ています。一方、実際のコードでは次のようになっています。
|
37 38 39 40 41 42 |
LDI A, 121 // A = MMIO in LDI B, 121 // 改行読み飛ばし ADDI A, 35 // 'W' = -34 なら A = 1, 'B' = -55 なら A < 0 JP INIT_L1 // if (A == 'W') MOVI A, -1 // A = MyColor INIT_L1: |
キモとなるのは 35 を足している点です。これによって、'W' = -34 の場合は A = 1 > 0 となり、'B' = -55 の場合は A = -20 < 0 となります。すなわち、'W'かどうかの判定と一緒に A = 1 を生成することができます。
例外処理を一切考えない限界プログラムだからこそ為せる技で、即値命令 2 つ = 4 words の削減となります。
相手の入力がパスの'P'であるかの判定でも同じことをしています。
|
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
OPP_TURN: MOVI B, 121 LD A, B // MMIO in ADDI C, 57 // C = col ADDI A, 42 // check 'P' (A は 'A'-'G', 'P' のみなので 'P' のときだけ正になる) JP OPP_PASS LD A, B // MMIO in LD B, B // 改行読み飛ばし ADDI A, 73 // A = row CALL MAKE_POS // C = pos LDI A, 101 // A = OppColor STI 103 // ApplyColor = OppColor CALL APPLY // 相手入力は合法と仮定するので戻り値は無視する. SUB A, A // A = 0 STI 110 // OppPass J MY_TURN // 遷移元: OPP_TURN (JP) // 前提: A = 1, B = 121 OPP_PASS: STI 110 // OppPass = 1 LD C, B // 改行読み飛ばし |
まとめ
243 words という非常に限られた命令サイズでオセロを実現するために、合法手判定のアルゴリズムを工夫したり、 1 命令でも削減するための局所最適化をたくさん行いました。
個別に紹介はしませんでしたが、即値命令やジャンプ命令は命令長が 2 で重いので、共通即値をレジスタ化したり、フォールスルーによるジャンプ命令削減は当然試しています。
プログラムを書く上で苦労したのはレジスタの割り当てで、 Libra the Processor には A 、 B 、 C の 3 つしかレジスタがない上に A レジスタがオペランドの一方として固定されているので、できるだけメモリやスタックに退避しなくて済むように、移動と計算を同時に行えるように、等を意識しながら割り当てを考えていました。
記事を書いて振り返ると改善できる点がまだまだありましたが、イベント直前に 3 日で作ったにしては上出来なんじゃないかなと思います。
最後までご覧いただきありがとうございました。 Libra the Processor のプログラムを書いてみたいというチャレンジャーがいましたら、シミュレータはブラウザまたは node.js で動かせるので、ぜひ挑戦してみてください。投稿者が泣いて喜びます。
