Difference between revisions of "Theory of ladder escapes"
(This gives an algorithm capable of checking in a finite time whether a position is a 2nd, 3rd or 4th row ladder escape.) |
|||
| Line 384: | Line 384: | ||
QED. | QED. | ||
| + | |||
| + | == 5th and 6th row ladder escapes == | ||
| + | |||
| + | To push this theory 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 is not immediate. 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 of this awaits for anyone who tries to extend these results to 5th row ladders or higher. | ||
Revision as of 00:30, 21 May 2016
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 need to formalise what it means to be a ladder! After we have done this, we can formalise what it means to be a ladder escape, but now there is a catch. A ladder escape (say, to make things precise, 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, however far away it is. So strictly speaking to check that a pattern is a 4th row ladder escape we need to check that red can connect to the edge from an *infinite set* of positions (the ladder can be as far away as you like). This raises the issue of how one can possibly 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 these have no practical use and it will take a lot of work, so I have not done this. 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 I do not know how to resolve; I think that in theory there could be no 7th row ladder escapes at all!
Contents
Ladders
There is no issue at all with defining a 2nd row ladder: it looks like this.
There is a minor issue with defining 3rd and higher row ladders though. We want a definition which 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 couple of 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 (moving from left to right, say) to have no stones on the first three rows to the right of the ladder (until we reach the escape of course), we do not want to also guarantee that there are no stones on the first row to the left of the ladder.
Here is the definition I came up with. A third row ladder is a pattern like this:
The asterisk is not part of the pattern. The red piece can be thought of as being 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.
So that is my working definition of a third row ladder, and it seems to work in practice.
The problems compound themselves as we move up the board. Here is my working definition of a 4th row ladder:
You see that I have replaced the blue piece with an asterisk (indicating "not part of the pattern"). This is OK because hexes which are not part of the pattern may as well be blue pieces. What I am suggesting here is that for a 4th row ladder to become established we should demand that the triangle with 6 hexes 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 to make the ladder established red needs at a minimum those 6 vacant hexes under their red stone.
I have said above that I will be restricting my attention to 2nd, 3rd and 4th row ladders, and one of the reasons for this is that I do not know a satisfactory definition of a 5th row ladder. What I do know is that this
will not do, because it turns out that if it is blue to play in the diagram below:
then blue can block the ladder with this move:
The main line is complex; see http://littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=669 for example. The conclusion from this is that red needs more space in order to ensure that the ladder is established, and because I am only an amateur hex player I do not really know the minimal amount required or even if one can expect a "natural" answer to this -- perhaps there is more than one kind of 5th row ladder.
A similar issue arises with 6th row ladders -- I do not know how much space to guarantee red under the ladder stone. And for 7th row ladders I have already explained in open problems about edge templates that the situation is even worse -- no amount of space under the ladder (even if we demand that the entire 5th row is clear) seems to guarantee a red connection if blue just ignores the ladder and plays elsewhere, from which I deduce that I am struggling to make sense of the notion of a 7th row ladder from a theoretical point of view whilst simultaneously being aware that there is probably essentially no use for it from a practical point of view either.
2nd 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 a pattern that looks something like this.
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 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:
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 coming in from the left. A second row ladder escape is the following data. It is a pattern, plus two hexes with pluses 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 plays along the ladder and by induction this is an edge template.
QED
Definition: A 2nd row ladder escape template is minimal if the following two things are true. Firstly, removing any hex from the pattern 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 http://www.drking.org.uk/hexagons/hex/templates.html]: the following positions are minimal second row ladder escapes:
(note that the corresponding pattern on Dr King's site is not minimal; I have moved the plusses)
(note that the corresponding pattern on Dr 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 Dr King's site, and there are several more there).
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:
(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 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 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 and red replies thus:
then we see that by the inductive hypothesis, piece 3 is connected to the edge, and hence piece 1 is too.
For position A+(m+1) we need to work a little more. The position we need to consider is this:
(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. For the second
red just wins outright. And for the third this sequence is forced for blue:
and red is connected because by induction B+m connects to the edge.
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
Here are some remarks about this argument.
(I will elaborate on these later) 1) necessary but not sufficient (weird example of 3rd row escape for which hypothesis of lemma doesn't hold) 2) 3rd row escape is not a 2nd row escape 3) Is a 3rd row escape a 2nd row escape if we demand an extra row somehow? Not sure this is interesting.
Examples: crib from King website. Fix the one where the plusses slope the wrong way.
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 a pattern plus four plussed hexes 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:
A: B: C: D: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 the 2nd and 3rd row ladders do *not* have vacant hexes above them, in contrast to the 3rd row ladder escape result where the 2nd row ladder had a vacant hex above it.
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 B case is the most fun. We consider the following position:
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 with a blue stone all lose instantly:
Any of the moves marked 2 below can be answered by red 3, moving us to position A+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 will deal with later:
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 2 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, modulo the fact that we need to deal with C+(m+1). Let's do this now.
From C+(m+1) all moves lose instantly other than the two lines below:
leads to C+m, and
leads to D+m. In particular this finishes the proof for B and C. Finally D, the easiest:
D+(m+1) leads straight to D+m.
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.
5th and 6th row ladder escapes
To push this theory 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 is not immediate. 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 of this awaits for anyone who tries to extend these results to 5th row ladders or higher.
