Xi'an's Og

A game Le Monde mathematical puzzle:

On a linear board of length 17, Alice and Bob set alternatively red and blue tokens. Two tokens of the same colour cannot sit next to one another. Devise a winning strategy for the first player.

In the ‘Og tradition, this calls for a recurrent R code:

[sourcecode language=”r” gutter=”false”]
game=function(n=17,col=1,tak=rep(0,n)){
frei=rew=0*tak
# stopping rule
if (sum(tak==col)==0){
frei=(tak==0)}else{
for (i in (1:n)[tak!=-col])
frei[i]=(min(abs((1:n)[tak==col]-i))>1)}
# left positions
if (sum(frei)>0){
for (i in (1:n)[frei==1]){
prop=tak;prop[i]=col
rew[i]=1-game(n=n,col=-col,tak=prop)}}
# outcome of best choice
return(max(rew))}
[/sourcecode]

While I did not run the rudimentary recursive function for n=17, I got a zero return from n=2 till n=12, meaning that the starting player is always going to lose if the other player plays optimally.

This entry was posted on October 9, 2015 at 12:15 am and is filed under Books, Kids, Statistics, University life with tags Le Monde, mathematical puzzle, R, recursive function. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.