はじめに

最近マンカラというゲームに興味をもち少し遊んでみたのですが、どういった戦略で手を進めればよいかわからなかったので自分で思考エンジンを作ってみることにしました。

マンカラとは

Wikipediaによると「アフリカや中近東、東南アジアにかけて古くから遊ばれている、伝統的な一群のゲーム（ボードゲーム）の総称である。」とあります。「マンカラ」自体は総称なので異なるルールのゲームが数多くあるのですが、今回は「カラハ」と呼ばれるルールの思考エンジンを作ります。
Wikipedia(マンカラ): https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%82%AB%E3%83%A9

使用するプログラミング言語

今回はRustを使って実装しました。選定理由は高速に動作するからというのとRustの勉強のためです。プログラムが高速に動作すれば局面探索や後で説明する自己対局にかかる時間も短縮できるので実行速度は非常に重要な要素です。
また思考エンジンのパラメータ最適化のためにPythonを使っています。

ソースコード

ソースコードはGitHubで公開しています。Windows10 64bitで動作するバイナリも公開していますが、CUIなので操作しにくい点があることはご了承ください。
リポジトリ: https://github.com/dsanno/mancala

用語

この記事やプログラム内で使用する用語について説明します。
簡単な説明にとどめるので先にルールを読んでおくことをお勧めします。

用語	意味
pit	盤上で横２列に並んだ穴
store	盤上の両側にある２つの穴
seed	pit, storeに入れる駒または石
sow, sowing	自分のseedをpit, storeにひとつづつ入れていく動作
lap	選択したpitから取り出したすべてのseedに対してsowを行う動作、lapが自分のstoreで終わった場合には手番が変わらずもう1度lapを行うことができる。
capture	sowingが自分の空のpitで完了したときに、最後のseedと反対側にあるの相手のpitのseedを全て自分のstoreに入れる動作

思考エンジンの概要

思考エンジンの役割は「局面が与えられたときに最善と考えられる次の手を選択する」です。

機能

思考エンジンは以下の機能を備えています。

先読み
- アルファ・ベータ法による局面の先読みを行います。
局面評価
- 先読みの末端ノードでは独自の評価関数により局面評価を行います。
- 局面評価に使用するパラメータは機械学習によって最適化します。
定石
- 序盤の局面の評価は定石テーブルに登録しておき、探索しなくても評価値を得られるようにしておきます。

局面評価関数のパラメータ最適化方法

パラメータ最適化は以下の手順で行いました。

思考エンジン同士の自己対局を繰り返す。
1.の局面評価関数の出力が1.の対局結果に近くなるようにパラメータ最適化を行う。
1, 2を繰り返す

モジュール構成

思考エンジンは以下のモジュールで構成されています。

board: 局面管理モジュール。
- enum Turn: 手番を表すenum。
- struct Board: 局面を管理する構造体。
engine::evaluator: 評価関数モジュール。
- struct Evaluator: 局面評価を行う構造体。
engine::com: 局面探索(先読み)モジュール。
engine::position_map: 局面テーブル管理モジュール。
- struct PositionMap: 局面とその評価値を保持する構造体。

局面管理モジュール`board`を実装する

最初に局面の状態を管理するboardを実装します。

データ構造

マンカラ盤を構成するenum, structは以下の通りです。

pub const PLAYER_NUM: usize = 2;

#[derive(Copy, Clone, PartialEq, Debug)]
pub enum Turn {
    First,
    Second,
}

#[derive(Copy, Clone)]
struct BoardState {
    turn: Turn,
    stores: [isize; PLAYER_NUM],
    seed_states: [i64; PLAYER_NUM],
}

pub struct Board {
    state: BoardState,
    history: Vec<BoardState>,
}

enum Turn: 手番が先手にあるか後手にあるかを表します。
struct BoardState: 局面の状態を表します。
- turn: 現在の手番を表します。
- stores: 各プレイヤのstoreにあるseedの数を表します。
- seed_states: 各pitの中のseedの個数を表します。型がi64になっていますが少ない演算で複数のsowの結果を計算できるようにするためです。seed_statesの各バイトがpitの中のseed個数になっています。
struct Board: 局面と局面の履歴を表します。

