iconEuler Examples

Paper Scissors Stone

by R. Grothmann

We compute the optimal strategy for the game paper-scissors-stone. First the win-loss matrix. E.g., the first column means, that paper looses to scissors and wins to stone.

>shortformat; A=[0,1,-1;-1,0,1;1,-1,0]
        0         1        -1 
       -1         0         1 
        1        -1         0 

We are optimizing the worst case. I.e. we have to maximize the minimum of A.p for probabilities p. That is, maximize h under the conditions A.p>=h, 1'.p=1.

We add 1 to every element of A, to make sure the solution h is positive. this does not change the solution p.

>A1=A+1;

Next we need to expand the matrix A to reflect the equations A.p-h>=0, and 1'.p=1. We have the unknown vector p1,p2,p3,h.

>A2=(A1|-1)_(ones(1,3)|0)
        1         2         0        -1 
        0         1         2        -1 
        2         0         1        -1 
        1         1         1         0 

The right hand side of the equations is the following vector.

>b=zeros(3,1)_1
        0 
        0 
        0 
        1 

The target function has the following vector. Note that we have the unknowns p1,p2,p3,h.

>c=zeros(1,3)|1
[0,  0,  0,  1]

We need a vector, reflecting the type of equations (1=greater equal, 0=equal).

>eq=ones(3,1)_0
        1 
        1 
        1 
        0 

Now we can call the simplex algorithm.

>{p,res}=simplex(A2,b,c,eq=eq,max=true); ...
 res
0

res=0 shows that a solution has been found. We print p, and find that we have to choose all three with equal chance.

>p[1:3]
 0.333333 
 0.333333 
 0.333333 

The game is fair.

>p[4]-1
0

Game with 4 choices

Now we add "well" as a possible choice. The well looses only against paper.

>A=[0,1,-1,-1;-1,0,1,1;1,-1,0,1;1,-1,-1,0]
        0         1        -1        -1 
       -1         0         1         1 
        1        -1         0         1 
        1        -1        -1         0 
>A1=A+1; ...
 A2=(A1|-1)_(ones(1,4)|0); ...
 b=zeros(4,1)_1; ...
 c=zeros(1,4)|1; ...
 eq=ones(4,1)_0; ...
 {p,res}=simplex(A2,b,c,eq=eq,max=true);

This time, we must not play stone. Anytime, the opponent plays stone, he looses on average.

>p[1:4]
 0.333333 
 0.333333 
        0 
 0.333333 

Examples