最高のオセロ盤を作りたくて ○● #Rx

はじめに

SNS×オセロの話を書こうと思ったのですが、よく考えたらオセロ特有の話が少ないのでやめます ¹

今回は、最高のオセロ盤を求める旅を書きます。
設計的な話がメインです。記事内のコードは擬似的なものに過ぎません。²

ゴールは、「解析機能や盤面配置機能などのリッチな機能が可能」かつ「保守性が高い」、そんなオセロ盤を作ることとします。

段階的な構成になっています。
まとめはシンプルですが、そこだけ見てもだいたい伝わるかもです

1. 長さ64の配列って考えればいいんでしょ？

64 マスなんでしょ? 一次元配列でよくないです？

final board = List.filled(64, 'empty');
// 初期配置
board[23] = 'white'
board[24] = 'black'
board[31] = 'black'
board[32] = 'white'
// f5 に黒が着手
board[33] = 'black'

実装できる気しかしないですね。はい。
でも、なんか、「f5」という座標を「33個目」と表現するのではなく、「fの5」って解釈したい。そう思ったとします。
ということで、配列をネストさせてみましょう。

2. 二次元の配列で座標っぽさを出していく

final board = List.generate(8, (i) => List.filled(8, 'empty'));
// 初期配置
board[3][3] = 'white'
board[3][4] = 'black'
board[4][3] = 'black'
board[4][4] = 'white'
// f5 に黒が着手
board[4][5] = 'black'

[x][y] って感じで、なんだか座標っぽさが出たような気がします。
ほんとは別に必要ではないのですが、とりあえず次に進みます。
AI対局機能を入れることになったとしましょう。²

3. AI との対局機能

例えば αβ法を使って実装します。

最高です。一人で対局できちゃいます。これで大会に出なくても大丈夫
という冗談はさておき、更なる高みを目指し、もっと高速な解析機能を実現したくなったとします。

3. 解析を少しでもはやく

オセロ界隈では有名なソフトウェアである edax 等を見てみると、bitboard と宣っています。
それでは、ビットボードの概念を取り入れましょう。³

final initialPlayerBoard = 0x0000000810000000;
final initialOpponentBoard = 0x0000001008000000;

配列を使わずにオセロ盤を表現できてしまいました。もう配列には戻れない身体になります。
おそらく解析機能も少し改善されたことでしょう。

しかし、ここで大きな課題にぶつかります。

序中盤の解析精度が低い

終盤は読み切れるので正確な値を求められるものの、序中盤はそうはいかないです。
これは困ります。

4. 評価値の精度を高くしたくて堪らない

オセロを多少やってる方ならご存知かと思いますが、上記の課題を倒すために book という概念があります。事前に学習させて評価値の情報をためとくやつです。
つまり、その機能を実装し、かつ大量に学習させておけば良いということになります。

しかし、解析自体が目標でない場合(何らかのツールやサービス作ってるとか)は、既存の素晴らしきソフトウェアを己のアプリケーションに組み込んだ方が幸せになりやすいと思います。

ガチ勢の間では edax が主流で、オセロの完全解析は事実上終わってるレベルです。⁴
そして、edax は CUI なので、開発者にとっては嬉しい限りです。色々できます。
edax が採用候補の筆頭なのは間違い無いでしょう。

よし、それじゃあ edax を組み込もう! となっても、edax を外部から制御可能なように I/F 整えてライブラリ化するのは結構大変です。
筆者も作って各所でそれを利用していたのですが、C 弱者のヘッポコなので、公開できる品質にはなってないです。
ここで朗報なのですが、lavox さんが libedax を公開してくれています。
自作のなんかより遥かに整備されていて最高です。Richardさん,lavoxさん、ありがとうございます!

そんなこんなで、libedax を自身のアプリケーションに埋め込んで解析機能を edax に寄せます。

例えば Android の開発なら、JNI を使って Kotlin から C を呼び、そこから edax(というかlibedax) の API を叩きます。

libedax.kt

fun edaxInit() {
    nativeEdaxInit()
}

native-lib.cpp

extern "C" void
    JNICALL
    Java_com_done_sensuikan1973_othellode_LibEdax_nativeEdaxInit(JNIEnv *env, jobject thiz)
{
    edax_init();
}

