####################################################################### ## BearoffOneDie Save this file as BearoffOneDie. To use it, # ## stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read BearoffOneDie # ## Then follow the instructions given there # ## # ## Written by Doron Zeilberger, Rutgers University , # ## zeilberg@math.rutgers.edu. # ####################################################################### print(`First Written: Sept. 21, 2005: tested for Maple 10 `): print(`Version of Sept. 21, 2005: `): print(): print(`This is BearoffOneDie one of the Maple packages`): print(`accompanying the article `): print(`"How to Play Backgammon (if you must) and how to Research it",`): print(` (if you have time)" `): print(`By Shalosh B. Ekhad and Doron Zeilberger.`): print(): print(`The most current version of this package and article`): print(`are available on WWW at:`): print(` http://www.math.rutgers.edu/~zeilberg .`): print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`): print(): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(`For a list of all procedure, type: ezra1();`): print(): ezra:=proc() if args=NULL then print(`BearoffOneDie`): print(`A Maple package for Winning the Bearoff stage of Backgammon played with ONE die`): print(): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(`The main procedures are: `): print(): print(`ExpectedLife, BestMovesS, BestMoves, Moves , ProbW `): print(` RankPositions , RandPositionsDetailed , Sipur, SipurC`): elif nargs=1 and args[1]=Box then print(`Box(m): all the vertices with the given range`): print(`e.g. Box([[0,4],[1,5]]);`): elif nargs=1 and args[1]=ExpectedLife then print(`ExpectedLife(Li): Given a list of length k, finds the expected`): print(`number of moves in optimal play with a k-die in`): print(`backgammon Bearoff Solitaire with ONE die`): print(`For example, try: ExpectedLife([2,2,2]);`): elif nargs=1 and args[1]=Exc1 then print(`Exc1(r,K,i): tests the hypothesis that in`): print(`r-die backgammon end-game, if the`): print(`roll is i, it is always`): print(`best to remove a checker from the i^th place`): print(`if it is occupied for all positions with K checkers`): print(`outputs all the exceptions to the rule`): elif nargs=1 and args[1]=FindP then print(`FindP(S,a,r): Given a list of exceptions and one exceptional move of the `): print(`highest number of checkes, finds its parents (if any) at level r`): print(`For example, try: gu:=Sipur(4,12): FindP(gu,gu[nops(gu)][1],nops(gu)-1)`): elif nargs=1 and args[1]=BestMovesS then print(`BestMovesS(Li,i): the expected duration of r(:=nops(Li))-faced `): print(` die backgammon`): print(`Solitaire with position Li and die-roll i`): print(`with optimal play followed by the optimal move(s)`): print(`For example, try: BestMovesS([2,3],1);`): elif nargs=1 and args[1]=BestMoves then print(`BestMoves(Li1,Li2,i): the probability of Player one winning`): print(`with position Li1, who just rolled i in k-faced die, and the other`): print(`player has position Li2 `): print(`in backgammon Bearoff `): print(`with optimal play followed by the optimal move(s)`): print(`For example, try: BestMoves([2,2],[2,2],1);`): elif nargs=1 and args[1]=Moves then print(`Moves(Li,i): all the legal moves from Li`): print(`with die-roll i (k=nops(Li) (in a k-die backgammon with ONE die)`): print(`For example, try: Noves([2,3],2);`): elif nargs=1 and args[1]=ProbW then print(`ProbW(Li1,Li2): Given two lists of length k, say,`): print(`representing the positions `): print(`of the two players in a k-faced die backgammon bearoff`): print(`with only pieces left in the homeboard (k:=nops(Li1)=nops(Li2)`): print(` (with ONE die) finds the probability of the first `): print(` (Li1) player winning `): elif nargs=1 and args[1]=POSki then print(`POSki(k,i,L): all positions in one-die backgammon end-game solitaire`): print(`with i counters `): elif nargs=1 and args[1]=POSkis then print(`POSkis(k,i,s): all positions in one-die backgammon end-game solitaire`): print(`with i counters whose pip-count is s`): print(`For example, try: POSkis(4,3,6);`): elif nargs=1 and args[1]=Sipur then print(`Sipur(r,K): all the excepions to greedy play (remove from the board if you can)`): print(` in an r-faced Backgammon Solitaire Bearoff`): print(`up to K checkers`): print(`For example, try: Sipur(6,11);`): elif nargs=1 and args[1]=SipurC then print(`SipurC(r,K,x,s,t): all the excepion in an r-faced Backgammon end-game`): print(`up to K checkers, compact and silent in terms of a generating`): print(` function where a term of the form s^i*t^j*x[1]^a1*...*x[r]^ar`): print(` indicates that the position is [a1, ..., ar] and the optimal move is`): print(`to move from position i to position j`): print(`For example, try: SipurC(4,12,x,s,t);`): elif nargs=1 and args[1]=Test1 then print(` Test1(r,K,i): tests the hypothesis that in`): print(`r-die backgammon end-game, if the`): print(`roll is i, it is always`): print(`best to remove a checker from the i^th place`): print(`if it is occopied for all others with <=K checkers`): print(`outputs all the exceptions to the rule`): elif nargs=1 and args[1]=RankPositions then print(`RankPositions(k,NumberOfCheckers,PipCount): a sorted table of `): print(`all the positions in k-die backgammon Solitaire `): print(`bearoff with NumberOfCheckers checkers and pip-count PipCount `): print(`sorted according to expected-life `): print(`For example, try: RankPositions(6,6,10);`) elif nargs=1 and args[1]=RankPositionsDetailed then print(`RankPositionsDetailed(k,NumberOfCheckers,PipCount): a sorted table of expected optimal-play life for `): print(`all the positions in k-die backgammon Solitaire `): print(`bearoff with NumberOfCheckers checkers and pip-count PipCount `): print(`For example, try: RankPositions(6,6,10);`) fi: end: ezra1:=proc() if args=NULL then print(`All the procedures are: `): print(): print(` ExpectedLife, FindP, BestMovesS, BestMoves, Moves , ProbW `): print(`POSki, POSkis, RankPositions , RandkPositionsDetailed, Box `): print(`Test1, Exc1, Sipur, SipurC`): else ezra(args): fi: end: #ExpectedLife(Li): Given a list of length k, finds the expected #number of moves in optimal play with a k-die in #backgammon with ONE die ExpectedLife:=proc(Li) local k,i: option remember: k:=nops(Li): if Li=[0$k] then RETURN(0): fi: add(BestMovesS(Li,i)[1],i=1..k)/k: end: #Moves(Li,i): all the legal moves from Li #with die-roll i (k=nops(Li) (in a k-die backgammon with ONE die) #For example, try: Noves([2,3],2); Moves:=proc(Li,i) local k,i1,gu: k:=nops(Li): if i>k or i< 1 then ERROR(`Second argument must be beteen 1 and `, k): fi: gu:={}: if {op(i..k,Li)}={0} then for i1 from i-1 by -1 to 1 do if Li[i1]>0 then RETURN({[op(1..i1-1,Li),Li[i1]-1,op(i1+1..k,Li)]}): fi od: RETURN({}): fi: if Li[i]>0 then gu:=gu union {[op(1..i-1,Li),Li[i]-1,op(i+1..k,Li)]}: fi: for i1 from i+1 to k do if Li[i1]>0 then gu:= gu union {[op(1..i1-i-1,Li),Li[i1-i]+1,op(i1-i+1..i1-1,Li),Li[i1]-1,op(i1+1..k,Li)]}: fi: od: RETURN(gu): end: #BestMovesS(Li,i): the expected duration of the game #with optimal play followed by the optimal move(s) BestMovesS:=proc(Li,i) local gu,alufim,shi,i1,muam,nase: gu:=Moves(Li,i): if gu={} then RETURN(0,{}): fi: alufim:={gu[1]}: shi:=ExpectedLife(gu[1]): for i1 from 2 to nops(gu) do muam:=gu[i1]: nase:=ExpectedLife(muam): if nase1 then lu:= lu union {gu[i1]}: print(`For position `, gu[i1], `and roll`, i , `the best moves are`): print(BestMovesS(gu[i1],i)[2]): fi: od: lu: end: #Exc1(r,K,i): tests the hypothesis that in #r-die backgammon end-game, if the #roll is i, it is always #best to remove a checker from the i^th place #if it is occupied for all positions with K checkers #outputs all the exceptions to the rule Exc1:=proc(r,K,i) local gu,i1,lu: if not 1<=i and i<=r then ERROR(`Out of range`): fi: gu:=POSki(r,K): lu:={}: for i1 from 1 to nops(gu) do if gu[i1][i]>0 then if gu[i1][i]-BestMovesS(gu[i1],i)[2][1][i]<>1 then lu:= lu union {gu[i1]}: print(`For position `, gu[i1], `and roll`, i , `the best moves are`): print(BestMovesS(gu[i1],i)[2]): fi: fi: od: lu: end: #Exc1Silent(r,K,i): tests the hypothesis that in #r-die backgammon end-game, if the #roll is i, it is always #best to remove a checker from the i^th place #if it is occupied for all positions with K checkers #outputs all the exceptions to the rule Exc1Silent:=proc(r,K,i) local gu,i1,lu: if not 1<=i and i<=r then ERROR(`Out of range`): fi: gu:=POSki(r,K): lu:={}: for i1 from 1 to nops(gu) do if gu[i1][i]>0 then if gu[i1][i]-BestMovesS(gu[i1],i)[2][1][i]<>1 then lu:= lu union {gu[i1]}: fi: fi: od: lu: end: #Sipur(r,K): all the excepion in an r-faced Backgammon end-game #up to K checkers Sipur:=proc(r,K) local K1,i,lu,LU,i1,LU1: LU:=[]: for K1 from 1 to K do LU1:=[]: for i from 1 to r do lu:=Exc1(r,K1,i): if lu<>{} then print(`When the roll was`,i, `and there were`, K1, `checkers , the exceptions to greedy play were`): lu:={seq([i,lu[i1],BestMovesS(lu[i1],i)[2][1]],i1=1..nops(lu))}: print(lu): LU1:=[op(LU1),op(lu)]: fi: od: if LU1<>[] then LU:=[op(LU),LU1]: fi: od: LU: end: #ProbW(Li1,Li2): Given two lists of length k, say, #representing the positions #of the two players in a k-faced die backgammon end-game #(with ONE die) finds the probability of the first #(Li1) player winning ProbW:=proc(Li1,Li2) local k,i: option remember: k:=nops(Li1): if nops(Li2)<>k then ERROR(`Bad input`): fi: if Li2=[0$k] then RETURN(0): fi: add(BestMoves(Li1,Li2,i)[1],i=1..k)/k: end: #BestMoves(Li1,Li2,i): the probability of Player one winning #with position Li1, who just rolled i in k-faced die #backgammon end-game #with optimal play followed by the optimal move(s) BestMoves:=proc(Li1,Li2,i) local gu,alufim,shi,i1,muam,nase: gu:=Moves(Li1,i): if gu={} then RETURN(0,{}): fi: alufim:={gu[1]}: shi:=ProbW(Li2,gu[1]): for i1 from 2 to nops(gu) do muam:=gu[i1]: nase:=ProbW(Li2,muam): if nase{} then lu:={seq([i,lu[i1],BestMovesS(lu[i1],i)[2][1]],i1=1..nops(lu))}: LU1:=[op(LU1),op(lu)]: fi: od: if LU1<>[] then LU:=[op(LU),LU1]: fi: od: LU1:=[]: for i from 1 to nops(LU) do lu:=LU[i]: ku:=0: for j from 1 to nops(lu) do ku:= ku +GF1(lu[j],x,t,s): od: LU1:=[op(LU1),ku]: od: LU1: end: GF1:=proc(V,x,t,s) local k,vu,j,vu1,vu2: vu:={}: for j from 1 to nops(V[2]) do if V[2][j]<>V[3][j] then vu:=vu union {j}: fi: od: if nops(vu)<>2 then print(`vu is`,vu): ERROR(`Something is wrong`): fi: vu1:=min(op(vu)):vu2:=max(op(vu)): if vu2-vu1<>V[1] then ERROR(`Something is wrong`): fi: s^vu2*t^V[1]*mul(x[k]^V[2][k],k=1..nops(V[2])): end: #IsGoodMono(LU,x,t,s,M1,i1,k):Given a list of sets of Exceptionals Polynomials #and a monomial M1 in LU[i1], finds out whether all descendats of M1 are #exceptionals (in k-faced one die Backgammon end-game), also returns the left-overs IsGoodMono:=proc(LU,x,t,s,M1,i1,k) local z,vu,i,j,gu,LU1: i:=degree(M1,t):j:=degree(M1,s): vu:={j,j-i}: gu:=M1: for i from 1 to k do if not member(i,vu) then gu:=gu/(1-z*x[i]): fi: od: gu:=taylor(gu,z=0,nops(LU)-i1+1): LU1:=LU: for j from 1 to nops(LU)-i1 do if {op(expand(coeff(gu,z,j)))} minus {op(LU[i1+j])}<>{} then RETURN(false): else LU1:=[op(1..i1+j-1,LU1), {op(LU[i1+j])} minus {op(expand(coeff(gu,z,j)))},op(i1+j+1..nops(LU1),LU1 )]: fi: od: true,LU1: end: