<jupyter_start><jupyter_text>[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/tanakat01/r-rivals/blob/main/notebooks/r-rivals.ipynb) アールライバルズのナッシュ戦略  ルール- https://www.youtube.com/watch?v=X4QCf6217Csに説明動画- https://shop.game-life.jp/blog/2015/04/09/105907にある説明を引用する．```道化(0)　：数値は最低だけど、カードの効果で勝負を次にもちこせます。　　　　　 実質カードの効果を無視する魔術師以外には負けません。　　　　　 勝てもしませんけど。姫(1)　　：このゲームの最大のキモとなるカード。　　　　　 このカードで相手の王子に勝てた場合、　　　　　 その時点でゲームに勝ちます。　　　　　 どんなに負け越していても勝ちになります。密偵(2)　：おそらく一番使い方が難しいカード。　　　　　 出した次の勝負は相手のカードを見てから　　　　　 何を出すか決められます。暗殺者(3)：このカードより弱いカードに負けて　　　　　 強いカードに勝つ特殊なカード。　　　　　 暗殺者で相手の将軍等の強いカードに勝てたら気持ちいいですよ！大臣(4)　：数値的には弱くないのですが…暗殺者に負けるため、　　　　　 実質勝てる相手が少ないです。　　　　　 ただ、勝てた場合はその勝利は２勝分！　　　　　　 価値ある勝利になります。魔術師(5)：担当的には一番使いやすいカード。　　　　　 相手の効果を無視して単純な数値のくらべ合いにもちこめます。　　　　　 道化に勝てる唯一のカードです。将軍(6)　：数値的に王子に次ぐ強いカード。　　　　　 さらに次の勝負の時に出すカードの数値を＋２できる　　　　　 強力な効果もあります。王子(7)　：数値的に最強のカード。　　　　　 暗殺者もよせつけないため、確実に勝ちたいときに使いましょう。　　　　　 ただし、相手の姫には気をつけて！```ルールの注意点- 道化の「勝負を持ち越す」は次に勝った人が2勝分の点を得るのか? - https://shop.game-life.jp/blog/2015/04/09/105907 の進行例を見るとそのとおり．- 引き分けは? - 道化の直後の場合は次の勝者が1勝取るようだが，それに倣う - 魔術師 - 将軍 は?  - 次のカード +2 を無効にするのか? -> そのとおり  - 「同じターンの相手のカードの効果を無効化」 - 片方が将軍を出した直後に魔術師 - 魔術師の場合は?  - 将軍の効果は生きる． - 将軍のあとのターンで暗殺者 - 密偵(+2) は暗殺者の勝ちで良いか?  - それはそう．     手番での状態- 自分がplayer1, 相手がplayer2とする．- それぞれのプレイヤの残りカード - mask1 (0 - 255), mask2 (0 - 255) - mask & (1 << i) ! = 0 の時に，カード i を保持- それぞれのプレイヤの得点状況 0-3, 0-3 - score1, score2- next win score - win_score1, win_score2 - drawが続くとwin_score1, win_score2 がともに +1 - 大臣を出してdrawだった時は+2とする(大臣がdrawのときの効果はdrawが続く限り続くものとする)．- 直前にどちらかだけが密偵を出したか? - dspy : 1の時は自分だけが密偵，-1の時は相手が密偵- 直前に自分が密偵だった時の，相手が先に出したカード - prevcard :　通常は -1 , dspy が1の時は，相手が先に出したカード- 直前に将軍 - dgeneral 2 の時は自分がgeneral, -2 の時は相手がgeneralこれを元に ```((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)```を状態とする．  両者が暗殺者 (assassin)の時関数 next_state_sub などの引数 double_assassin でルールの違いに対応．- double_assassin = False (default)のときは，両者がassassinを出しても，scoreが小さい方が勝つ．- double_assassin = True とすると，両者がassasinのときは，scoreが大きい方が勝つ．<jupyter_code>init_state = ((255, 255), (0, 0), (1, 1), 0, 0, -1)
# stateが終了状態かどうか?
def is_final(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    return score1 >= 4 or score2 >= 4 or (mask1 == 0 and mask2 == 0)
# 終了状態のゲームスコアをplayer1の立場から返す
def final_score(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    if score1 >= 4:
        return 1
    elif score2 >= 4:
        return -1
    else:
        return 0
# プレイヤ1からみた状態からプレイヤ2からみた状態を作り出す．
def neg_state(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    return ((mask2, mask1), (score2, score1), (wscore2, wscore1), -dspy, -dgeneral, prevcard)
# maskからmoveのリストに変換
def mask2moves(mask):
    return [i for i in range(8) if (1 << i) & mask != 0]
# moveのリストからmaskに変換
def moves2mask(moves):
    ans = 0
    for x in moves:
        ans |= (1 << x)
    return ans
# stateがプレイヤ1の手番かどうか?
def canmove(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    if dspy == 0:
        return True
    if dspy > 0 and prevcard >= 0:
        return True
    if dspy < 0 and prevcard < 0:
        return True
    return False
def state2moves(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    return ((mask2moves(mask1), mask2moves(mask2)), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)
def state2masks(state):
    ((moves1, moves2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    return ((moves2mask(moves1), moves2mask(moves2)), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)

def next_state_sub(state, move1, move2, double_assassin=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    assert (mask1 & (1 << move1)) != 0
    if (mask2 & (1 << move2) == 0):
        print('state', state, 'move1', move1, 'move2', move2, 'mask2', mask2)
    assert (mask2 & (1 << move2)) != 0
    # prince and princess
    mask1 ^= 1 << move1
    mask2 ^= 1 << move2
    if move1 == 1 and move2 == 7:
        return ((mask1, mask2), (4, 0), (0, 0), 0, 0, -1)
    elif move1 == 7 and move2 == 1:
        return ((mask1, mask2), (0, 4), (0, 0), 0, 0, -1)
    str1 = move1 + dgeneral
    str2 = move2
    # wizard
    if move1 == 5 or move2 == 5:
        if str1 == str2:
            return ((mask1, mask2), (score1, score2), (wscore1 + 1, wscore2 + 1), 0, 0, -1)
        elif str1 > str2:
            return ((mask1, mask2), (score1 + wscore1, score2), (1, 1), 0, 0, -1)
        else:
            return ((mask1, mask2), (score1, score2 + wscore2), (1, 1), 0, 0, -1)
    dgeneral = (2 if move1 == 6 else 0) + (-2 if move2 == 6 else 0)
    dspy = (1 if move1 == 2 else 0) + (-1 if move2 == 2 else 0)
    wadd1 = (2 if move1 == 4 else 1)
    wadd2 = (2 if move2 == 4 else 1)
    wscore1 = wscore1 + wadd1
    wscore2 = wscore2 + wadd2
    # when each player moves assassin at the same time, the order is reversed.
    if move1 == 3 and move2 == 3 and double_assassin:
        pass
    elif (move1 == 3 and move2 != 7) or (move2 == 3 and move1 != 7): 
        str1 = -str1
        str2 = -str2
    if move1 == 0 or move2 == 0 or str1 == str2:
        return ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, -1)
    if str1 > str2:
        return ((mask1, mask2), (score1 + wscore1 - 1, score2), (1, 1), dspy, dgeneral, -1)
    else:
        return ((mask1, mask2), (score1, score2 + wscore2 - 1), (1, 1), dspy, dgeneral, -1)
# normalize
def next_state(state, move1, move2, double_assassin=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = next_state_sub(state, move1, move2, double_assassin)
    wscore1 = min(4 - score1, wscore1)
    wscore2 = min(4 - score2, wscore2)
    return ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)
# spyの後
def half_move(state, move, double_assassin=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    assert dspy != 0
    if prevcard < 0:
        return ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, move)
    if dspy < 0:
        return next_state(state, prevcard, move, double_assassin)
    return next_state(state, move, prevcard, double_assassin)
def pp_state(state):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    return ((mask2moves(mask1), mask2moves(mask2)), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)<jupyter_output><empty_output><jupyter_text>早見表との比較特に何もない状態でやってみて，早見表と同じ表が出ることを確認する．|P1\P2|7|6|5|4|3|2|1|0|| --- | --- | --- | --- | --- | --- | --- | --- | --- ||7|△|○|○|○|○|○|■|△||6|×|△|○|○|×|○|○|△||5|×|×|△|○|○|○|○|○||4|×|×|×|△|×|○|○|△||3|×|○|×|○|△|×|×|△||2|×|×|×|×|○|△|○|△||1|◎|×|×|×|○|×|△|△||0|△|△|×|△|△|△|△|△|(表の説明)- ◎ : P1が「ゲーム」の勝ち- ○ : P1が「勝負」に勝ち- △ : 「勝負」は引き分け- × : P2が「勝負」の勝ち- ■ : P2が「ゲーム」の勝ち下のセルの実行結果は```△○○○○○■△×△○○×○○△××△○○○○○×××△×○○△×○×○△××△××××○△○△◎×××○×△△△△×△△△△△```となる．<jupyter_code>for i in range(7, -1, -1):
    l = ''
    for j in range(7, -1, -1):
        state = ((255, 255), (0, 0), (1, 1), 0, 0, -1)
        ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = next_state(state, i, j)
        if score1 >= 4:
            l += '◎'
        elif score1 > 0:
            l += '○'
        elif score2 >= 4:
            l += '■'
        elif score2 > 0:
            l += '×'
        else:
            l += '△'
    print(l)<jupyter_output><empty_output><jupyter_text>状態数を調べる．手番のプレイヤの視点での状態の数を数える．　以下の関数 gen_all_states を使って，double_assassin=False(default), Trueの両方のルールのもとで全ての状態を作成する．<jupyter_code># set all_states
def gen_all_states(double_assassin=False):
    all_states = [set()]
    all_states[-1].add(init_state)
    for i in range(8):
        nstates = set()
        magic_states = set()
        for s in all_states[-1]:
            ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
            moves1, moves2 = mask2moves(mask1), mask2moves(mask2)
            if dspy == -1:
                for move1 in moves1:
                    ns = half_move(s, move1, double_assassin)
                    magic_states.add(neg_state(ns))
                    for move2 in moves2:
                        ns1 = half_move(ns, move2, double_assassin)
                        if is_final(ns1):
                            continue
                        if ns1[3] != 1:
                            nstates.add(ns1)
                        nstates.add(neg_state(ns1))
                continue
            assert dspy == 0
            for move1 in moves1:
                for move2 in moves2:
                    ns = next_state(s, move1, move2, double_assassin)
                    if is_final(ns):
                        continue
                    if ns[3] != 1:
                        nstates.add(ns)
                    if ns[3] != -1:
                        nstates.add(neg_state(ns))
        all_states[-1] |= magic_states
        all_states.append(nstates)
    return all_states
all_states = gen_all_states()
all_states_da = gen_all_states(double_assassin=True)<jupyter_output><empty_output><jupyter_text>double_assassin = False, True のそれぞれについて，手番のプレイヤの残り枚数，出し方のパターンごとに状態数を数えたものを表として出力する．```double_assassin False残りカード枚数 & 同時出し & 先出し & 後出し8 & 1 & 0 & 0 \\7 & 50 & 6 & 42 \\6 & 1902 & 273 & 1638 \\5 & 27872 & 4574 & 22870 \\4 & 110786 & 22425 & 89700 \\3 & 102091 & 25777 & 77331 \\2 & 25374 & 6779 & 13558 \\1 & 2600 & 727 & 727 \\537103double_assassin True残りカード枚数 & 同時出し & 先出し & 後出し8 & 1 & 0 & 0 \\7 & 50 & 6 & 42 \\6 & 1904 & 273 & 1638 \\5 & 27882 & 4576 & 22880 \\4 & 110804 & 22438 & 89752 \\3 & 102081 & 25776 & 77328 \\2 & 25372 & 6779 & 13558 \\1 & 2600 & 727 & 727 \\537194```<jupyter_code>def print_all_states(double_assassin=False):
    print('double_assassin', double_assassin)
    print('残りカード枚数', '&', '同時出し', '&', '先出し', '&', '後出し')
    for i in range(8):
        ss = all_states_da[i] if double_assassin else all_states[i]
        simul, turn1, turn2 = 0, 0, 0
        for s in ss:
            ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
            if dspy != 0:
                #assert dspy == -1
                if prevcard == -1:
                    turn1 += 1
                else:
                    turn2 += 1
            else:
                simul += 1
        print(8 - i, '&', simul, '&', turn1, '&', turn2, '\\\\')
    print(sum(len(s) for s in (all_states_da if double_assassin else all_states)))
print_all_states(False)
print_all_states(True)
s = init_state
moves = [(1, 6), (6, 4), (4, 2), (0, 5), (5, 0)]
for m in moves:
    s = next_state(s, m[0], m[1])
    print('s', s, 'm', m)<jupyter_output><empty_output><jupyter_text>scipy.optimize.linprogの使い方同時出しの時にナッシュ均衡を与える戦略は混合戦略となる．この時のゲーム値と，ナッシュ均衡を与える戦略（の一つ）は線形計画法を用いて計算できる．線形計画法のソルバとして，scipy.optimize.linproghttps://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.htmlを使って線形計画法の問題を解く例をみていく．```scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='interior-point', callback=None, options=None, x0=None)```$$\min_{x}c^Tx$$s.t. $$A_{ub} x \le b_{ub},$$$$A_{eq} x = b_{eq},$$$$l\le x\le u$$で，```c = [-1, 4]A = [[-3, 1], [1, 2]]b = [6, 4]bounds =[    (None, None),   -∞ ≤ x ≤ ∞    (-3, None)      -s ≤ y ≤ ∞]```の条件で解いてみると，```x: array([10., -3.])```という解を得ることができる．<jupyter_code># sample
from scipy.optimize import linprog
c = [-1, 4]
A = [[-3, 1], [1, 2]]
b = [6, 4]
bounds =[
    (None, None),  # -∞ ≤ x ≤ ∞
    (-3, None)     # -s ≤ y ≤ ∞
]

res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='simplex')
print(res)<jupyter_output><empty_output><jupyter_text>厳密解の計算線形計画法の厳密解ソルバとして有名なものは，として QSOpt_ex , SoPlex などがあるが，本研究では　<NAME> 氏が作成したPython言語のみで書かれた Simplex 法プログラムhttps://github.com/dmishin/pylinprog を使用する．<jupyter_code>!curl -O https://raw.githubusercontent.com/dmishin/pylinprog/master/linprog.py
from fractions import Fraction
from linprog import linsolve
from linprog import RationalNumbers
from linprog import simplex_canonical_m
def toFrac(x):
    if x is None or isinstance(x, Fraction):
        return x
    return Fraction(x)
class linres:
    def __init__(self, x):
        self.x = x

def exact_linprog(C, A_eq, b_eq, A_ub, b_ub, bounds, method='simplex',callback=None,options=None):
    nonneg_variables = []
    for i, (low, high) in enumerate(bounds):
        if low == 0:
            nonneg_variables.append(i)
    num = RationalNumbers()
    print('nonneg_variables', nonneg_variables)
    resolution, sol = linsolve(C, ineq_left=A_ub, ineq_right=b_ub, eq_left=A_eq, eq_right=b_eq, 
                               nonneg_variables = nonneg_variables, num=num)
    return linres(sol)<jupyter_output><empty_output><jupyter_text>Nash均衡のゲーム値の計算 同時出し同時出しのナッシュ均衡戦略とその時のゲーム値を計算する．$$move1 = \{A_0, A_1, A_2, \ldots, A_{n - 1}\}$$$$move2 = \{B_0, B_1, B_2, \ldots, B_{n - 1}\}$$で，それぞれが$A_i, B_j$ を選択した時の，player 1 の立場からの利得の期待値を$R_{i,j}$とする．$Player_{1}$が確率$\pi = \{p_0, p_1, \ldots, p_{n - 1}\}$でそれぞれの手を選択するものとする．確率の定義により，$$ \sum_{i=0}^{n - 1} p_i = 1 $$プレイヤ2が$B_j$を選択した時のプレイヤ　1の利得は$$R(j, \pi) = \sum_{i=0}^{n-1} p_i R_{i, j}$$となる．プレイヤ2が最善の手を選択した時のプレイヤ　1の利得を$v$とすると，$0 \le j \le n - 1$の$j$について，$$v \le \sum_{i=0}^{n-1} p_i R_{i, j} $$が成り立つ．プレイヤ1のナッシュ均衡戦略の利得を求めるには，この制約のもとで，vを最大化するという線形計画法を解く必要がある．$$ x = (v, p_0, p_1, \ldots, p_{n - 1})^T$$$$ c = (-1, 0, 0, \ldots, 0)^T$$として，$c^T x$ を最小化する．$$ \sum_{i=0}^{n - 1} p_i = 1 $$の条件は，$$ A_{eq} = (0, 1, 1, \ldots, 1) $$$$ b_{eq} = 1 $$として，$$ A_{eq} x = b_{eq}$$と書ける．また，$$v \le \sum_{i=0}^{n-1} p_i R_{i, j} $$の条件は，$$A_{ub} = \left(\begin{array}{rrrrrr}1 & -R_{0, 0} & -R_{1, 0} & \cdots & -R_{i, 0} & \cdots & -R_{n - 1, 0} \\1 & -R_{0, 1} & -R_{1, 1} & \cdots & -R_{i, 1} & \cdots & -R_{n - 1, 1} \\\vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\1 & -R_{0, n - 1} & -R_{1, n - 1} & \cdots & -R_{i, n - 1} & \cdots & -R_{n - 1, n - 1} \\\end{array}\right)$$$$ b_{ub} = (0, 0, \ldots, 0)^T $$ として，$$ A_{ub} x \le b_{ub}$$とかける．これを解くことによって，ゲーム値，およびナッシュ均衡戦略（の一つ）を計算できる．理解を深めたい方は電通大の岡本吉央先生の講義資料「[離散最適化基礎論 第 3 回 戦略形 2 人ゼロ和ゲーム：離散構造とアルゴリズム (1)](http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/gametheory/lect03.pdf)」が参考になる．<jupyter_code>import scipy.optimize
import traceback
import sys
#from scipy.optimize import linprog
s2unique = {} # state でのplayer1にとっての最適解が uniqueかどうかを True, False で判定する．
def simultaneous(state, s2val, s2moves, double_assassin=False, mylinprog=scipy.optimize.linprog, debug=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    moves1, moves2 = mask2moves(mask1), mask2moves(mask2)
    n = len(moves1)
    c = [-1] + [0] * n
    bounds = [(None, None)] + [(0, None)] * n
    A_eq = [[0] + [1] * n]
    b_eq = [1]
    A_ub = []
    b_ub = []
    for j, move2 in enumerate(moves2):
        l = [1]
        for i, move1 in enumerate(moves1):
            l.append(-statevalue(next_state(state, move1, move2), s2val, s2moves, double_assassin, mylinprog))
        A_ub.append(l)
        b_ub.append(0)
    if debug:
        print('(A_ub, b_ub, A_eq, b_eq, bounds)', (A_ub, b_ub, A_eq, b_eq, bounds))
    res = mylinprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')
    if debug:
        print('res.x', res.x)
    moves = []
    for i, move1 in enumerate(moves1):
        moves.append((move1, res.x[i + 1]))
    s2moves[state] = moves
    return res.x[0]

def statevalue(state, s2val, s2moves, double_assassin=False, mylinprog=scipy.optimize.linprog):
    #print('statevalue: state', state)
    if is_final(state):
        return final_score(state)
    if state in s2val and state in s2moves:
        return s2val[state]
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    if dspy == 0:
        v = simultaneous(state, s2val, s2moves, double_assassin, mylinprog)
        ns = neg_state(state)
        if ns not in s2val:
            v1 = simultaneous(ns, s2val, s2moves, double_assassin, mylinprog)
            s2val[ns] = v1
    elif dspy == -1: 
        if prevcard >= 0:
            return -statevalue(neg_state(state), s2val, s2moves, double_assassin, mylinprog)
        moves1 = mask2moves(mask1)
        v, maxmove1 = -1, moves1[0]
        for move1 in moves1:
            ns = half_move(state, move1, double_assassin)
            v1 = statevalue(ns, s2val, s2moves, double_assassin, mylinprog)
            if v1 > v:
                v = v1
                maxmove1 = move1
        moves = []
        for i, move1 in enumerate(moves1):
            moves.append((move1, 1 if move1 == maxmove1 else 0))
        s2moves[state] = moves
    else:
        assert dspy == 1
        if prevcard < 0:
            return -statevalue(neg_state(state), s2val, s2moves, double_assassin, mylinprog)
        moves1 = mask2moves(mask1)
        v, maxmove1 = -1, moves1[0]
        for move1 in moves1:
            ns = half_move(state, move1, double_assassin)
            v1 = statevalue(ns, s2val, s2moves, double_assassin, mylinprog)
            if v1 > v:
                v = v1
                maxmove1 = move1
#                v = max(v, statevalue(ns, s2val, s2moves, double_assassin, mylinprog))
        moves = []
        for i, move1 in enumerate(moves1):
            moves.append((move1, 1 if move1 == maxmove1 else 0))
        s2moves[state] = moves
    s2val[state] = v
    return v
    

def save_s2val(file, s2val):
    ret = []
    for state in s2val:
        ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
        v = str(s2val[state])
        ret.append([mask1, mask2, score1, score2, wscore1, wscore2, dspy, dgeneral, prevcard, v])
    s = json.dumps(ret)
    with open(file, 'wt') as wf:
        wf.write(s)

def save_s2moves(file, s2moves):
    ret = []
    for state in s2moves:
        ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
        vs = []
        for m, p in s2moves[state]:
            vs.append([m, str(p)])
        ret.append([mask1, mask2, score1, score2, wscore1, wscore2, dspy, dgeneral, prevcard, vs])
    with open(file, 'wt') as wf:
        json.dump(ret, wf)<jupyter_output><empty_output><jupyter_text>計算と保存計算した結果だけを使うならば，後の「公開データのダウンロードとロード」まで飛ばしてください．<jupyter_code># s2val, s2movesの計算と保存
s2val = {}
s2moves = {}
statevalue(init_state, s2val, s2moves)
save_s2val('s2val.txt', s2val)
save_s2moves('s2moves.txt', s2moves)
# s2val_da, s2moves_daの計算と保存
s2val_da = {}
s2moves_da = {}
statevalue(init_state, s2val_da, s2moves_da, double_assassin=True)
save_s2val('s2val_da.txt', s2val_da)
save_s2moves('s2moves_da.txt', s2moves_da)
# s2val_exact, s2moves_exactの計算と保存
s2val_exact = {}
s2moves_exact = {}
statevalue(init_state, s2val_exact, s2moves_exact, mylinprog=exact_linprog)
save_s2val('s2val_exact.txt', s2val_exact)
save_s2moves('s2moves_exact.txt', s2moves_exact)
# s2val_da_exact, s2moves_da_exactの計算と保存
s2val_da_exact = {}
s2moves_da_exact = {}
statevalue(init_state, s2val_da_exact, s2moves_da_exact, double_assassin=True, mylinprog=exact_linprog)
save_s2val('s2val_da_exact.txt', s2val_da_exact)
save_s2moves('s2moves_da_exact.txt', s2moves_da_exact)<jupyter_output><empty_output><jupyter_text>公開データのダウンロードとロード計算した結果は https://github.com/tanakat01/r-rivals/tree/main/data にJSON形式で公開している．そこからダウンロードして，ロードして計算結果を得ることができる．<jupyter_code>import json
def load_s2val(file, str2num=float):
    s2val = {}
    with open(file, 'rt') as rf:
        s = json.load(rf)
    for mask1, mask2, score1, score2, wscore1, wscore2, dspy, dgeneral, prevcard, v in s:
        s2val[((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)] = str2num(v)
    return s2val
def load_s2moves(file, str2num=float):
    s2moves = {}
    with open(file, 'rt') as rf:
        s = json.load(rf)
    for mask1, mask2, score1, score2, wscore1, wscore2, dspy, dgeneral, prevcard, vs in s:
        s2moves[((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard)] = [[x[0], str2num(x[1])] for x in vs]
    return s2moves

!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2val.txt
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2moves.txt
s2val = load_s2val('s2val.txt')
s2moves = load_s2moves('s2moves.txt')
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2val_da.txt
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2moves_da.txt
s2val_da = load_s2val('s2val_da.txt')
s2moves_da = load_s2moves('s2moves_da.txt')
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2val_exact.txt
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2moves_exact.txt
from fractions import Fraction
s2val_exact = load_s2val('s2val_exact.txt', str2num=Fraction)
s2moves_exact = load_s2moves('s2moves_exact.txt', str2num=Fraction)
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2val_da_exact.txt
!curl -O https://raw.githubusercontent.com/tanakat01/r-rivals/main/data/s2moves_da_exact.txt
from fractions import Fraction
s2val_da_exact = load_s2val('s2val_da_exact.txt', str2num=Fraction)
s2moves_da_exact = load_s2moves('s2moves_da_exact.txt', str2num=Fraction)<jupyter_output><empty_output><jupyter_text>初期局面での戦略まずは，初期局面でのナッシュ均衡戦略を表示する．```s2val[init_state]```は，ゲームの対称性から0になるはずである．実際に求めてみると，```8.782536712126523e-17```とほぼ0になっていることがわかる．<jupyter_code>s2val[init_state]<jupyter_output><empty_output><jupyter_text>同時出しの状態 state を与えて利得行列を表示する関数 print_return_matrix を作成する．　初期状態 `init_state` を与えた結果を整形したのが以下の表になる．P1＼P2 |  0 |  1 | 2 | 3 | 4 | 5 | 6 | 7 --- | --- | --- | --- | --- | --- | --- | --- | ---0 | 0 | -0.01177 | -0.49893 | 0.04516 | -0.10607 | 0.00193 | 0.07208 | 0.358121 | 0.01177 | 0 | -0.49910 | 0.32692 | -0.61282 | -0.01548 | 0.01164 | 12 | 0.49893 | 0.49910 | 0 | 0.31530 | -0.42120 | -0.01222 | 0.01580 | 0.280453 | -0.04516 | -0.32692 | -0.31530 | 0 | 0.31017 | -0.01332 | 0.36280 | 0.059224 | 0.10607 | 0.61282 | 0.42120 | -0.31017 | 0 | -0.02830 | -0.05954 | -0.053825 | -0.00193 | 0.01548 | 0.01222 | 0.01332 | 0.02830 | 0 | -0.26833 | -0.282086 | -0.07208 | -0.01164 | -0.01580 | -0.36280 | 0.05954 | 0.26833 | 0 | -0.232177 | -0.35812 | -1 | -0.28045 | -0.05922 | 0.05382 | 0.28208 | 0.23217 | 0<jupyter_code>def print_return_matrix(state, double_assassin=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    moves1, moves2 = mask2moves(mask1), mask2moves(mask2)
    n = len(moves1)
    print('P1＼P2', end='')
    for j, m2 in enumerate(moves2):
        print('&', m2, end='')
    print('\\\\')
    def roundstr(v):
        if abs(v) < 1e-7:
            return '0'
        elif abs(v - 1) < 1e-7:
            return '1'
        elif abs(v + 1) < 1e-7:
            return '-1'
        return f'{v:0.5f}'
    for i, m1 in enumerate(moves1):
        print(m1, end='')
        for j, m2 in enumerate(moves2):
            ns = next_state(state, m1, m2, double_assassin)
            v = statevalue(ns, s2val_da if double_assassin else s2val, s2moves_da if double_assassin else s2moves, double_assassin)
            print(f' & {roundstr(v)}',end='')
        print('\\\\')
print_return_matrix(init_state)<jupyter_output><empty_output><jupyter_text>次に，ナッシュ均衡戦略で，どのアクションをどの確率でどの確率で生成するかを表示する．```s2moves[init_state]```の実行結果は```[[0, 0.0], [1, 0.0], [2, 0.22175583508357324], [3, 0.2719122699143252], [4, 0.22684759633778984], [5, 0.23428083687676557], [6, 0.0], [7, 0.0452034617875461]] ``` となる<jupyter_code>s2moves[init_state]<jupyter_output><empty_output><jupyter_text>このことから* 「道化(0)」，「姫(1)」，「将軍(6)」は出さない* スパイ(2)は確率 0.22175583508357324 で出す* 暗殺者(3)は確率 0.2719122699143252 で出す* 大臣(4)は確率 0.22684759633778984 で出す* 魔術師(5)は確率 0.23428083687676557 で出す* 王子(7)は確率 0.0452034617875461 で出すで出す戦略が，ナッシュ均衡戦略であることがわかる．なお，2人零和ゲームの性質により，ナッシュ均衡でのゲーム値の一意性は保証されるが，戦略には複数のナッシュ均衡があり得るので，もう少し詳しく検証する．まず，「道化(0)」，「姫(1)」，「将軍(6)」を出したときの，相手が上記の戦略を採用したときの，期待値を求める．<jupyter_code># 同時のみ
def val_against_nash(state,s2val,s2moves):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    moves1 = mask2moves(mask1)
    allans = []
    for move1 in moves1:
        ans = 0
        ret = []
        for move2, p in s2moves[neg_state(state)]:
            ns = next_state(state, move1, move2)
            v = statevalue(ns,s2val, s2moves)
            ans += p * v
            ret.append([move2, v])
        print('move1', move1, 'ans', ans, 'ret', ret)
        allans.append((move1, ans))
    return allans<jupyter_output><empty_output><jupyter_text>```val_against_nash(init_state,s2val, s2moves)```の実行結果は```[(0, -0.1057820599352605), (1, -0.11922403397700802), (2, 1.708702623837155e-15), (3, -1.0568802777388697e-15), (4, -6.92154666914746e-16), (5, -7.441963711940502e-16), (6, -0.036274634064723046), (7, 1.6958638798894469e-16)]```となる．<jupyter_code>val_against_nash(init_state,s2val, s2moves)<jupyter_output><empty_output><jupyter_text>このことから，相手がここで計算したナッシュ均衡戦略を採用し，自分は初期状態で道化，姫，将軍を出して，それ以降はナッシュ均衡戦略を採用した時，利得の期待値が，* 道化(0) -0.1057820599352605* 姫(1) -0.11922403397700802* 将軍(6) -0.036274634064723046となり，ナッシュ均衡での利得0を下回ることがわかる．  有効なアクション数得られたナッシュ均衡戦略において，残りカード枚数ごとの有効な(0より大きい確率の)アクション数を同時着手について求めたものを計算する．先出し，後出しでは得られた戦略では有効なアクション数は常に1となるので，省略する． 結果を整形したのものが以下の表になる．カード枚数＼アクション数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 --- | --- | --- | --- | --- | --- | --- | --- | --- 1  |  0 | 2600 | 0 | 0 | 0 | 0 | 0 | 0 | 0 2  |  0 | 19333 | 6041 | 0 | 0 | 0 | 0 | 0 | 0 3  |  0 | 58522 | 33351 | 10218 | 0 | 0 | 0 | 0 | 0 4  |  0 | 38200 | 33424 | 32451 | 6711 | 0 | 0 | 0 | 0 5  |  0 | 4005 | 4997 | 10469 | 7522 | 879 | 0 | 0 | 0 6  |  0 | 73 | 169 | 539 | 769 | 334 | 18 | 0 | 0 7  |  0 | 2 | 4 | 7 | 12 | 23 | 0 | 2 | 0 8  |  0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0<jupyter_code># 有効な手の数の分布
counter = [[0] * 9 for _ in range(9)]
for s in s2moves:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if dspy != 0:
        continue
    moves1 = mask2moves(mask1)
    c = 0
    for m, p in s2moves[s]:
        if abs(p) > 1e-5:
            c += 1
    counter[len(moves1)][c] += 1
print('カード枚数＼アクション数 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\')    
for i in range(1, 9):
    print(i, ' & ', ' & '.join(str(x) for x in counter[i]), '\\\\')<jupyter_output><empty_output><jupyter_text>アクション数が7の状態を表示させる．<jupyter_code>for s in s2moves:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if dspy != 0:
        continue
    moves1 = mask2moves(mask1)
    c = 0
    for m, p in s2moves[s]:
        if abs(p) > 1e-5:
            c += 1
    if c == 7:
        print(s, s2moves[s])<jupyter_output><empty_output><jupyter_text>各カードが何ターン目の勝負で出されるかナッシュ均衡戦略同士の対戦で，どのカードが何ターン目の勝負で出される確率が高いかを計算する．出力結果を整形した表が以下になる．カード番号＼ターン | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8  | not used --- | --- | --- | --- | --- | --- | --- | --- | --- | --- 0 | 0.00000 | 0.14488 | 0.11867 | 0.12525 | 0.14147 | 0.10949 | 0.04932 | 0.01382 | 0.29709 1 | 0.00000 | 0.09852 | 0.07259 | 0.08968 | 0.09935 | 0.09615 | 0.08730 | 0.05038 | 0.40603 2 | 0.22176 | 0.16342 | 0.11464 | 0.06882 | 0.03578 | 0.01979 | 0.01056 | 0.00348 | 0.36175 3 | 0.27191 | 0.15931 | 0.14973 | 0.12193 | 0.05189 | 0.03662 | 0.02154 | 0.01174 | 0.17533 4 | 0.22685 | 0.17773 | 0.14569 | 0.11136 | 0.07806 | 0.05767 | 0.04432 | 0.01909 | 0.13923 5 | 0.23428 | 0.05530 | 0.08505 | 0.09827 | 0.10931 | 0.07653 | 0.02990 | 0.00869 | 0.30268 6 | 0.00000 | 0.07570 | 0.14545 | 0.16684 | 0.15398 | 0.09199 | 0.05191 | 0.01520 | 0.29893 7 | 0.04520 | 0.12515 | 0.14961 | 0.11707 | 0.09065 | 0.07277 | 0.05207 | 0.02613 | 0.32136 SUM | 1.00000 | 1.00000 | 0.98142 | 0.89921 | 0.76050 | 0.56102 | 0.34692 | 0.14853 | 「姫(1)」が0.40603の確率で使われないうちに勝負がつくカードだということは，ゲームの性質から予想されるとおりであるが，次に使われない確率が高いカードが「密偵(2)」だというのは，そこそこ意外と言えるかもしれない．ナッシュ均衡戦略同士の対戦における引き分け対戦の確率は 0.07585 となった．<jupyter_code>def addprob(state, v, probs, s2moves):
    if state not in s2moves:
        ns = neg_state(state)
        probs[ns] = probs.get(ns, 0) + v
    else:
        probs[state] = probs.get(state, 0) + v


def propagate_prob(state, s2moves, probs, double_assassin=False):
    if is_final(state):
        return
    if state not in probs:
        return
    p = probs[state]
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    negs = neg_state(state)
    if dspy == 0:
        v = 0
        for m1, p1 in s2moves[state]:
            for m2, p2 in s2moves[negs]:
                ns = next_state(state, m1, m2, double_assassin)
                addprob(ns, p * p1 * p2, probs, s2moves)
    elif dspy == -1:
        assert prevcard < 0
        for m1, p1 in s2moves[state]:
            ns = half_move(state, m1, double_assassin)
            addprob(ns, p * p1, probs, s2moves)
    else:
        assert dspy == 1
        assert prevcard >= 0
        for m1, p1 in s2moves[state]:
            ns = half_move(state, m1, double_assassin)
            addprob(ns, p * p1, probs, s2moves)
probs = {}
probs[init_state] = 1
for level_states in all_states:
    for s in level_states:
        if s[5] < 0:
            propagate_prob(s, s2moves, probs)
    for s in level_states:
        if s[5] >= 0:
            propagate_prob(s, s2moves, probs)
cprob = [[0] * 8 for _ in range(8)]
for i, level_states in enumerate(all_states):
    for s in level_states:
        if s[5] < 0:
            p = probs.get(s, 0)
            if s[3] != 0:
                p *= 0.5
            for m, p1 in s2moves[s]:
                cprob[i][m] += p * p1
    for s in level_states:
         if s[5] >= 0:
            p = probs.get(s, 0) * 0.5
            for m, p1 in s2moves[s]:
                cprob[i][m] += p * p1
print('cards＼turn &', ' & '.join(str(x) for x in range(1, 9)), ' & not used \\\\')
for c in range(8):
    print(c, end='')
    for j in range(8):
        print(f' & {cprob[j][c]:.5f}', end='')
    notused = 1 - sum(cprob[j][c] for j in range(8))
    print(f' & {notused:.5f} \\\\')
print('SUM', end='')
for j in range(8):
    print(f' & {sum(cprob[j]):.5f}', end='')
print(' & \\\\')<jupyter_output><empty_output><jupyter_text>ランダムプレイヤ相手の利得ランダムプレイヤの戦略をナッシュ均衡戦略におけるs2movesと同じように「状態からmove確率への辞書」の形で計算し，変数s2random_moves　に代入する．<jupyter_code>s2random_moves = {}
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    moves = mask2moves(mask1)
    n = len(moves)
    ms = [(move, 1/n) for move in moves]
    s2random_moves[s] = ms<jupyter_output><empty_output><jupyter_text>大きさ2の配列 ps2val を `[プレイヤ1の戦略，プレイヤ2の戦略]` として与え，ある状態からそれ以降，それぞれのプレイヤがその戦略でプレイした時の利得の期待値を計算する関数 state_p2_value は以下のように定義できる．<jupyter_code>from typing import List
def state_p2_value(state, turn, sts, ps2val, double_assassin=False):
    if is_final(state):
        return final_score(state)
    if (turn, state) in ps2val:
        return ps2val[(turn, state)]
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    negs = neg_state(state)
    if dspy == 0:
        v = 0
        for m1, p1 in sts[turn][state]:
            for m2, p2 in sts[1 - turn][negs]:
                ns = next_state(state, m1, m2, double_assassin)
                v += p1 * p2 * state_p2_value(ns, turn, sts, ps2val, double_assassin)
    elif dspy == -1:
        if prevcard >= 0:
            return -state_p2_value(negs, 1 - turn, sts, ps2val, double_assassin)
        v = 0
        psum = 0
        for m1, p1 in sts[turn][state]:
            psum += p1
            ns = half_move(state, m1, double_assassin)
            v += p1 * state_p2_value(ns, turn, sts, ps2val, double_assassin)
        assert abs(psum - 1) < 1e-5
    else:
        assert dspy == 1
        if prevcard < 0:
            return -state_p2_value(negs, 1 - turn, sts, ps2val, double_assassin)
        v = 0
        psum = 0
        for m1, p1 in sts[turn][state]:
            psum += p1
            ns = half_move(state, m1, double_assassin)
            v += p1 * state_p2_value(ns, turn, sts, ps2val, double_assassin)
        assert abs(psum - 1) < 1e-5
    ps2val[(turn, state)] = v
    return v<jupyter_output><empty_output><jupyter_text>プレイヤ1として，linprogで求めたナッシュ均衡戦略，プレイヤ2がランダム戦略を用いた時の初期状態の利得の期待値は　0.46077987737649917　となった．利得は負け-1, 引き分け0, 勝ち1なので勝率に換算すると7.3割程度になる．一般にナッシュ均衡ポリシーは一意でないので，ナッシュ均衡戦略であり，ランダムプレイヤに対する勝率がこれよりも大きくなる戦略は存在する可能性はあるが，どの戦略に対しても期待値が0以上であり，ランダムプレイヤに7割以上の勝率となる戦略が存在することが確かめられたことになる．<jupyter_code>ps2val = {}
against_random = state_p2_value(init_state, 0, (s2moves, s2random_moves), ps2val)
print(against_random)<jupyter_output><empty_output><jupyter_text>負ける王子は出さないが他はランダムなプレイヤ相手の期待利得完全なランダムプレイヤでは，「密偵」によって出す順序が決まっているときに，「相手が先に「姫」を出したのに，自分が後から「王子」を出す」，「相手が「姫」をもっているのに，自分が先に「王子」を出す」という負けが確定することがあきらかなアクションも等確率で生成してしまう．この2つのパターンを除いて等確率で手を選択する戦略に対するナッシュ均衡戦略の利得の期待値は約 0.43970 となった．<jupyter_code>s2noprince_moves = {}
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    moves = mask2moves(mask1)
    if 7 in moves and len(moves) > 1 and (prevcard == 1 or (prevcard == -1 and dspy == -1 and (mask2 & (1 << 1)) != 0)):
        moves.remove(7)
    n = len(moves)
    ms = [(move, 1/n) for move in moves]
    s2noprince_moves[s] = ms
ps2val = {}
against_noprince = state_p2_value(init_state, 0, (s2moves, s2noprince_moves), ps2val)
print(against_noprince)<jupyter_output><empty_output><jupyter_text>大逆転現在の獲得ポイントが高いほうが勝率が高いと予想される．これを確かめるために，P1のポイントと，P2のポイントごとの「P1の勝ち，勝ちでも負けでもない，P2の勝ち」の状態数を数える．まずは，同時出しの状態で，P1のポイントと，P2のポイントごとの「P1の勝ち，勝ちでも負けでもない，P2の勝ち」の状態数を計算する．出力を整形したのが以下の表になる．P1＼P2 | 0 | 1 | 2 | 3 --- | --- | --- | --- | ---0 |(580, 2191, 580) |(2371, 5830, 1346) |(2939, 9582, 2199) |(2500, 11147, 4843) 1 |(1346, 5830, 2371) |(3234, 10284, 3234) |(3277, 14135, 4333) |(2643, 13545, 8720) 2 |(2199, 9582, 2939) |(4333, 14135, 3277) |(3994, 14165, 3994) |(3149, 10342, 6597) 3 |(4843, 11147, 2500) |(8720, 13545, 2643) |(6597, 10342, 3149) |(2499, 4426, 2499)<jupyter_code>wl = [[[0] * 3 for _ in range(4)] for _ in range(4)]
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if dspy != 0:
        continue
    v = s2val[s]
    if abs(v - 1) < 1e-5:
        wl[score1][score2][0] += 1
    elif abs(v + 1) < 1e-5:
        wl[score1][score2][2] += 1
    else:
        wl[score1][score2][1] += 1
print('P1＼P2 & 0 & 1 & 2 & 3 \\\\')
for i in range(4):
    print(i, '&', end='')
    for j in range(4):
        print(tuple(wl[i][j]), '&' if j != 3 else '', end='')
    print('\\\\')<jupyter_output><empty_output><jupyter_text>次に，手番出しの状態で，P1のポイントと，P2のポイントごとの「P1の勝ち，勝ちでも負けでもない，P2の勝ち」の状態数を計算する．出力を整形したのが以下の表になる．P1＼P2 | 0 | 1 | 2 | 3 --- | --- | --- | --- | ---0 |(1273, 237, 305) |(4368, 697, 1083) |(5920, 2314, 1792) |(5591, 5077, 3443) 1 |(4188, 556, 1342) |(8186, 1917, 2298) |(8942, 6455, 3139) |(9539, 10515, 7323) 2 |(7245, 1303, 1793) |(12674, 4217, 2139) |(15130, 8765, 3371) |(13122, 7437, 7500) 3 |(10761, 2053, 1502) |(20450, 4307, 1947) |(20515, 4598, 2892) |(10705, 1767, 3734)<jupyter_code># P1, p2が(0,3)で wscore1が1なのに勝てる例
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if abs(s2val[s] - 1) < 1e-5 and score1 == 0 and score2 == 3 and dspy == 0 and wscore1 == 1:
        print(s)
# P1, p2が(0,3)で wscore1が2なのに勝てる例
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if abs(s2val[s] - 1) < 1e-5 and score1 == 0 and score2 == 3 and dspy == 0 and wscore1 == 2:
        print(s, state2moves(s))

s = ((240, 54), (0, 3), (2, 1), 0, 0, -1)
print(s2moves[s])
wl = [[[0] * 3 for _ in range(4)] for _ in range(4)]
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if dspy == 0:
        continue
    v = s2val[s]
    if abs(v - 1) < 1e-5:
        wl[score1][score2][0] += 1
    elif abs(v + 1) < 1e-5:
        wl[score1][score2][2] += 1
    else:
        wl[score1][score2][1] += 1
print('P1＼P2 & 0 & 1 & 2 & 3 \\\\')
for i in range(4):
    print(i, '&', end='')
    for j in range(4):
        print(tuple(wl[i][j]), '&' if j != 3 else '', end='')
    print('\\\\')<jupyter_output><empty_output><jupyter_text>P1のポイントが0, P2のポイントが3でも勝てるケースがかなり多いが，これには，たとえば前のターンで「密偵」を出して，自分に「姫」が残っているのに相手が「王子」を出した状態が含まれていたり，引き分けがたまっていて，P1のポイントが0でも次の「勝負」に勝てば4点になる状態も含まれていて，「大逆転」といえるほどではない．引き分けによって貯まった「勝負」がなく，P1のポイントが0, P2のポイントが3 の必勝状態は 405 個見つかったが，いずれも，前のカードで前の「勝負」で自分が「密偵」を出した後出しの状態だった．そのうち，自分が「姫」を持っているのに相手が先出しで「王子」を出した状態を除くと 284個だった．あの1つとして，(([3, 4, 5, 6, 7], [1, 2, 3, 4, 6]), (0, 3), (1, 1), 1, 0, 3) をみてみる．これは相手が，[姫(1), 密偵(2), 暗殺者(3), 大臣(4), 将軍(6)] の中から「暗殺者(3)」を先出しした状態である．ここで「王子(7)」を出すと「暗殺者」の能力に関わらず，勝ち(([3, 4, 5, 6], [1, 2, 4, 6]), (1, 3), (1, 1), 0, 0, -1) に遷移する．次は「将軍(6)」を出してその後，手数はかかるが勝ちが確定する．  双方が暗殺者を出したときの処理「暗殺者」の効果に関してはここまでは説明書に基づいて「強さ」が小さい方が勝つとして，双方が「暗殺者」を出した時も「強さ」が小さい方が勝つと解釈した．一方で説明書の説明には合致しないが，「暗殺者」の効果を「強さ」の大小が逆転すると解釈して，双方が「暗殺者」を出した時には，再逆転して「強さ」が大きいほうが勝つとするルールも成立する．双方が「暗殺者」を出したときは，「強さ」は同じなので，この2つのルールで違いがないと思われるかもしれないが，前の「勝負」でどちらかが片方が「将軍」を出した場合は，「将軍」を出したプレイヤの「強さ」は本来の「暗殺者」の「強さ」3に+2されて5となっているので，どちらが勝つかが変わることになる．このルールの変更を行なった時にはは，関連する関数を `double_assassin = True`　として呼び出して計算するのは最初に見た通りである．また，状態数についても既に表示した．初期状態のナッシュ均衡戦略は```s2moves_da[init_state]```で得られる．<jupyter_code>s2moves_da[init_state]<jupyter_output><empty_output><jupyter_text>```[[0, 0.0], [1, 0.0], [2, 0.22156547500457635], [3, 0.2727160147959778], [4, 0.22684188446746653], [5, 0.2345877102316777], [6, 0.0], [7, 0.04428891550030161]]```オリジナルルール(`double_assassin=False`)と比べると，「密偵」，「大臣」，「王子」を出す確率を少し減らし，「暗殺者」，「魔術師」を出す確率を少し増やしている．勝率の変化が大きい状態の例として，```(([3, 6], [3, 4]), (3, 3), (1, 1), 1, -2, 3)```をみてみる．これは，前の「勝負」で自分の「密偵(2)」を出し，この「勝負」で，相手が「暗殺者(3)」を出した状態である(相手は前回「将軍(6)」を出して「強さ」を +2している)．暗殺者逆転ルールでは，自分が「将軍(6)」を出すと相手の勝ち．「暗殺者(3)」を出しても「強さ」3と5で相手の勝ちとなる．```s = state2masks((([3, 6], [3, 4]), (3, 3), (1, 1), 1, -2, 3))print('double_assassin', s2val_da[s])```を実行してみる．<jupyter_code>s = state2masks((([3, 6], [3, 4]), (3, 3), (1, 1), 1, -2, 3))
print('double_assassin', s2val_da[s])<jupyter_output><empty_output><jupyter_text>実行結果は，```double_assassin -1.0```となり，手番の負けが確かめられる． それに対して，しかし，オリジナルルールでは「暗殺者3」を出して「強さ」が3と5でこの「勝負」は自分が勝ち，ゲーム全体も勝つ．すなわち，勝敗が入れ替わる状態である．```print('original', s2val[s])```を実行してみる.<jupyter_code>print('original', s2val[s])<jupyter_output><empty_output><jupyter_text>実行結果は，```original 1.0```となり，手番の勝ちが確かめられる．  厳密解ソルバの利用厳密解は簡単な有理数にはならなかった．たとえば，初期状態で「密偵（2）」を出す確率は```s2moves_exact[init_state][2][1]```で得られる．<jupyter_code>s2moves_exact[init_state][2][1]<jupyter_output><empty_output><jupyter_text>これは，```140507605428419060087662949460607193964309474782825567523650344946508297203215257415118500503363932771617461666421410134123668781288277916606554904829098450308940224612049396180907378584184206355527991915950224354666408093704231056162489860261795606256062765425584003493412778180740047509335812149418772763860215384193049361312750491025484595088274322914145934819306102997789841157559076378079867070726593931923082168875006723979001511363510556623403583706092894006571083579472251277801279632167758109385981715767360879908088372145979208611219581840203189452795107564114627491906960633613405851206368863871225805528506755915871943983520285818039563380219891615341784109657661720193101498201373455296983623899092812229011502661593698328297747036818201225064392387883590231491333649095625352671243312517156141069078486154908696029293676062647954431513255315373321328530199500437422794750823798513801945618548134657849989883444700072345106483420241582387892861759764695779695451864380854533647222230113059578863444223038180477061386718874263184813284046092172283946052673158357305685364277875912339028630560970591418854694066929452173615116316676577013800094659708158266096356866902059455171383792117082179258025434733867176534641392120052304961434590560246671969259574721420567278727376789824822257581538265348784795256137710426334695012798802311599249672119820329658223658530709530213353374794991081436675598186880254488173219006436589650544211491023310713679074531600906690392226937061385701518545331908227958950343300742781342309712944498724873083383096838395960729330573716756672223003793157949401097623223863690306227012341004187775827049062275867177922038818545545539807839978182419062030986104746186137914642696116420931963050908465919834914723158789803080756343736512315808416165016665871340421160513924417557070955351633604820436967820789571255941378117028565730664261722398944120125732768630660127370305730844155008507520299052025977844674297395717754097027399045939183416179158880238006203601802211056490153201923764615367906344587639541600502283348158870389904117241565269103585637738482901743648706204644803700579767416454626776060035896356693009069529421881168277010407434485318528968809381877572815594874387329320431201146386825255158549270560549172749890288623815962807922634520372279011329552302870431889054172755850614585484156391744206420145917233399232178047736965693918732657723678721791645342661970981540905051324499255481820887343035777508773247206338529425599209383462965440333893347091338455013284878270823361406140993084967760884892935171709058903138962011595789609157527444525866793586272790321388792375089545730287614533361864636647115524164850556776763433638626554866229693747528357883707016653834340237956198997694643207413870505737031451916052399282068400359699244183425585284344900941978482510416748726960042432243995785975184064744878764389381138436115291566182126682911241201034832752886540236949735561238994252589815374035193720883857010208077879467778577634527307618816332767196657840692688835646684524157300596009778686316115802738721530348457177600600071425085363720014084228824230137823060955408169996804875377799718097679244944994154110381054870701857752253534342431479555080353121204272265705943737035```となり，残念ながらシンプルな解にはならなかった．  検証厳密解 s2val と通常解 s2val_exact で大きな差がないかどうかの検証をおこなう．`double_assassin=True`, `double_assassin=False` のどちらでも $10^{-8}$以下の違いはなかった．<jupyter_code># 厳密解と通常解との差がないかどうかの検証
for k in s2val:
    if abs(s2val[k] - s2val_exact[k]) > 1e-8:
        print('k, s2val, s2val_exact', (k, s2val[k], s2val_exact[k]))
# 厳密解と通常解との差がないかどうかの検証 (double_assassin = True)
for k in s2val_da:
    if abs(s2val_da[k] - s2val_da_exact[k]) > 1e-8:
        print('k, s2val_da, s2val_da_exact', (k, s2val_da[k], s2val_da_exact[k]))<jupyter_output><empty_output><jupyter_text>解の一意性のチェック同時出しの解が一意かどうかは，目的関数を等式制約に加えた上で，目的関数として，各変数の最大化，最小化で解いてみて，元の解と一致するかどうかでチェックできる．<jupyter_code>def is_unique_simultaneous(state, s2val, s2moves, double_assassin=False, mylinprog=scipy.optimize.linprog, debug=False):
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = state
    moves1, moves2 = mask2moves(mask1), mask2moves(mask2)
    n = len(moves1)
    c = [-1] + [0] * n
    bounds = [(None, None)] + [(0, None)] * n
    A_eq = [[0] + [1] * n]
    b_eq = [1]
    A_ub = []
    b_ub = []
    for j, move2 in enumerate(moves2):
        l = [1]
        for i, move1 in enumerate(moves1):
            l.append(-statevalue(next_state(state, move1, move2), s2val, s2moves, double_assassin, mylinprog))
        A_ub.append(l)
        b_ub.append(0)
    if debug:
        print('(A_ub, b_ub, A_eq, b_eq, bounds)', (A_ub, b_ub, A_eq, b_eq, bounds))
    res = mylinprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')
    if debug:
        print('res.x', res.x)
    moves = []
    for i, move1 in enumerate(moves1):
        moves.append((move1, res.x[i + 1]))
    x = res.x[1:]
    s2moves[state] = moves
    A_eq.append([1] + [0] * n)
    b_eq.append(res.x[0])
    if debug:
        print('A_eq', A_eq, 'b_eq', b_eq)
    for i in range(n):
        for j in [-1, 1]:
            c = [0] * (n + 1)
            c[i + 1] = j
            res = mylinprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')
            if abs(res.x[i + 1] - x[i]) > 1e-7:
                if debug:
                    print('x', x, 'res.x', res.x)
                return False
    return True
count_uniq, no_uniq = 0, 0
for s in s2val:
    ((mask1, mask2), (score1, score2), (wscore1, wscore2), dspy, dgeneral, prevcard) = s
    if dspy != 0:
        continue
    if not is_unique_simultaneous(s, s2val, s2moves):
        no_uniq += 1
    else:
        count_uniq += 1
print('count_uniq', count_uniq, 'no_uniq', no_uniq)        
s = init_state
print('s', s, 'is_unique_simultaneous(s)', is_unique_simultaneous(s,s2val, s2moves))
s = ((253, 253), (0, 0), (2, 2), 0, 0, -1)
print('s', s, 'is_unique_simultaneous(s)', is_unique_simultaneous(s, s2val, s2moves))
s = ((251, 251), (0, 0), (2, 2), 0, 0, -1)
print('s', s, 'is_unique_simultaneous(s)', is_unique_simultaneous(s, s2val, s2moves))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15548212543244921, 'fraction_numerical': 0.15767763683136699, 'mean_word_length': 3.691323345817728, 'pattern_counts': {'":': 0, '<': 156, '<?xml version=': 0, '>': 144, 'https://': 17, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '446073', 'license': 'Apache-2.0', 'n_tokens_mistral': 26663, 'n_tokens_neox': 22837, 'n_words': 3613, 'path': 'notebooks/r-rivals.ipynb', 'repo_name': 'tanakat01/r-rivals', 'size': '45103'}