Difference between revisions of "Theory of ladder escapes"
(→Examples: Added another example of a 3rd row ladder escape.) |
(→Examples: Added another example of a 5th row ladder escape.) |
||
| Line 801: | Line 801: | ||
coords="hide" | coords="hide" | ||
contents="E +:a1 E +:a2 E +:a3 E +:a4 E +:a5 R b1 R b2 E *:c1 E *:d1 E *:d2" | contents="E +:a1 E +:a2 E +:a3 E +:a4 E +:a5 R b1 R b2 E *:c1 E *:d1 E *:d2" | ||
| + | /> | ||
| + | |||
| + | The following fifth row ladder escape also escapes 2nd row ladders at distance 2 or greater, 3rd row ladders at distance 0 or greater, and 4th row ladders at distance 2 or greater: | ||
| + | <hexboard size="6x5" | ||
| + | coords="hide" | ||
| + | contents="E *:a2 E *:a3 E *:a4 E *:a5 E *:a6 E +:b2 E +:b3 E +:b4 E +:b5 E +:b6 R c3 E *:e1" | ||
/> | /> | ||
Revision as of 00:08, 9 August 2020
The object of this page is to formalise precisely what it means for a pattern to be a ladder escape. To do this, we first formalise what it means to be a ladder.
Informally, a ladder escape (say, a 4th row ladder escape) is supposed to give the attacker a guarantee that their 4th row ladder will be able to connect to the edge, no matter how far away from the ladder escape the ladder starts. So strictly speaking, to check that a pattern is a 4th row ladder escape, we must check that the attacker can connect to the edge from an infinite set of positions. This raises the issue of how one can check in a finite time whether a given pattern is a 4th row ladder escape.
This issue is resolved on this page for 2nd, 3rd, 4th, and 5th row ladders. It might be possible to resolve it for 6th row ladders but this has not yet been done, partly because such ladders are of little practical use. For 7th row ladders we run into a new difficulty – Blue can simply ignore the ladder and play near the escape, because no appropriate 6th row edge template seems to be known which will connect an ignored 7th row ladder to the edge. This presents a theoretical obstruction which is currently unresolved. It may in theory be that there are no 7th row ladders at all.
For the purpose of our analysis, we assume that all ladders move from left to right along the red bottom edge, with Red being the attacker. Of course, the analogous analysis also applies to ladders moving in the opposite direction or along different edges.
The analysis of 2nd–4th row ladders on this page was originally contributed by the user Wccanard in 2016.
Contents
Second row ladders
Definition of ladder
There is no issue at all with defining a 2nd row ladder. Informally, a 2nd row ladder looks like this:
Note that at each point in the ladder, Blue's move is forced. Red can choose to continue pushing the ladder as long as she wants to. We formally define a second row ladder as follows:
Definition.. A second row ladder is a pattern like this:
L2:Here, the red stone is on the second row, and we call it the ladder stone. Red's goal is to connect the ladder stone to the bottom edge. The cell immediately below and to the right of the ladder stone is empty. We denote this pattern by L2.
Definition of ladder escape
Before we give the formal definition of a second row ladder escape, let us consider an example. The following pattern is an example of a second row ladder escape.
Of course directly underneath the pattern is the bottom (red) edge. The cells marked "+" indicate where the ladder connects. The reason this is a second row ladder escape is that however far away the ladder is,
Red can guarantee a connection from the ladder stone (marked 1) to the bottom edge. Note that the cells marked "*" can be of any color; but since the ladder escape must be valid regardless of the color of these cells, we may as well assume the worst case, i.e., all cells marked "*" can be thought of as blue stones.
Let us clarify what the hexes marked "+" in the ladder escape pattern mean. They indicate the last point where the 2nd row ladder is allowed to start. So for example, saying that the pattern above is a second row ladder escape means (among other things) that Red must win the following position:
Here, Red's ladder stone is marked "1", and the claim (easily verified) is that even with Blue to play, Red can connect the ladder stone to the bottom:
The reason that the pattern is a second row ladder escape is that this escape sequence works even if the ladder is a long way away:
Even here, Red can force a connection to the edge, even if it is Blue's move, because Blue must keep defending on the first row and Red keeps attacking on the second row,
and now we are back at the previous position with the ladder right next to the escape, where we have already seen that Red can break through to the edge. We can now give a more formal definition of a second row ladder escape.
Definition. A second row ladder escape template (or simply second row ladder escape) is given by the following data. It is a pattern, plus two hexes marked "+", such that one of the hexes marked "+" is on the first row, the other is on the second row up and directly to the left of the first one, and such that neither of the hexes marked "+", nor any hex to their left, are in the pattern. This data is subject to the following axiom: any position consisting of a second row ladder,
followed directly to the right by an arbitrary number (zero or more) of pairs of vacant hexes on the first and second rows,
followed by the second row ladder escape pattern (where the ladder slots into the escape by putting the ladder or rightmost column of vacant hexes onto the hexes marked "+") is an edge template, in the sense that even if it is Blue's turn to move, Red can guarantee a connection from the ladder stone marked 1 to the edge.
Terminology and notation: If we have a pattern with two cells marked "+" that is of the shape required for a second row ladder escape, but we are not sure whether it satisfies the axiom of a second row ladder escape, then we refer to it as a candidate for a second row ladder escape (or simply candidate if the rest is clear from the context). A candidate is valid if it is actually a ladder escape.
If P is a candidate for a second row ladder escape and n ≥ 0 is an integer, we write n+P for the result of shifting the cells marked "+" to the left by n positions, filling the gap with n columns of two empty hexes each. Similarly, we write L2+n for the result of appending n columns of two empty hexes to the right of a second row ladder L2. Finally, we write L2+n+P for a 2nd row ladder, followed by n columns of empty hexes, followed by an escape candidate P. We call this a "second row ladder at distance n". When n = 0, we sometimes just write L2+P. With this notation, we can rephrase the definition of a 2nd row ladder escape as follows: a candidate P is a 2nd row ladder escape if and only if L2+n+P is a template connecting the ladder stone to the edge, for all n ≥ 0.
We also define what it means for a ladder escape template to be minimal.
Definition. A 2nd row ladder escape template is minimal if the following two things are true. First, removing any hex from the pattern, or removing a red stone from the pattern (and replacing it with an empty hex) gives a new pattern which is not a 2nd row ladder escape template any more. And second, if the two hexes directly to the right of the two cells marked "+" are both vacant hexes in the pattern, then moving the cells marked "+" one hex to the right results in a new pattern which is not a 2nd row ladder escape.
Below, we will use analogous terminology and notations for ladders and ladder escapes on the 3rd and higher rows.
Characterization of ladder escapes
The definition of a 2nd row ladder escape allows the ladder to be an arbitrary distance away from the escape, which is of course what we want in practice; there is no reason that the escape should be right next to the ladder. However, this means that we cannot directly use the definition to check that something is a 2nd row ladder escape, because this would require checking that infinitely many patterns are edge templates. Can we find some finite criterion for checking 2nd row ladder escapes? Fortunately, as every Hex player knows, the answer is yes. We have the following theorem:
Theorem 1. Consider a candidate P for a 2nd row ladder escape. Schematically:
(Here the asterisks can indicate any stones at all.) Then P is a valid 2nd row ladder escape if and only if L2+P is an edge template for Red.
Proof. If the ladder escape is valid, then by definition, L2+n+P is an edge template for all n ≥ 0, and in particular for n = 0. This proves the left-to-right implication.
To go the other way we actually have to play some Hex, but it's pretty trivial. We must show that L2+n+P is an edge template for all n. This is an easy induction on n. For n = 0, the claim is true by assumption. If n > 0, then Blue must play directly below Red's ladder stone (or else Red will connect to the edge immediately), and now Red can play a ladder stone at distance n−1 on the second row, which is an edge template by induction hypothesis. □
Examples
We can use Theorem 1 to prove that all of the following patterns are minimal second row ladder escapes. Most of these templates are taken from David King's website, and there are several more there. Cells marked "*" are not part of the ladder escape template. For several of the templates, the corresponding pattern on David King's site is not minimal by our definition; for these templates, we have moved the cells marked "+" to the right to make the template minimal.
In the below templates, the stone marked 10 indicates a stone connected to the bottom edge, but the connection is not shown. The connection from 10 to the edge must not use any of the empty hexes in the pattern.
Third row ladders
Definition of ladder
There is a minor issue with defining 3rd and higher row ladders. We want a definition that is useful in practice and not too restrictive. For example, we surely want this to be a third row ladder:
even though there are a few blue stones on the first row. It is intuitively clear (and also provably true) that these blue stones cannot be of any help to Blue (they can never play a crucial role in any blue connection). So although we want a 3rd row ladder to have no stones on the first three rows to the right of the ladder (until we reach the escape), we do not want to also guarantee that there are no stones on the first row to the left of the ladder. We formally define third row ladders as follows.
Definition. A third row ladder is a pattern like this:
L3:The red stone is again called the ladder stone, and Red's goal is to connect the ladder stone to the bottom edge. The cells marked "*" are not part of the pattern, and may be of any color or even outside the board. These cells can be assumed to be blue, although this is not required. We denote this pattern by L3.
The key part of the definition is that we are guaranteeing the triangle of three empty hexes under the red ladder stone. This is a minimal requirement, because for example if one of these cells were filled,
then in reality the game could look like this,
and Blue can block the ladder with this move.
Definition of ladder escape
We have seen a lot of the formalism of ladder escapes in the above section on second row escapes. However there is a new twist with third row ladder escapes, because Blue can defend against a third row ladder in more than one way: Blue can at some stage decide to yield to the second row. The following definition is unsurprising.
Definition. A third row ladder escape is given by the following data. It consists of a pattern, and three hexes marked "+" (none of these hexes marked "+" are part of the pattern) going from the first to the third row, up and left as in the below picture, which is sitting on the bottom edge:
Here, the hexes marked "*" can be anything, they are just part of a general pattern, which could certainly go above the third row, and to the left above the hexes marked "+", and to the right, if necessary. The pattern must have the property that no hex directly to the left of any of the hexes marked "+" can be part of the pattern. To be a third row ladder escape, the pattern must satisfy the property that for all n ≥ 0, if we insert a third row ladder at distance n into the pattern at the three hexes marked "+", the resulting position is an edge template connecting the Red ladder stone to the bottom edge, with Blue to move. Or equivalently in symbols, it must satisfy that for all n ≥ 0, L3+n+P is an edge template connecting the ladder stone to the bottom edge.
Like for second row escapes, a pattern that has the required shape for a ladder escape, but it is not (yet) known to be a valid ladder escape, is called a candidate.
In pictures, for our pattern above (still marked with stars) to be a 3rd row ladder escape, it must give rise to an edge template when we attach a 3rd row ladder at distance 0,
or at distance 1,
or at distance 6,
or at any other distance.
Characterization of ladder escapes
Just like for second row ladder escapes, we again find ourselves in the situation that trying to use the definition to check that something is a 3rd row ladder escape involves checking that infinitely many positions are edge templates. Once again, we have a theorem that allows us to replace this by a finite condition.
Definition. If P is a candidate for a kth row ladder escape, then P′ denotes the candidate for a (k−1)st row ladder escape obtained by removing the topmost "+" from P. The cell that formerly contained the topmost "+" is not part of the pattern P′.
Theorem 2. Consider a candidate P for a 3rd row ladder escape. Assume that (a) L2+P′ is an edge template and (b) L3+P is an edge template, each such template connecting the ladder stone to the bottom edge. Then P is a valid third row ladder escape.
Proof. First note that by Theorem 1, because L2+P′ is an edge template, P′ escapes all 2nd row ladders. Now under the assumptions of the theorem, we must show that L3+n+P is an edge template for all n ≥ 0. We prove this by induction on n. For n = 0, the claim is true by assumption (b). Now suppose the claim is true for some n. To show the claim for n+1, consider the position L3+(n+1)+P. The first three columns of this position look like this:
(This is followed by n more columns of three empty hexes and by the pattern P). Blue has three possible moves in a triangle under stone 1, and Blue needs to play one of these or he will lose instantly. We analyze all three moves in turn.
For the first, Red pushes the ladder and will connect to the edge because by induction hypothesis, L3+n+P connects to the edge, so stone 3 connects to the edge, and so stone 1 does too.
For the second, Red just wins outright, i.e., we do not need to use the induction hypothesis.
And for the third, Red responds like this. Since stone 3 is a 2nd row ladder stone, it is connected to the edge because, as we noted above, P′ is a 2nd row ladder escape. Therefore stone 1 is also connected.
The induction is now complete, showing that P is a 3rd row ladder escape. □
Remark: in more concrete terms, Theorem 2 states that a pattern P is a 3rd row ladder escape if the pattern becomes an edge template (connecting the ladder stone to the edge) when we attach each of the following two patterns to it at the cells marked "+":
A:
B:
In contrast to the situation with 2nd row ladders, while Theorem 2 is sufficient to show that a position is a 3rd row ladder escape, it is not necessary. For example, consider the following third row ladder escape template P:
One can check directly that L3+2+P and L2+(2+P)′ are both edge templates, so that 2+P is a 3rd row ladder escape by Theorem 2. In particular, L3+n+P is an edge template for all n ≥ 2. Moreover, one can check that L3+P and L3+1+P are also edge templates, so that P is a valid 3rd row ladder escape.
It is, however, not a valid 2nd row ladder escape for ladders at distance 0, because in the position L2+P′,
the ladder stone marked "1" cannot connect to the edge.
Theorem 2 is therefore not sufficient to check that a given pattern is a 3rd row ladder escape. We need to work a little harder to get a necessary and sufficient condition for 3rd row ladder escapes.
Lemma 3 (2nd to 3rd row jump). Any 3rd row ladder escape also escapes 2nd row ladders that start at distance 2 or greater. More specifically, if L3+P is an edge template, then so is L2+(2+P)′.
The lemma is perhaps easier understood in pictures: given any 3rd row ladder escape, replacing the three cells marked "+"
by the pattern
yields a 2nd row ladder escape.
Proof. Assume L3+P is an edge template. We must show that L2+(2+P)′ is an edge template. It looks as follows, with P added to it:
But Blue must play 2, and Red can jump to 3. Then 3 is a 3rd row ladder stone, and is connected to the edge because L3+P is an edge template by assumption. Therefore, 1 is also connected.
□
We now finally get a necessary and sufficient condition for 3rd row ladder escapes in the following theorem.
Theorem 4. Consider a candidate P for a 3rd row ladder escape. Then P is a valid 3rd row ladder escape if and only if L3+P, L3+1+P, and L3+2+P are edge templates.
Proof. The left-to-right implication is trivial, since by definition, if P is valid then L3+n+P is an edge template for all n, including n = 0, 1, 2. For the opposite implication, assume that L3+P, L3+1+P, and L3+2+P are edge templates. By Lemma 3, L2+(2+P)′ is an edge template. By Theorem 2 and the assumption about L3+(2+P), 2+P is a 3rd row ladder escape. It follows that L3+n+P is an edge template for all n ≥ 2. Since we additionally assumed this to be the case for n = 0 and n = 1, P is a valid third row ladder escape. □
As a matter of fact, Theorem 4 is not tight. We can get the following better result. However, the proof of Theorem 4 generalizes more easily to 4th row and higher ladders, which is why it is of interest.
Theorem 5. Consider a candidate P for a 3rd row ladder escape. Then P is a valid 3rd row ladder escape if and only if L3+P and L3+1+P are edge templates.
Proof. The left-to-right implication is trivial. For the right-to-left implication, by Theorem 4, it suffices to show that L3+2+P is an edge template. Indeed, consider Blue's options in the position L3+2+P:
As usual, there are only two possible moves for Blue to avoid losing immediately. If Blue moves at 2, then Red can respond at 3, which connects to the edge because L3+1+P is an edge template by assumption.
If Blue instead moves at 2, then Red responds as follows, which connects to the edge because L3+P is an edge template by assumption.
□
Examples
Here are some examples of third row ladder escapes. Again most of these are taken from David King's website. For several of the ladder escape templates, the version shown on David King's website is not minimal by our definition; in these cases, we have moved the cells marked "+" to the right to make the template minimal. All of the templates in this section have been proven to be third row ladder escapes using Theorem 5. All of them are minimal. As before, a stone marked "10" is assumed to be connected to the bottom row, but the connection is not shown.
The following third row ladder escapes also escape 2nd row ladders at distance 0 or greater:
The following third row ladder escape also escapes 2nd row ladders at distance 1 or greater (but not at distance 0):
The following third row ladder escapes also escape 2nd row ladders at distance 2 or greater (but not at distance 0 or 1):
The version of this last pattern on David King's website has the cells marked "+" (he uses arrows) sloping in the other direction; the location that is shown here makes the template minimal.
The following is a rather strange example of a third row ladder escape:
All of the cells marked "*" (and especially those that appear to the left of the cells marked "+") are not part of the template. One of the reasons this example is strange is that if the ladder starts at distance 1 or greater, the pattern is no longer minimal. Since the ladder must come from the left, this template therefore does not come up in practice. Nevertheless, it satisfies our formal definition of a 3rd row ladder escape. This template also escapes 2nd row ladders at distance 2 or greater (but not at distance 0 or 1).
2nd row escapes from 3rd row escapes
One may ask whether all 3rd row ladder escapes are also 2nd row ladder escapes. To some extent, this is true: we have already seen in Lemma 3 that every 3rd row ladder escape is also a 2nd row ladder escape, provided that the 2nd row ladder starts at distance 2 or greater, and provided that there is enough room on the 3rd row – specifically, we require the topmost "+" of the 3rd row ladder escape, and the cell immediately to its left, to be empty.
While many 3rd row ladder escapes also happen to work for 2nd row ladders at distance 0 and 1, not all of them do. The examples above show that Lemma 3 is tight, in the sense that there exist some 3rd row ladder escapes that do not escape 2nd row ladders starting at distance 0 and/or 1.
Fourth row ladders
Definition of ladder
Definition. A fourth row ladder is a pattern like this:
L4:Again, the red stone is called the ladder stone and Red wants to connect the ladder stone to the bottom edge. The cells marked "*" are not part of the pattern and may be assumed to be blue. We denote this pattern by L4.
The key part of the definition is that the 6 hexes forming a triangle below the ladder stone are all vacant. Note that even filling in one of these can break the ladder: even if we fill in the bottom left corner of the triangle,
then Blue has this move,
which is easily seen to stop the ladder. To establish the ladder, Red needs at a minimum those 6 vacant hexes under her ladder stone.
Definition of ladder escape
The definition of a 4th row ladder escape is entirely analogous to that of 2nd and 3rd row ladder escapes.
Definition. A fourth row ladder escape is a pattern, plus four hexes marked "+" (not part of the pattern) going up and left from the first to the fourth row, such that there is no hex in the pattern to the left of any hex marked "+". This data must satisfy the following axiom: adding a 4th row ladder at distance n, for any n ≥ 0, connects the red ladder stone to the bottom edge, with Blue to move.
As before, a candidate is a pattern that has the correct shape, but is not (yet) known to be a valid escape.
Characterization of ladder escapes
We have already encountered all of the relevant ideas. If you have worked through the ideas in the second and third row escapes then this will be relatively easy, other than the actual Hex, which this time is quite fun!
Theorem 6. Consider a candidate P for a 4th row ladder escape. If L2+P′′, L3+P′, L4+P, and L4+1+P are valid edge templates, then P is a 4th row ladder escape.
Proof. The idea of the proof is the same as for 3rd row ladders. First observe that by Theorems 1 and 2, since L2+P′′ and L3+P′ are edge templates, P′ escapes all 3rd row ladders and P′′ escapes all 2nd row ladders. We must prove that L4+n+P is an edge template for all n ≥ 0. We proceed by induction on n. The base cases n = 0 and n = 1 hold by assumption. For the induction step, assume the claim is true for n ≥ 1. We need to prove the claim for n+1.
Consider the position L4+(n+1)+P. It looks like this, with n−1 additional columns of four vacant hexes and the pattern P attached on the right:
We need to prove that the ladder stone 1 is connected to the edge.
The five moves marked 2 below all lose instantly to Red 3:
The two moves marked 2 below also lose instantly:
The move marked 2 below can be answered by Red 3, moving us to position L4+n+P, which is an edge template by the induction hypothesis.
Move 2 below leads us to a 2nd row ladder, which P′′ escapes, so 5 (and therefore 1) is connected to the edge:
Both moves marked 2 below lead us to a 3rd row ladder, which P′ escapes, so 3 (and therefore 1) is connected to the edge:
Move 2 below also leads to a 3rd row ladder (note Blue 4 must be in the triangle left and below from Red 3; Blue can also play out the bridge between 1 and 3 but this doesn't help):
Move 2 below leads us to a 2nd row ladder:
The final choice for move 2 below also gives a 2nd row ladder.
This completes the induction, so P is a 4th row ladder escape. □
Remark: In more concrete terms, Theorem 6 states that P is a 4th row ladder escape if adding each of the following patterns to P gives an edge template.
A: B: C: D:Remark: Theorem 6 is analogous to Theorem 2. It gives a sufficient, but not a necessary condition for a candidate to be a 4th row ladder escape. Once again, the criterion in Theorem 6 can be checked in a finite amount of time. To get a theorem with a necessary and sufficient condition, we need another "jump lemma":
Lemma 7 (3rd to 4th row jump). Any 4th row ladder escape also escapes 3rd row ladders that start at distance 3 or greater. More specifically, if L4+P and L4+1+P are an edge templates, then so is L3+(3+P)′.
Proof. Consider the position L3+(3+P)′, which looks as follows, with P added to it:
There are only two possible moves for Blue that don't lose immediately. If Blue moves at 2, then Red can respond at 3, which is a 4th row ladder stone and connects to the edge because L4+1+P is an edge template by assumption.
In Blue moves instead at 2 in the following diagram, then Red can respond as shown.
Now Red's stone 9 is a 4th row ladder stone. Although the additional red stone 5 does not belong in the L4 template, this stone can only help Red. By assumpion, L4+P is an edge template, and so stone 9, and therefore stone 1, is connected to the edge. □
We then arrive at a necessary and sufficient condition for fourth row ladder escapes.
Theorem 8. Given a candiate P for a 4th row ladder escape. Then P is a valid 4rd row ladder escape if and only if L4+P, L4+1+P, L4+2+P, ..., L4+6+P are edge templates.
Proof. The proof is similar to that of Theorem 4. Again, the left-to-right implication is trivial. For the right-to-left implication, assume that L4+P, L4+1+P, L4+2+P, ..., L4+6+P are edge templates. By Lemma 7 applied to P and 2+P, we know that L3+(3+P)′ and L3+(5+P)′ are edge templates. By Lemma 3 applied to (3+P)′, we know that L2+(2+(3+P)′)′ is an edge template, and therefore also L2+(5+P)′′, which differs from L2+(2+(3+P)′)′ only in that it contains two additional empty hexes. Since L2+(5+P)′′, L3+(5+P)′, L4+(5+P), and L4+(6+P) are edge templates, we know by Theorem 6 that 5+P is a valid 4th row ladder escape. Therefore, L4+n+P is an edge template for all n ≥ 5. Since we assumed this to be also true for n = 0, 1, 2, 3, 4, it follows that P is a valid 4th row ladder escape. □
Remark: Like Theorem 4, it is likely that Theorem 8 is not tight, in the sense that there probably exists an even simpler condition that is necessary and sufficient for 4th row ladder escapes (perhaps analogous to Theorem 5). Also, in practice, Theorem 6 is often easier to check since it involves fewer conditions.
Examples
Here are some examples of fourth row ladder escapes. Most are taken from David King's website. In each case we have moved the column of "+"s as far as possible to the right to yield a minimal template. The validity of all of these escapes has been proved using Theorem 8.
The following fourth row ladder escape templates also escape 2nd and 3rd row ladders at distance 0 or greater:
The following fourth row ladder escape templates also escape 2nd row ladders at distance 1 and greater, as well as 3rd row ladders at distance 0 or greater.
Fifth row ladders
Definition of ladder
Definition. A fifth row ladder is a pattern like this:
L5:As usual, the red stone is called the ladder stone and Red's goal is to connect it to the bottom edge. The cells marked "*" are not part of the pattern. We denote this pattern by L5.
Unlike in the case of 2nd, 3rd, and 4th row ladders, this time it is not sufficient for a triangle of cells below and to the right of the ladder stone to be empty. We also need three additional empty cells to the left of this triangle. This is a minimal requirement; if even one of these cells is occupied by Blue, for example like this:
then Blue can block the ladder with this move:
The main line is complex; see for example this Little Golem discussion thread. Therefore, to establish the ladder, Red needs at minimum the specified 13 vacant hexes under the ladder stone.
Definition of ladder escape
The definition of a 5th row ladder escape is as expected.
Definition. A fifth row ladder escape is a pattern, plus five hexes marked "+" (not part of the pattern) going up and left from the first to the fifth row, such that there is no hex in the pattern to the left of any hex marked "+". This data must satisfy the following axiom: adding a 5th row ladder at any distance n ≥ 0 connects the red ladder stone to the bottom edge, with Blue to move. As usual, a candiate is such a pattern that satisfies everything except perhaps the axiom.
Characterization of ladder escapes
Theorem 9. Consider a candiate P for a fifth row ladder escape. Assume L5+P, L5+1+P, L5+2+P, L4+P′, L4+(1+P)′, L3+P′′, and L2+P′′′ are all edge templates. Then P is a 5th row ladder escape.
Proof. The proof idea is the same as for 3rd and 4th row ladders, but there are a lot more cases to consider. First, note that by previous theorems, P′ escapes all 4th row ladders, P′′ escapes all 3rd row ladders, and P′′′ escapes all 2nd row ladders. We prove by induction on n that L5+n+P is an edge template for all n ≥ 0. The base cases n = 0, 1, 2 are true by assumption. For the induction step, assume the claim is true for n ≥ 2. We need to prove the claim for n+1.
Consider the position L5+(n+1)+P, which looks like this (followed by an additional n−2 columns of five empty hexes and the pattern P):
The eight moves marked 2 below all lose instantly to Red 3 by edge template IV-1-a:
The three moves marked 2 below also lose instantly by edge template IV-1-a:
The six moves marked 2 below give a 4th row ladder, which P′ escapes.
This leaves us with 11 more moves to consider. If Blue pushes the ladder by making the move marked 2 below, Red can answer 3, moving us to position L5+n+P, which is an edge template by the induction hypothesis.
Move 2 below gives a 3rd row ladder, which P′′ escapes.
If Blue plays move 2 below, Red can answer 3, forcing Blue to respond in the ziggurat below and to the left of stone 3. If Blue plays in any of the cells marked 4, Red plays 5 and gets a 4th row ladder, which P′ escapes. Blue could have also first intruded upon the bridge between 1 and 3, but this does not help. From now on, we tacitly ignore bridge intrusions that are not helpful to Blue.
If, on the other hand, Blue plays 4 below, then Red gets a 2nd row ladder, which P′′′ escapes.
If Blue plays move 2 below, Red gets a 2nd row ladder, which P′′′ escapes.
If Blue plays move 2 below, Red can answer 3, forcing Blue to respond in one of the hexes marked 4. Then Red can play 5 and gets a 3rd row ladder, which P′′ escapes.
Similarly, if Blue plays move 2 below, Red can answer 3, forcing Blue to respond in one of the hexes marked 4. Then Red can play 5 and gets a 3rd row ladder, which P′′ escapes.
If Blue plays move 2 below, Red can answer 3. There are only four hexes where Blue can respond without losing outright. If Blue moves in one of the three hexes marked 4, then Red gets a 3rd row ladder, which P′′ escapes.
If Blue instead moves in the hex marked 4 below, then the sequence plays out slightly differently, but Red still gets a 3rd row ladder.
If Blue plays move 2 below, Red can answer 3. Then Blue must respond in any of the hexes marked "+", or else Blue will immediately lose to edge template III1b or a ziggurat.
If Blue responds in one of the two hexes marked 4, Red gets a 3rd row ladder.
If Blue instead responds with move 4 below, Red gets a 2nd row ladder.
If Blue instead responds with move 4 below, Red still gets a 2nd row ladder.
If Blue plays move 2 below, Red can answer 3. Then Blue must respond in one of the hexes marked "+" to avoid immediately losing to edge template III1b.
If Blue responds in one of the hexes marked 4 below, Red gets a 3rd row ladder.
If Blue instead responds in one of the hexes marked 4 below, Red gets a 2nd row ladder.
If Blue instead responds at 4, Red gets a 3rd row ladder.
If Blue instead responds at 4, Red gets a 2nd row ladder.
If Blue instead responds at 4, Red gets a 2nd row ladder.
If Blue plays move 2 below, Red can answer 3. Then Blue must respond in one of the hexes marked "+" to avoid immediately losing to edge template III1b or a bridge.
If Blue responds in one of the hexes marked 4 below, Red gets a 2nd row ladder.
If Blue instead responds at 4 below, Red also gets a 2nd row ladder.
Finally, if Blue plays move 2 below, Red gets a 2nd row ladder.
This completes the induction, so P is a 5th row ladder escape. □
Remark: In more concrete terms, Theorem 9 states that P is a 5th row ladder escape if adding each of the following patterns to P gives an edge template.
A: B: C: D: E: F: G:Like Theorems 2 and 5, Theorem 9 gives a sufficient, but not necessary condition for 5th row ladder escapes. We do not currently have a necessary and sufficient condition. One problem is that is it not clear if there is an appropriate "jump lemma" from 4th to 5th row ladders. We do have the following generalization of Theorem 9, which gives a weaker sufficient condition (it is likely also necessary, but this has not been shown):
Theorem 10. Given a candiate P for a 5th row ladder escape. If there is some n ≥ 0 such that L5+P, L5+1+P, ..., L5+n+P, L5+(n+1)+P, L5+(n+2)+P, as well as L4+(n+P)′, L4+((n+1)+P)′, L3+(n+P)′′ and L2+(n+P)′′′, are edge templates, then P is a valid 5th row ladder escape.
Proof. This follows directly from Theorem 9 applied to n+P. □
Examples
Here are some examples of fifth row ladder escapes. The validity of these escapes has been proved using Theorem 10. These escapes are minimal.
The following fifth row ladder escapes also escape 2nd–4th row ladders at distance 0 or greater:
The following fifth row ladder escape also escapes 2nd row ladders at distance 2 or greater, 3rd row ladders at distance 0 or greater, and 4th row ladders at distance 1 or greater:
The following fifth row ladder escape also escapes 2nd row ladders at distance 2 or greater, 3rd row ladders at distance 0 or greater, and 4th row ladders at distance 2 or greater:
Sixth row ladders and up
It is currently unknown how much space must be guaranteed under the ladder stone to form a 6th row ladder, or if a viable notion of 6th row ladders exist at all. For 7th row ladders the situation is even worse. As explained in open problems about edge templates, no amount of space under the ladder (even if we demand that the entire 5th row is clear) is known to guarantee a red connection if Blue just ignores the ladder and plays elsewhere. Thus, it is possible that 6th and 7th row ladders do not even exist in theory. Of course they do not occur in practice either.
To push the theory of ladder escapes to the 6th row and beyond, one first needs to come up with a rigorous definition of a ladder (the issue being how much space one needs under the ladder stone to stop blue from cutting off the ladder immediately). Once this is done one needs to come up with a finite list of hypotheses to guarantee that something is a ladder, analogous to, say Theorems 1, 2, and 6 above. This may not be as easy as it looks.