とにかく、これでまた一歩幸せになりました。

5. あれ、私のオセロ実装いらなくない?

はい。残念ながらもう不要ですね。
edax を組み込んだ今、オセロのロジックを自前で持つ意味はほぼ無いと思います。
なぜなら、当然 edax にそれがあるので。

自前で実装したビットボードを捨てて、依存関係を整理します。

Your Code
|
edax : オセロに関するロジックの全てを担う

不要な実装がなくなって、また１つ幸せになりました。
しかし、旅はまだ長いです。

5. 「盤面配置機能もあるよね？」

解析機能なんていうリッチなものを備えてると、「盤面配置機能は当然ありそう」ってなりますね。わかります。

この機能自体は、特段難しいとかは無いと思います。問題はこの機能自体というより、全体的な依存関係,状態管理です。
おそらくここまでは「オセロをプレイする」を念頭に置いた設計になっているはずですが、この機能の登場により、オセロ盤に求められる処理が変わります。
Tap = 着手 だったのが Tap = 配置 になります。

実際にはもっと色んな機能が出てくるはずなので、雑に設計すると溺れます。(溺れたことあります)
状態管理 は重要なポイントなので、丁寧に倒したいところです。

個人的には BLoC + Reactive Extensions の考え方で組むのが好きなので、その話を書きます。

例えば、「edax との対局モードで、ユーザーが f5 をタップしました」
この時どんな処理が必要そうでしょうか?
数個羅列してみましょう。

着手処理を行う
- もし着手不可なら toast を出す
- 盤面の状態を更新する
- edax 側が着手するまでは、画面に「AI が考え中だよー」みたいなのを表示する
- 盤面の最善手を求めて、自動で着手する
- ユーザーが着手してから edax が着手するまでの秒数は、ユーザーが好きに設定できるようにしておきたい
黒と白の石数表示を更新する
現在の手番がどっちなのかを更新する
最終着手のマスに、赤いマークをつけておく
降参ボタンを押されたら、 AIの思考を止めさせて降参処理を進める

愚直に書いてみます。

void Tap(String coordinate) {
  blockBoardUi();
  if (!canMove) {
    showToast('$coordinate は置けないよー');
  }
  blackCount = getBlackCount();
  blackCountText = '$blackCount 石';
  whiteCount = getWhiteCount();
  whiteCountText = '$whiteCount 石';
  turn = getTurn();
  turnText = '$turn の番です'
  markUp(coordinate);
  wait(waitTime); // user が設定した秒数だけ、edax の着手を遅らせる
  .
  .
  .
}

...

BLoC + Reactive Extensions の考え方で整えて、保守性を獲得しにいきます。
BLoC というのは Business Logic Component のことで、アプリケーション固有のロジックです。

OthelloBoardUi : オセロ盤の UI。ボタンや画像、石数ラベルなど
OthelloBoardBloc : オセロ"盤" のロジック
LibEdax : "オセロ"のロジック

Reactive Extensions を取り入れて、以下のように宣言的に記述します。

othello_board_bloc.dart

/// 黒石の数を配信する (Stream)
ValueObservable<int> get blackDisc => _blackDiscController;
final _blackDiscController = BehaviorSubject<int>();

/// 着手したい座標を受け付ける場所 (Sink)
final moveController = PublishSubject<String>();

/// 受け取った座標に対して、いくつかのイベントを配信する
moveController.stream.listen((coordinate) async {
  final isSuccessful = await libEdax.move(coordinate);
  if (isSuccessful) {
    _blackDiscController.add(libEdax.getBlackDiscCount());
    // _whiteDiscController.add(libEdax.getWhiteDiscCount());
    // 他にも色々...
  }
});

othello_board_ui.dart

// f5 の場所を tap したら、それだけを BLoC に伝える
othelloBoardBloc.moveController.add('f5');

// 黒石の数の配信を聞いて、テキストを更新する
StreamBuilder<int>(
  stream: othelloBoardBloc.blackDisc,
  initialData: 2,
  builder: (context, blackDisc) {
    return DiscLabel(
        size: iconSize,
        discColor: Colors.black,
        discCount: blackDisc.data,
    );
  }
);

