#Nathan Fox #Homework 9 #I give permission for this file to be posted online ##Read old files read(`C9.txt`): #Help procedure Help:=proc() : print(` fS(a,b,i) , FS(a,b) , fR(a,b,i) , FR(a,b) `): print(` fG(a,b,i) , FG(a,b) , LegalMovesG(a,b,i) `): print(` fD(a,b,i,j) , FD(a,b) , LegalMovesD(a,b,i,j) `): end: ##Problem 1 #Prolong the game as much as possible fS:=proc(a,b,i) local m: option remember: if a=0 and b=0 then return 0: fi: 1+max(seq(FS(m[1],m[2]),m in LegalMoves(a,b,i))): end: FS:=proc(a,b) option remember: if a=0 and b=0 then return 0: fi: (1/2)*fS(a,b,1)+(1/2)*fS(a,b,2): end: ##Does the limit of FS(n,0)/F(n,0), as n goes to infinity exist? ##If it does, what is it? #The limit appears to exist and be about 1.125 ##Problem 2 #F(n,0) is really close to (4/3)*n+2/9 #c1=4/3 because in order to win [n,0], you must win [n-1,0] #(so c1>1), but it should be easier than winning [n,0] #followed by [1,0] (so c1<3/2=F(1,0)). Hence, c1=4/3 makes sense ##Problem 3 #Play randomly fR:=proc(a,b,i) local m,L,ra: #option remember: (don't want this. we're being random) if a=0 and b=0 then return 0: fi: L:=[seq(FR(m[1],m[2]),m in LegalMoves(a,b,i))]: ra:=rand(1..nops(L)): L[ra()]+1: end: FR:=proc(a,b) #option remember: if a=0 and b=0 then return 0: fi: (1/2)*fR(a,b,1)+(1/2)*fR(a,b,2): end: ##Does the limit of FR(n,0)/F(n,0), as n goes to infinity exist? ##If it does, what is it? #The limit appears to exist and be about 1.03, but it's actually #rather unclear, since FR requires removing option remember, #which makes it take a really long time to run FR(n,0) if #n>7 ##Problem 4 #Play greedily fG:=proc(a,b,i) local m,L: option remember: if a=0 and b=0 then return 0: fi: for m in LegalMovesG(a,b,i) do return 1+FG(m[1],m[2]): od: end: FG:=proc(a,b) option remember: if a=0 and b=0 then return 0: fi: (1/2)*fG(a,b,1)+(1/2)*fG(a,b,2): end: #Board=square1 and square2 #a+b counters (a,b) #roll die, get 1 or 2 #On a 1, (a,b) -> (a-1,b+1) [a>=1 and b=0] or (a,b-1) [b>=1] #On a 2, (a,b) -> (a-1,b) [a>=1] or (0,b-1) [a=0] #Greedy legal moves LegalMovesG:=proc(a,b,i) local S: S:={}: if i=1 then if a>=1 and b=0 then S:=S union {[a-1,b+1]}: else S:=S union {[a,b-1]}: fi: else: if a>=1 then S:=S union {[a-1,b]}: else S:=S union {[a,b-1]}: fi: fi: S: end: ##Does the limit of FR(n,0)/F(n,0), as n goes to infinity exist? ##If it does, what is it? #The limit appears to exist and be 1. In other words, the greedy #strategy is optimal ##Problem 5 #Two dice! fD:=proc(a,b,i,j) local m: option remember: if a=0 and b=0 then return 0: fi: 1+min(seq(FD(m[1],m[2]),m in LegalMovesD(a,b,i,j))): end: FD:=proc(a,b) option remember: if a=0 and b=0 then return 0: fi: (1/4)*fD(a,b,1,1)+(1/4)*fD(a,b,2,2)+(1/2)*fD(a,b,1,2): end: #Board=square1 and square2 #a+b counters (a,b) #roll two dice, get [1,1], [1,2], [2,1], or [2,2] #On [1,1], get 4 1-moves #On [1,2] or [2,1], get a 1-move and a 2-move #On [2,2], get 4 2-moves LegalMovesD:=proc(a,b,i,j) local S: option remember: S:={}: if {i,j}={1} then if b>=4 then S:=S union {[a,b-4]}: elif a=0 then S:=S union {[0,0]}: fi: if b>=2 and a>=1 then S:=S union {[a-1,b-2]}: elif a=1 then S:=S union {[0,0]}: fi: if a>=2 then S:=S union {[a-2,b]}: fi: if a>=3 then S:=S union {[a-3,b+2]}: fi: if a>=4 then S:=S union {[a-4,b+4]}: fi: elif {i,j}={1,2} then if a>=1 and b=0 then S:=S union {[a-1,0]}: fi: if a>=1 and b>0 then S:=S union {[a-1,b-1]}: fi: if a=0 and b=1 then S:=S union {[0,0]}: elif a=0 then S:=S union {[0,b-2]}: fi: elif {i,j}={2,2} then if a>=4 then S:=S union {[a-4,b]}: elif a=3 and b=0 then S:=S union {[0,0]}: elif a=3 then S:=S union {[0,b-1]}: elif a=2 and b<=1 then S:=S union {[0,0]}: elif a=2 then S:=S union {[0,b-2]}: elif a=1 and b<=2 then S:=S union {[0,0]}: elif a=1 then S:=S union {[0,b-3]}: elif a=0 and b<=3 then S:=S union {[0,0]}: elif a=0 then S:=S union {[0,b-4]}: fi: fi: S: end: #It appears that FD(n,0)-FD(n-1,0) approaches 4/9 from above #as n->infinity