手を2回叩いた後に攻撃などのアクションをする遊びの均衡戦略

はじめに

ゲーム理論を使って，昔懐かしの手遊びゲームの均衡戦略を導きます．題材は 手を2回叩いた後に攻撃などのアクションをする遊び です．本記事では Twice Clap Game (TCG) と呼びます．

完全情報ゲームなどの必勝法のあるゲームの記事はよく見かけますが，必勝法がなく，確率的に手を選択することが均衡となるゲームの解説は珍しいかと思います．お楽しみいただければと思います．

お断り

以下の説明を省きます．

• ゲーム理論の基礎
• 均衡戦略／混合戦略の定義
• 行列ゲームの定義／アルゴリズム
• アルゴリズムの正当性／収束性

Twice Clap Game

TCGにはローカルルールがたくさんありますが，本記事では以下のルールを扱います．

• 二人で実施
• プレイヤはポイントを持つ（初期値は$0$点，最大値は$n$点）
• 勝敗が決まるまで以下を繰り返す
• 手を二回叩いた後に「溜め（$1$；charge）」「攻撃（$2$；attack）」「防御（$3$；defense）」「大攻撃（$4$；strong attack）」のいずれかを二人同時に出す
• 各プレイヤの手に応じてそれぞれのポイントが変化（溜め：$+1$，攻撃：$-1$，防御：$0$，大攻撃：$-n$）
• 手の組合せによって「勝ち（$+$）」「負け（$-$）」が決まる（行がプレイヤ１の行動，列がプレイヤ２の行動）

\begin{align} \begin{matrix} & \text{charge} & \text{attack} & \text{defense} & \text{strong attack} \\ \text{charge} & & - & & - \\ \text{attack} & + & & & - \\ \text{defense} & & & & - \\ \text{strong attack} & + & + & + & \end{matrix} \end{align}

• ポイントがマイナスになっても負け
• 互いにポイントがマイナスになったら，ポイント$0$点から再開

「大攻撃」があるのが特徴です．これがあることで，ポイントをたくさん溜めることが重要な戦略となり，ポイントごとに戦略が変化すると考えたため，採用しました．

均衡戦略

結論だけ知りたいという方が大半？かと思いましたので，先に均衡戦略をまとめます．均衡戦略の計算方法は付録で説明します．

$n = 3$のとき，各ポイント状況$(i_1, i_2)$での均衡戦略は以下となります．プレイヤ１のポイントが$i_1$，プレイヤ２のポイントが$i_2$です．冗長になるので，$i_1 \leq i_2$の場合だけを示します．数値がその手を選択する割合を示します．＊マークがついている場合，どの手を選択してもよいです．

\begin{align} \begin{matrix} & & \text{player 1} & & & & \text{player 2} & & & \\ i_1 & i_2 & \text{charge} & \text{attack} & \text{defense} & \text{strong attack} & \text{charge} & \text{attack} & \text{defense} & \text{strong attack} \\ 0 & 0&1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0.65 & 0 & 0.35 & 0 & 0.65 & 0.35 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 3 & * & * & * & * & * & * & * & * \\ 1 & 1 & 0.31 & 0.22 & 0.47 & 0 & 0.31 & 0.22 & 0.47 & 0 \\ 1 & 2 & 0.3 & 0.26& 0.44& 0 & 0.22 & 0.25& 0.53& 0 \\ 1 & 3 & * & * & * & * & 0 & 0 & * & * \\ 2 & 2 & 0.19& 0.4& 0.4& 0 & 0.19 & 0.4& 0.4 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 & 0 & 0& 0& 1 \\ 3 & 3 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix} \end{align}

(0, 0)

お互いに「溜め」が最適です．当然ですね．

(0, 1)

プレイヤ２は攻撃できるので，プレイヤ１には防御の選択肢が現れます．最適な割合まで分かるのが，理論の良いところですね．

(0, 2)

ポイントが３になると必勝の大攻撃が使えるので，プレイヤ２は溜めを選択します．プレイヤ１は攻撃できないので，プレイヤ２は安心して溜めを選択できます．

(0, 3)

プレイヤ２は大攻撃ができるので，早速使うのかと思いきや，よく解析してみると，この状況ではお互いにどの手を選択しても，最終的にはプレイヤ２が勝利できます．大攻撃以外は舐めプですね．

(1, 1)

ここからは，お互いに攻撃ができるので，「溜め」「攻撃」「防御」をバランスよく組み合わせた複雑な戦略が必要になってきます．どの配分が最適かは，人手で導き出すのは難しいので，アルゴリズムを使う意義が出てきます．

(1, 2)

状況$(1, 1)$と類似していますが，プレイヤ１は攻撃の割合を増やしています．プレイヤ２にポイントが３まで増やしてほしくないため，牽制しているのだと思われます．プレイヤ１が攻撃を増やすので，プレイヤ２も安易に溜めをできず，防御の割合を増やしています．

(1, 3)

状況$(0, 3)$と同様に，＊マークの手であれば，どの手を選択しても，最終的にはプレイヤ２が勝利できます．舐めプです．

(2, 2)

お互いに大攻撃まであと１ポイントなので，状況$(1, 1)$よりも攻撃に割合を割き，牽制し合っていることが分かります．

(2, 3)

状況$(0, 3), (1, 3)$ではプレイヤ２に舐めプが許されていましたが，プレイヤ１もあと１点で大攻撃なので，舐めプの余裕はありません．プレイヤ２の最適行動はやっと大攻撃です．

(3, 3)

当然，お互いに「大攻撃」が最適です．

勝利確率

以上の均衡戦略を使った場合に，各ポイント状況でプレイヤ１が勝利できる確率は以下です．行がプレイヤ１のポイント，列がプレイヤ２のポイントです．ポイントが等しい時は勝率が五分，ポイントが相手よりも多くなるほど勝率が上がることが分かります．この特徴は「大攻撃」がない場合には現れません．その場合，どの状態でも勝利は五分になります．

\begin{align} \begin{pmatrix} 0.5 & 0.17 & 0 & 0 \\ 0.83 & 0.5 & 0.26 & 0 \\ 1 & 0.74 & 0.5 & 0 \\ 1 & 1 & 1 & 0.5 \end{pmatrix} \end{align}

おわりに

均衡戦略が分かったとことで，それを暗記して，頭の中でサイコロを振って，行動を選択するのは困難かと思います．そこで，付録のプログラムでは，相手の行動を入力するだけで均衡戦略となる行動を提示してくれる機能を実装しています．（打ち込みの時間を相手が許してくれるかはわかりませんが．．．）これを使って正月はキッズを圧倒しましょう！

付録

以降は均衡戦略を計算する方法を説明します．

動的ゲーム／マルコフゲーム

既に均衡戦略で見てきたように，TCGではポイントの状態によって戦略（どの手をどの割合で出すのか）が変わります．このように，状態によって戦略が変化するゲームは動的ゲームと呼ばれます．動的ゲームでは，プレイヤの行動によって状態が変化します．特に，過去の状態の履歴に依存せず，現在の状態と行動のみによって移動先の状態が決まる場合は，マルコフゲームと呼ばれます．本記事では，状態の集合に各プレイヤの「勝ち」に対応する状態を加えます．各プレイヤの目標は，それぞれの勝利状態に移動することです．

定式化

では，TCGをマルコフゲームとして定式化します．まず，各プレイヤのポイントの組$(i_1, i_2)$を状態とします．ポイントの範囲は$0 \leq i \leq n$です．また，プレイヤ１の勝利状態を$(n+1, n+1)$，プレイヤ２の勝利状態を$(n+2, n+2)$とします．ゲームは状態$(0, 0)$から開始します．プレイヤはそれぞれの手を選択し，ポイントが変化することで状態が移動します．勝敗が決まった場合は，勝ったプレイヤの勝利状態に移動し，ゲームは終了です．

