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: `
 ]