初めてのオセロAI

本記事では、初めてオセロAIを作るにあたっての覚書です。不正確な記述や改善の余地があるかもしれませんが、温かい目でご覧いただけますと幸いです。

はじめに

この記事では大学の課題の一環として、RustでオセロAIを作ることを最終目標としています。

私のスペックは以下の通りです。

• Rustは何もわからない
• 競技プログラミング(Algo)でC++はある程度書いた経験がある
• 機械学習やAIの分野はAHCを除けば初めて

以下では、実際に私が取り組んだ順にフェーズを分けて、何をしてきたかを紹介したいと思います。

Phase0: Rustの学習

Rustをいじるのは初めてだったので、まずはRustの習得から始めます。正直、勘でも一定程度は書けるとは思いますが、最近流行りの言語なので、せっかくの機会に体系的に学習してみようと思いました。

なぜか¹元々Rustの環境構築はされていたので、すぐに言語仕様の習得に移ることができました。

今回は大規模な開発にはならなそうだったので、ある程度限定的に、Rustツアー様にお世話になりました。実行環境がサイト上にあり、非常にわかりやすくかつ手軽に学ぶことができます。

Rustの仕様を私が説明しても、Rustツアー様の下位互換になるだけですので、素人目線の感想だけ載せておきます。

• 全体的に関数型言語を関数型っぽくないように隠そうと頑張っている部分が多い
• (特に型において)痒い所に手が届く機能が多い
  • ただ(特に文字列周りは)初学者にはちょっと難しい
• 所有権システムは大規模開発にかなり向きそう
• オブジェクト指向的部分も(少なくとも私が学んだ範囲では)C++に比べてかなり直感的

のような感想を抱きました。最近Rustが流行るのも納得だと思います。

Phase1: ボードの実装~最低限のAI

まずはオセロのルールを実装しなければ始まりません。
これから探索を回すことを考えると、

struct InnerBoard{
    my_board : u64,
    opponet_board : u64
}

のようにそれぞれのu64で自分と相手のボードを管理したいです。

また、次の処理を高速に行いたいです。

• 駒を置く処理
• 自分/相手の駒を数える処理
• 自分/相手の置けるマス目の列挙
• 盤面の各マスに重みを設定し、u64を0と1の列とみなした時に内積を計算する²

方針としては全て同じで、列や行、斜めはたかだか8なので、全て前計算します。
複雑なbit演算に心が折れそうになりましたが、頑張ります。

特に難しいのは、列や斜めのマスの情報を下位8bitに縮約することで、これは次のようなビット演算で達成できます。

const MASK1 : u64 = 0x0100010001000100;
const MASK2 : u64 = 0x0001000100010001;
const MASK3 : u64 = 0x0003000000030000;
const MASK4 : u64 = 0x0000000300000003;
const MASK5 : u64 = 0x0000000f00000000;
const MASK6 : u64 = 0x000000000000000f;
fn shrink_bit_8(data: u64) -> u64 {
    let t1 = ((data & MASK1) >> 7) | (data & MASK2);
    let t2 = ((t1 & MASK3) >> 14) | (t1 & MASK4);
    let t3 = ((t2 & MASK5) >> 28) | (t2 & MASK6);
    return t3;
}

また、評価関数は暫定的なものとして、置ける位置と自分の石の数のシグモイド関数による重み付け和として実装しました。
現状は一手も読んでいないので非常に弱いです。(ランダム相手に2/3ほどで勝てる程度の強さです。)

Phase2: ネガスカウト法

探索アルゴリズムとしては、現在のAIで非常に一般的となっているネガスカウト法を採用しようと思いました。

ネガスカウト法は、探索中に興味のある評価値の範囲を指定して探索するアルファ-ベータ法の改良です。、「予測値³」を用いて最良の選択肢以外の探索は有望かどうかを見て⁴から本格的な探索を行うことで、全体的な探索を軽くしようとするものです。

さらに、オセロにおいては同じ盤面を何回も探索することが予想されるため、盤面をXOR-shiftの改良でハッシュすることによってキャッシュを持つようにしました。アルファ-ベータ法の性質により、評価値は厳密値ではなく、〇〇以上/以下のような形で得られることもあるので、それを管理するフラグが必要です。これによって評価回数を一定程度減らすことができます。

一例にキャッシュに乗せた情報を下に添付します。

pub struct CacheElement {
    pub my_board: u64,
    pub opponent_board: u64,
    pub depth: u8,
    pub next_move: u8,
    pub value: f32, // 評価値
    pub exact: bool,
    pub complete: bool, // 読み切ったか
    pub lower_bound: bool,
    pub upper_bound: bool
}

以下は中盤の例ですが、現在の実装でもおよそ1秒間に10万〜20万盤面ほど読めていることがわかります。

