#Nathan Fox
#Homework 11
#I give permission for this file to be posted online

##Read old files
read(`C11.txt`):
read(`hw10.txt`): #for LegalMovesG

#Help procedure
Help:=proc():
print(` FNE(Ef,r,cap) , Exceptions2(N,j) , Exceptions4(N,j) `):
print(` PWG(L1,L2,r) , pWG(L1,L2,r,i) `):
end:

##Problem 1
#FNE(Ef,r,cap): inputs number of die faces
#outputs smallest N for which Ef(N,r)
#is nonempty
#or returns FAIL if no such N exists <= cap
FNE:=proc(Ef,r,cap) local N:

for N from 1 to cap do
    if nops(Ef(N,r))>0 then
        return N:
    fi:
od:

return FAIL:

end:

#FNE(Exceptions3,1,15) outputs 3, once I altered it to include
#positions such as [0,0,3].  It outputs 5 before that change
#FNE(Exceptions3,2,15) ouputs FAIL (so no such N<=15 exists)

##Problem 2
#Exception2(N,j): inputs a positive integer N and a positive
#integer r in {1,2}, and outputs all pairs of positions
#[[i1,i2], [j1,j2]] in Bearoff with house-size 2 and 2-faced
#fair ONE die, and i1+i2=N, j1+j2=N, where the two strategies
#disagree, and by how much they lose from their perspectives.
Exceptions2:=proc(N,j) local i1,i2,j1,j2,gu,P,Pw,lu1,lu2:

gu:={}:

for i1 from 0 to N do
    for i2 from 0 to N-i1 do
        for j1 from 0 to N do
            for j2 from 0 to N-j1 do
                if [i1,i2]<>[0,0] and [j1,j2]<>[0,0] then
                    if f([i1,i2],2,j)[1]<>
                        fW([i1,i2],[j1,j2],2,j)[2] then
                        print(`In position `,
                            [[i1,i2],[j1,j2]], 
                            `the strategies conflict when the die rolled`, j):
                        P:=f([i1,i2],2,j)[1]:
                        Pw:=fW([i1,i2],[j1,j2], 2,j)[2]:
                        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):

                        lu1:=evalf(F(Pw,2)-F(P,2)):
                        print(`The increase in expected duration if you follow the latter is`, lu1):

                        lu2:=evalf(FW([j1,j2],P,2)-FW([j1,j2],Pw,2)):

                        print(`The loss of proba. of winning if you follow the former is`,lu2):

                        gu:=gu union {[[i1,i2],[j1,j2],
                            P,Pw,lu1,lu2]}:
                    fi:

                fi:
            od:
        od:
    od:
od:

gu:

end:

#FNE(Exceptions2,1,20) outputs FAIL, so there does not
#exist an exceptional N<=20
#It also outputs FAIL for N<=30

##Problem 3
#Exception4(N,j): inputs a positive integer N and a positive
#integer r in {1,2,3,4}, and outputs all pairs of positions
#[[i1,i2,i3,i4], [j1,j2,j3,j4]] in Bearoff with house-size
#4 and 4-faced fair ONE die, and i1+i2+i3+i4=N, j1+j2+j3+j4=N,
#where the two strategies disagree, and by how much they lose
#from their perspectives.
Exceptions4:=proc(N,j) local i1,i2,i3,i4,j1,j2,j3,j4,
    gu,P,Pw,lu1,lu2:

gu:={}:

for i1 from 0 to N do
  for i2 from 0 to N-i1 do
    for i3 from 0 to N-i1-i2 do
      for i4 from 0 to N-i1-i2-i3 do
        for j1 from 0 to N do
          for j2 from 0 to N-j1 do
            for j3 from 0 to N-j1-j2 do
              for j4 from 0 to N-j1-j2-j3 do
                if [i1,i2,i3,i4]<>[0,0,0,0] and
                    [j1,j2,j3,j4]<>[0,0,0,0] then
                  if f([i1,i2,i3,i4],4,j)[1]<>
                        fW([i1,i2,i3,i4],[j1,j2,j3,j4],4,j)[2] then
                    print(`In position `,
                        [[i1,i2,i3,i4],[j1,j2,j3,j4]], 
                        `the strategies conflict when the die rolled`, j):
                        P:=f([i1,i2,i3,i4],4,j)[1]:
                        Pw:=fW([i1,i2,i3,i4],[j1,j2,j3,j4],
                            4,j)[2]:
                        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):

                        lu1:=evalf(F(Pw,4)-F(P,4)):
                        print(`The increase in expected duration if you follow the latter is`, lu1):

                        lu2:=evalf(FW([j1,j2,j3,j4],P,4)-
                            FW([j1,j2,j3,j4],Pw,4)):

                        print(`The loss of proba. of winning if you follow the former is`,lu2):

                        gu:=gu union {[[i1,i2,i3,i4],[j1,j2,j3,j4],
                            P,Pw,lu1,lu2]}:
                  fi:
                fi:
              od:
            od:
          od:
        od:
      od:
    od:
  od:
od:

gu:

end:

#FNE(Exceptions4,1,7) outputs 2

##Problem 4
#PWG(L1,L2,r) that inputs lists L1, L2 denoting the positions
#of White and Black, and a positive integer r indicating the
#die-size, and outputs the probability of White (who is about
#to move) winning if both players follow the greedy strategy.
PWG:=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(pWG(L1,L2,r,i)[1], i=1..r)/r:

end:

#pWG(L1,L2,r,i): The probability of L1 winning
#if the roll was i, followed by the greedy move
pWG:=proc(L1,L2,r,i) local tom:
option remember:

tom:=LegalMovesG(L1,i): #will be a singleton set

(1-PWG(L2,tom[1],r)),tom[1]:

end: