LoginSignup
TrendQuestionOfficial EventOfficial ColumnOpportunitiesOrganization
なぜ会社のノウハウをオープンにするの？TISの本部長に聞いてみた
10
5

More than 3 years have passed since last update.

オセロ Advent Calendar 2019 Day 15

@sensuikan1973

posted at

updated at

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

Rx,オセロ,ビットボード,Bloc,edax

はじめに

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

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

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

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

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'

実装できる気しかしないですね。はい。:innocent:
でも、なんか、「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対局機能を入れることになったとしましょう。2

3. AI との対局機能

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

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

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

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

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

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

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

:open_hands: 序中盤の解析精度が低い :open_hands:

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

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

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

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

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

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

そんなこんなで、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 = 配置 になります。

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

個人的には 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 の着手を遅らせる
  .
  .
  .
}

... :innocent:

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 の依存関係整理 + 状態管理の見通しが改善されました。5

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

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. まとめ

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

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

  1. これはこれでFlutter/Firebase関連のネタがいっぱいあるので、いつか書きたいなと思ってます。 ↩

  2. ai... ↩

  3. 基礎情報としては、だいぶ昔の雑な記事ですが、https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43 とかがあります。 ↩

  4. 「人間が人間に勝つための情報」という意味で「事実上」と書いてます。 ↩

  5. すごくざっくり書いてしまいましたが、詳細は https://qiita.com/sensuikan1973/items/4664864ae3b7a1fdadfa とかを見て下さい。 ↩

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
Sign upLogin
10
5