2025-07-21 20:58:22 - AI Thinking
O: 22 pieces, X: 14 pieces
  ABCDEFGH
1 OOOOOOO·
2 OOXXXOX✓
3 OOXOOX✓✓
4 OOXOXXX✓
5 OOXXX✓✓✓
6 OOX✓✓✓··
7 O·✓✓····
8 ········
Placeable: H2 G3 H3 H4 F5 G5 H5 D6 E6 F6 C7 D7
Remaining time: 15976 ms, Allocated time: 1141 ms
Depth 1: nodes=15, evals=14, score=10.00, move=50
Depth 2: nodes=36, evals=18, score=11.01, move=51
Depth 3: nodes=237, evals=162, score=17.00, move=50
Depth 4: nodes=433, evals=198, score=17.00, move=50
Depth 5: nodes=2370, evals=1727, score=17.00, move=50
Depth 6: nodes=5392, evals=2787, score=17.00, move=50
Depth 7: nodes=29499, evals=23316, score=16.00, move=50
Depth 8: nodes=57798, evals=31453, score=16.99, move=50
Search completed: Total nodes=95780, Total evals=59675, Ratio=62.30%
Final: Depth=9, Best move=50, Score=16.99, Finished=false
End : 2025-07-21 20:58:23

2025-07-21 21:13:02 - AI Thinking
O: 18 pieces, X: 15 pieces
  ABCDEFGH
1 OOOOOOOO
2 OOOOOOO✓
3 ✓XXXOOX✓
4 ✓XXXXOX✓
5 ✓✓XXX✓X✓
6 ·✓✓✓X✓X✓
7 ····✓✓✓·
8 ········
Placeable: H2 A3 H3 A4 H4 A5 B5 F5 H5 B6 C6 D6 F6 H6 E7 F7 G7
Remaining time: 17629 ms, Allocated time: 1137 ms
Depth 1: nodes=20, evals=19, score=18.00, move=37
Depth 2: nodes=50, evals=20, score=18.00, move=37
Depth 3: nodes=285, evals=228, score=17.00, move=16
Depth 4: nodes=755, evals=348, score=17.00, move=16
Depth 5: nodes=4438, evals=3725, score=16.00, move=16
Depth 6: nodes=9939, evals=4941, score=17.00, move=37
Depth 7: nodes=71920, evals=60270, score=16.00, move=37
Depth 8: nodes=186754, evals=99433, score=17.00, move=37
Search completed: Total nodes=274161, Total evals=168984, Ratio=61.64%
Final: Depth=9, Best move=37, Score=17.00, Finished=false
End : 2025-07-21 21:13:03

また、ちょっとした工夫として、残り14手くらいに割り当てる時間を大幅に増加させて、一気に最後まで読み切らせる工夫をしています。⁵
まだ終盤特化の探索は実装していないので、これは後で実装します。

Phase3: 評価関数の実装

評価関数の実装には非常に頭を悩ませました。
具体的な案としては

• 盤面点 + その他簡単に計算できる特徴量のパラメータを重回帰分析
• ある特定の盤面パターンへの評価付け
• ニューラルネットワーク

