センチュリー: スパイスロードは2017年に発売されたボードゲームです。
このゲームでは、プレイヤーはスパイスを表すトークンを入手・交換して自分の手元のトークン価値を高め、さらにはトークンから点数カードへの交換を狙います。トークンには黄・赤・緑・茶の4種類あり、おおむね後者になるほど価値が高く感じられます。

※ 詳しいルールについては適当に検索していただくと良いと思います。

点数カードは36枚あるのですが、カードによってコスト（入手に必要なトークンの種類・個数）は異なる上に、カードはプレイヤー間で取り合う対象になっています。最終的に得られた点数カードの合計点を競うゲームなので、どのカードが高効率なのか見極めるのが大切です。

ここからは、4色のトークンと勝利点カードに設定された勝利点の関係について調べてみます。巷にある考察だと、黄=1点、赤=2点、緑=3点、茶=4点としてカードの価値を論じることが多いように思います。

この点数の置き方は、素朴で暗算もしやすく取り扱いやすい仮定です。なんとなくカードリストを見るに、ゲームデザイナーもそう意図してデザインしているのかもしれません。しかしこれ、どれぐらい妥当なのでしょうか？

この記事では逆に、存在する点数カードから各色トークンの価値を推定してみることにします。つまり、他に妥当な価値の置き方が本当に無いのかどうかを、点数カードリストから調べます¹。

方針

4種類のトークンの価値を変数として、個々の得点カードの点数を計算してみます。計算した結果とカードの実際の勝利点を比較した結果が、最小になるような価値が、今回知りたい値です。

もう少しちゃんと定式化していきます。黄・赤・緑・茶トークンの価値がそれぞれ$v_y, v_r, v_g, v_b$点だったとします。このとき例えば、黄3個・緑2個で9点の点数カードがあったとすると、このカードの価値は$3v_y + 2v_g = 9$のはずです。同様の制約を全てのカードについて作って方程式を解けば$v_y, v_r, v_g, v_b$の値が求まる……と言いたい所ですが、カードは多数（36枚）あるので、この等式制約は満たせません。

かわりに、実際の勝利点との誤差を表す非負変数$z$を導入して、満たすべき制約を不等式の形で表します。上記の例だと$|3v_y + 2v_g - 9| \le z$とします。この$z$が最小になるように$v_y, v_g$を選ぶ問題を解くことにします。このやり方なら、点数カードが多数あっても各カードごとの$z$の総和を最小化する、という形で問題を整理できます²。

ちなみに$|x| \le z$を$-z \le x \le z$のように書き換えることで、絶対値は簡単に外せるのにも注目します。絶対値を外さないと線形計画問題になりません。

方針のまとめ

まとめると、今回解きたい問題は、次のような最適化問題になります。

黄・赤・緑・茶トークンの価値がそれぞれ$v_y, v_r, v_g, v_b$点、$i$番目のカードの黄・赤・緑・茶トークンがそれぞれ$c_{yi}, c_{ri}, c_{gi}, c_{bi}$個、$i$番目のカードの勝利点を$p_i$、非負の変数を$z_i$とする。次の式が最小になるような$v_y, v_r, v_g, v_b$の組を求めたい:

$$
\sum_{i=1}^{36} z_i \
$$

ただし次の制約がある:

$$
-z_i \le v_yc_{yi} + v_rc_{ri} + v_gc_{gi} + v_bc_{bi} - p_i \le z_i
\ (i = 1, 2, \dots, 36)
$$

この問題は線形計画法で扱われる最小化問題です。

解法の実装

筆者はあまり詳しくないですが、線形計画問題は古くから研究されているらしく、専用のソルバーも多数存在します。今回はPythonのライブラリであるPuLPを使って問題を記述し解かせることにしました。PuLPにはデフォルトでCBCというソルバーが組み込まれているようです。

コードは見るだけでなんとなく意味が取れると思います。変数をLpVariableで表し、それに演算子オーバーロードで制約を組み立てることができます。できあがった制約をLpProblemに渡して解かせるだけです。ドキュメントを読む限りだと、最初に渡した式が最小化したい式になるようです。

import pulp
import csv

