Difference between revisions of "Theory of ladder escapes"

Revision as of 04:17, 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.

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 piece is on the second row, and we assume it is connected to the (invisible) top edge. The cell immediately below and to the right of the red piece 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 pieces.

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 we regard stone 1 as connected to the top, and the claim (easily verified) is that even with blue to play, red can connect to the bottom:

The reason that the pattern is a second stone 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. A pattern

(where here the asterisks can indicate any pieces 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 piece (or else Red will connect to the edge immediately), and now Red can playing a ladder piece at distance n−1 on the second row, which is an edge template by induction hypothesis. □

Examples

We can use the above theorem 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; the cells marked "+" have been moved.

Note that the corresponding pattern on David King's site is not minimal; 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 pieces on the first row. It is intuitively clear (and also provably true) that these blue pieces 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 cells marked "*" are not part of the pattern, and may be of any color or even outside the board. The lower one of these cells is usually occupied by a blue piece (because otherwise Red could do something better than a 3rd row ladder), but we do not require this as part of the definition. The red piece is assumed to be connected to the top.

The key part of the definition is that we are guaranteeing the triangle of three empty hexes under the red piece. This is a minimal requirement, because for example if one of these pieces 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 piece 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 piece 3 is connected to the edge, and hence piece 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 piece 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 piece 3 connects to the edge, and so piece 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 piece 5 connects to the edge, and therefore piece 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 piece cannot connect to the edge or to the 10 pieces. 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 piece 3 is connected to the edge, and therefore piece 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 piece connected to the bottom row.

This latter pattern above – a single stone on the second row – is Wccanard's favourite, because the above theorem 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 plus 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 cells marked "*" are not part of the pattern, and the red piece is assumed to be connected to the top.

The key part of the definition is that the 6 hexes forming a triangle below the laddering piece 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. If adding each of the following patterns to a pattern P gives an edge template:

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 all numbers up to 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 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: again we have given a criterion which can be checked in a finite time. Once again, the criterion is necessary but not sufficient.

Fifth row ladders and up

From the above definitions of 2nd, 3rd, and 4th row ladders, one may guess that the definition of a 5th row ladder is a pattern of this form:

However, this definition does not work, because it turns out that if it is Blue's turn in the diagram below,

then Blue can block the ladder with this move.

The main line is complex; see for example this Little Golem discussion thread. The conclusion from this is that Red needs more space in order to ensure that the ladder is established. It is not currently known what the minimal required amount of space is, or even if there is a natural answer to this question. It is theoretically possible that there is more than one kind of 5th row ladder.

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.