はじめに
最近マンカラというゲームに興味をもち少し遊んでみたのですが、どういった戦略で手を進めればよいかわからなかったので自分で思考エンジンを作ってみることにしました。
マンカラとは
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 | 盤上で横2列に並んだ穴 |
store | 盤上の両側にある2つの穴 |
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
に局面が登録されていたらそれを最善として探索は行いません。 - 複数の手に対して局面が登録されている場合には評価値が最大となる手を選びます。
- 1手進めた局面が
- 自己対局
- 自己対局の場合は様々な手を試して局面の多様性を大きくしたいので
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を作りたいですね。