関数

struct Boardは以下の関数を使えます。

関数	説明
`pub fn reset(&mut self)`	局面を初期化します。
`pub fn turn(&self) -> Turn`	現在の手番を返します。
`pub fn store(&self, turn: Turn) -> isize`	storeにあるseedの個数を返します。
`pub fn seed(&self, turn: Turn, index: usize) -> isize`	指定したpitのseedの個数を返します。
`pub fn is_over(&self) -> bool`	ゲームが終了しているかどうかを返します。
`pub fn play(&mut self, index: usize) -> Option<()>`	一手進めます。ルール上有効な手なら`Some(())`を、無効な手なら`None`を返します。
`pub fn undo(&mut self) -> Option<()>`	一手戻します。初期局面では局面を戻せないのでNoneを返します。
`pub(crate) fn seed_states(&self) -> [i64; PLAYER_NUM]`	`seed_state`を返します。後で説明する局面テーブルが利用します。create外部からは使うことを想定していないので`pub(crate)`をつけています。

また関連するものとして以下の関数を実装しました。

関数	説明
pub fn opponent_turn(turn: Turn) -> Turn	指定したプレイヤ(先番、後手番)と逆のプレイヤ返します。

注意する点として、playは一回のlapに該当します。マンカラでは一方のプレイヤが連続でlapを行うことがありますがこのときはlapの回数分playを呼び出す必要があります。またplayを呼び出した後に手番が入れ替わるかどうかは局面に依存します。

実装内容

play

playの実装は(選択したpitの位置, pitのseed個数)に対する(自分のseed_statesの差分、相手のseed_statesの差分、自分のstoreの増分)を配列にしておき、playを呼び出すと配列からそれぞれの値を読み取ってseed_statesとstoresに足すようにしました。これにより少ない計算回数で局面を更新することができます。配列はの中身はあらかじめ計算しておき、constとしてコードに直書きしました。
他にも手番が入れ替わるか、captureを行うか、終局したかのチェックを行っています。

undo

undoを呼び出すと一手前に戻しますが、まずplay呼び出し時にhistoryに現在のBoardStateをpush()しておきます。undoではhistoryをpop()して一手前の状態を取得します。

その他

その他の関数の実装は難しいものではないので割愛します。

局面評価関数を実装する

局面評価関数の概要

局面評価関数は局面状態を入力するとゲームの最終結果(自分のstore個数 - 相手のscore個数)の予測を出力するものとしました。
評価関数の出力の候補としては、最終結果(囲碁なら陣地の差分、オセロなら石の差分)の予測、勝率の予測、何かを基準とした相対的な値(例えば将棋で歩1枚を基準とした値)があります。囲碁プログラムは勝率、オセロプログラムは最終結果を予測することが多いです。将棋プログラムについては詳しくないのですが、歩の価値を基準とした評価値を使っているようですが、最近は勝率予測もあるんでしょうか？
マンカラでは10～20手先の完全先読みは難しくなく、比較的容易に最終結果を予測できると考えて最終結果を採用することにしました。

局面評価関数の構成

局面評価は(現局面の手番側のstore個数) - (現局面の相手側のstore個数) + (pit状態から予測した将来得られるstoreの差分)で行います。
現局面のstore個数は確定しているので将来得られるstoreをどう予測するかが鍵となります。
今回は以下の方法で行いました。

3個のpitのパターンを考える。
3個のpitはあるpitと向かい合ったpit、別のpitで構成される。
- 例えば先手番の一番左のpit、後手番の一番左のpit、先手番の左から3番目のpit
それぞれのパターンの部分的な評価値を計算する。
すべてのパターンの部分的評価値の合計を将来得られるsotre差分の予測とする。

式で表すと以下のようになります。

先手番のpitを左から(A1, A2, A3, A4, A5, A6)で表す、後手番のpitを(先手番から見て)左から(B1, B2, B3, B4, B5, B6)で表す

