#Feb. 25, 2013, C10.txt

Help:=proc(): print(` LegalMoves(L,i) , F(L,r), f(L,r,i) `):
print(`SimulateOptimalGameV(L,r) `):
print(`SimulateOptimalGameT(L,r) `):
end:

#General Bearoff Backgammon with an r-faced (fair) die
#labeled(1, ...r ) and a field of size nops(L)
#starting with L=[L[1], ..., L[nops(L)]] counters
#L[i] counters at the ith-location are distance i from the end

#F(L,r): inputs a list L of non-negative integers L and
#a pos. integer r, and outputs the Expected number of
#rolls until the end under OPTIMAL play
F:=proc(L,r) local i:
option remember:


add(f(L,r,i)[2],i=1..r)/r:

end:


#f(L,r,i): inputs L and r as above and i between 1 and r
#and  outputs the OPTIMAL move, followed by the
#expected length if you do it
f:=proc(L,r,i) local rec,champ, Moves, hopeful:
option remember:
Moves:=LegalMoves(L,i):

if Moves={} then
  RETURN(FAIL,0):
fi:

champ:=Moves[1]:

rec:=F(champ,r):

for hopeful in Moves minus {Moves[1]} do
 
  if F(hopeful,r)<rec then
       champ:=hopeful:
        rec:=F(champ,r):
  fi:

od:

champ,rec+1:

end:

#LegalMoves(L,i): inputs a list of length nops(L)
#and a pos. integer i telling you that the option
#to move any counter i pieces towards the end
#without waste. And if you must waste, minimize it

LegalMoves:=proc(L,i) local S, j:

if i>nops(L) then
  RETURN(FAIL):
fi:

if L=[0$nops(L)] then
 RETURN({}):
fi:
  

S:={}:

if L[i]>0 then
  S:=S union {[op(1..i-1,L),L[i]-1,op(i+1..nops(L),L)]}:
fi:

for j from i+1 to nops(L) do
  
  if L[j]>0 then
#a counter distance j away goes to distance j-i away
   
 S:=S union {[op(1..j-i-1,L) , L[j-i]+1, op(j-i+1..j-1,L),
               L[j]-1, op(j+1..nops(L),L)]}:
  fi:


od:


if S<>{} then
  RETURN(S):
fi:


for j from i-1 by -1 to 1  while L[j]=0 do od:

{ [op(1..j-1,L),L[j]-1,op(j+1..nops(L),L)] }:

end:


#Simulates a Bearoff game with initial position L
#and a fair r-faced die (labeled 1, ...r)
#using pseudo-random number:
#Verbose version
SimulateOptimalGameV:=proc(L,r) local L1,live,co,i:

live:=rand(1..r):
co:=0:

L1:=L:

while L1<>[0$nops(L)] do

i:=live():
co:=co+1:
print(`The roll was`, i):

L1:=f(L1,r,i)[1]:

print(`The move was to go to`,L1):

od:

co:
end:

#Simulates a Bearoff game with initial position L
#and a fair r-faced die (labeled 1, ...r)
#using pseudo-random number:
#Terse version
SimulateOptimalGameT:=proc(L,r) local L1,live,co,i:

live:=rand(1..r):
co:=0:

L1:=L:

while L1<>[0$nops(L)] do

i:=live():
co:=co+1:


L1:=f(L1,r,i)[1]:



od:

co:
end: