「ライナー・クニツィアのキングダム」の盤面認識と最小費用流問題

最近の日本では、アナログゲームとかボードゲーム（ボドゲ）とか言われる娯楽の人気が高まってきているようです。ボードゲームにはアナログならではの独特の魅力があるのですが、一方で、往々にして機械的にできるような作業がめんどくさいことがあり、得点計算もその1つです。

今回は、「ライナー・クニツィアのキングダム」というボードゲームを題材に、画像認識を駆使して盤面を認識するプログラムを書きました。盤面のどこがどんな状態か分かると、点数計算の自動化につなげることができるでしょう（そこまではできませんでしたが）。

ちなみに筆者は機械学習エキスパートではないので、あくまで、やってみたよ的な内容になります。実装自体は楽しかったですが、 それほど良い結果が出たわけではない点には予めご留意ください。

「キングダム」について

巨匠であるクニツィアの古典的名作の1つに、キングダムというタイトルがあります。ゲームのルールはざっくり言ってこんな感じです（今回のお題に必要な範囲でのみ説明します）。タイルと城をうまく配置して高得点を狙うボドゲです。

• ゲームに参加するプレイヤーたちは順番にタイルを山からランダムに引き、5x6のマス目のどこかに配置する
  • タイルには-5から+6までの値が割り振られている
• 特殊効果を持つタイルがいくつかある。例えば、金鉱タイルは同じ列のタイル値を2倍にする
• タイルを配置するかわりに、自分の城コマを置いてもよい
  • 城にはレベル（1から4）がある
• 自分の城と同じ縦列横列にあるタイルの値の合計に、城のレベルを掛けた値が、自分の点数になる

一例ですが、以下の場合は青プレイヤーは、青のレベル3城から、横列に関して$(1+6-3) \times 3=12$点、縦列に関して$(4 \times 2) \times 3 = 24$点を得ています。まだまだ空きマスがあるので点数の変化はありそうです。

キングダムはとてもよくできたボドゲなのですが、点数計算がややこしいという問題があります。縦と横を全部足して城のレベルを掛ける、という操作を城の数だけやらないといけない上に、特殊効果の処理もやらねばなりません。

盤面認識をしたい

さて、このボドゲでの点数は盤面から一意に定まるので、画像認識等を駆使して自動計算できるのではと考えました。
もっとも、そういったタスクを例えばアプリにするのはそれなりに大変なので、そもそもそういうことが技術的に可能か調べたいという動機を持ちました。

この記事ではこんな問題を解くことを考えます。

• 入力として盤面の写真画像が与えられたとする
• 画像から盤面の状況を読み取り、どのマスにどういったタイルが置かれているか認識する

筆者は画像処理とか機械学習とかについて素人ですが、これぐらいなら比較的簡単にできるのでは？ と思い取り組みました。

アルゴリズム/実装

まずは画像認識によって盤面を読み取る所です。盤上の個々のオブジェクトを認識するのが難しそうだったので、そこについて検討しました。

今回はディープラーニングというやつを触ってみたかったのですが、教師付き機械学習をさせるには学習用のデータセットが必要です。そこで、タイルを色々な角度から動画撮影し、そこから合計2000フレーム程度の静止画を切り出し、それにdata augmentationを適用することでデータセットとしました。

さらに、複雑なネットワーク全体を学習させるのではなく、ImageNetで学習済みの重みを流用して転移学習させるように構成します。つまり、重み学習済みモデルの一番上の層を抜いて全結合層を足し、そこだけを学習させます。

実装にはKerasを使いました。転移元のネットワークとしてMobileNetV2を使っている深い理由はありません。「モバイルっていうぐらいだし軽そう」程度の気持ちでした。

label_castle = ['tile_castle' +
                str(i+1)+c for c in ['b', 'r', ] for i in range(4)]
CLASSES = [
    'tile_-1', 'tile_-2', 'tile_-3', 'tile_-4', 'tile_-5', 'tile_-6',
    'tile_1', 'tile_2', 'tile_3', 'tile_4', 'tile_5', 'tile_6',
    'tile_dragon', 'tile_goldmine', 'tile_mountain', 'tile_wizard',
] + label_castle
NUM_CLASS = len(CLASSES)
INPUT_SIZE = 96

def load_model():
    base = MobileNetV2(include_top=False, input_shape=(
        INPUT_SIZE, INPUT_SIZE, 3))
    top_model = Sequential()
    top_model.add(Flatten(input_shape=base.output_shape[1:]))
    top_model.add(Dense(128, activation='relu'))
    top_model.add(Dropout(0.5))
    top_model.add(Dense(NUM_CLASS, activation='softmax'))

    model = Model(inputs=base.input, outputs=top_model(base.output))
    return model

こんな感じのモデルを学習させました。学習の過程はよくあるものなので省略しますが、最終的にvalidation accuracy=0.9程度の分類器が得られました。

これにてタイル画像（と城）の分類器が手に入りました。これを使って盤面をどう認識させるのかという課題は残りますが、今回は画像を機械的に5×6分割してそれぞれをタイルとみなし、分類器に入力することにしました。

