You recall dynamic programming I hope: Solve small solutions. Glue them together. Let's look at the classic: string comparison some vs. sammy Draw the matrix. Figure out the rule for going backwards work back towards the beginning. Duellists: / duel.k, Dennis Shasha, October 2001 / Alternate moves. / Player 1 goes first at multiples of 20 (or in our case, even distances). / Duellists -- Keith Carradine and Harvey Keitel / Napoleon Pistol. Gribeauval 1806. flintlock. / One doesn't hear about duels so often these days, so Ecco was / quite surprised to hear the request from one Austerlitz Toulemonde. / "I am from the Napoleonic Society," he explained. / "We use firearms from the time of the Emperor and when disagreements arrive / we allow duels, though only to the first touch and / our vests are made of kevlar. / Even when we're wounded, no one gets too badly hurt, / because our members prefer modern surgeons / to barbers. / / Now it happens that I have been caught in {\em flagrant delit} / with the extremely charming wife of another member. / To protect his honor, he has slapped me on the face and / we must duel tomorrow. / In this duel, I am the offender and he is the challenger. / "The basic duel scenario here is that there are two people / start by standing 100 paces apart. / The offender has two bullets and the challenger has three / bullets. / So, he has more bullets. / At each distance, starting with the offender, / one duellist can choose to shoot at most one bullet / provided he has any left. / Then the other duellist can choose to shoot / at most one bullet if he has any left. / If neither is hit at that distance, each dueler walks 5 paces towards / the other, thus bringing the duelers 10 paces closer to one another. / The duellist who went first the last time goes second this time. / "Now the probability that a dueler will hit his opponent / grows as the distance shrinks, i.e. (100 - dist)/100." / "So if either of you has a bullet left and the other has none, the / one with the bullet surely win," Liane said. / My question to you is: what should my strategy be? / Assuming that he / The duelers / A dueler is allowed to shoot only once at a certain distance and / the duelers approach one another 10 paces at a time (5 paces each) / after both each has a chance to shoot or not (and assuming neither is shot). / One's chance of touching is defined by the formula: / (maxdist-dist)/maxdist / For the purposes of this program, I've replaced 10 paces by 1 pace. / Now, we have g1mat which is the best prob that player 1 can do from / given configuration (player 1's move, so much distance, so many / shots for player 1 and so many shots for player 2). / g2mat is the least winning prob for player 1 that player 2 can manage / when it is player 2's move. / To figure out the moves, find the first time that some player shoots and / then continue from that configuration. / All other configurations are simply unattainable assuming rational play. / To play this as a game, form the array but ignore the output from out. / Then use doesshoot1 or doesshoot2 to decide which is the best move. / Start with g1mat. / APPLICATION SPECIFIC / prob of hit and miss p:{[dist] (maxdist - dist) % maxdist} q:{[dist] 1 - p[dist]} / whatever the distance probability player 1 has a slightly better shot improve: 1 / if improve: 1 then both have same prob of hitting at distance. p1:{[dist] improve*p[dist]} q1:{[dist] 1 - p1[dist]} p2:p q2:q / probability that player 1 will win if he has m1 bullets / and m2 has m2 bullets and they are dist apart / and it is player 1's turn and whether player 1 went first or not / is determined by the isfirst flag g1:{[dist; m1; m2; isfirst] if[g1mat[dist;m1;m2; isfirst] > -1; :g1mat[dist;m1;m2; isfirst]] / greater than -1 means already set / :(g2[dist;m1;m2]) | ((p[dist]) + (q[dist] * g2[dist;m1-1;m2])) if[isfirst = 1 x1: (g2[dist;m1;m2; 0]) / player 1 doesn't shoot x2: ((p1[dist]) + (q1[dist] * g2[dist;m1-1;m2; 0])) / player 1 shoots and succeeds with prob p1[dist] or misses and then / prob depends on the g2. ] if[isfirst = 0 / if player 1 was not first this time he will be next time / so recursion goes to player 1 x1: (g1[dist-1;m1;m2; 1]) / you try at a smaller distance x2: ((p1[dist]) + (q1[dist] * g1[dist-1;m1-1;m2; 1])) / you shoot / at this distance and then you get another chance at a smaller / distance because the chance to go first alternates. / never take this second choice ] if[x2 > x1 / shoots if[m1 > 1 out,: ,("Player 1 at "), ($dist), (" having "), ($m1), (" bullets, shoots. Prob to win: "), ($x2), (". Player 2 has: "), ($m2) out,: :[isfirst; (" Player 1 was first."); ("Player 1 was second.")] ] if[m1 = 1 out,: ,("Player 1 at "), ($dist), (" having one bullet, shoots. Prob to win: "), ($x2), (". Player 2 has: "), ($m2) out,: :[isfirst; (" Player 1 was first."); ("Player 1 was second.")] ] ] :x1 | x2 / first part is if player 1 doesn't shoot. / second part is if player 1 does. } / probability that player 1 will win if he has m1 bullets / and m2 has m2 bullets and they are dist apart / and it is player 2's turn and whether player 2 is going first at this / distance is determined by the isfirst flag g2:{[dist; m1; m2; isfirst] / if[m1 = 0; :0] / if[m2 = 0; :1] if[g2mat[dist;m1;m2; isfirst] > -1; :g2mat[dist;m1;m2; isfirst]] / -1 is the initial value; so if not that then this is known if[1 = isfirst x1:(g1[dist;m1;m2;0]) / if player 2 chooses not to shoot, / control passes to player 1 x2: (q2[dist] * g1[dist;m1;m2-1;0]) / if player 2 hits, then / value to player 1s 0; else with prob q2[dist], prob of / player 1 winning is g1[dist;m1;m2-1;0] ] if[0 = isfirst / if player 2 is not first this time, he will be next time x1:(g2[dist-1;m1;m2;1]) / if second this time, then be first the next time x2: (q2[dist] * g2[dist-1;m1;m2-1;1]) / or try to shoot and remaining / value is prob of missing * prob player 1 wins if player 2 goes / first next ] if[x2 < x1 / note that player 2 is a minimizer if[m2 > 1 out,: ,("Player 2 at "), ($dist), (" having "), ($m2), (" bullets, shoots. Prob to win: "), ($1-x2), (". Player 1 has: "), ($m1) out,: :[isfirst; (" Player 2 was first."); ("Player 2 was second.")] ] if[m2 = 1 out,: ,("Player 2 at "), ($dist), (" having one bullet, shoots. Prob to win: "), ($1-x2), (". Player 1 has: "), ($m1) out,: :[isfirst; (" Player 2 was first."); ("Player 2 was second.")] ] ] :x1 & x2 / first part is player 2 not shooting so distance gets closer by 10 / paces (here represented as 1) / second part is player 2 shooting. } / Once we've constructed the matrix, we answer the question about whether / we shoot or not at a certain distance. doesshoot1:{[dist; m1;m2; isfirst] if[isfirst = 0; :0] / never worthwhile to shoot in that case if[m1 = 0; :0] / can't shoot if have nothing if[isfirst = 1 x1: (g2mat[dist;m1;m2;0]) x2: ((p1[dist]) + (q1[dist] * g2mat[dist;m1-1;m2;0])) ] :~ x2 < x1 } doesshoot2:{[dist; m1;m2; isfirst] if[isfirst = 0; :0] / never worthwhile to shoot in that case if[m2 = 0; :0] / can't shoot if have nothing if[isfirst = 1 x1:(g1mat[dist;m1;m2;0]) x2: (q2[dist] * g1mat[dist;m1;m2-1;0]) ] :~ x2 < x1 } / DATA out: () maxdist: 10 / maxdist sets of 10 paces / set up  0: "Which player number are you? (1, 2)\n" x: 0:  zz: :[("1") _in x; playernum: 1; playernum: 2]  0: "How many bullets does player 1 have? (0... 5)\n" x: 0 $0:  m1: x  0: "How many bullets does player 2 have? (0... 5)\n" x: 0$ 0:  m2: x num1: m1 / first mover bullets num2: m2 / second mover bullets / for every distance, for each number of bullets left for each player / fourth entry is whether a certain player is first or not. g1mat: ((maxdist+1); (num1+1); (num2+1); 2) # -1 / prob that player 1 wins -- player 1 moves g2mat: ((maxdist+1); (num1+1); (num2+1); 2) # -1 / prob that player 1 wins -- player 2 moves / initialization g1mat[0;;;]: 1 / if players are at 0 distance away, player 1 will win if he / has bullets; first entry is distance. g2mat[0;;;]: 0 / if players are at 0 distance away, player 1 will lose if / player 2 has bullets; first entry is distance. player 2 is a / minimizer. g1mat[;;0;]: 1 / if player 2 ever has 0 bullets, player 1 is sure to win / provided he has bullets; third entry is player 2 bullets g1mat[;0;;]: 0 / if player 1 has 0 bullets, he will lose. Not sure needed / second entry is player 1 bullets. g2mat[;0;;]: 0 / if player 1 ever has 0 bullets, player 1 is sure to lose g2mat[;;0;]: 1 / if player 2 ever has 0 bullets, player 1 wins. Needed? g1mat[0;0;0;]: 52 / neutral, neither player wins but can't get here g2mat[0;0;0;]: 52 / neutral, neither player wins but can't get here / EXECUTION idist: 0 while[idist < (maxdist+1) m1: 0 while[m1 < (num1+1) m2: 0 while[m2 < (num2+1) g1mat[idist;m1;m2;0]: g1[idist; m1; m2;0] g2mat[idist;m1;m2;0]: g2[idist; m1; m2;0] g1mat[idist;m1;m2;1]: g1[idist; m1; m2;1] g2mat[idist;m1;m2;1]: g2[idist; m1; m2;1] m2+: 1 ] m1+: 1 ] idist+: 1 ] /  0: ?out even:{[x] (_ x % 2) = (x % 2)} out2: () idist: maxdist m1: num1 m2: num2 while[idist > 0 onefirst: even[idist] if[1 = onefirst / player 1 goes first if[m1 > 0 if[doesshoot1[idist;m1;m2;1] out2,: ,("Player 1 (going first) at "), ($idist), (" having "), ($m1), (" bullet(s), shoots. Player 2 has: "), ($m2), (". Prob 1 wins: "), ($g1mat[idist;m1;m2;1]) m1-: 1 ] ] if[(m2 > 0) if[doesshoot2[idist;m1;m2;0] out2,: ,("Player 2 (going second) at "), ($idist), (" having "), ($m2), (" bullet(s), shoots. Player 1 has: "), ($m1), (". Prob 2 wins: "), ($1-g2mat[idist;m1;m2;0]) m2-: 1 ] ] ] if[0 = onefirst / player 1 goes second if[(m2 > 0) if[doesshoot2[idist;m1;m2;1] out2,: ,("Player 2 (going first) at "), ($idist), (" having "), ($m2), (" bullet(s), shoots. Player 1 has: "), ($m1), (". Prob 2 wins: "), ($1-g2mat[idist;m1;m2;1]) m2-: 1 ] ] if[m1 > 0 if[doesshoot1[idist;m1;m2;0] out2,: ,("Player 1 (going second) at "), ($idist), (" having "), ($m1), (" bullet(s), shoots. Player 2 has: "), ($m2), (". Prob 1 wins: "), ($g1mat[idist;m1;m2;0]) m1-: 1 ] ] ] idist-: 1 ] / definitely shoot at 0 distance if[m1 > 0 out2,: ,("Player 1 (going first) at "), ($idist), (" having "), ($m1), (" bullet(s), shoots. Player 2 has: "), ($m2), (". Prob 1 wins: "), ($g1mat[idist;m1;m2;1]) m1-: 1 ] if[m2 > 0 out2,: ,("Player 2 (going second) at "), ($idist), (" having "), ($m2), (" bullet(s), shoots. Player 1 has: "), ($m1), (". Prob 2 wins: "), ($1-g2mat[idist;m1;m2;0]) m2-: 1 ]  0: out2 / set up file: "duelshare" if[0 < # _i file: _i[0] ] parse:{[lines; orig1; orig2] m1: orig1 m2: orig2 distarr: () k: 0 while[k < #lines line: lines[k] flag: (0 = # & ~ line = " ") | (0 = #line) if[~ flag / non-empty i: line ? "," dist: 0 $line[!i] distarr,: dist line: (i+1) _ line i: line ? "," player: 0$ line[!i] line: (i+1) _ line shot: (line _sm "*sh*") | (line _sm "*sh*") if[shot :[player=1; m1-: 1; m2-: 1] ] ] k+: 1 ] if[0 = #distarr :(m1; m2; 10) ] if[1 = #distarr :(m1; m2; _ dist % 10) ] :[dist = distarr[(#distarr)-2] / same distance twice :(m1; m2; _ (dist-10) % 10) :(m1; m2; _ dist % 10)] } m1: num1 m2: num2  0: "Shall we play? (y,n)\n" x: 0:  while[(x _sm "*y*") | (x _sm "*Y*") a: 0: file triple: parse[a; num1; num2] m1: triple[0] m2: triple[1] r: triple[2] if[(playernum = 1) ishoot: 0 if[(even[r]) ishoot: doesshoot1[r;m1;m2;1] ] if[ishoot a,: ,($10*r), (","), ($playernum), (", shoot") /  0: ("Player 1 shoots at "),($10*r), (" with "), ($m1), (" bullets vs. "), ($m2), (" bullets for player 2.\n") ] if[~ ishoot a,: ,($10*r), (","), ($playernum), (", pass") ] ] if[(playernum = 2) ishoot: 0 if[~ (even[r]) ishoot: doesshoot2[r;m1;m2;1] ] if[ishoot a,: ,($10*r), (","), ($playernum), (", shoot") /  0: ("Player 2 shoots at "),($10*r), (" with "), ($m2), (" bullets vs. "), ($m1), (" bullets for player 1.\n") ] if[~ ishoot a,: ,($10*r), (","), ($playernum), (", pass") ] ]  0: a file 0: a  0: "Shall we play? (y,n)\n" x: 0: ` ]