最終局面までに得られるstoreの差分予測 = ((A1, B1, A2)のパターンに対する評価値) + ((A1, B1, B2)のパターンに対する評価値) + ((A1, B1, A3)のパターンに対する評価値) + ...

この部分的なパターンは以下の点を考慮して決めました。

連続lapを考慮しているか
captureを考慮しているか
パターン数が膨大になりすぎないか

この手法を実装するにあたってパターンの個数を求めなければなりません。
単純に考えると3個のパターンの組み合わせの数は1個のpitの状態数の3乗になります。(実際にはseed数が48個という上限があるのでそれより少ない)
1個のpitの正確な状態数は今のところ不明ですし、数が多すぎる懸念があるので以下の15通りの状態を考慮することにしました。

pitが空
pitにseed1個
pitにseed2個
...
pitにseed13個
pitにseed14個以上

seed14個以上をまとめているのは、発生回数が少ないのと、seedが14個以上あるpitをプレイした場合連続lapが発生しないためです(sowが一周するので完了時に必ずseedが2個以上になる)。
すると3個のpitのパターンの個数は15 * 15 * 15 = 3375個になります。
3個のpitの組み合わせは6 * 5 / 2 * 4 = 60個になるので、全部で3375 * 60個のパラメータが必要になります。

データ構造

局面評価を行うための構造体struct Evaluatorは以下のように定義しました。評価用パラメータをVecで保持するだけです。

pub struct Evaluator {
    pattern_values: Vec<Vec<i32>>,
}

関数

struct Evaluatorは以下の関数を使えます。

関数	説明
`pub fn new() -> Evaluator`	全てのパラメータを`0`で埋めた`Evaluator`を生成します。
`pub fn load(file_path: &str) -> std::io::Result<Evaluator>`	ファイルからパラメータを読み込んで`Evaluator`を生成します。
`pub fn evaluate(&self, board: &board::Board) -> isize`	局面の評価値を返します。

実装内容

new

pattern_valuesを0で埋めるだけです。

load

ファイルからパラメータを読み込んでpattern_valuesに格納するだけです。
Rustでのファイル読み込みについてよく理解していないのですが、愚直に4バイトずつ読み込んではi32に変換する、という処理を繰り返しています。

evaluate

各パターンのパターンインデックスを計算してpattern_valuesから部分評価値を取得して足し合わせています。実際のコードは以下のようになっています。
SEED_TO_INDEX_0等はseed個数からパターンインデックスの差分を得るための配列です。(pit_a, pit_b, pit_c)のパターン番号はSEED_TO_INDEX_0[pit_aのseed個数] + SEED_TO_INDEX_1[pit_bのseed個数] + SEED_TO_INDEX_2[pit_cのseed個数]になります。

    pub fn evaluate(&self, board: &board::Board) -> isize {
        let turn = board.turn();
        let opponent = board::opponent_turn(turn);
        let seed_states = board.seed_states();
        let seeds = seed_states[turn as usize].to_le_bytes();
        let opponent_seeds = seed_states[opponent as usize].to_le_bytes();

        let mut value = 0;
        value += self.pattern_values[0][SEED_TO_INDEX_0[seeds[0] as usize] + SEED_TO_INDEX_1[seeds[1] as usize] + SEED_TO_INDEX_2[opponent_seeds[0] as usize]];
        value += self.pattern_values[1][SEED_TO_INDEX_0[seeds[0] as usize] + SEED_TO_INDEX_1[seeds[1] as usize] + SEED_TO_INDEX_2[opponent_seeds[1] as usize]];
        ...
        value += self.pattern_values[58][SEED_TO_INDEX_0[seeds[4] as usize] + SEED_TO_INDEX_1[opponent_seeds[4] as usize] + SEED_TO_INDEX_2[opponent_seeds[5] as usize]];
        value += self.pattern_values[59][SEED_TO_INDEX_0[seeds[5] as usize] + SEED_TO_INDEX_1[opponent_seeds[4] as usize] + SEED_TO_INDEX_2[opponent_seeds[5] as usize]];

        (board.store(turn) - board.store(opponent)) * VALUE_PER_SEED + value as isize
    }

