最適化で変形じゃんけんを考える

## これなに

「[授業で使える　中学校数学パズル・ゲーム大全](https://www.meijitosho.co.jp/detail/4-18-281714-4)」という本のp136の問題について、3人の場合の戦略を考えてみます。

### その問題（アレンジしています）

> 3人で変形じゃんけんをします。みんなで同時に指を0本か1本か2本出します。3人の指の合計を3で割った余りと等しい指を出した人が勝ちです。

- 0人勝ちの場合：全員の得点0
- 1人勝ちの場合：勝った人の得点2、負けた人の得点-1
- 2人勝ちの場合：勝った人の得点0.5、負けた人の得点-1
- 3人勝ちの場合：全員の得点0

## 考え方その1

「[組合せ最適化でゲーム理論を解く](https://qiita.com/SaitoTsutomu/items/eeb19fc086640562513e)」を参考にして、混合戦略を最適化で解きましょう。

私（k）の各指を出す確率を`xyz = [x, y, z]`としましょう。
2人（iとj）が出す指に対する得点の最小値を最大化します。

定式化は参考先と同様に考えます。解いてみましょう。

```python
from pulp import LpProblem, LpMaximize, LpVariable, lpSum, value

def val(i, j, k):
    """kの得点"""
    h = (i + j + k) % 3
    wini = i == h
    winj = j == h
    wink = k == h
    s = wini + winj + wink
    return 0 if s % 3 == 0 else (3 - s) / s if wink else -1

m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
    for j in range(3):
        e = lpSum(val(i, j, k) * v for k, v in enumerate(xyz))
        m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
```

出力

```
-0.5 [0.0, 0.5, 0.5]
```

出力は、目的関数値と`xyz`の値です。
負け越してます。これは、2人（iとj）が私（k）を負かすために共闘している前提だからですね。

## 考え方その2

2人が共闘しないと仮定しましょう。一旦、1人（j）が混合戦略（`pjs`）に従い、1人（i）は、私（k）を負かすために最善を尽くすとします。
とりあえず、`pjs = [0.0, 0.5, 0.5]`とします。

```python
pjs = [0.0, 0.5, 0.5]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
    e = lpSum(pj * val(i, j, k) * v
              for j, pj in enumerate(pjs)
              for k, v in enumerate(xyz))
    m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
```

出力

```
-0.5 [0.0, 0.0, 1.0]
```

やっぱり負け越しています。これは、1人（i）が、私（k）を狙い撃ちしているからでしょうか。

## 考え方その3

2人分（iとjとします）の混合戦略を知っている場合を確認します。

```python
pis = [0.0, 0.5, 0.5]
pjs = [0.0, 0.0, 1.0]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
e = lpSum(pi * pj * val(i, j, k) * v
          for i, pi in enumerate(pis)
          for j, pj in enumerate(pjs)
          for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
```

出力

```
1.0 [1.0, 0.0, 0.0]
```

勝ち越しました。これは、2人（iとj）は、私（k）の戦略を知らず、私だけ2人の戦略を知っているからでしょう。

## 考え方その4

混合戦略を知られると対策を取られて不利になります。どうすればいいでしょうか？
1人（j）の混合戦略を`[1 / 3, 1 / 3, 1 / 3]`として試してみましょう。

```python
pjs = [1 / 3, 1 / 3, 1 / 3]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
for i in range(3):
    e = lpSum(pj * val(i, j, k) * v
              for j, pj in enumerate(pjs)
              for k, v in enumerate(xyz))
    m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
```

出力

```
0.0 [0.33333333, 0.33333333, 0.33333333]
```

1人（j）が均等に出す場合、私（k）も均等に出せば、最悪でも引き分けにできました。

## 考え方その5

2人（iとj）が均等に出す場合、残りの人の最適な混合戦略を確かめてみましょう。

```python
pis = [1 / 3, 1 / 3, 1 / 3]
pjs = [1 / 3, 1 / 3, 1 / 3]
m = LpProblem(sense=LpMaximize)
w = LpVariable('w')
xyz = [LpVariable(c, 0, 1) for c in 'xyz']
m += w
m += lpSum(xyz) == 1
e = lpSum(pi * pj * val(i, j, k) * v
          for i, pi in enumerate(pis)
          for j, pj in enumerate(pjs)
          for k, v in enumerate(xyz))
m += w <= e
m.solve()
print(value(m.objective), [value(v) for v in xyz])
```

出力

```
0.0 [0.0, 0.0, 1.0]
```

2人の混合戦略を知っていても、得点の期待値は0になりました。ちなみに、`xyz`をどのようにしても期待値は0です。

結局、「誰も共闘しない」という前提で、他の人に混合戦略を対策されたとしても均等に出せば、期待値は0になるようです。

均等にしないと対策されて負け越してしまうので、おそらくこれが取るべき戦略になると思われます。

以上