宝石の煌めき（Splendor）AIの開発記録②
宝石トークンの交換手
開発記録①で調査した3つのリポジトリでは、いずれもトークンの交換手が用意されていなかった。それゆえに、宝石トークンの交換をできないという制約の中でプレイするしかなく、実際の宝石の煌めきよりも狭い範囲での戦いとなってしまい、そもそもこの環境で強いAIを作ってもなぁ・・・、という気持ちであった。
実際、BGAで上位帯と戦っていても、トークンの交換はザラに行われているし、交換手は宝石の煌めきにおいて重要な行動だと思う。
ただ、真面目にトークンの交換を実装しようと思うと、そこまで容易ではないことがわかる。手持ちの総枚数が8 / 9 / 10枚で場合分けをする必要があり、9 / 10枚持ちの場合は、それぞれで取るトークンと返すトークンの枚数でさらに場合分けが発生する。例えば9枚持ちの場合、3枚取り2枚返却と2枚取り1枚返却といった具合である。さらに、取る / 返却トークンのそれぞれで、同色 / 異色の場合分けも発生し、実装はさらにカオスになってくる。
ここまで考えただけでも、先人がなぜ交換手の実装を諦めたのかがわかってくる。
ただ、根気よく場合分けしてカウントすると、実装できたので、その方法を紹介する。あらゆる交換パターンを考えた結果、筆者がプレイする際にあらゆる交換まで考慮してプレイできるようになり、勝率が上がった（気がする）ので、交換は宝石の煌めきにおいて重要なんだと思う。
実装済みの全行動の確認
以下がalpha-zero-generalに実装済みの全行動（81通り）である。
ID = 0〜11 → 場にある宝石カード（12枚）の購入（12通り）
ID = 12〜26 → 場（12枚）+山札一番上（3枚）の宝石カードの予約（15通り）
ID = 27〜29 → 予約したカードの購入（3通り）
ID = 30〜59 → トークンを取る（30通り）
30〜34 → 1個取り（$${_{5}C_{1}=5}$$通り）
35〜44 → 2個（異色）取り（$${_{5}C_{2}=10}$$通り）
45〜54 → 3個（異色）取り（$${_{5}C_{3}=10}$$通り）
55〜59 → 2個（同色）取り（$${_{5}C_{1}=5}$$通り）
ID = 60〜79 → トークンの返却（20通り）
60〜64 → 1個返却（$${_{5}C_{1}=5}$$通り）
65〜74 → 2個（異色）返却（$${_{5}C_{2}=10}$$通り）
75〜79 → 2個（同色）返却（$${_{5}C_{1}=5}$$通り）
ID = 80 → パス（何もしない）
既に、ID = 60〜80で2枚返却まで実装済みであるため、4.の取る行動と5.の返却行動の組み合わせで、ほとんどの交換手を実装できそうであることがわかる。
しかし、これは実装を進めているうちに気づいたことだが、実装済みの手の単なる組み合わせだけで起こりうる交換手を完全に表現できるわけではない。10枚持ちの場合、3枚取り3枚返却という手が起こりうるが、3枚の返却はそもそも未実装であるため、別途実装方法を考える必要がある。
交換手の実装
ここからは考えられる交換手を、場合分けしながら実装していく。なお、実装を進める中で実装できていない手が見つかったりしたという経緯があるので、行動IDの順序に多少の前後があったりするが、悪しからず。
また、取る色と返す色に被りは無いものとして以下の場合分けを進める。
例えば、
+（白, 青, 緑）ー（緑, 赤）という変化は、
+（白, 青）ー（赤）と同じ変化なので、
3枚取り2枚返却の場合では考えず、2枚取り1枚返却で考えることとする。
i) 3枚取り1枚返却の場合
5色から3色取る組み合わせのそれぞれに残り2色を返却する組み合わせが存在するため、$${_5C_3×_2C_1=20}$$通りとなる。
ii) 3枚取り2枚返却の場合
取る組み合わせはi)と同じく$${_5C_3=10}$$通りで、返却は残り2色の重複を許した組み合わせなので、$${_{2+2-1}C_2=3}$$通り、すなわち合計で$${10×3=30}通りとなる。
iii) 異色2枚取り2枚返却の場合
2枚取りを含む場合は、異色 / 同色どちらも起こりうるため、少しややこしい。
異色に限定すると、
取る組み合わせ → 5色から2色選ぶ$${_5C_2=10}$$通り
返す組み合わせ → 残りの3色から重複を許して2色選ぶ$${_{3+2-1}C_2=6}$$通り
となり、合計で10×6=60通りとなる。
iv) 同色2枚取り2枚返却の場合
取る2色が同色の場合、返却は残り4色から重複を許して2色選ぶ組合わせのため、
$${_5C_1×{_{4+2-1}C_2}}=50$$通りとなる。
v) 異色2枚取り1枚返却の場合
1枚返却の場合もiii), iv)と同様である。
5色から2色選び、残りの3色から1色選ぶため、$${_5C_2×_3C_1=30}$$通り
vi)同色2枚取り1枚返却の場合
5色から1色選び、残りの4色から1色選ぶため、$${_5C_1×_4C_1=20}$$通り
vii) 1枚取り（金含まず）1枚返却の場合
1枚取りの場合には、金の可能性も考える必要があるが、取る色に金を含めると、予約するカードによって、行動を分ける必要が出てくるため、ここでは金は含めず、viii)で考えることにする。
金を含めない場合、5色から1色選び、残りの4色から1色選ぶため20通りとなる。
viii) 1枚取り（金）1枚返却の場合
金を取るという行動は、予約の通り数だけ行動を分けることになる。すなわち、15通りの予約手それぞれに、5色の返却パターンが存在することになるので、
$${15×5=75}通りとなる。
ix) 3枚取り3枚返却の場合
筆者は、vii)までで全ての交換を表現できたと思っていたが、よくよく考えてみると、10枚持ちの場合は3枚取って3枚返す交換パターンが起こりうる。
5色のうちから3色取って3色返すのだから、必ず1色重複して、実質2取り2返却と同じだろうと勘違いしていた。実際には、返却の3枚は重複があり得て、
+（白, 青, 緑）ー（赤, 赤, 黒）のようにすると、i）〜viii）に含まれない交換パターンとなってしまう。
このパターンは、5色から3色選び、残り2色を重複を許して3枚に配分する（4通り）組み合わせのため、
$${_5C_3×4=40}$$通りとなる。
i)〜ix)を合計すると、交換手だけで、345通りである。（そりゃ誰も実装しようと思わんわな・・・）
交換を実装したため、既存の返却だけの手（ID=60〜79）は不要になり、それ以外の60通り+1（パス）の行動に追加する形となって、今の宝石AIの全行動数は406通りとなった。
そう考えると、宝石の煌めきが人気の理由の一つが、交換を含めた取りうる手の数の多さなのかもしれない。
骨が折れる作業ではあったが、ここまでで金の返却を除く、起こりうる全ての交換手をカウントすることができた。カウントさえできれば、あとは行動IDと既存の行動IDの組との紐付けをしていくだけなので、実装するのは簡単である。（とはいえ数は多いが）
ここまでの実装は既に済んでおり、下記リポジトリにて公開中なので、Splendor-AIに興味のある方は学習させて対戦してみてください。詳しい実装の仕方や、学習方法・AI同士の対戦のさせ方などについては、次回以降に書こうと思います。
最後に
実装が足りてない！や、ここが間違っている！などアドバイスなどあれば、気軽にコメントで教えてください！
現状では金の返却や、購入時の支払いパターン（金を使うか否か）までは、実装できていません。BGAを見ているとガチモードでは、支払いに使うトークンまで選べるため、究極の理想は支払いパターンまで分けて全行動を実装するのが理想だとは思っています（さすがにすぐ実装しないけど）。果たして、金を使わなくても良い盤面であえて金を使った方が良い盤面などあるのだろうか・・・。有識者の方いたら教えてください。