with open("CenturySpiceRoad_PointCards.tsv") as f:
    # 各色の価値
    yv = pulp.LpVariable("YellowValue", 0)
    rv = pulp.LpVariable("RedValue", 0)
    gv = pulp.LpVariable("GreenValue", 0)
    bv = pulp.LpVariable("BrownValue", 0)

    zlist = list()
    constlist = list()

    reader = csv.reader(f, delimiter="\t")
    next(reader)  # skip header
    for index, card in enumerate(reader):
        spieces, vp = card[0], int(card[1])
        # スパイスの個数
        cy, cr, cg, cb = (
            spieces.count("Y"),
            spieces.count("R"),
            spieces.count("G"),
            spieces.count("B"),
        )
        score = cy * yv + cr * rv + cg * gv + cb * bv
        zi = pulp.LpVariable(f"Z{index}", 0)
        constlist.append(score - vp <= zi)
        constlist.append(score - vp >= -zi)
        zlist.append(zi)
    
    # LpProblemの構築
    prob = pulp.LpProblem("Estimate token's values", pulp.LpMinimize)
    prob += pulp.lpSum(zlist)
    for c in constlist:
        prob += c

    prob.solve()

    print("--------- Results --------")
    print("Status:", pulp.LpStatus[prob.status])
    for v in prob.variables():
        print(v.name, "=", v.varValue)

スクリプトで読み込ませているのは次のようなTSVです。

Spices	VP
YYYGG	9
RRGG	10

実行結果について

こんな結果が得られました。ちゃんと最適解は見つかり、見事に黄=1点、赤=2点、緑=3点、茶=4点と判定しています。

--------- Results --------
Status: Optimal
BrownValue = 4.0
GreenValue = 3.0
RedValue = 2.0
YellowValue = 1.0
Z0 = 0.0
Z1 = 0.0
Z10 = 0.0
Z11 = 0.0
Z12 = 0.0
Z13 = 0.0
Z14 = 0.0
Z15 = 0.0
Z16 = 0.0
Z17 = 0.0
Z18 = 0.0
Z19 = 0.0
Z2 = 0.0
Z20 = 0.0
Z21 = 0.0
Z22 = 0.0
Z23 = 0.0
Z24 = 1.0
Z25 = 1.0
Z26 = 1.0
Z27 = 1.0
Z28 = 1.0
Z29 = 1.0
Z3 = 0.0
Z30 = 1.0
Z31 = 2.0
Z32 = 2.0
Z33 = 2.0
Z34 = 2.0
Z35 = 2.0
Z4 = 0.0
Z5 = 0.0
Z6 = 0.0
Z7 = 0.0
Z8 = 0.0
Z9 = 0.0

ちょっと面白いなと思ったのは、トークンの価値に関しては非負である以上の制約を付けていない点です。

黄・赤・緑・茶の価値順をソルバーは知りません。茶色が高価値トークンである事をソルバーは知らなかったはずです
トークンの価値が整数だとも制約していません

それでも、ソルバーはカードの勝利点だけを見て、最も良さそうな価値付けを考えた結果、この結論にたどり着いています。

元のシートでも計算されていますが、黄=1点、赤=2点、緑=3点、茶=4点と仮定した時に、カードの実際の勝利点とのズレが出るカードは、全体からすると比較的少数です。この価値付けからズレてしまうと最適解からもズレてしまうので、他のより良い解は無いということなのでしょう。

まとめ

線形計画ソルバーを使ってトークンの価値を計算してみました。直接的な結果としてはあまりおもしろくはなく、巷で言われているトークン価値は妥当だと分かりました。

今回は初めてソルバーというものを使ってみたのですが、おそらく問題が単純でごく小さいからだと思うのですが、とても簡単に結果が出せちゃうので面白いツールだなと思いました。

ちなみにですが、センチュリー: スパイスロードの実際のゲームでは、どの点数カードがどの順に出るかは運の要素があります。そのため、トークンの価値だけで行動を決めることはできないはずです（もちろん目安にはなりそうですが）。

もしこのボードゲームに興味がある方がいたらボードゲームカフェ等で遊んでみてください。

ゲームでは交易カードというカードも使うのですが今回考慮しません。 ↩
この記事ではzの総和を目的関数としますが、このやり方が常に最善とは限りません。例えば、全てのzのうち最大値を最小化しようとする方針も考えられます。 ↩