画像認識の実行例を、入力画像とスコアのTop3の形で示します。

画像	結果（スコアTop3）	結果について
	('tile_1', 0.7549042), ('tile_dragon', 0.20605816), ('tile_-6', 0.033933274)	Top1が正しく+1のタイルであると認識されています。
	('tile_4', 0.56890464), ('tile_3', 0.3660375), ('tile_-6', 0.060791533)	迷っていますが+4のタイルと誤認識しています。文字部分が欠けているのが影響しているのかもしれません。
	('tile_castle1b', 0.6946332), ('tile_castle2b', 0.29654786), ('tile_castle3b', 0.008818952)	レベル1城だと認識されていますが、これは塔が3つあるのでレベル3城です。

誤認識については、そもそも文字部分が欠けているなど、入力画像の品質が影響しているのかもしれません。このように、データセットはそれほど品質のよくない画像が結構な割合で含まれています（もうちょっと丁寧に作ったほうがよかったと反省しています）。
また、そもそも学習データが足りてないのかもしれません😥が、このまま一通り作ってみたかったので続けます。

タイル認識スコアからの盤面認識

前節までで得られたのは、全てのマスについて「マスのタイルがxxxだと思われるスコア」です。これを元に、スコアから盤面の状態を確定させる問題を解きます。ゲームの性質より、タイルの置かれ方にはいくらかの制約が与えられています。

• タイルの枚数以上に当てはめをする意味はない。例えば、金鉱タイルが3箇所にあるという当てはめは成立しないので除外したい
• 確定した盤面は、スコアが最大化されていてほしい。このとき、スコアは和でなく積が妥当
  • 画像認識ではsoftmaxによる分類問題を解いたので、スコアは一種の確率と解釈できる
  • 最もそれらしい解の出力としては、そのタイル並びになるという確率を最大化したい。それは全てのマスのスコアの積となる

この組み合わせ最適化的な問題は、たぶん解法があるだろうけどよく分からない……ので、競プロ勢に聞いたところ一発でした。

• スコアの積を最大化する問題は、スコアの対数の和を最大化する問題だと考えられる
• 和を最大化する問題は、最小費用流問題に還元できる

なるほど……？？？ 対数変換と最小費用流問題について、それぞれ簡単に見ていきます。

積の最大化は対数和の最小化

前者についてはごく簡単です。変数$x_1, x_2, \cdots, x_n \in (0, 1]$があり、それらの積

$$
s = \prod_{i=1}^{n} x_i
$$

が最大となるとき、対数をとった

$$
\log s = \sum_{i=1}^{n} \log x_i
$$

もまた最大となります。なぜなら対数関数は（0より大きい範囲で）単調増加関数だからです。つまり、元の問題に戻すと、全てのスコアを対数関数に通した値の合計値が最大になるような組み合わせを探せばいいわけです。

筆者はあまり理解していないですが、統計学の最尤推定で、尤度関数ではなく対数尤度関数を考えるのと同様の方針に見受けられます。そもそも、この記事で解きたい問題が（組合せ最適化的な色彩を帯びつつも）最尤推定と呼べるのかもしれません。

ちなみに数値計算上のテクニックのような話になりますが、$x_i$が$0$になってしまうと対数が取れなくなるので、$x_i$には微小な値を加えて計算します。

最小費用流問題

最小費用流問題は、エッジに対して費用と流量という属性が付いたグラフ上の始点〜終点間について、ある流量を満たし費用が最小となる経路を見つける問題です。記事の本題から外れてしまうので理論に深入りはしません。ここでは解きたいタイルの問題が、グラフに還元できることを確認します。

問題をグラフ表現できたなら、最小費用流問題にはソルバがあるのでそれを使えば解けます。
https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.max_flow_min_cost.html#networkx-algorithms-flow-max-flow-min-cost

それでは問題を小さくして説明します。
タイルA, Bがそれぞれ2枚あり、タイルを置くマスは3箇所あったとします。各マスにはタイルAのスコアとタイルBのスコアが与えられています。

num_A = 2
num_B = 2
tile_score = [(0.95, 0.05), (0.3, 0.7), (0.6, 0.4)]  # それぞれのタプルは (Aのスコア, Bのスコア)

この例だと、例えば1つめのマスは、とてもAっぽいということを表しています。
タイル配置の問題は、次のようなグラフで表すことができます。

import math
import networkx as nx

num_A = 2
num_B = 2
tile_score = [(0.95, 0.05), (0.55, 0.45), (0.6, 0.4)]  # それぞれのタプルは (Aのスコア, Bのスコア)

G = nx.DiGraph()
S, E = 0, 100  # 始点と終点
tile_A, tile_B = 1, 2  # tile ID

def score(x):
    """
    max_flow_min_costは整数重みでのみ動作保証されているらしいので、
    定数倍である程度の精度を引き出してから切り捨てる。
    また、xが0でも式が壊れないように、微小な値を足す。
    """
    x = -(10000 * math.log(x + 0.0001))
    return int(x)