ポイントは、
BLoC 側は、黒石の数などを配信するが、それが何にどう使われるかは知ったこっちゃ無いよ。UI 側で自由に購読してどうぞ〜 な点と、
UI 側は「f5に着手したよ」だけを BLoC に伝え、それでどんなイベントが起きるかは知ったこっちゃ無い 点です。

これにより、Logic と UI の依存関係整理 + 状態管理の見通しが改善されました。⁵

ということで、盤面配置機能の追加がしやすくなりました。

6. edax じゃなくて XXX を使いたい！

ガチプロの方は edax を超えるものを作ってしまうかもしれませんし、あるいは他の誰かが作るかもしれません。
少なくとも筆者には無理です。ありがとうございました。そして、よろしくお願いします。

とにかく、edax を使うとは限らないわけです。(既成の book の質的に、実際にはほぼ edax になると思うのですが)
また、test を書く際に適切に Mock 出来ないようでは良い設計とは言えないと思います。

そして、↓に書いたように、ユーザーの設定値によっても色々挙動を変えなければいけません。

ユーザーが着手してから edax が着手するまでの秒数は、ユーザーが好きに設定できるようにしておきたい

というわけで、オブジェクトを注入するデザインパターンを採用します(Dependency Injection)。
まず、登場人物の名前を適切なモノに変えます。

OthelloBoardUi : オセロ盤の UI。ボタンや画像、石数ラベルなど
OthelloBoardBloc : オセロ"盤" のロジック
OthelloEngine : "オセロ"のロジック

そして、OthelloBoardBloc は、こんな感じで生成することになります。

final userSettings = Provider.of<UserSettings>(context);
final othelloEngine = Provider.of<OthelloEngine>(context);

OthelloBoardBloc(
  othelloEngine: othelloEngine,
  aiWaitTime: userSettings.aiWaitTime,
);

これで、オセロのロジックを担う Engine を都度決められますし、OthelloEngineMock なるモックを作って適切に test が書けるようになりました。

othello_engine_test.dart

OthelloBoardBloc(
  othelloEngine: OthelloEngineMock(),
  aiWaitTime: 3,
);

また、ユーザーの設定値 というオセロとは関係のないモノを、ちゃんとオセロの外に定義するようになっています。

以上により、依存関係や状態管理が整って幸せ度が増します。

7. 同じような処理を2回書くの疲れたよ?

iOS/Android のアプリを、例えば Flutter で開発しているとしましょう。
OthelloEngine の奥として edax を据えるでしょうから、C を呼び出す必要があります。
Dart と Swift/Kotlin と C を繋ぐ I/F を書かなきゃいけないわけですが、だいたいは同じような処理です。

まず、glue code に疲れたという思いが湧いてきます。そして、パフォーマンス的にもより良い(はず)の方法があります。
FFI(今回だと C の呼び出し)です。多くの言語でサポートされています。Flutter/Dart では最近の話です。
これにより、Dart > Swift/Kotlin > C となっているのを、Dart > C とできます。

何を何で開発しているかにもよりますが、FFI のサポート有無は、オセロの何かを作る際に考慮したい観点の１つだと思っています。

8. まとめ

図にするとこれだけのことを長々書いていました... 参考になれば嬉しいです。
旅はおわってないです。最近だと、画像の作り方とか悩んでます。

ちなみに、Flutter 向けライブラリとして、libedax を wrap して iOS/Android で使えるモノを作ったので、公開できるように質を上げていこうと思います。
と思っていたのですが、有難いことに dart:ffi が出てきたので、そっちに置き換えてからです...

これはこれでFlutter/Firebase関連のネタがいっぱいあるので、いつか書きたいなと思ってます。 ↩
ai... ↩
基礎情報としては、だいぶ昔の雑な記事ですが、https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43 とかがあります。 ↩
「人間が人間に勝つための情報」という意味で「事実上」と書いてます。 ↩
すごくざっくり書いてしまいましたが、詳細は https://qiita.com/sensuikan1973/items/4664864ae3b7a1fdadfa とかを見て下さい。 ↩