注意すべき点としては

現在の手番から見た評価を返す
- これは現在の手番を基準としたほうが良いというよりは、どちらのプレイヤを基準としているか理解して実装しないと先読みの処理などの思考エンジンの実装を間違えてしまうという意味です。
最後に((現在の手番のstore個数) - (相手のstore個数)) * VALUE_PER_SEEDを足す
- VALUE_PER_SEEDはseed1個の価値です。評価値は「seed3.45個分」のようになるのでseed1個の価値をあらかじめ決めておきます。VALUE_PER_SEEDは100としました。

局面テーブルを実装する

局面テーブルとは、局面と評価値やその他の情報を保持するテーブルです。
定石の検索、過去対局で現れた局面の検索のために使います。
局面探索のキャッシュ(局面探索中に評価済みの局面が現れたら局面テーブルに保存されている評価値を返す)に使うこともできますが、今回の実装ではキャッシュは実装していません。

データ構造

局面テーブルのデータ構造は以下のようになっています。

pub struct PositionKey(i64, i64);
pub struct PositionValue {
    pub value: i32,
    pub visit: i32,
}

pub struct PositionMap(HashMap<PositionKey, PositionValue>);

struct PositionKey: 局面テーブルの検索キーです。中身は(手番側のseed状態, 相手側のseed状態)です。
struct PositionValue: 局面テーブルに登録される値で局面情報です。valueは手番がある側から見た評価値を、visitは局面の発生回数を表します。
struct PositionMap: 局面テーブルとなる構造体です。

関数

PositionMapでは以下の関数を使えます。

関数	説明
`pub fn load(file_path: &str) -> std::io::Result<PositionMap>`	ファイルから局面テーブルを読み込んで`PositionMap`を生成します。
`pub fn save(&self, file_path: &str) -> std::io::Result<()>`	局面テーブルをファイルに保存します。
`pub fn len(&self) -> usize`	局面テーブルに登録されている局面数を返します。
`pub fn get(&self, board: &Board) -> Option<PositionValue>`	局面テーブルから指定した局面の情報を取得します。
`pub fn insert(&mut self, board: &Board, value: isize) -> ()`	局面を登録します。

実装内容

注意すべきこととして、PositionMapに登録する局面は以下のように不要な情報を除いています。

手番情報を持たない
- 登録時に手番がある側から見た局面、評価値となるように正規化します。
store個数を持たない
- 両者のstore個数が0と仮定した場合の評価値となるように正規化します。
- 具体的には局面テーブルに登録される評価値 = 局面の評価値(手番から見た) - 手番側のstore個数 - 相手側のstore個数となります。

get

与えられた局面からPositionKeyを生成し、HashMapからPositionValueを取得して正規化して返します。局面が見つからなかった場合にはNoneを返します。

insert

与えられた局面と評価値から正規化したPositionKey、PositionValueをHashMapに登録します。
PositionValueのvisitは登録済みの値をインクリメントします。

その他

その他の関数については特筆すべきことはないので割愛します。

局面探索(先読み)を実装する

局面探索はcomモジュールで行っています。

関数

comモジュールは以下の関数を提供します。

関数	説明
pub fn find_best_move(board: &mut board::Board, depth: isize, evaluator: &evaluator::Evaluator, position_map: &position_map::PositionMap, explore: bool) -> Move	与えられた局面から最善と考えられる手を探索します。
pub fn register_position_map(board: &mut board::Board, position_map: &mut position_map::PositionMap, value: isize) -> ()	局面テーブルに局面を登録します。このとき局面テーブルに登録されている局面がゲーム木を構築して評価値がMini-Max値になるようにします。

実装内容

find_best_move

先読みを行って最善と思われる手を探索します。基本的にはアルファ・ベータ法による探索ですが以下のような処理を加えています。

子ノードのソート

探索時に子ノードを評価値の高い順にソートすると、枝刈りが多く発生して探索効率が良くなります。アルファ・ベータ法を使うプログラムではよく行われていると思います。

