What _is_ a ladder? a 5th row non-ladder problem.

I have been trying to figure out what a ladder escape it, and then I realised that I didn't actually really know *precisely* what a ladder is. Here are some comments and what for me was a surprising conclusion. Let's start with this position (white to play).

I'm afraid that in this post, all ladders are going to go from right to left. This (on the right) is most definitely a second row ladder, and the two stones on the left are most definitely a second row ladder escape. It's white to move. Black has a second row ladder, and a second row ladder escape, and we can all see that black can win; white is forced to play along the first row and black along the second row, and in the end black connects to the stones on the left and wins.

Now let's go onto the 3rd row.

White to play? Who wins this? Well again this is pretty easy. If white keeps playing in the second row then black keeps playing in the first row, and if white drops to the first row then black ladders along the second row. But be careful! If we modify the position slightly:

then black does *not* have a ladder. It's white's move and white can do this

which wins. Black's ladder was not a ladder, it wasn't somehow established enough.

Let's now move to the 4th row. We might guess that black wins this:

because the ladder is in some sense looks "established". For sure, if we give white one more stone:

(white's move) then this is a win for white because of this move:

But let's go back to the original 4th row ladder picture. Is black *definitely* through? We have to check moves like this:

I'm not saying this is hard to do -- I'm just pointing out that it is not *immediately* obvious that black can ladder their way to the stones at the end --one has to check that those diagonal white stones in the bottom right can't somehow be used for some magic.

I've checked that black has enough to ensure a ladder in this position. But when I went onto the 5th row:

I found that this position is a win for white! I think the main line is hard to find. Here's a trmph link to the position if people want to play around: [www.trmph.com]

The reason I got interested in this was that I want to draw a "template" (just a finite fragment of a board) and say things like "this template is the *definition* of a black 5th row ladder". The idea is that the template has some fixed finite number of hexes in, and outside those hexes everything (other than the 5 rows where the ladder is going, and the path from the ladder piece to the top) can be filled with white stones. My positions above are working definitions for 2nd, 3rd and 4rd row ladders, but now I realise that I don't really know what a 5th row ladder is; I know I need more space than what I'm offering black above but I am not clear about how much more they need. I think that I will just stick to 2nd, 3rd, 4th row ladders from now on.

As a consequence I should say that suddenly when people are asking question such as "is a 10th row ladder escape also a 7th row ladder escape" -- suddenly I am really confused about how to actually make this a rigorous question. For all I know there's some crazy play by white which actually blocks a 10th row ladder in its tracks even without those white stones on the edge!

It would help if you told us what White's winning move is in your last example

It's probably p18. The main line is probably this, which uses Tom's move

Yes p18 apparently wins, and either I'm misunderstanding this computer output or m18 does as well. The m18 move -- I don't know whether this is just a weird consequence of 19 x19 being too small or not. But the basic point is that white has a lot of possibilities. After m18 black can play R16 of course, but this 4th row piece is not connected to the edge because the template for a 4th row piece that doesn't need any of the white stones on the bottom right needs a lot of stones on the left (including m18).

We could just imagine removing all the white stones on the bottom right, apart from the one at the top. But then if you move everything up to the 6th or 7th row (and move everything to a 100x100 board) then white has a lot of time because black doesn't even (as far as I know, on the 7th row) even have a one-move direct threat, so white even seems to have a free move. This is a theoretical complication as far as I am concerned. I would like to have some robust theoretical framework where I can say something like "this theoretical position is a 10th row ladder escape, and hence black will win if he can form a 10th row ladder over there and then ladder into it" (let me clarify that I am not suggesting that this is of any practical use on a 19x19 board -- I am talking now about general abstract theory of hex on a board of arbitrary size). But now I realise that because there is no known 8th row (say) template, it is literally impossible for me to formulate this rigorously, because if black has what looks to the world like a 10th row ladder, and then we have a region which is supposed to be a 10th row ladder escape, then white can just ignore the ladder completely and play a move directly in the escape which kind of screws things up, because the formal theory of ladder escapes kind of relies on black being able to force the ladder to get right up to the escape before white has the time to play any moves in the escape area. If white just plays a random move in the escape then black can leap down to the 9th row or whatever, but there seems to be no known 9th row template so white can now just go and deal with blacks intrusion after playing in the ladder.

My conclusion from looking at this is that although we all know that there is such a thing as a 2nd row ladder, 3rd row ladder, 4th row ladder, 2nd row ladder escape, 3rd row ladder escape and 4th row ladder escape, **it is not clear to me how much further these concepts extend**. In particular my initial motivation for thinking about this -- trying to give a rigorous proof of a statement of the form "if x < y then a y'th row ladder escape is also an x'th row ladder escape" -- has now been knocked sideways because I cannot actually formulate the question in a rigorous way.

Basically (in summary) if we can't find a 7th row single-stone template then an 8th row ladder can in theory be ignored, and my impression is that this completely messes up the abstract concept of an 8th row ladder escape.

"x less than y" in the last-but-one para (the forum ate my less than sign)

Interesting stuff again! :-)

