Archive for infinite recursion

awalé

Posted in Kids, pictures, R with tags , , , on May 13, 2013 by xi'an

Awalé board on my garden table, March 15, 2013Following Le Monde puzzle #810, I tried to code an R program (not reproduced here) to optimise an awalé game but the recursion was too rich for R:

[sourcecode language=”r” gutter=”false”]
Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?
[/sourcecode]

even with a very small number of holes and seeds in the awalé… Searching on the internet, it seems the computer simulation of a winning strategy for an awalé game still is an open problem! Here is a one-step R function that does  not produce sure gains for the first player, far from it, as shown by the histogram below…  I would need a less myopic strategy by iterating  this function at least twice.

[sourcecode language=”r” gutter=”false”]
onemorestep=function(x,side){
# x current state of the awale,
# side side of the awale (0 vs 1)

M=length(x);N=as.integer(M/2)
rewa=rep(0,M)
newb=matrix(0,ncol=M,nrow=M)

for (i in ((1:N)+N*side)){

if (x[i]>0){
y=x
y[i]=0
for (t in 0:(x[i]-1))
y[1+(i+t)%%M]=y[1+(i+t)%%M]+1

last=1+(i+t)%%M
if (side){ gain=(last<=N)
}else{ gain=(last>N)}

if (gain){# ending up on the right side
rewa[i]=0
while (((last>0)&&(side))||((last>N)||(!side)))
if ((y[last]==2)||(y[last]==3)){
rewa[i]=rewa[i]+y[last];y[last]=0
last=last-1
}else{ break()}
}
newb[i,]=y
}
}
if (max(rewa)>0){
sol=order(-rewa)[1]
}else{ sol=rang=((1:N)+N*side)[x[((1:N)+N*side)]>0]
if (length(rang)>1) sol=sample(rang,1,prob=x[rang]^3)}

return(list(reward=max(rewa),board=newb[sol,]))
}
[/sourcecode]

gains of player 1 obtained from using associated R code

4 Comments »

Le Monde puzzle [#815]

Posted in Books, Kids, R with tags , , , , on April 12, 2013 by xi'an

The last puzzle was as follows:

Take a card stack with 32 cards and divide it into five non-empty piles. A move consists in doubling a pile size by taking card from a single and larger pile. Is it possible to recover the original stack by repeatedly using moves? Same question for 100 cards and five piles.

I first defined a recursive R function to check if this was obvious:

[sourcecode language=”r” gutter=”false”]
destock=function(stock){

vale=FALSE
if (max(stock)==32){ #success
vale=TRUE}else{
#empty piles must remain empty
i0=min((1:4)[stock[1:4]>0])

for (i in i0:4){
for (j in (i+1):5){
stuck=stock
stuck[i]=2*stock[i] #doubling
stuck[j]=stuck[j]-stock[i] #borrowing
stuck=sort(stuck)
vale=vale||destock(stuck)
if (vale) break()
}
if (vale) break()
}}
return(vale)
}
[/sourcecode]

Then I launched the R code with random starting values:

[sourcecode language=”r” gutter=”false”]
stack=sample(1:5,27,rep=TRUE)
stock=rep(1,5)
for (i in 1:5) stock[i]=1+sum(stack==i)
stock=sort(stock)
[/sourcecode]

obtaining either a solution or “infinite recursion” warnings. In the first case, getting a sequence like

[sourcecode language=”r” gutter=”false”]
> destock(stock)
[1] 5 5 7 7 8
[1] 0 7 7 8 10
[1] 0 0 8 10 14
[1] 0 0 2 14 16
[1] 0 0 4 12 16
[1] 0 0 8 8 16
[1] 0 0 0 16 16
[1] 0 0 0 0 32
[1] TRUE
[/sourcecode]

and, in the second, observing an infinite cycle like

[sourcecode language=”r” gutter=”false”]
> destock(stock)
[1] 3 4 7 8 10
[1] 1 6 7 8 10
[1] 2 5 7 8 10
[1] 3 4 7 8 10
[1] 1 6 7 8 10
[1] 2 5 7 8 10
[1] 3 4 7 8 10
[1] 1 6 7 8 10
Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?
[/sourcecode]

The above shows that there exist pile configurations that do not allow for this recursive algorithm to converge. I then thought of introducing randomness in the exploration of the tree as possibly avoiding infinite regress

[sourcecode language=”r” gutter=”false”]
for (i in sample(i0:4)){
[/sourcecode]

and, lo and behold!, it worked for every attempt:

[sourcecode language=”r” gutter=”false”]
> destock(stock)
[1] 3 4 7 8 10
[1] 3 3 8 8 10
[1] 0 6 8 8 10
[1] 0 2 8 10 12
[1] 0 2 2 12 16
[1] 0 2 2 4 24
[1] 0 2 2 4 24
[1] 0 0 4 4 24
[1] 0 0 4 8 20
[1] 0 0 4 8 20
[1] 0 0 4 8 20
[1] 0 0 4 8 20
[1] 0 0 4 12 16
[1] 0 0 8 8 16
[1] 0 0 0 16 16
[1] 0 0 0 16 16
[1] 0 0 0 16 16
[1] 0 0 0 16 16
[1] 0 0 0 16 16
[1] 0 0 0 16 16
[1] 0 0 0 0 32
[1] TRUE
[/sourcecode]

It is rather straightforward to prove that the scheme works for a size equal to a power of two like 32 while it cannot work for sizes different from a power of 2. Like 100.

2 Comments »