読みの浅い部分では子ノードの静的評価を行ってソートする
- 子ノードを探索するときに、まず1手だけ進めて局面評価を行い1手戻すという処理を全ての手に対して行います。そして評価値の高い子ノードから順番に探索します。
読みの深い部分ではヒューリスティックな方法で子ノードをソートする
- ヒューリスティックな方法といってもたいしたことはしていなくて、storeに近いpitから探索を行っているだけです。マンカラではstoreに近いpitの方が良い手になりやすいようです。

定石探索

PositionMapに登録されている手を定石として利用します。以下の2通りの方法で利用しています。

通常の対局
- 1手進めた局面がPositionMapに局面が登録されていたらそれを最善として探索は行いません。
- 複数の手に対して局面が登録されている場合には評価値が最大となる手を選びます。
自己対局
- 自己対局の場合は様々な手を試して局面の多様性を大きくしたいのでPositionMapに登録されている局面を避けるようにして手を選択します。
- ただしすべての手に対して局面が登録されている場合にはモンテカルロ木探索におけるUCTを使って手を選択します。(Wikipedia: モンテカルロ木探索)。UCTを使うことで自己対局時に有望な手を中心に幅広い手を選択します。
- 具体的には子ノードの評価値を$$ v + c \sqrt{ \frac{\ln{N}}{n}} $$ とします。$v$は子ノードの局面評価値、$n$は子ノードの訪問回数です。$N$は理論的にはゲームの実行回数なのですが、実装上の都合でPositionMapの登録局面数としました。$c$は定数で大きくすると幅広い手を選ぶようになり、小さくすると比較的同じ手を多く選ぶようになります。$c$は32や96などの値をいくつか試しました。

register_position_map

PositionMapに局面を登録します。
このときに単純に登録するのではなく、以下のような処理にしています。
この処理を行うとPositionMap内でゲーム木を構築することができ、登録局面の評価値はそれより先の局面のMini-Max値になり評価値の精度が高まります。

登録局面から1手進める。
1手進めた局面がPositionMapに登録されていた場合、その評価値を覚えておく。
1, 2を全ての手に対して行い評価値の最大値を現局面の評価値とする。
1手進めた局面が1つも登録されていない場合には、渡された評価値を登録する。

自己対局とパラメータ最適化を繰り返す

以下のようにして思考エンジン同士の自己対局とパラメータ最適化を繰り返しました。

思考エンジン同士の自己対局を行い対局で現れた局面をPositionMapに登録する。局面評価値はゲームの最終結果とする。
自己対局を繰り返す。
ある程度対局を繰り返したらPositionMapに登録されている局面と評価値のセットを使ってパターン評価値を最適化する。
1～3を繰り返す。

パターン評価値の初期評価値は0で埋めてもいいですしランダムな小さい値にしてもよいと思います。
0で埋めた場合には自分のstoreと相手のstoreのseed数差分の最大化を目指すGreedy戦略になりますが、これでもけっこう強いです。

どこまで強くなったのか？

パラメータ最適化によって相当強くなったと思います。
定石もけっこう充実しましたし20手くらいの先読みなら数秒で完了するのでほぼ完璧な手を打てるのではと期待していますが実際のところ人間の強豪や完璧なプレイと比べるとどの程度かは不明です。
比較対象としてインストールしてみたスマホアプリには先手でも後手でも勝てるようになりました。

マンカラの分析はどこまで進んでいるのか

マンカラの思考アルゴリズムはどこまで進んでいるのか気になって調べてみたのですが、英語版Wikipediの"Kalah"によると今回扱ったルールは既に完全解析がなされています。
https://en.wikipedia.org/wiki/Kalah
状態数がそこまで多いわけではないので終盤データベースを使って完全解析することができたようです。

最後に

強そうな思考エンジンを作ることができてよかったです。
ただCUIしか用意していないので使いづらいですし対局しても味気ないのでGUIが欲しいです。
できればアニメーションつきのGUIを作りたいですね。