I think (and this may just be phrasing things you already said differently) that an important point is, in how for black has a direct threat in the initial position if one ignores the ladder escape. On a second row ladder the treat is obvious. There is only one field where white has to respond. On a third row ladder black has 2 direct threats and the overlap is tow fields, so white is forced to play on one of those. This translates to keeping the ladder on row 3 or allowing it to fall down to row 2. On the fourth row, black still has direct threats, but the area white has to play in is a lot larger.

To me it is entirely unclear if black even has a direct threat for ladders on rows 5 and above. This may depend on the board width of course. If there is no direct threat, I guess it shouldn't be called a ladder. So for me the question if there even is such a thing as a 10th row ladder is an open one.

This is an edge template:

so this means that there is a chance that one can make sense of a 5th row ladder.

On the other hand I do not know a 5th row template which is one move away from this sort of position:

(of course you can extend the region to the left or the right as long as you like) and hence I cannot rule out the possibility that 6th row ladders "do not exist" in the sense that if white decides to play in a completely different region in the position above, can black definitely connect?

Put another way -- in the position above, if it's *black* to move, does black have a win? (you are allowed to extend the board as far to the left (with white stones on the 7th row) and to the right (with white stones on the 5th row) as you like).

If it is unknown whether black can force a win in the above position, if it's black's move, then in my mind this is a theoretical obstruction to even defining what a 6th row ladder escape *means*. Of course some expert can come along and tell me that g10 wins or something -- but the theoretical point is that even if this is clearly a win for black, it's not so clear on the 10th row. So my thesis is that just like the single-stone edge template question ("for which n is there a single-stone edge template with one stone on the n'th row?") there is an analogous "ladder template" question, and until these are resolved there are *as far as I can see* theoretical obstructions to formalising what one means by a ladder and a ladder escape at these heights.

Let me end by saying that I have resolved these issues in my mind for 2nd, 3rd and 4th row ladders, and it would not surprise me if it were possible to resolve them for 5th and maybe even higher row ladders -- what I don't know is whether one can hope to resolve them for ladders on all rows because for me the question seems to be harder than the single-stone template problem, which as far as I know remains unsolved.

It seems that benzene says the position above is a win for black if black moves first. Let's take it up a row.

OK benzene has gone very quiet about the 7th row ladder being ignored. So currently I am unclear about whether 7th row ladders "exist" but there is a chance that one could try and say something about 5th and 6th row ladders. On the other hand from a practical point of view it's not clear whether we're that interested. It seems to me that there is a theoretical obstruction to talking about n'th row ladders in general, and what I am currently not clear on is how big n can be before I start seeing issues that we can't resolve.

I'll finish for now by saying explicitly the simplest problem that I currently don't know the answer to:

Black has a 7th row ladder and white just decides to ignore it and play somewhere else (see the marked stone) instead of chasing black along the 7th row. It's now black's move -- who wins? In other words we can all see white's last move is foolish -- but is it a *losing* move?

Could you please explain the link between this discussion and the 6 row template problem which I would naively think as simpler?

I thought some people here said they had found a 6 row template, what is the status now?

Also is the board infinite for the problem just above?

I mean, I don't want to hijack this thread with another question.

It is just that all the different posts you wrote are interesting, and you seem to go somewhere, but I don't get the big picture and the logical argument to where you are heading.

On a board which is 11 high and say 13 large, if Black has played in the centre, he should win. Will he win by two 6 row templates or just because of the influence this central stone gives him as the board is not large enough for a 6 row template?

Or do you think solving a 6 row template is just an epi phenomenon and don't tell us anything new on hex theory for 1000x1000 boards?

Hi. Let me try and answer all your questions.

Let's say black has a 7th row ladder and white chooses to ignore it. I guess black must then play on the 6th row so let's assume he does. So the question is: if it's white to move in the position below, then does black win?

Yes, there is a 6th row template. It just can't be used for the 7th row ladder problem above because of the 5th row white stones. The only single-stone 6th row template that I know has a vacant hex to the left of the 6th row stone *and* a vacant hex to the right of the 6th row stone. So it can't be used for that 6th row stone. The question is whether there is a 6th row single-stone edge template which fits into the above board.

Sure the board can be infinite. But of course if there is a template then it will fit on a finite board. But I am not saying 19x19 is enough -- I just don't know.

The two fundamental questions about ladders that I have are the following.

