iconEuler Examples

Analysis of Games

by R. Grothmann

Games of strategy can be analyzed in Euler

In this notebook, we provide examples for all three methods. You will see that games in math are a fascinating subject.


We start the following simple game:

Throw a dice, and decide, if you want to accept, or to try another throw. If you try again and throw the same or something less you lose and get nothing. If you decide to stop you get the current value. You can repeat that as often as you want.

What is the best strategy, and what is the average win?

You might notice that this is similar to Jeopardy, where you have a chance to answer each question correctly and promote, or fall back to nothing. The probabilities may be harder to nail down, but the idea is the same.

The solution is to work back from the 6 to the 1 and compute the expected win for each throw. The value of a 6 is just 6. For any lower number, we decide to throw again if the expected value of higher numbers is better than the value we have.

Let us make a function for this.

>function value (n) ...
 for i=n-1 to 1 step -1;
 return v
[3.5,  3,  3,  4,  5,  6]

The result is, that we keep 3 to 6, and try again with 1 and 2. The 2 has value 3, since

Analysis of Games

and the 1 has a better value (!) since

Analysis of Games

Note that we take the value 3 for the number 2 to compute the value of 1. I.e., if we throw a 2 after the 1, we throw again.

The expected win is a bit more than 4.

>fraction mean(value(6))

What, if we play the same game with a deck of 1000 cards?

>v=value(1000); plot2d(v):

Analysis of Games

It is clear that v(x)=x for x large enough. The turning point is at 414, where we are better off to try again.


The expected win is about 627.


Continuous Case

Let us explain this graph. We play the game in the interval [0,1], choosing points there at random. If we get x, and choose to continue, our expected win is the average of v(t) for t>=x.

Analysis of Games

First of all, the turning point s is easy to compute, since v(t)=t for t>=s.

>&integrate(t,t,x,1), &solve(%=x,x)
                                1   x
                                - - --
                                2   2

                 [x = - sqrt(2) - 1, x = sqrt(2) - 1]

The value of s is the second solution. It explains the turning point at 414 we observed in the discrete case for n=1000.


Left of s, we can differentiate the equation which defines v and get

Analysis of Games

with the solutions

Analysis of Games

We determine lambda, such that the two branches fit.


Now we can make a function of that.

>function v(x) := max(lambda*(exp(-x)),x);

The function looks as expected from the case n=1000.


Analysis of Games

The expected win is just lambda as computed above.


We can get the same result in Maxima using symbolic analysis.

>s &= sqrt(2)-1; lambda &= s/exp(-s),
                                     sqrt(2) - 1
                      (sqrt(2) - 1) E

>&integrate(lambda*exp(-x),x,0,s)+integrate(x,x,s,1) | ratsimp
                                     sqrt(2) - 1
                      (sqrt(2) - 1) E

Discrete Case

It is also possible to compute the discrete results exactly. We seek a discrete function with

Analysis of Games

It is clear, that v(k)=k for large i.

>&assume(k>0,n>0); sk &= sum(i,i,k+1,n)/n | simpsum | factor
                         (n - k) (n + k + 1)
                                 2 n

We compute the turning value k0. So we search the largest value k, where v(k)>k. In this case, v(k) becomes the sum on the right side of its equation.

>&solve(sk=k,k); k0 &= k with %[2]
                    sqrt(8 n  + 8 n + 1) - 2 n - 1

The fraction k0/n has the known limit.

                             sqrt(2) - 1

For smaller values than k0, we get

Analysis of Games


Analysis of Games

Analysis of Games

So it is no surprise, that the exponential function appears. In fact, we get the same result in the limit.

>&(1+1/n)^k0*k0, &limit(%/n,n,inf) | ratsimp
                sqrt(8 n  + 8 n + 1) - 2 n - 1
          1                   2
        ((- + 1)
                                   (sqrt(8 n  + 8 n + 1) - 2 n - 1))/2

                                     sqrt(2) - 1
                      (sqrt(2) - 1) E


The rules of this game are quite simple. You probably know it: Each player selects secretly rock, paper or scissors, and both show their selection with hand signs at the same time. The win matrix for this game is the following.

Analysis of Games

Our selection is one of the columns, and the selection of the opponent is one of the rows. The outcomes are in the table, seen from our side.

