by R. Grothmann 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) ...
n=cols(x); if n>1 then return max(x[1]-f(x[2:n]),x[n]-f(x[1:n-1])) else return x[1] endif endfunction
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.
>f(1:10)
5
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.
>f([1,10,1,1,1,1,1,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) ...
n=cols(x); if n>1 then e=extrema([x[1]-(fi(x[2:n])),x[n]-(fi(x[1:n-1]))]); return {e[3],e[4]} else return {x[1],1} endif endfunction
>side=["left","right"];
1 means left and, and 2 means right end.
>{a,i}=fi(1:10); a, side[i],
5 right
For a challenge, let us simulate an optimal game.
>function simulate (x) ...
n=cols(x); if mod(n,2)==0 then "A takes:" else "B takes:" endif; if n==1 then x[1], return x[1]; endif {a,i}=fi(x); if i==1 then x[1]|" from the left", simulate(x[2:n]); else x[n]|" from the right", simulate(x[1:n-1]); endif return a endfunction
>v=simulate([1,10,20,30,10,1]); "Result:", v,
A takes: 1 from the right B takes: 1 from the left A takes: 10 from the left B takes: 20 from the left A takes: 30 from the left B takes: 10 Result: 10
>simulate(1:5);
B takes: 5 from the right A takes: 4 from the right B takes: 3 from the right A takes: 2 from the right B takes: 1
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; endif; endfunction
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); endfunction
Now we can solve 100 coins, which would be unthinkable with the simple recursion above.
>fifast(1:100)
50
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) ...
n=cols(x); return sum(x[2:2:n])-sum(x[1:2:n]) endfunction
>g([1,10,20,30,10,1])
10
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),
-1 3