######################################################################
## Sulam Save this file as  Sulam. to use it,                        #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read Sulam <Enter>                                #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  zeilberg@math.rutgers.edu.                                       # 
######################################################################

with(linalg):


print(`First Written: Nov. 2005: tested for Maple 10 `):
print(`Version of Nov.  , 2005:  `):
print():
print(`This is Sulam, A Maple package 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 is available on WWW at:`):
print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/Sulam  .`):
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 the supporting functions type: ezra1();`):
print():
 

ezra:=proc()
if args=NULL then

print(` Sualm: A Maple package for Generalized Simplified (one die) bearoff solitaire `):
print(`The MAIN procedures are:`):
print(` BestMove, EL, Moves  `):

elif nargs=1 and args[1]=BestMove  then
print(`BestMove(POS,k,i): Best move from position POS in`):
print(`k-faced ONE fair die Bearoff Solitaire`):
print(`For example, try: BestMove([1,2,3,4],4,1);`):

elif nargs=1 and args[1]=EL  then
print(`EL(POS,k): the expected number of moves in optimal play`):
print(`of Bearoff Solitaire with ONE k-faced die in position POS`):
print(`for example, try EL([1,2,3,4],4);`):

elif nargs=1 and args[1]=Moves  then
print(`Moves(L,i): in Bearoff Solitaire, given a position`):
print(`L a sorted list describing the distances of the`):
print(`remaining checkers (a sorted list), and a die-roll i, finds all the`):
print(`possible moves. For example, try:`):
print(`Moves([3,3],1);`):

else
 print(`There is no such thing as`, args):

fi:


end:



#Moves(L,i): in Bearoff Solitaire, given a position
#L a sorted list describing the distances of the
#remaining checkers (a sorted list), and a die-roll i, finds all the
#possible moves. For example, try:
#Moves([3,3],1);
Moves:=proc(L,i) local gu,j,L1:

gu:={}:

if max(op(L))>=i then
for j from 1 to nops(L) do
 if L[j]>i then
  gu:=gu union {sort([op(1..j-1,L),L[j]-i,op(j+1..nops(L),L)])}:
 fi:
  if L[j]=i then
   gu:=gu union {[op(1..j-1,L),op(j+1..nops(L),L)]}:
  fi:
od:

 RETURN(gu):
else
L1:=sort(L):
RETURN({[op(1..nops(L1)-1,L1)]}):
fi:
end:

#EL(POS,k): the expected number of moves in optimal play
#of Bearoff Solitaire with ONE k-faced die in position POS
#for example, try EL([1,2,3,4],4);
EL:=proc(L,k) local i:
option remember:
if L=[] then
 0:
else
 1+add(BestMove(L,k,i)[2],i=1..k)/k:
fi:
end:

#BestMove(POS,k,i): Best move from position POS in
#k-faced ONE die Bearoff Solitaire
#For example, try: BestMove([1,2,3,4],4,1);
BestMove:=proc(L,k,i)
local gu,alufim,shi,muam,i1:
option remember:
gu:=Moves(L,i):
alufim:={gu[1]}:
shi:=EL(gu[1],k):
for i1 from 2 to nops(gu) do
 muam:=EL(gu[i1],k):
 if muam<shi then
    shi:=muam:
  alufim:={gu[i1]}:
 elif muam=shi then
  alufim:=alufim union {gu[i1]}:
 fi:
od:
alufim,shi:
end: