Think about transformation rock-paper-scissors by optimization

what is this

Strategy for 3 people on the problem of p136 of the book "Encyclopedia of junior high school math puzzles and games that can be used in class" Consider.

The problem (arranging)

Three people play rock-paper-scissors. Everyone puts out 0, 1 or 2 fingers at the same time. The winner is the one who puts out a finger equal to the sum of the three fingers divided by three.

--0 people win: 0 points for all --In case of 1 person win: 2 points for the winner, 1 point for the loser ――In the case of two wins: score of the winner 0.5, score of the loser -1 --If 3 players win: 0 points for all players

Way of thinking 1

Let's solve the mixed strategy by optimization by referring to "Solving game theory by combinatorial optimization".

Let the probability of putting out each finger of me (k) be xyz = [x, y, z]. Maximize the minimum score for the fingers given by two people (i and j).

The formulation is considered in the same way as the reference destination. Let's solve it.

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

def val(i, j, k):
    """k score"""
    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])

output

-0.5 [0.0, 0.5, 0.5]

The output is the objective function value and the value of xyz. I'm losing. This is because it is a premise that two people (i and j) are fighting together to beat me (k).

Way of thinking 2

Let's assume that the two do not fight together. Once one (j) follows a mixed strategy (pjs) and one (i) does his best to beat me (k). For the time being, set pjs = [0.0, 0.5, 0.5].

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])

output

-0.5 [0.0, 0.0, 1.0]

After all I am losing. Is this because one person (i) is shooting at me (k)?

Way of thinking 3

Let's see if you know a mixed strategy for two people (let's say i and j).

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])

output

1.0 [1.0, 0.0, 0.0]

I won. This is probably because the two (i and j) do not know my (k) strategy, only I know their strategy.

Way of thinking 4

If you know the mixed strategy, you will be disadvantaged by taking measures. What should i do? Let's try the mixed strategy of one person (j) as [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
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])

output

0.0 [0.33333333, 0.33333333, 0.33333333]

If one person (j) puts out evenly, and I (k) puts out evenly, at worst I could draw.

Way of thinking 5

If the two (i and j) are evenly distributed, try to find the best mixing strategy for the rest.

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])

output

0.0 [0.0, 0.0, 1.0]

Even though I knew the mixed strategy of the two, the expected score was 0. By the way, the expected value of xyz is 0 no matter what.

After all, on the premise that "no one will fight together", even if other people take measures against the mixed strategy, the expected value seems to be 0 if they are evenly issued.

This is probably the strategy you should take, as if you don't make it even, you'll be dealt with and lose.

that's all

Recommended Posts

Think about transformation rock-paper-scissors by optimization
Think about menus by combinatorial optimization
About vanilla continent optimization
Grouping by combinatorial optimization
Think about architecture in python
Affine transformation by OpenCV (CUDA)
About batch_size specified by keras
Sazae-san's rock-paper-scissors prediction by LightGBM
About type comparison by PHP
Think about dropouts with MNIST