Difference between revisions of "Theory of ladder escapes"

Revision as of 01:33, 7 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

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 to be the a pattern like this, with Blue to move:

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.

Second row ladder escapes

I have only formulated the definition of an n'th row ladder for 2<=n<=4 above. Let me start this discussion of ladder escapes with a discussion of 2nd row ladder escapes, because here we can see the main points without any of the technicalities about how much space one is supposed to allow under a ladder -- there is no space under the ladder.

Let me start with an example. An example of a second row ladder escape is the following pattern.

Of course directly underneath the pattern is the bottom (red) edge. The pluses 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 I have replaced asterisks with blue stones -- any hex not in the pattern or the ladder can be thought of as a blue stone, as red is not allowed to move there.

Let me clarify what the plussed hexes 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 (amongst 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.

Now we can guess the general definition. Before I start I should say that for simplicity I won't allow mirror images and all 2nd row ladders should be thought of as moving right and approaching the escape from the left. A second row ladder escape is the following data. It is a pattern, plus two hexes with plusses in them, such that one of the plussed hexes is on the first row, the other is on the second row up and directly to the left of the first hex, and such that neither of the plussed hexes nor any hex directly to the left of either of the plussed hexes are in the pattern. This data is subject to the following axiom: any position comprising of a second row ladder

followed directly to the right by as many pairs of vacant hexes as you like 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 onto the plussed hexes) is an edge template, in the sense that even if it is blue 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 template is that it becomes an edge template when you slot in a second row ladder at distance n, for all values of n>=0.

This is an interesting definition because it 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 to check that something is a 2nd row ladder escape we need to check that *infinitely many* patterns are edge templates. How can we do this? Well of course as every Hex player knows,

Lemma: a pattern

(where here the asterisks can indicate any pieces at all) is a second row ladder escape if, and only if, replacing the plussed hexes 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 plusses with a second row distance zero ladder right next to the escape gives an edge template (indeed a second row ladder escape means that this position and infinitely many other positions are an edge template). So this finishes the implication in one direction.

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, and this is an easy induction on n, because blue must play directly below red's ladder piece and now red can continue playing the ladder on the second row, and by induction this is an edge template.

QED

Examples

Definition: A 2nd row ladder escape template is minimal if the following two things are true. Firstly, 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 secondly, if the two hexes directly to the right of the two plussed stones are both vacant hexes in the pattern, then moving the plussed hexes one hex to the right results in a new pattern which again is not a 2nd row ladder escape.

Corollary (cf. David King's website): the following positions are minimal second row ladder escapes:

(note that the corresponding pattern on David King's site is not minimal; I have moved the plusses)

(note that the corresponding pattern on David King's site is not minimal; I have moved the plusses)

(here and below the 10 indicates a stone connected to the bottom edge, but the connection is not shown)

and so on and so on (these templates are all taken from David King's site, and there are several more there).

Third row ladders

Definition

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 a third row ladder to be a pattern like this, with Blue to move:

The cell marked "*" is not part of the pattern, and may be of any color or even outside the board. 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.

Third row ladder escapes

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 drop to the second row.

The following definition is unsurprising: A third row ladder escape is the following data: it is a pattern, and three plussed hexes (none of these plussed hexes 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 row of a Hex board:

(here the starred hexes can be anything, they are just part of a general pattern, which could certainly go above the third row if necessary). The data must have the property that no hex directly to the left of any of the plussed hexes can be part of the pattern. And the data is subject to the axiom that for any n>=0, if you insert a third row ladder at distance n onto the pattern at the three plussed hexes, the resulting position is an edge template connecting the ladder stone to the bottom edge.

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 template at distance 0

or at distance 1

or at distance 6

or at any distance you like.

Now here is the interesting question. Again we find ourselves in the situation that trying to check that something is a 3rd row ladder escape template involves checking that infinitely many positions are edge templates. How do we get round to this?

Proposition: If we have a pattern plus three plussed hexes with nothing to the left of the plusses, and if 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 plusses:

and

then the pattern is a third row ladder escape.

Proof: Call the positions above A and B (so A is a 3rd row ladder and B is a second row ladder with an empty space on top). If n>=0 is an integer then by A+n I mean the position A at a distance n, that is, A followed by n columns of three empty hexes. Similarly by B+n I mean position B followed by n columns of three empty hexes. I claim 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. By assumption it is true for n=0. Say we have established it for n=m>=0 (that is, we know that A+m+pattern and B+m+pattern are both edge templates) and we want to establish these facts for A+(m+1) and B+(m+1). Let us first consider the left most two columns in position B+(m+1):

(and imagine that this goes on to connect to the pattern). It is blue's move and blue only has one move which does not lose instantly. If blue plays this move then red can reply thus:

Now by our inductive hypothesis, position B+m is an edge template. This implies that piece 3 is connected to the edge, and hence piece 1 is too. So B+(m+1) is also an edge template.

For position A+(m+1) we need to work a little more. The position we need to consider is this -- the first three columns of position A+(m+1)

(and imagine that it goes on to connect to the pattern). This time blue has three moves in a triangle under piece 1 and blue needs to play one of them or blue will lose instantly. We analyse all three in turn:

For the first

red will connect to the edge because by induction A+m connects to the edge, so piece three connects to the edge, 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 this sequence is forced for blue:

and red is connected because by the inductive hypothesis B+m connects to the edge, which means that piece 5 connects to the edge, so 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.

QED

Examples

I want to make some remarks about this argument, but first here are some examples of third row ladder escapes; in each case one can prove that the pattern is an escape using the proposition above. Again these are all taken from David King's website.

[the 10 in the above template indicates a piece connected to the bottom row; note that I have moved the plusses one hex to the right from the version on David King's website, which is not minimal].

[again the 10 indicates a piece connected to the bottom row]

[this latter pattern above -- a single stone on the second row -- is my favourite, because the proposition in this section can be used to show that it is a 3rd row ladder escape even though the template is so small.

[note that the version of the above pattern on David King's website is not minimal; I have moved the plusses one hex to the right]

[note that the version of the above pattern on David King's website has the plusses (he uses arrows) sloping in the other direction; the location that I have put them makes the template minimal].

All of the patterns above can be proved to be third row ladder escapes using the proposition above, and I think they're all minimal.

However there are also some cautionary remarks to be made about 3rd row ladder escapes.

Firstly, in contrast to the situation with second row ladders, the proposition in this section is sufficient to show that a position is a third row ladder but it is not necessary. For example, here is a third row ladder escape:

It's a bit of a weird one, but one can check directly that (using notation as in the theorem) 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. However B+P is the position

and the 1 piece (connected to the top) cannot connect to the bottom or the 10 pieces. Our proposition is hence not sufficient to check that a given pattern is a 3rd row ladder escape. A weaker version of the proposition would however suffice: if P is a pattern and there exists some N>=0 such that B+N+P and all of A+N+P, A+(N-1)+P, A+(N-2)+P, ..., A+1+P, A+P are edge templates, then P is a 3rd row ladder escape pattern. This modified proposition is necessary and sufficient (because the attacker can choose to move up a row if they are laddering on the 2nd row).

My second remark is that despite all this, a 3rd row escape is not in general a 2nd row escape. More formally, if P (with its three plusses) is a third row ladder escape template, it may not be the case that removing the top plus gives us a second row ladder template. 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.

An even weaker question one could ask: what if we have a third row ladder escape, and we replace the top plus sign with an empty hex considered as part of the pattern? Is this always a 2nd row template? Again the answer is no and the weird example above (with A+n+P an edge template and B+n+P for all n>=1 an edge template, but not B+P) is a counterexample.

Conclusion: a third row ladder escape template is not always a second row ladder escape template!

Fourth row ladders

Definition

We define a fourth row ladder to be a pattern like this, with Blue to move:

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 triangle with 6 hexes below the laddering piece is 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.

Fourth row ladder escapes

We have seen all the ideas now. 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!

A fourth row ladder escape is the following data. It is a pattern, plus four plussed hexes (not part of the pattern) going up and left from the first to the 4th row, such that there is no hex in the pattern to the left of any plussed hex. This data has to satisfy the following axiom: adding the pattern to a 4th row ladder (which I carefully defined above) at distance n, for any n>=0, gives an edge template.

Proposition: If adding each of the following patterns to a pattern P gives an edge template:

then P is a 4th row ladder escape.

Remark: again we have given a criterion which can be checked in a finite time.

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: again the same idea. 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 case n=0 is our assumption. We need to play a little Hex to get our induction going.

The A case is easiest: A+(m+1)+P equals B+m+P so we're done by our inductive hypothesis.

The second easiest case is case D:

Remember what we are doing -- this is the first two columns of position D at distance (m+1) from the pattern. From D+(m+1) blue must defend under the red ladder, and then red can play to the above position; we know by the inductive hypothesis that D+m is an edge template, and hence D+(m+1) is too.

We next deal with the position C+(m+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+m, and this

leads to D+m. In either case we are done by the inductive hypothesis.

The B case is the most fun. We consider the following position B+(m+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+m+P which is an edge template by the inductive hypothesis.

Move 2 below leads us to D+m:

Move 2 below leads us to C+(m+1) which we have already dealt with.

Move 2 below leads us to C+m (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+m:

Move 2 below leads us to D+m:

The final choice for move 2 below also leads us to D+m.

This completes the analysis for B and hence for all four templates.

So the induction is finished and in particular in all cases A+m+P is an edge template, meaning that P is a 4th row ladder escape.

QED.

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.