## 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)
}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,]))
}
``` ### 4 Responses to “awalé”

1. Wayne Says:

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.

• xi'an Says:

Thank you. I got bored on Saturday, trying to complete a three-step ahead program… You are right, go is the challenge!

2. Ronan Says:

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/

• xi'an Says:

Great: I was fishing for this kind of comments…

This site uses Akismet to reduce spam. Learn how your comment data is processed.