の方法を考えました。
幸い、Egaroucidで公開されているnyanyan様の教師データ(https://www.egaroucid.nyanyan.dev/ja/technology/train-data/) を使用させていただくことで、さまざまな評価関数の学習を簡単に行うことができました。この場を借りて厚く感謝申し上げます。

まずは一番単純である盤面点 + その他簡単に計算できる特徴量のパラメータを重回帰分析を試みましたが、R^2が負になり、うまく行きませんでした。

その原因として、

• 強い多重共線性
  • あるマスとその周囲のマスの様子は全く独立ではない
  • 置ける場所の数もある程度盤面の広がり方に比例する
  • 解放度もおいているマスに強く依存する
• モデルの複雑性
  • 教師のモデルは非常に強力であるため、線形和では十分表現できなかった
• 浮動小数点誤差
  • (そもそもモデルがほとんど合致しなかったせいで)係数パラメータがとても小さい値になってしまい、行列計算の間に大きな相対誤差が発生した

ことが挙げられると思います。

次に、ニューラルネットワークを試してみました。ニューラルネットワークと盤面パターンの認識は本質的にかなり似ています。盤面パターンを陽に求めるのは、パラメータの次元数が多く非常に複雑で、それならいっそのことニューラルネットワークまで手を出してみようと思いました。

PyTorchをGoogle Colabで実行することにより、学習を行いました。
モデルとしては、入力がbit board + 自分の手番の3 * 8 * 8ノード、中間層として一層目32 * 8 * 8、二層目64 * 8 * 8ノード、結合層128ノードとしました。また、活性化関数としてReLUを用います。⁶

学習結果は、以下のようになり、十分良い学習ができたと思います。惜しむべくはGPU使用の制限上、5Epochまでしか学習を回すことができませんでしたが、決定係数が良いので一旦は満足です。

Epoch 5/5 [Training]: 100%|██████████| 19871/19871 [33:55<00:00,  9.76it/s, loss=54]
Epoch 5/5 [Validation]: 100%|██████████| 4968/4968 [07:28<00:00, 11.09it/s]
Epoch 5/5, Train Loss: 54.0366, Val Loss: 52.7002, Val R²: 0.8920

また、簡単な定石も実装しました。
12石以下の盤面全てについて最善手を調べ、定石としました。

工夫した点として、課題の制約としてコードのメモリ上限があったため、RunLength圧縮を行うことでnaiveの60%程度のバイト数に抑えました。⁷
これはnyanyan様のデータベースに13石以下の場面が評価値と共に全てデータベース化されていたため、容易に実装が可能です。

Phase4: 評価関数の改良、終盤の読み切り

Phase3では、評価関数に単純なCNNを用いていましたが、そうではなく、ある特定の石のパターンを認識した評価関数をつくると良いと聞いたので、評価関数の改良を試みました。

Michael Buro(1997)による論文を参考にし、パターンを入力とした1層のNNを評価関数にしました。

Phase3との30戦の対局の結果、21勝8敗1分⁸で、おおよそ72.5%ほどの勝率があることがわかりました。よって、Phase4は0.1%有意にPhase3より強く、elo-レーティングにして160ほどの差があることになります。

また、オセロの終盤は読み切ることができ、それによって終盤の悪手を防ぐことができます。今回は、石数の差に関心はなく、勝敗にのみ関心があったため、評価関数を1, 0, -1の三値にすることができ、これによって高速化が可能です。

読み切りを高速化するために、次の工夫を行いました。

• 速さ優先探索
  • 相手の候補手が少なくなるような着手を優先して探索する
• 勝敗による枝刈り
  • 一つでも「勝ち」の手を発見したら、最終石差に関わらず探索を打ち切る⁹
• キャッシュの利用
  • 盤面→勝敗の写像を保存するmapを持って、同一場面の探索結果を使い回すようにした
  • 副産物的に、2回目以降の探索を探索済み盤面ならば一瞬で終了できるようになった
• 空きマスが少ない時の特化
  • 空きマスが4マス以下の時はキャッシュを利用しない
  • 空きマスが1マスの時の判定を高速化する

以上の工夫によって、18マス空きの盤面ではほとんどの盤面で20秒以内の読み切りができるようになりました。盤面によっては20マス空きの盤面からの読み切りも20秒程度で終了することが確認できています。

そのほか期限の都合上実装できなかった工夫として、

• 並列実行
• 空きマスの偶奇を利用した探索順のリオーダリング
• 最終石差の評価、特に負け盤面での最善手の特定

があります。どうやら頑張ると24マス空きくらいまでの読み切りが可能らしいです(?!)。

できなかったこと

初めてのオセロAIで、色々と改善点があると思います。

代表的なものだと、

• 評価関数の軽量化、特に差分更新
  • NNを実装してからは1秒に5000盤面程度しか読めなくなっていた
• 定石の強化
  • 明らかに登場することがない盤面の定石を持っている反面、12石以降のよく出てくる盤面の定石は持っていない
• 評価関数の改良
  • GPUが欲しくなった
  • 並列実行をできるようにもしたかった
• SIMD
  • MACではSIMDを動かすことができなくて、デバッグ不可と判断した

最後に

ここまでお読みいただき、ありがとうございます。

初めてのAI作成だったので、色々と学びがあり、また目に見えて強さが変わるのはなかなか面白かったです。
定量的なレート評価をしたわけではないので、客観的な強さを語ることが難しいのですが、少なくとも私が軽くボコボコにされる程度の強さにはなりました。

次は作ったAIを使って初めてのアプリ制作をしてみたいと思っているので、完成したらまた記事を出します。その時はまた、よろしくお願いします。

追記:
記事が完成したので、よければこちらもお読みください。

また、作成したAIと遊べるサイトも作ったので、気が向いたら是非遊んでみてください。

1. 友人のRustaceanにいつの間にか勝手に入れられていました、ありがとう ↩

2. 評価関数に使いそうだと思いました ↩

3. 浅い探索結果や現在の場面の評価値を用いるなどのヒューリスティクスを用います ↩

4. ゼロウィンドウ探索 ↩

5. ただバグがあって、稀に読み切っているはずなのに評価値が悪化します ↩

6. 初めてのNNだったので、Gemini Proに頼り切りで、まだあまり理解できていません... ↩

7. その他些細な工夫は行なっていますが、重要でないため割愛します ↩

8. 引き分けは検定の上で無視しています ↩

9. 課題の要件上、石数の差は見られなかったので ↩