#C10.txt and C11.txt combined: Help:=proc(): print(`LegalMoves(L,i), FW(L1,L2,r), fW(L1,L2,r,i), Exceptions3(N,j) `): print(` LegalMoves(L,i) , F(L,r), f(L,r,i) `): print(`SimulateOptimalGameV(L,r) `): print(`SimulateOptimalGameT(L,r) `): 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: #fW(L1,L2,r,i): The probability of L1 winning #if the roll was i, followed by the optimal move fW:=proc(L1,L2,r,i) local tom, champ,rec,mr: option remember: if L1=[0$nops(L1)] then RETURN(FAIL): fi: tom:=LegalMoves(L1,i): if tom={} then RETURN(FAIL): fi: champ:=tom[1]: rec:=1-FW(L2,champ,r): for mr in tom minus {tom[1]} do if 1-FW(L2,mr,r)>rec then champ:=mr: rec:=1-FW(L2,mr,r): fi: od: rec,champ: end: #FW(L1,L2,r): Probability of winning if your are about #to roll and your position is L1 and your opponent's #is L2 in a SINGLE r-faced fair die FW:=proc(L1,L2,r) local i: option remember: if L1=[0$nops(L1)] and L2<>[0$nops(L2)] then RETURN(1): fi: if L2=[0$nops(L2)] and L1<>[0$nops(L1)] then RETURN(0): fi: add(fW(L1,L2,r,i)[1], i=1..r)/r: end: Exceptions3:=proc(N,j) local i1,i2,i3,j1,j2,j3,gu,P,Pw,lu1,lu2: gu:={}: for i1 from 0 to N do for i2 from 0 to N-i1 do for i3 from 1 to N-i1-i2 do for j1 from 0 to N do for j2 from 0 to N-j1 do for j3 from 1 to N-j1-j2 do if f([i1,i2,i3],3,j)[1]<> fW([i1,i2,i3],[j1,j2,j3],3,j)[2] then P:=f([i1,i2,i3],3,j)[1]: Pw:=fW([i1,i2,i3],[j1,j2,j3], 3,j)[2]: lu1:=evalf(F(Pw,3)-F(P,3)): lu2:=evalf(FW([j1,j2,j3],P,3)-FW([j1,j2,j3],Pw,3)): if lu2>0 then print(`In position `,[[i1,i2,i3],[j1,j2,j3]], `the strategies conflict when the die rolled`, j): print(`according to the minimize-expected length, the optimal move is`): print(P): print(`according to the maximize the probability of winning, the optimal move is`): print(Pw): print(`The increase in expected duration if you follow the latter is`, lu1): print(`The loss of proba. of winning if you follow the former is`,lu2): gu:=gu union {[[i1,i2,i3],[j1,j2,j3], P,Pw,lu1,lu2]}: fi: fi: od: od: od: od: od: od: gu: end: #Feb. 25, 2013, C10.txt #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)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: