If you are just starting with Python I hope the small problems in this blog are helpful. All you need to solve or follow them is very basic knowledge of Python and curiosity.
Each post uses trinkets to run python on the browser. You can modify and run the code on the blog post itself.

Tuesday, September 15, 2015

Castle Defense III-Exact mathematical solution



A recap

In the previous two posts we looked at two different ways of solving the following problem: A group of \(n\) soldiers, each carrying a canon and a rifle, attacks a castle which has initial strength \(s\). If \(s>0\) at the end of a bloody day, the castle can send \(dpw\) defenders a day out of its gates to battle the soldiers.  On the  the first day, all soldiers fire their canons at the castle decreasing its strength to \(s-n\). In the ensuing days the castle and the soldiers battle it out following these rules:
  1. All the soldiers fire first. A soldier can either fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.
  2. Each of the defenders will then shoot one soldier (and only one) killing him.
  3. If the castle still has strength points (i.e. \(s>0\)) it will send a new batch of defendersPerWave (dpw) defenders at this point. The total number of defenders in the next round (day) will then be \(defenders=defenders + defendersPerWave\).
  4. Repeat 1 through 3 each new day.
  5. If all soldiers are killed by the defenders, the castle wins even if its strength is zero.
  6. If there are zero defenders left after the soldiers shot and the castle strength is also zero, the soldiers win.
The soldiers want to destroy the castle and its defenders in the minimum number of days/waves. If that is not possible how many days does it take for them to lose?
In the first post of this series we described two simple strategies in which the soldiers, in each wave, either decided to attack the castle first and only then its defenders or vice versa, i.e. attack the defenders first and only  then the castle. Neither of these approaches was able to find the minimum number of days solution for every set of initial values of \(s\), \(n\) and \(dpw\).

In the second post we described a recursive brute force search algorithm that correctly finds the minimum number of days for the soldiers to win and the exact steps-the path from the initial state towards the end goal- that the soldiers should take to win the battle in that minimum number of days. The algorithm is also used to find all possible solutions not just those that lead to a win by the soldiers in a minimum number of days but also solutions in which the castle wins and solutions in which the soldiers win in a non minimum number of days.

In this post we will do a careful mathematical study of the problem and use its peculiar structure to determine, given the number of initial soldiers \(n\), the number of initial castle hits/strength \(s\) and the number of defenders per wave \(dpw\),
1) Whether the soldiers can win and, if they can, what is the minimum number of days it takes for them to do so and what is the strategy the soldiers should use to accomplish it. We will be able to give a complete answer to this.
2) If the soldiers can not win, what is the minimum number of days for the castle to win and which strategy should the castle follow to achieve this. This is harder than 1) but we will go over some cases.
3) Finally is there a simple way to find all the paths that lead to a win by either side? Unfortunately it is too difficult to find these without an exhaustive search.

This post is fairly advanced mathematically and it is perhaps the hardest of this blog's posts so far. The result of all this hardship is  a deeper insight into the problem as well as a quicker way to solve it. In particular we will see that the analysis will give the best strategy the soldiers should follow and therefore will tell us the path from the initial state to the goal state without the need to do a computationally expensive search like we did in our second post .

1. The case \(s\leq n\) : The castle can not win


If the number of soldiers \(n\) is greater or equal to the castle strength \(s\), then the soldiers clearly win in one day (in the first day right after they discharge their canons on the castle).

2. The case \(s > n\): When can the soldiers win?

In the opposite case where the number of initial soldiers is smaller than the initial  castle strength, there will always be (bad) soldier strategies that lead to the castle winning.

In some cases however even if they follow the best strategy, the soldiers can not win. In this section we would like to determine for what initial values of \(n,s,dpw\) can the soldiers win and the minimum number of days it will take for them to achieve the win.

Lets introduce some notation: For a given day i, let \(c_{i}\) be the remaining castle strength, \(s_{i}\) be the remaining number of soldiers and \(d_{i}\) the remaining number of castle defenders. Let \(dpw\) be the number of defenders the castle sends each new day/wave.


2.a Best strategy if \(dpw<n\): Kill all defenders every day


Consider first the case where \(d_{i}=dpw\) at the start of a given day, i.e. the soldiers killed all defenders the previous day.

Suppose that on this day the soldiers kill some defenders, leaving \(x\) of them at the end of the day (i.e. \(dpw-x\) of the soldiers killed  \(dpw-x\) defenders, the remaining \(s_{i}-(dpw-x)\) soldiers shot at the castle and the \(x\) defenders shot back at the soldiers leaving \(s_{i}-x\) of them standing), and the castle is left standing (i.e. \(c_{i}>0\)). Then the start of the new day (\(i+1\)) begins with the following numbers

\begin{align}
s_{i+1} &= s_{i}-x\tag{1}\label{ref1}\\ \\
d_{i+1}& = dpw+x\tag{2}\label{ref2}\\ \\
c_{i+1}&=c_{i}-[s_{i}-(d_{i}-x)]=c_{i}-[s_{i}-(dpw-x)]=(c_{i}+dpw)-(s_{i}+x)
\tag{3}\label{ref3}
\end{align}

Clearly on day \(i+1\) there are more defenders and less soldiers than on day \(i\).

Lets suppose that  the soldiers on day \(i+1\) decide to kill all \(d_{i+1}\) defenders again. This means that the remaining \(s_{i+1}-d_{i+1}\) soldiers attack the castle. We still assume that \(c_{i+1}>0\).
Then at the start of the next day we will be left with

\begin{align}
s_{i+2}& = s_{i+1}=s_{i}-x\\ \\
d_{i+2}& = dpw\\ \\
c_{i+2}&=c_{i+1}-(s_{i+1}-d_{i+1})=c_{i}+dpw-s_{i}-x-s_{i}+x+dpw+x=c_{i}+2dpw + x-2s_{i}\tag{4}\label{ref4}
\end{align}

where we replaced the quantities on day \(i+1\) with \ref{ref1},\ref{ref2},\ref{ref3}.

If however the soldiers killed all defenders every single day (i.e. \(x=0\)), we would have on day \(i+2\)

\begin{align}
s_{i+2}& = s_{i+1}=s_{i}\\ \\
d_{i+2}&= dpw \\ \\
c_{i+2}&=c_{i}+2dpw -2s_{i}\tag{5}\label{ref5}
\end{align}

i.e. the castle would end up with less strength points (since \(c_{i+2}\) in \ref{ref5} is smaller than \(c_{i+2}\) in \ref{ref4}).

From this analysis we see that the castle strength is smaller on day \(i+2\) if the soldiers kill all defenders every single day instead of leaving some alive and firing a few extra shots at the castle.

Therefore the soldiers, if they can, should never leave defenders and the castle alive on the same day. It is possible that \(c_{i+2}=c_{i}+2dpw + x-2s_{i}<0\), i.e. the soldiers finish the castle on day \(i+1\) while leaving \(x\) defenders alive. But they could also have been done with the castle on day \(i+1\) or earlier if they kept killing all defenders (since if \(c_{i}+2dpw + x-2s_{i}<0\) obviously \(c_{i}+2dpw-2s_{i}<0\) ) and they would have the added bonus of not having lost any soldier. So while it is not always completely disadvantageous to leave some defenders alive, it is never advantageous since the soldiers can finish always in the same number of days and with all the soldiers alive by always killing all the defenders.

Given this optimal strategy, how many days does it take for the soldiers to win? It is convenient to break this question into two: 1) In which day should the castle be destroyed, i.e. how many days should it take to bring the castle down and 2) How many days after the castle has been destroyed it takes for the soldiers to kill all defenders. It turns out that to answer 1) we must first answer 2).


Number of days to kill all defenders (after the castle has been destroyed)


Lets suppose the castle is destroyed on day \(q\). Since up to day \(q\) the soldiers have been killing all defenders every day, all the soldiers are still alive. Let \(n\) be the number of initial soldiers (i.e. \(s_{1}=n\)). At the start of day \(q\), \(c_{q}\) of the  \(n\) soldiers shoot at the castle destroying it. The remaining \(n-c_{q}\) soldiers fire then at the \(dpw\) defenders leaving
\begin{equation}
x=dpw-(n-c_{q})=c_{q}+dpw-n
\end{equation}
of the defenders standing.

Afterwards the number of soldiers and defenders in the days after the castle was destroyed \(q+1, q+2, q+3, ...\), changes like this

\begin{align}
d_{q+1}&=x\\ \\
s_{q+1}&=n-x\\ \\
d_{q+2}&=d_{q+1}-s_{q+1}=2x-n\\ \\
s_{q+2}&=s_{q+1}-d_{q+2}=n-x-2x+n=2n-3x\\ \\
d_{q+3}&=d_{q+2}-s_{q+2}=2x-n-2n+3x=5x-3n\\ \\
s_{q+3}&=s_{q+2}-d_{q+3}=2n-3x-5x+3n=5n-8x
\end{align}

More generally we can write

\begin{align}
d_{q+i+1}&=xFib(2i+1)-nFib(2i)\tag{def}\label{def}\\ \\
s_{q+i+1}&=nFib(2i+1)-xFib(2i+2)\tag{sold}\label{sold}
\end{align}
where \(Fib\) is the Fibonacci sequence of numbers (see for example Wikipedia).

It turns out that the Fibonacci  \(p\) term can be written in closed form as

\begin{align}
Fib(p) &=\frac{\phi^{p}-(-\phi)^{-p}}{\sqrt{5}}\\ \\
\phi    &=\frac{1+\sqrt{5}}{2}
\end{align}

where \(\phi\) is the golden ratio (see for example Wolfram Mathworld).

It follows that the number of defenders reaches zero, \(d_{q+i+1}=0\)  for \(i=k\) such that

\begin{align}
xFib(2k+1)-nFib(2k)=\frac{x(\phi^{2k+1}-(-\phi)^{-2k-1})-n(\phi^{2k}-(-\phi)^{-2k})}{\sqrt{5}}=0
\end{align}

Because any negative number raised to an even power like \(2k\) is a positive number, this can be rewritten as
\begin{align}
(x\phi-n)\phi^{2k}+(x\phi^{-1}+n)\phi^{-2k}&=0
\end{align}
or
\begin{align}
\phi^{4k}(n-x\phi)&=(n+x\phi^{-1})
\end{align}
Taking the logarithm in the base \(\phi\) of both sides then leads to
\begin{align}
\log_{\phi}\phi^{4k}(n-x\phi)&= 4k+\log_{\phi}(n-x\phi)=\log_{\phi}(n+x\phi^{-1})
\end{align}
solving for \(k\) gives,
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{n+x\phi^{-1}}{n-x\phi}}{4}\right\rceil\tag{6}\label{ref6}\\ \\
x\equiv x_{q}&=dpw-(n-c_{q})=c_{q}+dpw-n\tag{7}\label{ref7}\\ \\
\phi    &=\frac{1+\sqrt{5}}{2}
\end{align}

The ceiling in the above expression  takes into account that depending on the values of \(x,n\) there might not be an integer value of \(k\) for which the number of defenders is zero, i.e. the defenders might be zero for a decimal value of \(k\). We should therefore round up to the nearest integer that decimal value, since we are interested in finding out the day \(k\) in which the number of defenders becomes zero or negative, i.e. the soldiers will win on the day \(k\) after \(q\) in which \(d_{q+k}<=s_{q+k}\).

Note that to find \(k,x\) we need to know \(c_{q}\) which is the castle strength at the beginning of the day the castle was destroyed. To find it we next turn to finding \(q\), the number of days to destroy the castle.

Number of days to destroy the castle


Following the optimal strategy, the soldiers decrease the castle strength to \(s-n\) on the first day and every day (after the first), \(dpw\) of the soldiers kill \(dpw\) defenders and the remainder \(n-dpw\) soldiers decrease the castle strength by \(n-dpw\). The number of soldiers remains \(n\). That means that at the beginning of the day \(q\) in which the soldiers destroy the castle, the soldiers, castle strength and the remaining defenders are
\begin{align}
s_{q}&=n\\ \\
c_{q}&= s-n-(q-1)(n-dpw)=s-nq+(q-1)dpw\\ \\
d_{q}&=x_{q}=dpw-(n-c_{q})=dpw-n+c_{q}=s+qdpw-(q+1)n\tag{8}\label{ref8}
\end{align}

The question for the soldiers is: should they attack the castle on day \(q\) or should they wait?
They should wait another day if the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q+1\)  plus one day is smaller than the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q\) or in other words (using \ref{ref6})
\begin{align}
\frac{\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}}{4}+1<\frac{\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}}{4}
\end{align}
We can rewrite this as
\begin{align}
\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}-\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}>4
\end{align}
or combining the subtraction in the \(log\) and then removing the \(log\)
\begin{align}
\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}\frac{n-x_{q+1}\phi}{n+x_{q+1}\phi^{-1}}>\phi^{4}
\end{align}cross multiplying leads to
\begin{align}
n^{2}-nx_{q+1}\phi+nx_{q}\phi^{-1}-x_{q}x_{q+1}>\phi^{4}[n^{2}+nx_{q+1}\phi^{-1}-nx_{q}\phi-x_{q}x_{q+1}]
\end{align}
rearranging and taking into account that
\begin{align}
\phi^{4} &=\frac{7+3\sqrt{5}}{2}=3\phi+2\\ \\
\end{align}
we arrive at
\begin{align}
(3\phi+1)n^{2}+(3+2\phi^{-1}+\phi)nx_{q+1}-(3\phi^{2}+2\phi+\phi^{-1})nx_{q}\phi-(3\phi+1)x_{q}x_{q+1}<0\tag{9}\label{ref9}
\end{align}
noticing that
\begin{align}
\phi^{-1}&=-\frac{1}{2}(1-\sqrt{5})\\ \\
\phi^{2}&=\frac{3+\sqrt{5}}{2}=\phi+1\\ \\
3+2\phi^{-1}+\phi&= 3\phi+1\\ \\
3\phi^{2}+2\phi+\phi^{-1}&=2(3\phi+1)
\end{align}
we can rewrite \ref{ref9} as
\begin{align}
(3\phi+1)[n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}]<0
\end{align}
or
\begin{align}
n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}<0\tag{10}\label{ref10}
\end{align}
we can see from \ref{ref7} or \ref{ref8} that
\begin{align}
x_{q+1}&=s+(q+1)dpw-(q+2)n=x_{q}+dpw-n\tag{11}\label{ref11}
\end{align}
so replacing this into \ref{ref10} we get
\begin{align}
x^{2}_{q}-ndpw+dpwx_{q}>0
\end{align}
solving this quadratic equation and keeping only the positive solution (since we are assuming \(x_{q}>0\)) we get
\begin{align}
x_{q}>\frac{-dpw+\sqrt{dpw^{2}+4ndpw}}{2}
\end{align}
replacing \(x_{q}\) with \ref{ref8} we get
\begin{align}
2s+2q(dpw-n)-2n>-dpw+\sqrt{dpw^{2}+4ndpw}
\end{align}
solving for \(q\)
\begin{align}
q=\left\lceil\frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\tag{12}\label{ref12}
\end{align}
This is the minimum number of days it takes for the soldiers to kill the castle.
We also point out that the optimal strategy followed by the soldiers of always killing all defenders each day and then attacking the castle is only possible if \(dpw<n\).

2.b The case \(n<s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n\)


What happens if \(dpw\geq n\)? At the end of the first day, the castle is down to \(c_{2}=s-n\) strength points and sends out \(dpw\) defenders.
On the second day, the soldiers have to split their fire on the castle and on the defenders. Otherwise if they just fire at the castle, they will be all killed by the end of the second day. They also have to kill enough defenders that they are not killed by the remaining defenders.
Lets write down the changes in the number of soldiers, defenders and castle hits as the days go by:
At the beginning of the 2nd day we have
\begin{align}
s_{2}&=n\\
d_{2}&=dpw\\
c_{2}&=s-n
\end{align}
Lets assume that the soldiers leave \(x_{2}\) defenders alive on the second day.
At the beginning of the 3rd day then
\begin{align}
s_{3}&=n-x_{2}\\
d_{3}&=dpw+x_{2}\\
c_{3}&=c_{2}-[n-(dpw-x_{2})]=s-2n+dpw-x_{2}=(s-2n)+dpw-x_{2}
\end{align}
Lets assume that the soldiers leave \(x_{3}\) defenders alive on the third day.
At the beginning of the 4th day then
\begin{align}
s_{4}&=n-x_{2}-x_{3}\\
d_{4}&=dpw+x_{3}\\
c_{4}&=c_{3}-[n-x_{2}-(dpw+x_{2}-x_{3})]=(s-2n)+(dpw-n)+dpw+x_{2}-x_{3}
\end{align}
Lets assume that the soldiers leave \(x_{4}\) defenders alive on the fourth day.
At the beginning of the 5th day then
\begin{align}
s_{5}&=n-x_{2}-x_{3}-x_{4}\\
d_{5}&=dpw+x_{4}\\
c_{5}&=c_{4}-[n-x_{2}-x_{3}-(dpw+x_{3}-x_{4})]=(s-2n)+ 2(dpw-n)+dpw + 2x_{2}+x_{3}-x_{4}\tag{13}\label{ref13}
\end{align}
A necessary condition for the soldiers to win is that on the last day of the battle, lets call it \(q\), the castle strength \(c_{q}=0\) but the number of soldiers \(s_{q}>0\).
If we follow the pattern in \ref{ref13} we have on the last day of the battle (\(x_{2}, x_{3},...,x_{q-1}\) is the number of defenders left alive by the soldiers on days 2,3,...,\(q-1\))
\begin{align}
s_{q}&=n-x_{2}-x_{3}-...-x_{q-1}\\
d_{q}&=dpw+x_{q-1}\\
c_{q}&=c_{q-1}-[n-x_{2}-x_{3}-...-x_{q-2}-(dpw+x_{q-2}-x_{q-1})]=(s-2n)+ (q-2)(dpw-n)+dpw+(q-3)x_{2}+(q-4)x_{3}+...-x_{q-1}
\end{align}
This result shows that if \(s\geq 2n, dpw\geq n\), \(c_{q}>0\), i.e. it is impossible for the soldiers to win because the castle strength can never become zero.
Therefore for the soldiers to have a chance the castle strength must be \(n\leq s<2n\).

Clearly the best strategy for the soldiers is not to only shoot at the defenders every day (as they should do if \(dpw<n\)). Since \(dpw\geq n\), if the soldiers only fire at the defenders and not at the castle, the castle will keep adding \(dpw\) defenders every round and it will win quickly.

The following table shows the values of \(x_{n-1},c_{n},d_{n},s_{n}\) if the castle is destroyed at the end of the 2nd, 3rd, 4th day. We simply set \(c_{3}=0\) above if the castle is destroyed on the second day, or \(c_{4}=0\) above if the castle is destroyed on the third day, etc.

Notice that because the castle is destroyed, it doesnt add \(dpw\) to the defenders on the day it is destroyed.

Day castle killed \(x_{n-1}\) \(s_{n}\) \(d_{n}\)
2 (\(c_{3}=0\)) \(x_{2}=(s-n)+(dpw-n)\) \(s_{3}=n-x_{2}=n-(s-n)-(dpw-n)\) \(d_{3}=x_{2}=(s-n)+(dpw-n)\)
3 (\(c_{4}=0\)) \(x_{3}=(s-n)+2(dpw-n)+x_{2}\) \(s_{4}=n-x_{2}-x_{3}=n-(s-n)-2(dpw-n)\)-2x_{2} \(d_{4}=x_{3}=(s-n)+2(dpw-n)+x_{2}\)
4 (\(c_{5}=0\)) \(x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\) \(s_{5}=n-x_{2}-x_{3}-x_{4}=n-(s-n)-3(dpw-n)-3x_{2}-2x_{3}\) \(d_{5}=x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\)

Since \(s-n>0,dpw-n\geq 0, x_{2}\geq 0, x_{3}\geq 0\) it is obvious from this table that the number of soldiers on the day the castle is destroyed is largest and the number of defenders on that same day is the smallest if the castle is destroyed on the second day (i.e. \(s_{3} > s_{4} > s_{5}, d_{3} < d_{4} < d_{5}\)).
That means that the fastest way for the soldiers to win is by destroying the castle on the second day.

It is also clear from the table that:

  •  The higher \(s\) and \(dpw\) the smaller the number of soldiers and the higher the number of defenders on the day the castle is destroyed. This means that there is a narrow range of values of \(s\) and \(dpw\) for which the soldiers can win.
  • The number of defenders and soldiers if the castle is destroyed on day 3 is dependent on \(x_{2}\) i.e. how many defenders where left alive by the soldiers on day 2. The higher \(x_{2}\) the higher the number of defenders on day 3 (i.e. the higher \(d_{4}\)) and the lower the number of soldiers (i.e. the lower \(s_{4}\)). Now notice that \(x_{2}\) is the highest when the castle is destroyed on day 2 because that is when most of the soldiers fire is directed towards the castle.
  • \(x_{2}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.
  • The number of defenders if the castle is destroyed on day 4 is dependent on \(x_{2}, x_{3}\) i.e. how many defenders where left alive by the soldiers on day 2 and day 3. The higher \(x_{3}\) the higher the number of defenders on day 4 (i.e. the higher \(d_{5}\)). Now notice that \(x_{3}\) is the highest when the castle is destroyed on day 3 because that is when most of the soldiers fire is directed towards the castle.
  • \(x_{3}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.

It is quite tricky to find all possible solutions in which the soldiers win without an exhaustive search. For example if \(dpw=n\), there is always an infinite number of solutions in which the soldiers win: they can kill the castle on day 2, or day 3, or day 4 or day 5 or any day they want. How? For example if they want to destroy the castle on day 5 they kill the \(dpw=n\) defenders that the castle sent on days 2,3,4 and then on day 5 they destroy the castle. The same pattern can be repeated if the soldiers want to destroy the castle on any day.

Besides having to destroy the castle by the second day, the soldiers must be able to finish off the defenders. This can be accomplished in \(k\) days after the castle is destroyed with \(k\) given by \ref{ref6}.  What is \(x\) in the expression \ref{ref6} for \(k\)? It is the number of defenders left at the end of the second day. We know that at the end of the first day the castle is down to \(s-n\) strength points and at the end of the second day \(s-n\) of the soldiers finish it of. The remaining \(n-(s-n)=2n-s\) then attack the \(dpw\) defenders leaving \(x=dpw-(2n-s)=dpw+s-2n\) defenders.
This agrees with the expression for \(x\) in \ref{ref7}.

From day 3 onward the soldiers and the defenders battle it out and their numbers change according with the logic above that led to \ref{ref7}. In particular the number of defenders and soldiers after \(2+i+1\) days is given by \ref{def} and \ref{sold}. The game progresses until the number of defenders is negative or zero while the number of soldiers is positive.

We already know that since \(dpw\geq n, n<s<2n\), that \(s+dpw>2n\) so obviously \(x=dpw+s-2n>0\). But \(x\) can not be arbitrarily large otherwise the defenders will overwhelm the soldiers and win the game. In other words we want the number of soldiers to be positive for all values of  \(i\) in \ref{sold}. Since the soldiers number will be the smallest the larger the value of \(i\) this means we want the smallest possible value of the soldiers to still be positive. This happens when we take the limit \(i\rightarrow \infty\) i.e.
\begin{align}
n-x\lim_{i\to\infty}\frac{Fib(2i+2)}{Fib(2i+1)}>0
\end{align}
since \(\lim_{i \to \infty}Fib(2i+2)/Fib(2i+1)=\phi\)  (see for example Wikipedia) this is the same as
\begin{align}
x\phi<n
\end{align}
or after replacing \(x=dpw+s-2n\)
\begin{align}
dpw+s<(2+\phi^{-1})n=(\phi+1)n
\end{align}
In other words the soldiers can win if \(dpw\geq n, n<s<2n\) only if \(2n<dpw+s<(\phi+1)n\) .

Recaping the ways the soldiers can win

It is time to summarize all the cases described in detail above.
Case Condition Soldiers minimum moves to win Soldiers strategy
1 \(s\leq n \) 1 All soldiers fire their cannons at the castle.
2a \(s> n\)
\( dpw < n\)
\(q+max(0,k) days\)
\begin{align}
q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{{2(dpw-n)}}\right\rceil\\ \\
k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\tag{14}\label{ref14}\\ \\
\end{align}
Kill \(dpw\) defenders for the first \(q\) days until the castle strength vanishes.
Afterwards just shoot at the defenders left and be done in \(k\) days.
2b \(n < s < 2n\)

\( dpw \geq n\)

\( 2n < dpw+s<(\phi+1)n\)
\( 2 + max(0,k) days\)
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\tag{15}\label{ref15}\\ \\
\end{align}
Destroy the castle in two days and battle the defenders in the next \(k\) days.
2c \(n < s < 2n\)

\( dpw \geq n\)

\( 2n < dpw+s\geq(\phi+1)n\)
Can not win No winning strategy
2d \( s > 2n\)

\(dpw\geq n\)
Can not win No winning strategy


Minimum number of days for the castle to win

The general case is quite complicated and we will just describe a few cases.

If \(dpw+s\leq 2n, s>n,dpw<n\) the castle can not win. After the first day, \(dpw+castleStrength\leq n\) and since there are \(n\) soldiers and they attack first, the soldiers win on the second day.

If \(dpw+s> 2n, s>n, dpw<n\) the castle sometimes will not be able to win and when it can win it will need more than 2 days at a minimum to win because the number of defenders per day is not enough to kill the soldiers in one day (the maximum value of  \(dpw=n-1\)).

At the end of the first day \(dpw+castleStrength>n, castleStrength=s-n\).

If \(dpw=n-1\) which is the maximum value of defenders to obey \(dpw<n\), the castle will take at least 3 days to win. It can win on the third day only if \(s>2n\) [the soldiers attack the castle only on the first two days leaving it with \(1\) strength point and leaving \(1\) soldier only standing. If that soldier then destroys the castle, it will be killed by the \(2n-2\) defenders on the third day. 

If \(s=n+2, dpw=n-1, n>1\), the castle can not win. The soldiers on the first day reduce the castle strength to 2. On the second day the soldiers have two options: 1) they destroy the castle and kill \(n-2\) defenders leaving only one. That one kills a soldier and is then killed by the remaining soldiers on the third day. 2) If on the contrary the soldiers killed all defenders and 1 strength point, the third day would start with \(n-1\) defenders and the castle with \(1\) strength point, so the \(n\) soldiers would still win on the third day. If \(dpw<n-1\) the same arguments apply but to even less defenders. Besides \(s+dpw\leq 2n\). It follows that if \(s=n+2\) the castle can never win.

If \(s=n+3, dpw=n-1, n>2\), the castle can win under certain circumstances. 
The soldiers on the first day reduce the castle strength to 3. They then have 3 options: 1) On the second day they destroy the castle and kill all but 2 defenders. These kill 2 soldiers leaving at least one. The third day starts with \(2\) defenders and at least one soldier. The castle wins on the third day only if there is one soldier (i.e. if \(n=3\)). If there are two or more soldiers, the castle can not win.
2) On the second day they leave the castle with 1 point and kill all but 1 defender which then kills 1 soldier. The third day starts with \(n-1\) soldiers, \(n\) defenders and 1 castle strength point. The castle can now always win if the soldiers always hit the defenders but not the castle. That way the castle keeps sending \(n-1\) defenders, while the soldiers decrease steadily. Following this approach the castle can only win on the third day if \(n=3\)  [by destroying the castle and killing one defender, then the remaining two defenders kill the 2 soldiers] or on the fourth day if \(n=4\), etc.
3) On the second day they leave the castle with 2 points and kill all defenders. The third day starts with \(n-1\) defenders, \(n\) soldiers and 2 castle strength points. This is similar to what happens on the second day of the case \(s=n+2,dpw=n-1,n>1\) so we know there is no solution where the castle can win.
If  \(s=n+3, dpw<n-1\) we have \(s+dpw\leq 2n+1\) which is the same case as \(s=n+2, dpw<n\) above and has no solutions.

2.c The case \(n\geq 2n, dpw\geq n, dpw+s\geq(\phi+1)n\)

Left as an exercise.

2.d The case \(s\geq 2n, dpw\geq n\)

If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum if  on both days the soldiers attack only the castle and never attack the defenders.  The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.

If \(dpw=n\) the soldiers can tie the game by always killing all defenders starting on day 2.

 Lets recap all possibilities.

Recap 


Case Condition Soldiers minimum moves win Castle minimum moves win
1 \(s\leq n\) Win in one day Can not win
2a \(s> n\)
\( dpw < n\)
\(q+max(0,k)\) days
\begin{align}
q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\\ \\
k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\\ \\
\end{align}
Win in two days if \(dpw+s > 3n\)

Can not win if \(dpw+s\leq 3n\)
2b \(n < s < 2n\)

\( dpw \geq n\)

\( 2n < dpw+s<(\phi+1)n\)
\( 2 + max(0,k) days\)
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\\ \\
\end{align}
Left as an exercise
2c \(n < s < 2n\)

\( dpw \geq n\)

\( 2n < dpw+s\geq(\phi+1)n\)
Can not win Left as an exercise
2d \( s > 2n\)

\(dpw\geq n\)
Can not win Win in 2 days (soldiers attack the castle only)



  • If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum (if the soldiers attack the castle and not the defenders). The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.

  • If \(n<s<2n, dpw\geq n, (\phi+1)n<dpw+s\), the soldiers can not win but the castle might take more than 2 days to win at a minimum. Consider the following example

\(n=3819, s=5000, dpw=5000\)
The soldiers can not win. The castle can win in 3 rounds (but not in 2):
At the end of the first day, the castle is down to 1181. If the soldiers on day 2 instead of destroying the castle kill 3819 defenders, the remaining 1181 defenders would fire back and leave 2638 soldiers at the start of day 3 with 6181 defenders. If all the soldiers then attacked the castle on day 3, the soldiers would be all killed and would lose on day 3. 

On the other hand if we start with one extra soldier
\(n=3820, s=5000, dpw=5000\)
This falls into the second case above, since \(dpw+s=10000<(\phi+1)3820\). The soldiers can win in
\(2+k\) days where
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{3820+(10000-2\times 3820)\phi^{-1}}{3820-(10000-2\times 3820)\phi}}{4}\right\rceil=\left\lceil\frac{\log_{\phi}\frac{3820+2360\phi^{-1}}{3820-2360\phi}}{4}\right\rceil=5
\end{align}
I.e the soldiers can win in 7 waves:
At the end of the first day the castle strength is down to 1180, and there are 5000 defenders.
At the end of the second day, the castle is gone and 5000- 2640=2360 defenders remain. They then kill that many soldiers leaving 1460 soldiers.
At the end of the third day, there are 2360-1460=900 defenders and 1460-900=560 soldiers.
At the end of the fourth day, there are 900-560=340 defenders and 560-340=220 soldiers.
At the end of the fifth day, there are 340-220=120 defenders and 220-120=100 soldiers.
At the end of the sixth day there are 120-100=20 defenders and 100-20=80 soldiers.
At the end of the seventh day the soldiers win.

The castle can still win in 3 waves minimum if the soldiers attack the castle on the first day, attack the defenders on the second and attack the castle on the third day.

Notice that if the number of soldiers were \(n=3819\) and the soldiers followed the same strategy, we would have
End of first day: castle strength=1181 and 5000 defenders.
End of second day: castle strength=0, 5000-2638=2362 defenders, 3819-2362=1457 soldiers.
End of third day: 2362-1457=905 defenders and 1457-905=552 soldiers
End of fourth day: 905-552=353 defenders and 552-353=199 soldiers
End of fifth day: 353-199=154 defenders and 199-154=45 soldiers
End of sixth day:  154-45=109 defenders and all soldiers are dead.
The castle wins in six rounds. The soldiers can not win. What a difference a single soldier makes!


Code Implementation

Using the mathematical logic above it is straightforward to write code that finds the minimum number of days for the soldiers to win, as well as the path/strategy the soldiers should follow to accomplish that feat.

The tests in the tests.py class are labeled according with whether they fall under cases 2a, 2b, 2c, 2d in the classification given in the tables above.
The code in CastleDefenseIIIMath.py uses the formulae we derived above to quickly find the minimum number of days solution for the soldiers to win. 

There are now 54 tests as opposed to 27 in our previous two posts.
If you want to run just the previous 27 tests, make all_tests=old_tests in tests.py. This will run very quickly.
Some of the newer tests (like tests 37 and 46) take some time to execute but with some minutes of patience you will get the solution. Many of those newer tests would be impossible to run in a timely manner with our previous exhaustive search code.

Saturday, August 15, 2015

Castle Defense II - Exact Recursive Solution


In our previous post  we looked at two approaches to solve the following problem:
The gameSoldiers soldiers approached silently the remarkable place.
In the gloom the courtyard below looked of considerable size, and as several dark ways led from it under great round arches, it perhaps seemed bigger than it really was. 
Daylight was still a few hours away. The commander silently rose his right hand causing the company to come to an halt. He surveyed the hill where his men were standing which surrounded the castle below. It seemed to be the perfect spot. They needed to be careful and silent  since the danger would only disappear at sunrise. He was surprised they had been able to make it this far in the middle of the night without having been detected by the Count's minions.
The commander looked at his men; they were the best of the best. If anyone was going to remove this evil castle from this land these were the men capable of doing it. His hand drew a wide circle around the hill and the men moved the canons into position. They would need them to destroy the solid castle which could withstand castleHits hits (one canon shot, one hit).
Then they waited. As they sat they heard a sound in the courtyard —the agonized cry of a woman. Peering through the tall grass there, indeed, was a woman with disheveled hair, holding her hands over her heart as one distressed with running. She was leaning against a corner of the gateway. She seemed to be facing somebody for she shouted in a voice laden with menace:—
“Monster, give me my child!”
She threw herself on her knees, and raising up her hands, cried the same words in tones which wrung the soldiers' hearts. Then she tore her hair and beat her breast, and abandoned herself to all the violences of extravagant emotion. Finally, she threw herself forward, and, though they could not see her, they could hear the beating of her naked hands against the door.
Somewhere high overhead, probably on the tower, they heard the voice of the Count calling in his harsh, metallic whisper. His call seemed to be answered from far and wide by the howling of wolves. Before many minutes had passed a pack of them poured, like a pent-up dam when liberated, through the wide entrance into the courtyard.
There was no cry from the woman, and the howling of the wolves was but short. Before long they streamed away singly, licking their lips.
The wait was now unbearable for the men, but it was over quickly: The sun rose rapidly and the commander gave the sign. Taking turns, each soldier shot his canon at the castle. The castle strength was now down to \(castleHits=castleHits-gameSoldiers\).
They then waited for new canon balls to arrive, knowing the Count would not sit idly- and indeed as the sun set on the horizon and night fell, they saw a commotion, then the castle doors opening and defendersPerWave defenders leaving the castle. The enemies moved slowly toward the soldiers, who checked their rifles and waited in tense silence. Their commander had given instructions on what to do each day: how many (if any) should fire their rifles at the defenders and how many (if any) should fire their canons at the castle. He had sat beforehand with the city's scientist who had given him the best course of action for his men to employ each day such that the soldiers could destroy the castle in the minimum number of days.

In the ensuing days the castle and the soldiers battled it out following these rules:
  1. All the soldiers fired first. A soldier could fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier could only shoot once). One shot at a defender killed him. One shot at the castle decreased its strength by 1.
  2. Then each of the defenders would shoot one soldier (and only one) killing him.
  3. If the castle still had strength points (i.e. \(castleHits>0\)) it would send a new batch of defendersPerWave defenders at this point. The total number of defenders in the next round would be then \(defenders=defenders + defendersPerWave\).
  4. Repeat 1 through 3 in each new day.
  5. If all soldiers were killed by the defenders, the castle would win.
  6. If there were zero defenders left after the soldiers shot and the castle strength was also zero, the soldiers would win.
The scientist had given not just the minimum number of rounds the soldiers needed to win the battle (or if not possible the minimum number of rounds for the castle to win) but also the number of soldiers, defenders and castle hit points at the end/beginning of each round for the minimum number of rounds solution. 
The scientist was highly respected but as the days went on and their comrades died like flies, the soldiers questioned whether his approach was indeed the best. Some of the soldiers asked the commander why not use the technique of killing the defenders first and only then shoot at the castle. The commander showed them how this approach would lengthen their campaign (see previous post) since it would not lead to the minimum number of days to win and above all sometimes would lead at the castle winning (see tests 0,6,9,15 were this approach leads to a win for the castle). 
Some then argued that all their might should focus on the castle but again the commander showed them how it also failed to lead to victory sometimes (again see previous post, in particular the tests 11,12,17,18,22,26 and 26 where this approach leads to a win for the castle). He then decided to double check himself the scientist's calculations.

As we and the commander noticed, none of the two approaches in the previous post solved the problem correctly in all cases.
It is likely that there is a clever algorithm that solves the problem correctly always but it is not obvious right away how to go about finding it.
An easier approach is to solve the problem by brute force: Try all possible plays allowed by the rules at the beginning of each wave, trace paths from the beginning state until a state in which either the soldiers win or the castle wins (a goal state). Then pick among those paths those for which the number of rounds is minimum (as we have seen in our previous post, there will be cases where there is more than one path corresponding to a minimum number of rounds; take a look at the table in the previous post and in particular to tests that are correctly solved by both algorithms but that end up with a different number of soldiers left standing: tests 2,3,4,5,8,20,23,24).
In the following discussion we will, for every test from our previous post, compute all the paths that lead to a solution. We will store them in a dictionary where the key is the number of waves a given solution takes and the values are the paths from the start to the end goal (castle/soldiers win).

A RECURSIVE SOLUTION

A simple method to search through every possible path is given by the following code fragment


   # if castleHits =0, soldiers play against defenders only
   def soldiersVsDefenders(self,soldiers,defenders):
       # soldiers win or castle/defenders win
       if defenders <=0 or soldiers <= 0:             
          return
                       
       # do another round of fighting
       # 1. Soldiers kill as many defenders 
       defendersLeft = defenders - soldiers
       # 2. defendersLeft kill as many soldiers
       soldiersLeft = soldiers - defendersLeft 
      
       self.soldiersVsDefenders(soldiersLeft,defendersLeft, 1+wave)

 
  def oneWave(self,soldiers,defenders,castleHits,wave =0):
    # castle/defenders wins
    if soldiers <= 0: 
       return

    # castle is dead, let soldiers play against defenders
    if castleHits <= 0:           
        defendersLeft = defenders - self.dpw
        self.soldiersVsDefenders(soldiers,defendersLeft,path, wave)
        return
                 
    # try every possibility:
    # 1) all soldiers hit the castle, none hits the defenders
    # 2) all but one soldier hits the castle, the others hit the defenders
    # 3) all but two soldiers hit the castle, the others hit the defenders
    # ...
    # soldiers) no soldier hits the castle, all others hit the 
    # defenders
    for i in range(0,soldiers+1):
      if i > defenders:               
          break
      soldiersLeft = soldiers - (defenders -i)
      defendersLeft = defenders - i + self.dpw
      castleHitsLeft = castleHits - (soldiers -i)
      
      self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft,1+ wave)

  # start game
  def searchMinimumRecursive(self,soldiers,castleHits,defendersPerWave):
       self.dpw = defendersPerWave
       self.oneWave(soldiers,0,castleHits)
          
The oneWave method simulates... one round/wave of the game. It is first called by the searchMinimumRecursive with the initial values.
For each wave the method takes however many soldiers, defenders, castleHits are available at the beginning of that wave as arguments as well as the wave number (note how by default wave starts at 0).
The method then tries every possible path for those initial values recursively. This is achieved through the for loop
 
  for i in range(0,soldiers+1):

Lets walk through the loop:
  • When i=0, all soldiers hit the castle and all defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-defenders, defendersLeft=defenders+self.dpw, castleHitsLeft=castleHits-soldiers\). Then recurse with those values.
  • When i=1, all but one of the soldiers hits the castle, one soldier hits one defender and the remaining defenders-1 defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-1), defendersLeft=defenders-1+self.dpw, castleHitsLeft=castleHits-(soldiers-1)\). Then move to the next wave with those values.
  • When i=2, all but two of the soldiers hits the castle, two soldiers hit two defenders and the remaining defenders-2 defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-2), defendersLeft=defenders-2+self.dpw, castleHitsLeft=castleHits-(soldiers-2)\). Then move to the next wave with those values.
  • This pattern continues until i=soldiers.  For this case, all soldiers hit the defenders and the remaining defenders hit back at the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-soldiers), defendersLeft=defenders-soldiers+self.dpw, castleHitsLeft=castleHits\). 
If at any point in the loop \(i>defenders\) we quit the loop (otherwise the formulas for soldiersLeft, defendersLeft,castleHitsLeft would be wrong: since \(defenders-i\) would be <0, the next wave would start with more soldiers than the previous wave which is obviously not correct).
If at any point in the recursion, soldiers becomes zero or smaller it means we reached a goal state where the castle wins and we just return.
If at any point in the recursion, castleHits becomes zero or smaller, it means the castle can no longer send defenderPerWaves defenders at the end of each round.
In this case we subtract the defendersPerWave that we had  added to the defendersLeft in the for loop (because we didnt know at the time that castleHits<=0) and call the method soldiersVsDefenders.
Note that we do not increase the wave value in this call. This makes sense: We at first played regularly (in the for loop) and recursed by increasing the wave number and the number of defenders as if the castle still had points left. Then we realized that the castle is gone, so we subtracted back the defendersPerWave and call soldiersVsDefenders so that the correct play for this wave can be made with the remaining soldiers and defenders playing against each other (the castle is gone from the picture).
The soldiersVsDefenders method just plays out wave after wave of soldiers vs defenders recursively: All soldiers hit an equal number of defenders leaving \(defendersLeft=defenders-soldiers\) and the remaining defenders then hit back leaving \(soldiersLeft=soldiers-defendersLeft\) soldiers. Then it increases the wave number and recurses.
If at any point soldiers or defenders become zero or lower then the castle or the soldiers respectively win i.e we stop recursing.
This recursive process is a more complicated example of what sometimes is called depth first search/recursive  backtracking: Starting at the root it follows a path all the way down until it finds a goal state or until it reaches a dead end. Then it backtracks up and repeats.
To visualize this process lets draw all possible paths for a few of the test cases from our previous post.
Figure 2 shows all the paths tried by the recursive algorithm for test 0, which starts with gameSoldiers=10, castleHits=11, defendersPerWave=15.

Figure 2 test0 solutions as found by the recursive method

There are only 3 paths (S,D and CH stand for soldiers, defenders and castlehits at the beginning of each wave) that lead to wins: The two in red correspond to wins by the castle. The one in blue corresponds to the only possible win by the soldiers (thus it is the minimum number of waves solution we care about).
The blue solution (4 waves) is

S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=4,D=6, CH= 0 → S=2, D=2, CH=0 → S=2, D=0, CH=0

Notice how we didn't include S=4,D=21,CH=0 in the path because it corresponds to the jump from the oneWave method to the soldiersVsDefenders method as discussed above. The method oneWave realizes that the castle is gone, subtracts the 15 defendersPErWave to the number of defenders that had added incorrectly and calls soldiersVsDefenders that then battle each other. The two castle wins (both in 3 waves) are

S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=16, CH=0 

and

S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=15, CH=1 

A few words about these solutions and figure 2:
  • We adopt the convention that in the wave that the castle wins, the castle does not send defendersPerWave more defenders (otherwise the number of defenders in the last solution would be 30 not 15 in the last wave); 
  • Most end states (including both of the red solutions), have a negative final number of soldiers. We discard all of those for which the castleHits is also negative. Those for which castleHits are 0 or greater are good solutions and that is how we picked the two red solutions. 
  • The transitions labeled soldiersVsDefenders indicate that the algorithm having reached zero castle hits calls soldiersVsDefenders from then on.
  • Each transition is labeled by the value of i in the loop above. So we see that the only solution that leads to a win by the soldiers has 9 of the soldiers hitting at 9 of the defenders and one soldier hitting at the castle in the second wave. The two solutions that lead to a win by the castle have all 10 soldiers hit at 10 of the defenders but not at the castle (in the second wave) which turns out to be a big mistake for the soldiers.  
Lets look at test1 in figure 3, which does not have any solution leading to a win for the soldiers. Accordingly all solutions are marked in red.
Figure 3- test1 solutions as found by the recursive method
 Every single path from the initial state to an end state is a win for the castle. There are 7 such paths. There are no invalid paths like in the previous test.
Two of the paths achieve the win in 2 waves and the other 5 take 3 waves.

Test 2, starts with 2 soldiers and a castle with strength 10 which can send 1 defender per wave.
Not surprisingly most of the solutions again correspond to wins by the castle. There are wins by the castle in 3,4,5,6,7,8 waves. The soldiers however can win in 9 rounds in 2 different ways: Up until wave 7 the 2 soldiers hit at the defender and cut by 1 the castle hits. Wave 8 starts with 2 soldiers, 1 defender and 2 castleHits. The soldiers have now two options to win: Finish off the castle, and lose one soldier hit by the lone defender, then finishing off the defender in wave 9 which ends with 1 soldier left. Or hit the defender and the castle in wave 8, then in wave 9 finishing off the castle and the defender and ending with 2 soldiers. Interestingly these two solutions were found by the approximate approaches that we saw in our previous post.

Test 3, starts with 11 soldiers and a castle with strength 12 which can send 9 defenders per wave.
This case only admits a single solution: The soldiers win in two rounds.

Test 4 (12 soldiers, castleHits=32, defenders per wave =5) has 136 solutions in which the soldiers win and 797 in which the castle wins.

Test 10 in figure 4, has a single solution that leads to a win by the soldiers in 4 rounds/waves (path in blue). It also has a tie on the second wave (path in green). Eight other paths lead to a win by the castle:3 paths in 3 waves and 5 paths in 4 waves. As we saw in our previous post, the approach of always attacking the defenders first, leads to the tie (green) path, while the approach of attacking the castle leads to the correct solution (blue).
Figure 4- test10 solutions as found by the recursive method


RECURSIVE CODE WALKTHROUGH

Without further ado, lets look at the complete code that computes all the wins by the castle and the soldiers.

An important caveat: If you run this code as is be prepared to wait 5-7 minutes. That is how long it will take for all the 27 tests to run.
The code builds upon the recursive algorithm described above but it is moderately complicated due to the handling of the several goal states and above all by the computation of the path. We added many comments to make it more readable/understandable.

The file tests.py contains the 27 tests. It also has the runTests method which will run them all. You can edit the all_tests list in this method, to run just a few tests (or even only one test) at a time.

The file CastleDefenseIIRecursive.py contains the main algorithm (in the methods searchMinimumRecursive which calls the method oneWave which will call the method soldiersVsDefenders in the case where castleHits reach zero but there are soldiers and defenders to battle it out).

The main algorithm computes all the paths that go from the initial state to a state corresponding to a win by either the soldiers or the castle (not just the shortest paths but ALL paths; a nice challenge for you is to modify the code to find only the shortest paths). It is the computation of all these paths that makes the program so slow (for some of the 27 tests there are thousands of solutions). In order to limit the running time you will notice that in tests.py some tests (test_5, test_12, test_22, test_25, test_26) will only keep solution paths in which the soldiers win. This is controlled by setting to false the boolean self.trackCastleWins in CastleDefenseIIRecursive. You will notice that if this flag is false, whenever a goal state in which the castle wins (i.e. the number of defenders is <=0) is found in either the oneWave method or the soldiersVsDefenders method, the path  it is not added to the self.waveStats dictionary. If you are curious to see the runtime increase you can switch to True this flag in those 4 tests.

The solution paths are stored as lists in the dictionary self.waveStats.  These paths are grouped by the number of waves they take (the length of a path is always wave+1). These waves are the keys in the dictionary. Because of this grouping, for a given key lets say 3 there will be paths that correspond both to wins by the soldiers and by the castle. These paths all take 3 waves. In order to find a path with minimum wave/rounds in self.waveStats that correspond to a soldier's wins, the method searchMinimumRecursive in CastleDefenseIIRecursive loops through the keys in self.waveStats in sorted order from smallest to largest. As soon as it finds a path with soldiers>0 it returns all the paths at that key to the test that called searchMinimumRecursive (it assumes that all those paths are wins by the soldiers).
If it reaches the end of the loop and it did not find any solution with soldiers>0, that means the soldiers can never win and  it then returns all paths (corresponding to castle wins) at the smallest key in the dictionary. The runTests method will then display each step of each minimum wave path.

The method printSolutions (which is called by searchMinimumRecursive for each test) prints additional information: How many winning solutions corresponding to wins by the soldiers per wave were found and similarly how many solutions corresponding to wins by the castle per wave were found. It also prints out how many total paths correspond to wins by the soldiers and by the castle (independently of the number of rounds each of these paths takes).

PATH COMPUTATION

The complicated part of the code in CastleDefenseIIRecursive.py is the computation of the paths. Lets walk through the code to understand how each path from the initial state to a goal state (castle/soldiers win) is computed.
In the method searchMinimumRecursive, the path is initialized with the initial state and it is passed as an argument to the call self.oneWave
In the for loop of this method that tries all the possible outcomes, the number of soldiers, defenders and castleHits in the next wave is appended to the path list and self.oneWave is called recursively.
With each recursive call the wave value goes up by one and another step is added to the path list.

If, during a recursive call, the number of soldiers becomes negative or zero (i.e. the soldiers lose), we 
replace the very last step in the path list, with a zero number of soldiers and subtract defenders per wave from the number of defenders. This is because in the recursive call that led to soldiersLeft<=0, self.dpw were added to defendersLeft under the assumption that there were soldiers left for another round. Then the corrected path is added to the dictionary of solution paths, self.waveStats and right before the method returns the last step is removed because we are returning to the recursive call where self.wave is one less. 

All of this is easier to understand by looking for example at figure 3. Consider the path (S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=-1,D=8,CH=4). After correcting the last step to (S=0, D=4, CH=4) and adding the whole path to the dictionary of paths, we want to remove this last step, right before returning/backtracking to the level above. The code will then try the next path (S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=0,D=7,CH=5), correct the last step, add the path to the dictionary and remove this last step from the path before backtracking again one level up. If we did not remove the last step in the first path, then we would end up with the path  (S=3,D=0,CH=10)→ (S=3,D=4,CH=7) → (S=0,D=4,CH=4)   (S=0,D=7,CH=5), for the second path which is obviously wrong.

The other possibility during a recursive call is that the number of castleHits becomes 0 or negative.
Then in the self.oneWave method, we subtract from  defendersLeft the number of defenders per wave (because these were added in the calling method without realizing that since castleHits<=0, the castle cant send any more defenders), correct the last step in the path and call self.soldiersVsDefenders.
This method appends to the path with each wave until either the number of defenders or soldiers becomes zero or negative. If the number of soldiers is positive, but the number of defenders is negative, that means that in the previous call, self.soldiersVsDefenders added soldiers to the existing number of soldiers (since it does soldiersLeft=soldiers-defendersLeft and since defendersLeft<0, this means we are increasing the number of soldiers) which is not a valid move. Therefore we should subtract the number of defenders that we previously added to the number of soldiers. Thats what we do with soldiers=soldiers+defenders. The path is corrected, added to self.waveStats and then all the steps added to the path since self.oneWave called self.soldiersVsDefenders are removed, since we are returning to the self.oneWave method.

Again to understand this logic it is easier to look at an example. Consider the path (S=10,D=0,CH=11) → (S=10,D=15,CH=1) → (S=4,D=21,CH=0) → (S=4,D=6, CH=0) → (S=2, D=2, CH=0) → (S=2, D=0, CH=0) in figure 2. Since we are returning all the way up to the step (S=4,D=21,CH=0) (which is where self.oneWave called self.soldiersVsDefenders) we have to remove all the steps after that one before returning otherwise we would end up with an incorrect next path (just like in the example above were the castle wins).

The final piece is in the method self.oneWave loop. After we return back to self.oneWave (from another self.oneWave call or from self.soldiersVsDefenders) we check if it is the end of the loop (if soldiers<defenders, the end of the loop is at i=soldiers, otherwise it is at i=defenders, since when i>defenders we break out of it). If it is, we remove all steps that are above the current wave.

To understand this, consider the last path in figure 3, (S=3,D=0,CH=10) →  (S=3,D=4,CH=7) →  (S=2, D=5,CH=7)  → (S=-1(0),D=7(3),CH=7). When we return to self.oneWave where i=2, we remove the last step. But we immediately return to self.oneWave where i=3 so we have to remove the previous to last step to keep the path length equal to the length of the wave were we are returning to. 

OUTPUT

Below is the output for test 2. It first shows that the soldiers can only win in 9 rounds/waves and there are 2 solutions with that number of waves.
Next it shows that the castle on the other hand can win in 3, 4, 5, 6, 7, 8 waves and in each of these cases there are 2 solutions that lead to the win.
The 2 paths leading to a win by the soldiers (in 9 rounds) are then shown. They are the same up until the end of wave 7. At the start of wave 8 there are 2 soldiers, 1 defender and 2 castle hits. In the first solution the 2 soldiers vanish the castle hits then lose one soldier and kill the defender in wave 9. One soldier is left standing. In the second solution, the 2 soldiers kill the defender and one of the castle hits and in wave 9 repeat the same strategy, leaving 2 soldiers standing.

Executing test 2
soldiers win wave: number of solutions with that wave {9: 2}
castle win wave : number of solutions with that wave {3: 2, 4: 2, 5: 2, 6: 2, 7: 2, 8: 2}
number of soldier wins: 2
number of castle wins: 12
***************
Recursive Solution
***************
Starting numbers (Begin of Wave 1)
defenders per wave =1
----------------
Number of Soldiers: 2
Number of Defenders: 0
Total castle hits left: 10
                                   
End of Wave 1
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 8
                                   
End of Wave 2
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 7
                                   
End of Wave 3
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 6
                                   
End of Wave 4
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 5
                                   
End of Wave 5
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 4
                                   
End of Wave 6
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 3
                                   
End of Wave 7
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 2
                                   
End of Wave 8
Number of Soldiers: 1
Number of Defenders: 1
Total castle hits left: 0
                                   
End of Wave 9
Number of Soldiers: 1
Number of Defenders: 0
Total castle hits left: 0
                                   
Soldiers win in 9 rounds
Starting numbers (Begin of Wave 1)
defenders per wave =1
----------------
Number of Soldiers: 2
Number of Defenders: 0
Total castle hits left: 10
                                   
End of Wave 1
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 8
                                   
End of Wave 2
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 7
                                   
End of Wave 3
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 6
                                   
End of Wave 4
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 5
                                   
End of Wave 5
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 4
                                   
End of Wave 6
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 3
                                   
End of Wave 7
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 2
                                   
End of Wave 8
Number of Soldiers: 2
Number of Defenders: 1
Total castle hits left: 1
                                   
End of Wave 9
Number of Soldiers: 2
Number of Defenders: 0
Total castle hits left: 0
                                   
Soldiers win in 9 rounds
=================================

Note that for a given test, if the soldiers can win, the code will output all the minimum number of rounds solutions corresponding to the soldiers wins. It will not show the wins by the castle that take a minimum number of waves. Since however the dictionary self.waveStats has all solutions we could easily modify the runTests method to also print those castle wins.
If the soldiers can not win, then the code will output the minimum number of castle wins solutions like in test 7 below
========================================
Executing test 7
soldiers win wave: number of solutions with that wave {}
castle win wave : number of solutions with that wave {2: 2, 3: 2}
number of soldier wins: 0
number of castle wins: 4
***************
Recursive Solution
***************
Starting numbers (Begin of Wave 1)
defenders per wave =7
----------------
Number of Soldiers: 4
Number of Defenders: 0
Total castle hits left: 6
                                   
End of Wave 1
Number of Soldiers: 4
Number of Defenders: 7
Total castle hits left: 2
                                   
End of Wave 2
Number of Soldiers: 0
Number of Defenders: 5
Total castle hits left: 0
                                   
Castle wins in 2 rounds
Starting numbers (Begin of Wave 1)
defenders per wave =7
----------------
Number of Soldiers: 4
Number of Defenders: 0
Total castle hits left: 6
                                   
End of Wave 1
Number of Soldiers: 4
Number of Defenders: 7
Total castle hits left: 2
                                   
End of Wave 2
Number of Soldiers: 0
Number of Defenders: 4
Total castle hits left: 1
                                   
Castle wins in 2 rounds
========================================

SUMMARY

We end this post with a table that summarizes the output for all 27 tests. In particular it shows the number of wins for both soldiers and castle organized by the number of waves those wins take


Test Initial Soldiers/CastleHits/Defenders per wave Wins by the Soldiers (Wave/number of wins) Wins by the Castle (Wave/number of wins)
0 10/11/15 1 (wave 4/1 win) 2 (wave 3/2 wins)
1 3/10/4 None 7 (wave 2/2 wins, wave 3/5 wins)
2 2/10/1 2 (wave 9/2 wins) 12 (wave 3/2 wins, wave 4/2 wins, wave 5/2 wins, wave 6/2 wins, wave 7/2 wins, wave 8/2 wins)
3 11/12/9 1 (wave 2/1 win) None
4 12/32/5 136 (wave 4/2 wins, wave 5/21 wins, wave 6/29, wave 7/19, wave 8/22, wave 9/15, wave 10/15 wins, wave 11/9 wins, wave 12/4 wins)  797 (wave 3/6 wins, wave 4/71 wins, wave 5/115 wins, wave 6/146 wins, wave 7/152 wins, wave 8/126 wins, wave 9/90 wins, wave 10/54, wave 11/26 wins, wave 12/9 wins, wave 13/2 wins)
5 12/44/6 2743 (wave 7/15 wins, wave 8/66 wins, ..., wave 27/1 win ) 54157 (wave 3/16 wins, wave 4/123 wins, ..., wave 26/2 wins)-more than 20 minutes in chrome to get these
6 7/10/8 1 (wave 4/1 win) 15 (wave 3/6 wins, wave 4/9 wins)
7 4/6/7 None 4 (wave 2/2 wins, wave 3/2 wins)
8 8/10/6 1 (wave 2/1 win) None
9 4/5/5 1 (wave 3/1 win) 2 (wave 3/2 wins)
10 5/8/5 1 (wave 4/1 win) 8 (wave 3/3 wins, wave 4/5 wins)
11 10/50/9 14 (wave 37/2 wins, wave 38/1 win, wave 39/3 wins, wave 40/3 wins, wave 41/4 wins, wave 42/1 win) 4561 (wave 3/39 wins, wave 4/99 wins, wave 5/134 wins, wave 6/136 wins, wave 7/136 wins, wave 8/136 wins, ..., wave 43/2 wins )
12 19/50/15 4408 (wave 8/4 wins, wave 9/23 wins, wave 10/75 wins, wave 11/156 wins, wave 12/257 wins, wave 13/364 wins, wave 14/448 wins, wave 15/488 wins, wave 16/482,...,wave 28/11 wins, wave 29/3 wins, wave 30/2 wins) 208689 (wave 3/104 wins, wave 4/546 wins, wave 5/1560 wins, wave 6/3420 wins, wave 7/6390 wins, wave 8/10326, wave 9/14686 wins, wave 10/18782 wins,...,wave 29/9 wins, wave 30/2 wins)-more than 5 hours in chrome to get these
13 10/50/10 None 97 (wave 2/1 win, wave 3/42 wins, wave 4/49 wins, wave 5/5 wins)
14 8/9/18 None 2 (wave 2/2 wins)
15 9/11/12 1 (wave 4/1 win) 5 (wave 3/5 wins)
16 5/37/5 None 18 (wave 2/1 win, wave 3/12 wins, wave 4/5 wins)
17 9/33/8 12 (wave 22/2 wins, wave 23/2 wins, wave 24/2 wins, wave 25/4 wins, wave 26/2 wins) 1825 (wave 3/32 wins, wave 4/76 wins, wave 5/101 wins, wave 6/101 wins, wave 7/101 wins, wave 8/101 wins, ..., wave 26/2 wins)
18 8/21/7 9 (wave 11/1 win, wave 12/1 win, wave 13/3 wins, wave 14/3 wins, wave 15/1 win) 558 (wave 3/26 wins, wave 4/57 wins, wave 5/73 wins, wave 6/73 wins, wave 8/65 wins, wave 9/58 wins, wave 10/46 wins, wave 11/37 wins, wave 12/25 wins, wave 13/15 wins, wave 14/8 wins, wave 15/2 wins)
19 12/13/50 None 2 (wave 2/2 wins)
20 7/31/5 65 (wave 13/4 wins, wave 14/4 wins, wave 15/6 wins, wave 16/6 wins, wave 17/6 wins, wave 18/6, wave 19/6 wins, wave 20/6 wins, wave 21/6 wins, wave 22/6 wins, wave 23/5 wins, wave 24/4 wins) 3228 (wave 3/16 wins, wave 4/40 wins, wave 5/69 wins, wave 6/103 wins, wave 8/171 wins, wave 9/205 wins, wave 10/239 wins, wave 11/268 wins, wave 12/287 wins, wave 13/291 wins, wave 14/276 wins, wave 15/252 wins, ..., wave 25/2 wins)
21 19/50/14 5457 (wave 7/6 wins, wave 8/45 wins, wave 9/134 wins, wave 10/269 wins, wave 11/426 wins, wave 12/570, wave 13/661 wins, wave 14/671 wins, wave 15/618 wins, wave 16/525 wins, wave 17/425 wins, ..., wave 30/1 win) 181537 (wave 3/93 wins, wave 4/542 wins, wave 5/1667 wins, wave 6/3870 wins, wave 7/7361 wins, wave 8/11905 wins, wave 9/16518 wins, wave 10/20271 wins, wave 11/22018 wins, wave 12/21557 wins, wave 13/19346 wins, wave 14/16095 wins, ..., wave 29/2 wins)-more than 3 hours in chrome to get these
22 20/50/18 678 (wave 12/2 wins, wave 13/3 wins, wave 14/9 wins, wave 15/19 wins, wave 16/32 wins, wave 17/45, wave 18/50 wins, wave 19/54 wins, wave 20/57 wins, wave 21/57 wins, wave 22/56 wins, ..., wave 30/2 wins) 88037 (wave 3/137 wins, wave 4/606 wins, wave 5/1310 wins, wave 6/2167 wins, wave 7/3140 wins, wave 8/4077 wins, wave 9/4962 wins, wave 10/5737 wins, wave 11/6359 wins, wave 12/6794 wins, wave 13/6960 wins, wave 14/6872 wins, ..., wave 32/2 wins)-more than 1 hour and a half in chrome to get these
23 3/30/1 26 (wave 15/2 wins, wave 16/2 wins, wave 17/2 wins, wave 18/2 wins, wave 19/2 wins, wave 20/2, wave 21/2 wins, wave 22/2 wins, wave 23/2 wins, wave 24/2 wins, wave 25/2 wins, wave 26/2 wins, wave 27/2 wins) 300 (wave 3/1 win, wave 4/3 wins, wave 5/5 wins, wave 6/7 wins, wave 7/9 wins, wave 8/11 wins, wave 9/13 wins, wave 10/15 wins, wave 11/17 wins, wave 12/19 wins, wave 13/21 wins, wave 14/23 wins, ..., wave 26/2 wins)
24 2/50/1 2 (wave 49/2 wins) 92 (wave 3 through wave 48 with 2 wins for each wave)
25 9/43/7139 (wave 17/1 win, wave 18/4 wins, wave 19/7 wins, wave 20/8 wins, wave 21 to 31/9 wins each, wave 32/8 wins, wave 33/7 wins, wave 34/4 wins, wave 35/1 win) 14706 (wave 3/27 wins, wave 4/77 wins, wave 5/136 wins, wave 6/209 wins, wave 7/282 wins, wave 8/355 wins, wave 9/428 wins, wave 10/501 wins, wave 11/ 574 wins, wave 12/647 wins,...,wave 35/2 wins)
26 10/43/8 177 (wave 16/1 win, wave 17/2 wins, wave 18/8 wins, wave 19/9 wins, wave 20/11 wins, wave 21-wave 30/12 wins each, wave 31/10 wins, wave 32/8 wins, wave 33/6 wins, wave 34/2 wins 18165 (wave 3/34 wins, wave 4/100 wins, wave 5/181 wins, wave 6/282 wins, wave 7/383 wins, wave 8/484 wins, wave 9/585 wins, wave 10/686 wins, wave 11/787 wins, wave 12/888 wins,...,wave 31/ 55 wins, wave 32/25 wins, wave 33/9 wins, wave 34/2 wins)

For tests 5, 12, 21 and 22 we had to run the program for quite a long time (the approximate time is indicated in green) to find out the number of castle wins. The larger that number, the longer the run time. Test 12 took more than 5 hours (in Chrome) to find out that there are 208689 different ways for the castle to win.
Other interesting facts:

In every case where there is no soldiers win (test 1,7,13,14,16, 19) the shortest wave win by the castle always takes 2 waves. If there is at least a soldiers' win, and there are castle wins, the smallest castle win always requires 3 waves.

There are nearly always more solutions where the castle wins than solutions where the soldiers win.