1) Give a formal mathematical definition of an n'th row ladder escape and an algorithm which can decide in a finite amount of time whether a given position is an n'th row ladder escape.

Status: I can give some sort of definition for all n (the only issue is exactly how much space one has to demand under the ladder), but the hard part is proving that any escapes exist for n>=5. I can do this for 2<=n<=4: I have an algorithm which terminates in finite time and which gives a sufficient condition for something to be an n'th row  ladder escape for n<=4, but it might not be necessary for n=3,4 (it's necessary and sufficient for n=2). It might be possible to give an algorithm for n=5,6. If the position above is a win for white then I don't know how to formalise a useful definition for n=7 because some nice bunch of stones 100 columns away from a 2nd row ladder can easily force a win, but a nice bunch of stones 100 columns away from a 7th row ladder may *never* force a win if white can just ignore the ladder and then block it a move later. Indeed, more generally if it is actually true that there is *no* single-stone 10th row template (say) then it will almost certainly follow that there is no 11th row ladder escape.

2) Is it true that "all 3rd row ladder escapes are also 2nd row ladder escapes" and more generally all M'th row escapes are N'th row escapes if N is less than M?

Status: Again one has to formalise what this means before one can try and prove or disprove it. I have formalised the question about 3 and 2 precisely and it is *false*! But this might just be because my formalism is bad. I have not yet written down these thoughts but when I find the time I will write a theoretical post about ladders on hexwiki. I can formulate a revised version which is true. I currently don't know whether all 4th row ladder escapes are also 3rd row ladder escapes (indeed I only just figured out what I want this to mean).

Those are the two questions which are motivating this theoretical discussion about ladders. Let me again stress that I am well aware that 7th row ladder escapes are not really something which a practical hex player will care about; however I think that 3rd and 4th row ladder escapes are, and I was very confused with various responses I got to questions such as "is a single stone on the 5th row a 4th row ladder escape?" that I realised that I wanted to actually work on this question myself, and then I realised that I didn't really know how to verify that anything was a 4th row ladder escape (because black can play lots of weird moves on the 1st and 2nd rows that need to be countered, and maybe they start playing these moves when the ladder is 100 moves away or maybe when the ladder is 3 moves away, and there are a lot of possibilities that one needs to check), and then I realised that I didn't know what an n'th row ladder was and now here we are.

On an 11x13 board there's a trick where the player who wants to make the shortest connection automatically wins using a template strategy, but the template is the entire board and there's only one (it's not two edge templates). I don't think it's likely that you can win using two 6th row edge templates. Certainly you can't win using two 6th row templates right now -- because unfortunately the only known 6th row edge template has a vacant hex both to the left and to the right of the stone, so in particular if we try to use two templates for the two edges then they will overlap.

So somehow a key question is whether there is a 6th row edge template which does not use the hex directly to the right of the 6th row stone. Such templates are certainly known for 2<=n<=4 and I believe there's one for n=5, but my memory might be playing tricks on me.

I do think that looking for a 6th row template is important, because I feel that there is actually a chance that there is some sort of boundary for this question -- maybe there really is no single-stone 8th row edge template for example. And maybe there is no 6th row edge template which only uses one more 6th row hex. My impression from having played hex a bit is that these really might be a possibility. If this is true then this has consequences for exactly what one can do with templates. However a brute force computer approach seems to be out of reach, and becuase hex is pspace-complete we shouldn't expect some amazing new algorithm to come along any time soon.

wccanard: remember this template. Using it, it's easy to see why black wins the ignored 6th row ladder, and even for the 7th row the number of moves to check is greatly decreased. That makes it tractable to do by hand (and I'm almost certain black wins, though I didn't check all the lines yet).

Shalev -- yes! I remembered that I had seen a 5th row template on the short diagonal in this forum when talking about whether the 6th row template existed -- but I couldn't remember for sure if the template didn't need a vacant hex on each side of the stone and I didn't want to look through the forums because I was in a hurry. I glanced at Dr King's site but it wasn't there so I knew I'd have to come back to it later -- thanks for sorting it out for me.

Carroll -- note that even this doesn't solve the problem of templating your way to a connection on an 11x19 board, because even this 5th row template overlaps with the template you get by rotating it 180 degrees. That's a new phenomenon that occurs for single stone 5th row templates; there are single stone 4th row templates which do not overlap with their rotations, but I don't think I've ever seen a single stone 5th row one.

So there's a question -- is there a 5th row single stone template which does not overlap with its 180 degree rotation? Or even is there a 5th row single stone template for which the template stone sits in a "120 degree corner" like the standard 3rd row template?

This is a 5th row template which does not overlap with its 180 degree rotation.

shalev: I believe you! So 6th row ladders exist (which we knew already), and furthermore there's a proof that on a board of size 9 x 21 or so  you can win using two edge templates :-) (which I didn't know, but of course there are much better proofs that you can win on a 9x10 board. even playing second, that don't use edge templates at all).

So here's I think the boundary of my knowledge:

I don't know any single-stone 7th row edge templates. Probably they won't fit on a 19x19 board which is a practical obstruction to looking for one with a computer. If anyone knows a program which can analyse hex positions that won't fit onto a 19x19 board I'd be interested to hear.

I don't know whether 7th row ladders exist, because I don't know a single-stone 6th row edge template which fits in the first seven rows and doesn't need both the hex to the left and to the right of the 6th row stone. Shalev has posted some 5th row examples in this thread but I don't know how to move them up to the 6th row. In fact I don't even know of a single-stone 6th row edge template where the boundary of the template makes a 120 degree angle at the 6th row stone.

I don't yet know a way to prove that 5th row ladder escape is a 5th row ladder escape in a finite time (and similarly for 6th row; I can't even make the question make sense for 7th row though because of the issue above), however I do have a method for doing this -- this problem is accessible using the tools we have. Rather than explain the technique here I will write a post on hexwiki (one day) about how to rigorously check that something is a 3rd or a 4th row ladder escape, and then people will see what needs to be generalised. I really need to find the time to do this before I forget my ideas, which are currently being carried around in my bag on about 4 pieces of hexagonal graph paper!

