awalé
Following 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:
Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
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.
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,])) }
May 13, 2013 at 2:24 pm
Good topic! I wrote a Mancala-playing Python program for an AI course. It looked 7 moves ahead, which was enough to crush me consistently. The game itself is very widely played and there are quite a few variations in the details. It was fascinating to research it! (Mancala, Owari, Aware, Awale, etc. There are tournaments and serious competition out there.)
Of course, the ultimate game to program is Go/Baduk/Wei’chi.
May 13, 2013 at 5:15 pm
Thank you. I got bored on Saturday, trying to complete a three-step ahead program… You are right, go is the challenge!
May 13, 2013 at 1:01 pm
What do you mean by “computer simulation of a winning strategy”? Awale is solved, there is a database of the value of each move for each possible position.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.1561
Here is an applet that plays using the database:
http://awari.cs.vu.nl/awari/
May 13, 2013 at 5:14 pm
Great: I was fishing for this kind of comments…