# S -> tiles
G.add_edge(S, tile_A, capacity=num_A)
G.add_edge(S, tile_B, capacity=num_B)
# tiles -> scores
G.add_edge(tile_A, 10, capacity=1, weight=score(tile_score[0][0]))
G.add_edge(tile_B, 10, capacity=1, weight=score(tile_score[0][1]))
G.add_edge(tile_A, 20, capacity=1, weight=score(tile_score[1][0]))
G.add_edge(tile_B, 20, capacity=1, weight=score(tile_score[1][1]))
G.add_edge(tile_A, 30, capacity=1, weight=score(tile_score[2][0]))
G.add_edge(tile_B, 30, capacity=1, weight=score(tile_score[2][1]))
# scores -> E
G.add_edge(10, E, capacity=1)
G.add_edge(20, E, capacity=1)
G.add_edge(30, E, capacity=1)

# network flow
mincostFlow = nx.max_flow_min_cost(G, S, E)
mincost = nx.cost_of_flow(G, mincostFlow)
print(mincostFlow)
print(mincost)

すなわち

• タイル数の制約を表すため、Sからタイルの種類ごとに、タイルの数だけのcapacityを持ったエッジを張る
• タイルの場所によるスコアを表すため、タイルの種類からタイルの場所を表すノードまで、タイルのスコアだけのweightを持ったエッジを張る

こういった形で解きたい問題をグラフで表現しています。

構築したグラフに対しての実行結果を見てみます。

{0: {1: 2, 2: 1}, 1: {10: 1, 20: 0, 30: 1}, 2: {10: 0, 20: 1, 30: 0}, 10: {100: 1}, 20: {100: 1}, 30: {100: 1}, 100: {}}
13599

1: {10: 1, 20: 0, 30: 1}はタイルAが場所10と30で選択されたことを、2: {10: 0, 20: 1, 30: 0}はタイルBが場所20で選択されたことを表します。
どの場所についてもタイルは「Aっぽい」わけですが、Aは2つまでという制約がうまく働いているのが見て取れます。

ここまでで、盤面から各場所のスコアを出し、スコアから最もそれらしいタイルの当てはめをするアルゴリズムが手に入りました。次の節では実際に動かした結果を見てみます。

実行例

入力としてはこの画像を使いました。

そして出力として、次の結果を得ました。 認識ミスしている箇所を太字 にしてあります。

1	2	3	4	5	6
tile_3	tile_1	tile_castle2b	tile_castle3b	tile_castle1b	tile_6
tile_2	tile_castle2b	tile_wizard	tile_-4	tile_mountain	tile_dragon
tile_castle3r	tile_5	tile_castle4b	tile_-6	tile_5	tile_castle1b
tile_4	tile_castle1b	tile_-2	tile_2	tile_6	tile_-3
tile_1	tile_mountain	tile_goldmine	tile_castle4r	tile_-1	tile_4

全体の正答率としては$21/30 = 0.7 $です。実用的と言うにはいま一歩でしょうか。タイル識別の段階ではaccuracy=0.9程度だったはずなので、学習に何らかの不備があること（過学習が起きているなど？）が示唆されます。

先に説明した最小費用流問題の実装は効いているのでしょうか？ それぞれの箇所のスコアを確認してみたところ、例えば3行目1列目ですが

('tile_dragon', 0.9111946)
('tile_castle3r', 0.074532524)
('tile_castle2r', 0.008960187)

このように画像認識ではdragonと認識されている結果が、レベル3城であると置き換わっています。正答はレベル2城なので、もうちょっとですね。異常な盤面にならないことが保証されているとはいえ、スコアがある程度は正しくついていないと正確な当てはめは難しいことも分かります。

まとめ・感想

ゲーム盤面の認識を、タイルの画像認識とグラフの問題に還元することで解いてみました。

素人がちょろっと作業するだけで、完成度がそれなりのものなら簡単にできるんだなーというのが最初の感想です。画像認識に関して「やってみた」記事やサンプルコードは巷に溢れています。書籍も沢山出ています。しばしば魔術的なパラメータをたくさん持った謎のアルゴリズムを使うことになりますが、触ってみる程度ならブラックボックスとして扱えます。

つまり、一体何からすればいいのか分からない状態にはならなかったように記憶しています。

ただ一方で、難しさにも直面したお題だったかなと思っています。

• おそらくはデータの量・質ともに問題がありそうだが、多数の良質なデータを集めるのはかなり大変
• しかしそこを手抜くと微妙な結果になって跳ね返ってくる（微妙なデータへのアルゴリズム的な対応はなかなか難しそう）

改善点は多数あります。とはいえ解きたい問題を複数分野のアルゴリズムに還元できたのは、筆者的にはとても満足できる体験でした。

参考資料・出典

• ライナー・クニツィアのキングダム 完全日本語版
• 『実践 Deep Learning ―PythonとTensorFlowで学ぶ次世代の機械学習アルゴリズム』