アルゴリズム

本記事では，価値反復法を用いて均衡戦略を計算しました．価値反復法では，均衡解における，各状態$(i_1, i_2)$でプレイヤ１が勝利する確率$v_{i_1, i_2}$を扱います．勝利頂点では勝ち負けが確定しているので，$v_{n+1, n+1} = 1, v_{n+2, n+2} = 0$です．他の状態の値は事前には分からないので，最初は適当な値から開始し，均衡解での値に近づけていきます．

各状態$(i_1, i_2)$の確率値$v_{i_1, i_2}$の更新方法を説明します．前述の確率値が真の値であると仮定し，互いに勝つ確率を最大化する状態に移動するような均衡戦略を計算します．そして，その時の確率値で確率値$v_{i_1, i_2}$を更新します．

この均衡戦略は以下の行列$A \in \mathbb{R}^{4 \times 4}$を入力とする行列ゲームの均衡解として求められます．行列$A$の$(j_1, j_2)$成分は，プレイヤ１が行動$j_1$，プレイヤ２が行動$j_2$を選択した場合に移動する状態$(i'_1, i'_2)$の確率値$v_{i_1, i_2}$です．行列ゲームのプレイヤ１・２の均衡戦略をそれぞれ$x, y \in \mathbb{R}^4$とすると，確率値$v_{i_1, i_2}$は$x^\top A y$となります．

例えば，$n = 3$で，状態$(1, 3)$の行列$A$は以下です．$(1, 1)$成分は互いに溜めなので，ポイントが$1$増えますが，プレイヤ２は既に最大値$3$なので，状態$(2, 3)$に移動します．$(1, 2)$成分はプレイヤ１が溜め，プレイヤ２が攻撃なので，プレイヤ２の勝利で状態$(5, 5)$に移動します．
\begin{align} A = \begin{pmatrix} v_{2, 3} & v_{5, 5} & v_{2, 3} & v_{5, 5} \\ v_{4, 4} & v_{0, 2} & v_{0, 3} & v_{5, 5} \\ v_{1, 3} & v_{1, 2} & v_{1, 3} & v_{5, 5} \\ v_{5, 5} & v_{5, 5} & v_{5, 5} & v_{5, 5} \end{pmatrix} \end{align}

アルゴリズムは以下です．まず，各状態$(i_1, i_2)$の確率値$v_{i_1, i_2}$を$0.5$に初期化します．そして，各状態$(i_1, i_2)$の行列ゲームの均衡解を解き，状態$(i_1, i_2)$の価値$v_{i_1, i_2}$を均衡解での確率値に更新します．以上の処理を価値が収束するまで繰り返します．アルゴリズムの序盤では確率値は不確実な値ですが，結果が確定している勝利状態の値が周辺の状態に伝播していき，徐々に正しい値に収束していく，というイメージです．

1. 確率値$v_{i_1, i_2}$を$0.5$に初期化
2. while すべての確率値$v_{i_1, i_2}$が収束するまで：
3. 　　for $i_1, i_2 \in [0, n]$
4. 　　　　行列ゲームの均衡戦略での確率値で$v_{i_1, i_2}$を更新

プログラム

pythonのプログラムを ここ にまとめています．以下では使い方を説明します．まず，TwiceClapGameクラスのインスタンスtcgを生成します．このとき，最大ポイント数$n$を指定できます．tcg.solve()で均衡戦略を計算します．計算結果はインスタンスに保存されます．tcg.show()で各状態での戦略を表示します．遊ぶときにはtcg.play()を実行することで，相手の行動を入力するだけで均衡戦略となる行動を提示します．

      tcg = TwiceClapGame(3)
tcg.solve()
tcg.show()
tcg.play()