# Viraj Pandya, Experimental Mathematics, Spring 2013 # Homework Assignment 10 - March 4, 2013 # I give Dr. Z permission to post this file Help10:=proc(): print (`FG(L,r), fG(L,r,i), SimulateOptimalGameVG(L,r), SimulateOptimalGameTG(L,r)`): end: # All of the following procedures are the same as done in class, but they're the "Greedy" versions # as indicated by the G at the end of each procedure's name. # Greedy means that, in Bearoff, the player takes a piece out of the board if possible, and if not, then # the player must move a piecest closest to the end toward the end. # Example: [0,0,0,1,0,1] with a roll of 1 means player should go to [0,0,1,0,0,1], not [0,0,0,1,1,0] #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 ##### THE FOLLOWING ARE GREEDY PROCEDURES AS INDICATED BY G AT END OF NAME # MEANING THAT THE PLAYER MOVES A PIECE INTO THE ENDZONE (OUT OF BOARD) # IF THAT MOVE IS AVAILABLE (BASED ON ROLL i). ELSE, THE PLAYER # MOVES THE PIECE CLOSEST TO THE ENDZONE TOWARDS THE ENDZONE #FG(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 GREEDY play FG:=proc(L,r) local i: option remember: add(fG(L,r,i)[2],i=1..r)/r: end: #fG(L,r,i): inputs L and r as above and i between 1 and r #and outputs the GREEDY move, followed by the #expected length if you do it # remember greedy means to move piece into the endzone (out of board) if possible, # and if not possible, then move the piecest that is closest to the endzone # towards the endzone. fG:=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:=FG(champ,r): for hopeful in Moves minus {Moves[1]} do if FG(hopeful,r)=0 then champ:=hopeful: rec:=FG(champ,r): break: elif FG(hopeful,r)[0$nops(L)] do i:=live(): co:=co+1: print(`The roll was`, i): L1:=fG(L1,r,i)[1]: print(`The move was to go to`,L1): od: co: end: #Simulates a GREEDY Bearoff game with initial position L #and a fair r-faced die (labeled 1, ...r) #using pseudo-random number: #Terse version SimulateOptimalGameTG:=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:=fG(L1,r,i)[1]: od: co: end: #### THE FOLLOWING ARE THE PESSIMAL PROCEDURES AS INDICATED BY 'P' AT END OF NAME # MEANING THAT THE PLAYER TRIES TO MAXIMIZE THE EXPECTED DURATION OF BEAROFF GAME #FP(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 PESSIMAL play FP:=proc(L,r) local i: option remember: add(fP(L,r,i)[2],i=1..r)/r: end: #fP(L,r,i): inputs L and r as above and i between 1 and r #and outputs the PESSIMAL move, followed by the #expected length if you do it # remember pessimal means to maximize expected duration (# of rounds or rolls) fP:=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:=FP(champ,r): for hopeful in Moves minus {Moves[1]} do if FP(hopeful,r)>rec then champ:=hopeful: rec:=FP(champ,r): fi: od: champ,rec+1: end: #Simulates a PESSIMAL Bearoff game with initial position L #and a fair r-faced die (labeled 1, ...r) #using pseudo-random number: #Verbose version SimulateOptimalGameVP:=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:=fP(L1,r,i)[1]: print(`The move was to go to`,L1): od: co: end: #Simulates a PESSIMAL Bearoff game with initial position L #and a fair r-faced die (labeled 1, ...r) #using pseudo-random number: #Terse version SimulateOptimalGameTP:=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:=fP(L1,r,i)[1]: od: co: end: ##### THE FOLLOWING ARE THE RANDOM PROCEDURES AS INDICATED BY R AT END OF NAMES # MEANING THAT THE PLAYER PICKS A RANDOM (WITH RESPECT TO UNIFORM PROB DISTRIBUTION) # MOVE OUT OF THE ENTIRE LIST OF POSSIBLE MOVES (LegalMoves(L,i)) with(RandomTools): # i called that so i can pick a random element from set LegalMoves(L,i) by using # Generate(choose(Moves)): #FR(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 RANDOM play FR:=proc(L,r) local i: option remember: add(fR(L,r,i)[2],i=1..r)/r: end: #fR(L,r,i): inputs L and r as above and i between 1 and r #and outputs the RANDOM move, followed by the #expected length if you do it # remember random means to pick a random move out of LegalMoves(L,i) # with respect to the uniform probability distribution on LegalMoves(L,i) fR:=proc(L,r,i) local rec,champ, Moves: option remember: Moves:=LegalMoves(L,i): if Moves={} then RETURN(FAIL,0): fi: champ:=Generate(choose(Moves)): rec:=FR(champ,r): champ,rec+1: end: #Simulates a RANDOM Bearoff game with initial position L #and a fair r-faced die (labeled 1, ...r) #using pseudo-random number: #Verbose version SimulateOptimalGameVR:=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:=fR(L1,r,i)[1]: print(`The move was to go to`,L1): od: co: end: #Simulates a RANDOM Bearoff game with initial position L #and a fair r-faced die (labeled 1, ...r) #using pseudo-random number: #Terse version SimulateOptimalGameTR:=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:=fR(L1,r,i)[1]: od: co: end: ################ OLD STUFF ############# #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)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: