Difference between revisions of "Theory of ladder escapes"
m (minor formatting) |
(→Characterization of ladder escapes: Added one more case.) |
||
| Line 635: | Line 635: | ||
coords="hide" | coords="hide" | ||
contents="E *:a1 E *:b1 E *:c1 E *:d1 R 1:e1 E *:a2 E *:b2 E *:c2 E *:d2 E *:a3 E *:b3 E *:a4 B 2:e2 R 2:f1" | contents="E *:a1 E *:b1 E *:c1 E *:d1 R 1:e1 E *:a2 E *:b2 E *:c2 E *:d2 E *:a3 E *:b3 E *:a4 B 2:e2 R 2:f1" | ||
| + | /> | ||
| + | Move 2 below leads us to the following sequence of moves. After Red 5, Blue can either push the 3rd row ladder or yield to the 2nd row; depending on Blue's choice, we end up in position F+(''n''+1)+P or G+(''n''+1)+P, both of which we have already dealt with. | ||
| + | <hexboard size="5x8" | ||
| + | coords="hide" | ||
| + | contents="E *:a1 E *:b1 E *:c1 E *:d1 R 1:e1 E *:a2 E *:b2 E *:c2 E *:d2 E *:a3 E *:b3 E *:a4 B 2:f2 R 3:e2 B 4:d4 R 5:e3" | ||
/> | /> | ||
Revision as of 17:44, 8 July 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 and 4th row ladders. It might be possible to resolve it for 5th and 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:
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.
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 (or second row ladder escape template) 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 directly 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.
Notation: let's say that our 2nd row ladder pattern followed by n (an integer ≥ 0) pairs of vacant hexes is called a "second row ladder at distance n". What we are demanding of our second row ladder escape is that it becomes an edge template when we slot in a second row ladder at distance n, for all values of 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 again is not a 2nd row ladder escape.
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 know, the answer is yes. We have the following theorem:
Theorem 1. A pattern
(where here the asterisks can indicate any stones at all) is a second row ladder escape if and only if replacing the hexes marked "+" with a second row ladder at distance zero is an edge template for Red.
Proof. If the pattern is a second row ladder escape then by definition, replacing the cells marked "+" with a second row ladder at distance zero gives an edge template (indeed a second row ladder escape means that this position and infinitely many other positions are an edge template). This proves the right-to-left implication.
To go the other way we actually have to play some Hex, but it's pretty trivial. Say the pattern becomes an edge template if we insert a second row ladder at distance zero. We now have to prove that the pattern becomes an edge template if we insert a second row ladder at distance n for all n. This is an easy induction on n, because Blue must play directly below Red's ladder stone (or else Red will connect to the edge immediately), and now Red can playing 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. All 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.
Note that the corresponding pattern on David King's site is not minimal by our definition; the cells marked "+" have been moved.
Note that the corresponding pattern on David King's site is not minimal by our definition; the cells marked "+" have been moved.
Here and below the 10 indicates a stone connected to the bottom edge, but the connection is not shown.
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:
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.
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 is 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 data must have the property that no hex directly to the left of any of the hexes marked "+" can be part of the pattern. And the data is subject to the axiom 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.
In pictures, our pattern above (still marked with stars), if it is a 3rd row ladder escape, 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.
Theorem 2. Given a pattern with three hexes marked "+" of the shape required for third row ladder escapes. Assume the pattern becomes an edge template (connecting the ladder stone numbered 1 to the edge) when we attach each of the following two patterns to it at the cells marked "+":
A:
B:
Then the pattern is a third row ladder escape.
Proof. Let us call the above patterns A and B (so that A is a 3rd row ladder and B is a 2nd row ladder with an empty space on top). For any integer n ≥ 0, let us write A+n to denote the position A at distance n, that is, A followed by n columns of three empty hexes. Similarly, let us write B+n to denote position B followed by n columns of three empty hexes. We claim that, if inserting A and B both result in edge templates, then inserting A+n and B+n result in edge templates for all n. The proof is by induction on n. The case n=0 is true by assumption. Now assume we have established the claim for some n ≥ 0, i.e., we know that A+n+pattern and B+n+pattern are both edge templates. We wish to prove the claim for n+1. Let us first consider the leftmost two columns in position B+(n+1):
(and imagine that this goes on to connect to the pattern). It is Blue's move, and Blue only has one move that does not lose instantly. If Blue plays this move then Red can reply as follows:
Now by the induction hypothesis, position B+n is an edge template. This implies that stone 3 is connected to the edge, and hence stone 1 is too. So B+(n+1) is also an edge template.
For position A+(n+1) we need to work a little more. The position we need to consider is this — the first three columns of position A+(n+1)
(and imagine that it goes on to connect to the pattern). This time, 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, A+n 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, the following sequence is forced for Blue. Then Red is connected because by the induction hypothesis, B+n connects to the edge, which means that stone 5 connects to the edge, and therefore stone 1 does too.
The induction is complete, and in particular we can conclude that A+n+pattern connects to the edge for all n. So in particular, the pattern is a 3rd row ladder escape. □
In contrast to the situation with 2nd row ladders, Theorem 2 is sufficient to show that a position is a 3rd row ladder escape, but it is not necessary. For example, here is a somewhat strange 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 can check directly, using notation as in the theorem, that if P is this pattern then A+1+P and B+1+P are both edge templates, so the induction kicks in from there. Furthermore A+P is also an edge template, and therefore the pattern is a valid 3rd row ladder escape. On the other hand, in the position B+P,
the 1 stone cannot connect to the edge or to the 10 stones. Theorem 2 is hence not sufficient to check that a given pattern is a 3rd row ladder escape. We therefore need to work a little harder to get a necessary and sufficient condition for when a pattern is a 3rd row ladder escape.
Theorem 3. Suppose for some n ≥ 0, the position A+n+P is an edge template. Then B+(n+2)+P is an edge template.
Proof. In the position B+(n+2), Blue must defend the ladder with move 2, and Red jumps to 3:
By hypothesis, A+n+P connects to the edge, so stone 3 is connected to the edge, and therefore stone 1 is also connected to the edge. □
Theorem 4. Given a pattern P with three hexes marked "+" of the shape required for third row ladder escapes. Then P is a valid third row ladder escape if and only if A+P, A+1+P, and A+2+P are edge templates.
Proof. The left-to-right implication is trivial, since by definition, P is a valid ladder escape if and only if A+n+P is an edge template for all n, including n = 0, 1, 2. For the opposite implication, assume that A+P, A+1+P, and A+2+P are edge templates. By Theorem 3, B+2+P is an edge template. Therefore, the induction from the proof of Theorem 2 kicks in at n=2. It follows that A+n+P and B+n+P are edge templates for all n ≥ 2, and in particular, A+n+P is an edge template for all n ≥ 0. Therefore P is a third row ladder escape. □
Examples
Here are some examples of third row ladder escapes. Again these are all 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.
Here and below, the 10 indicates a stone connected to the bottom row.
This latter pattern above – a single stone on the second row – is Wccanard's favourite, because the Theorem 4 can be used to show that it is a 3rd row ladder escape even though the template is so small.
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.
All of the templates above have been proved to be third row ladder escapes using Theorem 4. All of them are minimal.
2nd row escapes from 3rd row escapes
One may ask whether all 3rd row ladder escapes are also 2nd row ladder escapes. Specifically, given a 3rd row ladder escape template with its three cells marked "+", is it the case that removing the top "+" gives a second row ladder escape? In general, the answer is no. The simplest counterexample is the following:
In words, this is a stone on the 4th row connected to the bottom edge. A perhaps clearer way of thinking about it is this:
A stone on the 4th row, connected to the bottom edge, is a 3rd row ladder escape, because Red just ladders over to it on either the 2nd or 3rd row and then leaps up to connect to it. However removing the top "+" gives us a pattern that is not a second row ladder escape, because for a second row ladder, Blue is allowed to completely occupy the third row (the third row is not part of the escape),
and Red cannot connect.
Instead, one could ask a weaker question: what if we have a third row ladder escape, and we replace the top "+" sign with an empty hex considered as part of the pattern? Is this always a 2nd row ladder escape? Again the answer is no, and the strange example after Theorem 2 above (with A+n+P an edge template for all n ≥ 0 and B+n+P an edge template for all n ≥ 1, but not B+P) is a counterexample. So a third row ladder escape template is not always a second row ladder escape template!
However, if the second row ladder starts far enough from the template, it is. We have the following theorem:
Theorem 5. Any 3rd row ladder escape also escapes 2nd row ladders that start at distance 2 or greater. More precisely, given any 3rd row ladder escape, replacing the three cells marked "+"
by the pattern
yields a 2nd row ladder escape.
Proof. This is essentially the same as the proof of Theorem 3. By Theorem 1, to prove that it is a 2nd row ladder escape, it is sufficient to prove that the following, with P added to it, is a template:
By Blue must play 2, and Red can jump to 3, using the 3rd row escape:
□
Fourth row ladders
Definition of ladder
Definition. A fourth row ladder is a pattern like this:
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.
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 red 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.
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. If adding each of the following patterns to a pattern P gives an edge template:
A: B: C: D:then P is a 4th row ladder escape.
Remark: Note that position B is A+1, and that it's crucial that we use A+1 rather than A in this argument; this is a new phenomenon which appears for 4th row ladders.
Proof. The idea of the proof is the same as for 3rd row ladders. We prove simultaneously that all of A+n+P and B+n+P and C+n+P and D+n+P are edge templates, by induction on n. The base case n=0 is our assumption. For the induction step, we need to play a little Hex. So assume the claim is true for n. We need to prove the claim for n+1.
The A case is easiest: A+(n+1)+P equals B+n+P, so we're done by our induction hypothesis.
The second easiest case is case D:
Remember what we are doing – these are the first two columns of position D at distance (n+1) from the pattern. From D+(n+1), Blue must defend under the red ladder, and then Red can play to the above position; we know by the induction hypothesis that D+n is an edge template, and hence D+(n+1) is too.
We next deal with the position C+(n+1). First note that there are only two moves which do not lose instantly for Blue. We now deal with these two moves in turn. This one
leads to C+n, and this
leads to D+n. In either case we are done by the induction hypothesis.
The B case is the most fun. We consider the following position B+(n+1):
Imagine that this, possibly after some columns of four vacant hexes, attaches to our pattern. 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 B+n+P, which is an edge template by the induction hypothesis.
Move 2 below leads us to D+n:
Move 2 below leads us to C+(n+1), which we have already dealt with.
Move 2 below leads us to C+n (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 C+n:
Move 2 below leads us to D+n:
The final choice for move 2 below also leads us to D+n.
This completes the analysis for B and hence for all four patterns.
So the induction is finished. In particular, A+n+P is an edge template for all n, meaning that P is a 4th row ladder escape. □
Remark: Theorem 6 is analogous to Theorem 2. It gives a sufficient, but not a necessary condition for something to be a 4th row ladder escape. Once again, the criterion in Theorem 6 can be checked in a finite amount of time. Unlike the case for 3rd row ladder escapes, we do not currently have a theorem with a necessary and sufficient condition. However, we have the following, which gives a weaker sufficient condition (it is likely to also be necessary, but we have not proved this):
Theorem 7. Given a pattern P with four hexes marked "+" of the shape required for 4th row ladder escapes. If there is some n ≥ 0 such that A+n+P, B+n+P, C+n+P, and D+n+P are edge templates, and such that A+P, A+1+P, ..., A+(n-1)+P are edge templates, then P is a valid 4th row ladder escape.
Proof. The proof is essentially the same as for Theorem 6, with the induction kicking in at n rather than 0. □
Examples
Here are some examples of third row ladder escapes, 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 6.
Fifth row ladders
Definition of ladder
Definition. A fifth row ladder is a pattern like this:
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.
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.
Characterization of ladder escapes
Conjecture. Consider a pattern P, with five cells marked "+", of the shape required for 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:then P is a 5th row ladder escape.
Remark: B, C, and E are A+1, A+2, and D+1, respectively; as in Theorem 6, these are needed to make the induction go through.
Proof. The proof idea is the same as for 3rd and 4th row ladders, but there are a lot more cases to consider. We prove by simultaneous induction on n that all of A+n+P, ..., F+n+P are edge templates. The base case n=0 is our assumption. For the induction step, assume the claim is true for n. We need to prove the claim for n+1.
The A, B, and D cases are easiest: A+(n+1)+P equals B+n+P, B+(n+1)+P equals C+n+P, and D+(n+1)+P equals E+n+P, so in each case we are done by induction hypothesis.
The cases for E, F, and G are almost identical to those in the proof of Theorem 6, which is not surprising since they are effectively ladders of height 4 and less (except with an additional empty hex above the ladder stone). So the only remaining case is C. Consider the position C+(n+1)+P, which looks like this (followed by an additional n 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 lead us to E+(n+1), which we have already dealt with.
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 C+n+P, which is an edge template by the induction hypothesis.
Move 2 below leads us to the following sequence of moves. After Red 5, Blue can either push the 3rd row ladder or yield to the 2nd row; depending on Blue's choice, we end up in position F+(n+1)+P or G+(n+1)+P, both of which we have already dealt with.
Sixth row ladders and up
A similar issue arises with 6th row ladders. It is currently unknown how much space must be guaranteed under the ladder stone to form a 6th row ladder, of if this is even possible at all. And 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 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 5th and 6th row, 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 templates analogous to, say, A to D in the 4th row argument above. This may not be as easy as it looks. For example B above is A plus one extra row, and when I tried to prove the result initially I only had A, C and D, and I could not get the argument to work; the extra space was essential. More issues of this nature surely await anyone who tries to extend these results to 5th row ladders or higher. Because I am not sure that 5th row ladder escapes really ever come up in practice, I am not particularly motivated to pursue this.