"If anyone knows a program which can analyse hex positions that won’t fit onto a 19x19 board I’d be interested to hear."

I have written my own, works without any size restrictions. Small problem: It's a bit slow, so when it will finally provide an answer to one of the questions discussed here, you'll have other problems to deal with, because the sun will have become a red giant by that time. :-)

My impression from reading what the Alberta group people wrote is that to speed things up you want to implement DFPN search and build in a load of templates.

That might or might not go beyond my skills, but it surely goes beyond my current level of enthusiasm. I wrote the (horribly slow) solver that I have in approximately 5 hours. :-)

What you gain on the swings you lose on the roundabouts :-)

I'm about to start writing about ladder escape templates on hexwiki.

I wrote up the problems I don't know how to solve at

http://hexwiki.amecy.com/index.php/Open_problems_about_edge_templates

clickable link

wccanard, very nice graphical example of why the concept of "ladder" in hex is fundamentally not bad and scalable. Moreover a "ladder" does not look at all like a real ladder, so it's also a poor choice of terms. The term is naturally copied from Go, where "ladders" actually look like ladders!

I think a better terminology for what you were trying to study and formalize is what happens when "both black and white are playing parallel to black's bottom edge".

Anyway, we "normal" players learn(ed) this by playing. This is why we tend to play initial moves on 5th row, and it's also why 19x19 (where the "ladders" are less important) could be interesting and fascinating to play...

*fundamentally bad and not scalable ;)

I mean, even on 4th row, it's hard to say what is a ladder and what is not... here are some realistic-looking examples: example 1, example 2, example 3

But on the other hand, vaguely speaking we can say that in all these both players are playing mostly in the horizontal direction.

I think you are edging around but not quite asking what I consider the fundamental question of Hex. Take a look at the last of the small diagrams, only with Black to play. Remember as wccanard said, Black may extend the position as far as they want to the left and right. Who wins? More generally is there any distance from the bottom where in an analogous position, White would win? I have seen working assumptions, but I've not seen a proof or demonstration that there is such a distance.

Whatever the distance is, there are templates to be found for every row up to one less than that distance.

dvd, i don't understand what diagram you're referring to, or i understand it but then i can't make sense of your question...

if the question is, "is there a one stone edge template for any distance?", i sincerely have no opinion on this! i don't even think it's relevant for practical play, because even if there is a edge template, it's so big it'll not fit in any reasonable board.

Here's a similar question: assume a board of height n where n is odd and width as large as wither player needs it to be to win, but may not be extended merely to extend play indefinitely. The first player, trying to connect left to right, plays in the middle row. For a given n, how wide does the second player need toe board to be?

and anyway, i used to think the answer to that question is "yes", but today i'm more inclined toward the "no"...

I think if there are answers, the patterns revealed in them will have application in practical play. I also find the questions more intersting than the game itself.

dvd, n+1 no? because of the n * (n+1) board pairing strategy...

let me be more precise, i think answer is "no" if we want the stone to connect going down... if we also allow it to connect down by going up, then maybe i'm still in the "yes" camp... but this has absolutely zero relevance for practical play!

An answer that maybe SEEM TO have practical relevance is an answer to: "on NxN empty board, which is the furthest row to have a pattern for connecting a single stone of this row to the edge?". But in truth even if we had this answer I wouldn't know how to use this information because there is always an influence of other stones.

It would have relevance for when to swap on the first move.