I.e., rock wins against scissors, scissors win against paper, and paper wins against rock (paper wraps the rock).

>A := [0,1,-1;-1,0,1;1,-1,0]; shortest A
        0         1        -1 
       -1         0         1 
        1        -1         0 

We develop a worst case tactics. So we select probabilities

Analysis of Games

for each item. With these we compute the minimal expected win under all possible selections of the opponent. This is the worst case for our selection of probabilities. We get

Analysis of Games

for all rows i, where h is the minimal win.

The best strategy with the least worst case outcome maximizes h under the above conditions, and the additional condition

Analysis of Games

This can be translated into a problem of linear programming.

>M := A|-1; ...
 M := M_[1,1,1,0]; ...
 shortest M
        0         1        -1        -1 
       -1         0         1        -1 
        1        -1         0        -1 
        1         1         1         0 

The variables are p1,p2,p3,h. The first three rows are the inequalities,

Analysis of Games

and the last one is the equality

Analysis of Games

The right hand side is 0 for the inequalities, and 1 for the equality.

>b := zeros(rows(A),1)_1

The equation type is 1 (>=) or 0 (=).

>eq := [1,1,1,0]'

The target is to maximize h, the last variable.

>c := zeros(1,cols(A))|1
[0,  0,  0,  1]

Now we can start the Simplex algorithm.

>fraction simplex(M,b,c,eq=eq,restrict=[1,1,1,0],max=1,>check)

The result is, that we have to select each item with the same probability. The worst outcome is 0.

I have put this all into the function game(A) contained in the file game.e.

>load games.e;

This function computes the optimal strategy p, and the worst case result.

>{p,res}=game(A); fraction p,
[1/3,  1/3,  1/3]


There is a modification of the game, with an additional item "well", which wins against scissors and rock (fall into well). The matrix for this is the following.

>A1 := [0,1,-1,1;-1,0,1,-1;1,-1,0,1;-1,1,-1,0]; shortest A1
        0         1        -1         1 
       -1         0         1        -1 
        1        -1         0         1 
       -1         1        -1         0 

The old optimal probabilities can no longer be used, since the opponent can beat them by selecting "well" all the time.

In fact, we get a different solution. We play paper, scissors, and well with equal probability.

>{p,res}=game(A1); fraction p
[0,  1/3,  1/3,  1/3]

The worst case is still 0. The game is fair. It must be fair, since it is absolutely symmetric. The game matrix for the opponent is -A'.


Simple Poker Game

The most simple Poker game goes like this: Both players get a random number from 1 to n.

In the latter case the player with the larger number gets the staked amount (wins 2$). With the same numbers, the outcome is 0.

The first player has three tactics:

1. pass all the time
2. hold with 1, pass with 2
3. pass with 1, hold with 2
4. hold with 1 and 2

2. is clearly inferior to 4., so we do cancel it from the list. The tactics remaining can be labelled

1. --
3. -+
4. ++

The second player has a similar list. The outcome is somewhat difficult to compute, since it depends on the probabilities of 1 and 2.

E.g., if player 1 selects -+ and player 2 selects -+, player 1 will loose 1$ when he gets a 1, and win 1/2$ on average when he gets a 2, since the other player in this case will pass with 1 and hold with 2. Thus the expected win of tactics -+ against -+ is

Analysis of Games

for the first player. This is of course an expected loss of 1/4.

E.g., let us compute -+ against ++. For 1, the first player gets -1$. For a 2 he wins 2$ with chance 1/2, yielding 1$ on average. The total average is 0$.

We fill out the matrix carefully.

Analysis of Games

>B1 := [-1,0,1;-1,-1/4,0;-1,0,0]; fraction B1
       -1         0         1 
       -1      -1/4         0 
       -1         0         0 

The following optimization says, that the first player has to select ++ all the time. If he doesn't the second player can punish him with -+.

[0,  0,  1]

We can compute the optimal strategy of the second player using the transposed matrix with reverted outcomes. He can select -+ all the time. But it is clear that he can also select ++.

[0,  0,  1]

More Card Values

We can try to expand this method to more than 2 values. Let us assume the players get 1 to n randomly with equal probability 1/n.

We consider only the tactic i: "Pass with less than i" for both players. E.g., i=1 means: "Pass never". One can see easily that this is the best tactic, which passes for i-1 card values.

