Libra the Processorでオセロしてみた

Libra the Processor で オセロしてみた きっちー＠rikeden_net 2025/5/9 自作CPUを語る会#7

何が大変だったか？ • 命令メモリが足りない!! • Libra the Processor は 5 trit CPU 命令メモリのアドレスも 5 trit なので 3^5 = 243 words しかない • 即値を使う命令は 2 words なので、使える命令数はもっと少ない • Codex に ISA を読み込ませてオセロプログラム書かせてみた • 試してみましたが、現在のLibra CPU制約だと厳しいです。 命令語数が 397語 になりました。 • CPU は後攻固定、メモリ初期化もしないでこの語数 • 独自 ISA なのにそれっぽいコードを書けてるのは驚き

結論 • 頑張って可能な限りコンパクトにアセンブリを手書きした結果、 241 words に収めることに成功！ • 合法手を返すことだけを考える • 左上から盤面を走査して最初に見つけた合法手を出力する • オセロサイトで試したところ、最弱の AI にギリ負けた • メモリ初期化や先手後手選択に対応 • パス連続で試合終了は判定できるが、勝敗判定は入れられず

三進ならではの工夫点 • 1 trit で黒/白/空 を表現可能ではあるが、プログラムが難しく なるためビットボード的なことはやっていない • 次世代機でもっと命令使えるようになったら試してみたい

三進ならではの工夫点 • オセロの盤面は 8x8 だけど、 番兵を含めて 9x10 で扱うと 上手くいく • 1次元配列として扱えば、 右の番兵は不要 • pos = row * 9 + col • * 9 は左シフト2回でできる 0 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

• 番兵の列 (col = 0) は 9 の倍数かどうかで判定でき、 これは下 2 桁が 00 であることで判定できる • row = pos / 9, col = pos % 9 で分解したいが、平衡三進数で は下 2 桁は 0 ~ 8 ではなく -4 ~ 4 となるため、そのままでは trit 操作で分解できない 00000 00001 0001# 00010 00011 001## 001#0 001#1 0010# 00100 00101 0011# 00110 00111 01### 01##0 01##1 01#0# 01#00 01#01 01#1# 01#10 01#11 010## 010#0 010#1 0100# 01000 01001 0101# 01010 01011 011## 011#0 011#1 0110# 01100 01101 0111# 01110 01111 1#### 1###0 1###1 1##0# 1##00 1##01 1##1# 1##10 1##11 1#0## 1#0#0 1#0#1 1#00# 1#000 1#001 1#01# 1#010 1#011 1#1## 1#1#0 1#1#1 1#10# 1#100 1#101 1#11# 1#110 1#111 10### 10##0 10##1 10#0# 10#00 10#01 10#1# 10#10 10#11 100## 100#0 100#1 1000# 10000 10001 1001# 10010 10011 101## 101#0 101#1 1010#

• 全体に -4 を加えると各行の下2桁が -4 ~ 4 になり、 上3桁が row, 下2桁が col に分解できる • (平衡三進数の切り捨ては四捨五入になるのだが、 通常の「0.5 足して切り捨てると四捨五入」の逆みたいな感じ) - - - - 00000 00001 0001# 00010 00011 001## 001#0 001#1 0010# 00100 00101 0011# 00110 00111 01### 01##0 01##1 01#0# 01#00 01#01 01#1# 01#10 01#11 010## 010#0 010#1 0100# 01000 01001 0101# 01010 01011 011## 011#0 011#1 0110# 01100 01101 0111# 01110 01111 1#### 1###0 1###1 1##0# 1##00 1##01 1##1# 1##10 1##11 1#0## 1#0#0 1#0#1 1#00# 1#000 1#001 1#01# 1#010 1#011 1#1## 1#1#0 1#1#1 1#10# 1#100 1#101 1#11# 1#110 1#111 10### 10##0 10##1 10#0# 10#00 10#01 10#1# 10#10 10#11 100## 100#0 100#1 1000# 10000 10001 1001# 10010 10011

その他の工夫点 • ひっくり返せるかをチェックする関数は用意していない。 あるのは 実際にひっくり返して問題なかったかを返す関数のみ • 試しに返してみて問題あったら終点から逆向きに同じ関数を適 用して元に戻す CMPI -34 JZ L1 MOVI A, -1 J L2 L1: MOVI A, 1 L2: ADDI 35 JP L1 MOVI A, -1 L1:

その他の工夫点 • 命令を1つでも削れるように謎の最適化を頑張る • e.g. ‘B’ (-55) なら -1, ‘W’ (-34) なら 1 を作りたいとき、 CMPI -34 // sign(A - (-34)) JZ L1 // sign == 0 ? MOVI A, -1 // else A = -1 J L2 L1: MOVI A, 1 // then A = 1 L2: 10 words ADDI A, 35 JP L1 MOVI A, -1 L1: // A += 35; sign(A) // sign > 0 ? // else A = -1 // then do nothing 6 words

THANK YOU FOR LISTENING! アセンブリのコード読みたければこちら↓ https://github.com/Kitchy-rikeden/libra-othello/blob/main/asm/othello.s

• https://github.com/Kitchy-rikeden/libra-othello/blob/main/asm/othello.s