First we build a matrix, which shows the outcome, if player 1 selects j, and player 2 selects i, for each card value 1 to n of player 1, and 1 to n of player 2.

>function T (i,j,n) ...
   in=1:n; jn=in';
   if j>1 then H[1:n,1:j-1]=-1; endif;
   if i>1 then H[1:i-1,j:n]=1; endif;
   return H

In the following example, player 2 does not pass with cards greater or equal 3, and player 1 does not pass with cards greater or equal 2. Here n=4.

Consequently, player 1 will lose 1$ with a 1, and player 2 will lose 1$, if player 1 has 2 or more, and he has less than 3. In all other cases, we can just compare cards for a loss or win of 2$.

>shortest T(3,2,4)
       -1         1         1         1 
       -1         1         1         1 
       -1        -2         0         2 
       -1        -2        -2         0 

Now we can compute the expected value for strategies i and j.

>function map expect (i,j,n) := totalsum(T(i,j,n))/n^2

The matrix A(n) in the following function is our game matrix.

>function A(n) := expect((1:n)',1:n,n)

The case n=2 is the lower right 2x2 matrix of above, but with columns and rows inverted, since ++ is now i=1 resp. j=1.

            0             0 
            0         -0.25 

Here is the 5x5 case.

>shortest A(5)
        0      0.12      0.08     -0.12     -0.48 
    -0.12     -0.04     -0.04      -0.2     -0.52 
    -0.08     -0.12     -0.16     -0.28     -0.56 
     0.12     -0.04      -0.2     -0.36      -0.6 
     0.48       0.2     -0.08     -0.36     -0.64 

Now we can compute the optimal strategy for player 1.

>{p,res}=game(A(5)); fraction p'


This result shows that a random bluff is a good move. Bidding with card value 1 looks unnatural at first sight. But we have to do it with probability 2/3.

The game is no longer fair. It is a loss for player 1.

>fraction res

If we forbid player 1 to bid with card 1, he loses more.

>M5=A(5); M5[:,1]=-1; ...
 {p,res}=game(M5); fracprint(p'), res

Let us look at the strategy for player 2. It turns out, that this player has to be more reasonable.

>{p,res}=game(-A(5)'); fracprint(p'), res

Let us try to disallow holding with 1 or 2 for player 2. The result is worse.

>M5=-A(5)'; M5[:,1:2]=-1;
>{p,res}=game(M5); fracprint(p'), res

A large Example

The case n=100 takes about 5 seconds on my computer. This is due to the generation of the the matrix A(n), which could be improved using a more direct formula. The Simplex algorithm is rather quick.

>A100=A(100); {p,res}=game(A100);

The result is: Never pass in 66% of the games, and pass in 0.34% of the games, if you have less than 34. You will lose 0.11 on average.

>nonzeros(p), fraction p[nonzeros(p)]', res
[1,  34]

Let us check, if this is indeed the worst case for the strategy v.


The strategy for the second player is the following.

>{p,res}=game(-A100'); ...
 nonzeros(p), fraction p[nonzeros(p)]', res
[34,  35]

The continuous case

In the continuous case, both players get a number between 0 and 1 with equal distribution in [0,1]. From our experiments, we think that we should bid always in 2/3 of the games, and bid with 1/3 or better in the rest 1/3 of the games.

We like to compute the worst case loss for this strategy. The equivalent of our matrix is a function

Analysis of Games

If the first player has strategy y ("pass with less than y"), and the second player strategy x ("pass with less than x"), then for y>x

Other cases balance out. Carefully computing the chances for y>x and y<=x leads to the following function.

>function f(x,y) ...
   if y>x then return -y+(1-y)*x+2*(y-x)*(1-y)
   else return -y+(1-y)*x-2*(x-y)*(1-x)

Analysis of Games

The result is as expected. For our strategy, the worst case occurs for x=1/3.

>xopt := fmin("2/3*f(x,0)+1/3*f(x,1/3)",0,1)

And it has the value -1/9.


We claim that the optimal strategies are

For the first player:

For the second player:

We already checked the outcome of the strategy of the first player. It is an average loss of -1/9.

Let us check the outcome for the second player.

>yopt := fmax("f(1/3,x)",0,1)

Indeed, the outcome is 1/9.

>fraction -f(1/3,yopt)

This proves that both strategies are optimal. The proof is rather obvious. But it is also a case of a duality relation in optimization.

Let us simulate the game with both players playing the optimal strategy. The following function gets a random number for both players and a random number for the first player, so that he can select his strategy.

>function map onegame (x,y,xrand) ...
 if xrand<1/3 and x<1/3 then return -1; endif
 if y<1/3 then return 1; endif;
 if x>y then return 2;
   else return -2;

The simulation should be close to -1/9 as expected.

>n=100000; sum(onegame(random(1,n),random(1,n),random(1,n))/n)

A Taking Game

I recently found the following game in a beautiful book by Peter Winkler (Mathematische Rätsel für Liebhaber). The game starts with a row of coins of various values. The players in turn can take a coin from either end of the row. The problem is to show that the first player cannot lose if the game starts with an even number of coins. I will present the solution at the end of the notebook.

The following is just a programming lesson, and has nothing to do with numerical math or symbolic solutions. We will compute the optimal strategy for this game.

So we start by defining a simple recursive function for the optimal value a player can achieve. The vector x contains the values of the coins.

>function f(x) ...
 if n>1 then
  return max(x[1]-f(x[2:n]),x[n]-f(x[1:n-1]))
  return x[1]

It should not be too difficult to see, why this works. Let us test some examples, where the optimal strategy is clear. E.g., if the coins are increasing from the left to right, it is obviously(?) best to take the coins at the large end.

E.g., the win for the first player is n (1 at each take), if the coins are 1 to 2n.


In the next example, we have to take ones, until the second player is forced to uncover the 10. So the win is 10-1=9.


If we want to know the optimal move, we need to return it too. So I change the code a bit.

>function fi(x) ...
 if n>1 then
  return {e[3],e[4]}
  return {x[1],1}

1 means left and, and 2 means right end.

>{a,i}=fi(1:10); a, side[i],

For a challenge, let us simulate an optimal game.

>function simulate (x) ...
 if mod(n,2)==0 then "A takes:" else "B takes:" endif;
 if n==1 then x[1], return x[1]; endif
 if i==1 then x[1]|" from the left", simulate(x[2:n]);
 else x[n]|" from the right", simulate(x[1:n-1]);
 return a
>v=simulate([1,10,20,30,10,1]); "Result:", v,
1 from the right
1 from the left
10 from the left
20 from the left
30 from the left
5 from the right
4 from the right
3 from the right
2 from the right

The recursion in the example above works for a small number n of coins. However, it generates 2^n function calls.

To avoid this in a recursive algorithm, we can add some memory for function results. In fact, there are only n^2 possible coin positions during the game.

So we add a matrix to denote the optimal value for the position x[i],...,x[j] in A[i,j] and the optimal move in I[i,j]. We set up the matrices once, and use the fact that Euler passes matrices by reference. Assigning to a submatrix will in fact change the matrix.

>function fifastrek (x,i,j,I,A) ...
 if I[i,j] then return A[i,j]; endif;
 if i==j then A[i,j]=x[i]; I[i,j]=i; return x[i], endif;
 a1=x[i]-fifastrek(x,i+1,j,I,A); a2=x[j]-fifastrek(x,i,j-1,I,A);
 if a1>a2 then I[i,j]=i; A[i,j]=a1; return a1;
 else I[i,j]=j; A[i,j]=a2; return a2;

Instead of global matrices, we write a main function.

>function fifast (x) ...
 n=cols(x); I=zeros(n,n); A=zeros(n,n);
 return fifastrek(x,1,n,I,A);

Now we can solve 100 coins, which would be unthinkable with the simple recursion above.


Solution of the Problem

How about the proof that the first player can always win at an even number of coins?

This is very simple with a trick. Number the coins from left to right. If you think about it, you see that the starting player can either take all the even coins, or all the odd coins. So he simply chooses, which is better.

>function g(x) ...
 return abs(sum(x[2:2:n])-sum(x[1:2:n]))

However, this is not the optimal strategy! In the following example the odd coins 4+6 yield a win of 1. But it is better to take the 7 first, and then either the 4 for a win of 3, or the 6 for a win of 7.

>h=[4,2,6,7]; g(h), fifast(h),