edge connections

http://www.hexwiki.org/index.php?title=Template_Va

says that an isolated hex on the 5th row (from the bottom) is connected to the bottom edge of an otherwise empty board, as long as the bottom edge is big enough (10 hexes big will do).

On what size board is a hex on the 6th row provably connected to the bottom edge? The 100th row? The n'th row?

I don't think a 6th row template has been found.

Not even on a 1000x1000 board??

Proving that some connection must exist is not the same as finding a specific sufficient template required for the connection.

Giving some sort of strategy-stealing argument that a connection exists isn't the same, I grant you. But how would one prove that a hex on the 6th row on a 1000x1000 board is connected to the bottom in any way other than finding a template??

I template need not exist, even if the player who puts a piece on the 6th row is winning. Maybe the opponent can block that particular piece, while the first player then can force a different connection.

I am interested in connecting one particular piece to the edge. I understand that this is not what the game of hex is about and that perhaps on the 1000x1000 board my win comes from a route not containing that piece. But I'm still not sure I am seeing the subtlety that other people are pointing out. Are you raising the possibility that it is actually impossible to force a connection from the 6th row to the edge on a 1000x1000 board?

I feel like a template from the 6th row doesn't exist. Currently it's just a feeling :)

Here's a related question. Do you think that on a 1000x1000 board, if vertical moves first and plays on the 6th row and "in the middle", (so he has "almost connected to the bottom"), is this likely to be a winning move or a losing move?

If we are talking about a one stone template I agree with Gregorios feeling. I even feel like this should be possible to prove.

If you however placed several stones in a row on the 6th row it should be no problem to force a connection.

I was talking about a 1-stone template. I've recently got interested in hex but am sort of trying to get it into my head at a theoretical level as well as becoming a practical player. It seems to me that either there would be a 6th row template on a 1000x1000 board, or playing in the 6th row is a losing move, because if there's no template then the stone is almost useless in some sense. But I can't make this rigorous and maybe it's not true.

It's not useless even if it can be blocked. The threat of connecting it can be enough to get a different connection, and then it has been useful.

Wc, I think it's implausible that a there's no template for a stone in the middle of the sixth row on a 1000x1000 board. But that doesn't mean that any particular template has been proven.

I think others are making more sweeping claims about the lack fo such template, and I'm sure they're wrong.

During the summer, when I thought I would have more time, I set out to verify that a single stone on the 6th row is connected to the edge, given sufficient width. I convinced myself, using JHex. So, if I didn't make any mistakes:

There *is* a 6th-row, 1-stone, template.

I wanted to determine the exact shape of the minimal template, but that's when life got busier, and I stopped working on it. I still have the JHex file, and hope to get back to it at some point. Or perhaps we can make a collaborative effort? Hexwiki is good at that, and also makes better pictures than I can do here (as you will see if you follow the technical discussion below).

The key idea is to make good use of parallel ladders on the 2nd and 4th rows. A link to the parallel ladder trick at hexwiki:

http://www.hexwiki.org/index.php?title=Parallel_ladder#2nd_and_4th_rows

Here are some more technical details, for those so inclined:

For instance, if you have a stone on the 4th row, and there is empty space in the 9 spaces remaining under that stone in a triangle [a triangle with 1 space in the 4th row, 2 spaces in the 3rd row, 3 spaces in the 2nd row, and 4 spaces in the 1st row], as well as sufficiently many blank spaces to the right [or, equivalently, to the left] in the first 4 rows, it is pretty easy to use parallel ladders on the 2nd and 4th rows to connect to the bottom. This immediately implies that the defender (trying to stop the 6th row stone from connecting) must play in a not-too-large set of spaces, more or less under the 6th-row stone, to defend against simply making a bridge down to a 4th row stone that can easily win with the parallel ladder trick.

The work is also reduced by making use of symmetry. For instance, the potential defending stone 4 rows down, and 2 to the right (from the 6th-row stone) is completely equivalent to the potential defending stone 4 rows down, and 2 to the left.

Using these ideas (and JHex to keep track of things), I found it was not hard to convince myself that there was no defense against the 6th-row stone. Looking at my JHex file again, I see I really only checked 11 potential defending stones under the 6th-row stone, and some of those were pretty easy to beat.

Thank you for the information Art! I thought no such template existed, and apparently I was wrong.

Maybe it would be possible to determine a minimum 6-row template with some computer assistance. Is it correct to say that a 6:th row template exists if, and only if, black has a winning move in the following figure where white is to move first (assuming that the board is infinite wide)?

That (above) is a formalism of the problem I was interested in (e.g. I did not want to involve any hexes on the 7th row, and you have filled them in for me).

Can you solve this sort of thing javerberg? My understanding is that one needs something like size 4 for a hex on the 3rd row and size 10 for a hex on the 5th. Maybe size 20 is plenty in practice?

I don't think that's an if-and-only-if condition. A 6th-row template could require some empty cells in the 7th (or higher?) rows. It could be that Black can still win if even White moves first in the diagram below (extended to the left and right as far as necessary), but not in your diagram above:

W.W.W.W.W.W.W.W.B.W.W.W.W.W.W.W.W.W.W

.e.e.e.e.e.e.e.W.B.e.e.e.e.e.e.e.e.e.

e.e.e.e.e.e.e.e.e.B.e.e.e.e.e.e.e.e.e

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.

e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.

e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.

where 'e' is an empty cell, 'B' is a black stone, 'W' is a white stone and '.' is just for spacing.

Hmm. How do you get a monospaced font in a forum post?

W.W.W.W.W.W.W.W.B.W.W.W.W.W.W.W.W.

.E.E.E.E.E.E.E.W.B.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.B.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

w.w.w.w.w.w.w.w.B.w.w.w.w.w.w.w.w

.E.E.E.E.E.E.E.w.B.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.B.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.

.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E

w.w.w.w.w.w.w.w.b.w.w.w.w.w.w.w.w.

.e.e.e.e.e.e.e.w.b.e.e.e.e.e.e.e.e

e.e.e.e.e.e.e.e.e.b.e.e.e.e.e.e.e.

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e

e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e

e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.

.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e.e

The one with lowercase w and uppercase B and E is the best of a bad lot.

Bla bla bla

|

|

V

Bla bla bla

W W W W W W W W B W W W W W W W W

. . . . . . . W B . . . . . . . .

. . . . . . . . . B . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

W W W W W W W W B W W W W W W W W

x. . . . . . . W B . . . . . . . .

. . . . . . . . . B . . . . . . .

x. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

x. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

x. . . . . . . . . . . . . . . . .

The 'x' characters are just there to work around LG's deletion of leading spaces on each line.

@wccanard, I agree that the 7:th row is not really needed. This is an alternative problem formulation. Red wins if he connects the red edges, and blue wins if he connects the blue edges. But both formulations are equivalent, right?

@MarleysG, by my understanding a template that requires empty cells on the 7:th row is not a 6:th row template.

@wccanard, forgot to answer your question. Yes, I belive it's possible to solve, but I can't be sure without trying. Red have a strong threat that blue have to answer, so the solution tree should not be too huge. On the other hand there is rather many empty cells, 20x6 = 120 cells and I have so far spent over 1000 cpu hours to solve 8x8 hex.

When I solved it using JHex, I did not use any cells on the 7th row.

But the diagram may need to be much wider than what I see from recent posts. I started on a 19x19 board, and did not play out every last detail once it was reduced to a smaller problem. For instance, as I mentioned above, you can use the parallel ladder trick once you're down to the 4th row with nothing directly below you (in the 4-row triangle) or anywhere to the left of that (or, respectively, right of that). Putting all those together may take even more than 19 cells across.

On the other hand, I think we need to make all the edges on the top row blue, except for the one edge space with the 6th-row stone. If blue wins this modified game, then red doesn't have a 6th-row template. So this matches javerberg's first, black and white, diagram more than the later, blue and red, diagram. But, as I said above, I don't know how wide you have to make it for red to be guaranteed a win. Both of those diagrams are only 11 spaces wide, and I'm pretty sure that's too narrow.

On another subthread of this thread, javerberg seems to want to solve this by brute force and tree search. Let me point out that 7x7 Hex was solved (at least initially) by computer, not by tree search, but by clever use of templates. I think the same thing would be true here. In fact, I don't think it would take many templates.

Here are references for computer solutions of 7x7 Hex, so you can see what I mean about use of templates (and computer):

I think this was the first computer proof, using dozens of templates found by computer:

http://www.ee.umanitoba.ca/~jingyang/hexsol.pdf

And here is another, later (I think), computer solution, using trees:

http://www.cs.ualberta.ca/~hayward/hex7trees/

I don't know enough computer science to get all the details. But if you are interested in programming solutions to Hex, these papers (and others you can find on the authors' websites) are probably good starting points.

@javerberg, I think the convention is that an Nth-row template has a black stone on the Nth row that is already connected to the top, and no such black stone on rows 1..N-1, regardless of which rows contain empty cells. This is the convention used at, for instance, http://www.drking.plus.com/hexagons/hex/templates.html, where two of the fourth-row templates require empty cells on the fifth row.

I think we all can agree that to prove a template with help of smaller templates is a much more elegant solution that brute force. But I do belive it would be very hard to prove that a template is a minimal one with this approach.

@Art, I think Hayward states that his 7x7 solution is the first done entirely by computer. Jing Yang's paper doesn't say where his 7x7 patterns came from, but I take it they were derived partially or entirely by hand.

Wait a minute. I've used "7x7 solution" with two different definitions. Jing Yang's 7x7 solution shows how the first player wins when the initial move is to the center cell. Hayward's 7x7 solution shows whether and how the first player wins for any initial move.

@MarleysG, thank you for the link. I do not agree with this terminology, but I may be one of few with such opinion.

Since Art claims there is a 6:th row template that does not require 7:th row stones I belive my first figure should adequate in this case.

@Art, I agree. The board for a 6:th row template is likely to need more width 13 cells. In post with the first figure I assumed an infinite wide board, but I was too lazy to draw such a figure :).

javerberg: don't worry about drawing the infinite width board :)

But it does seem to make it more difficult to attack with computer. One possibility is to decide what the answer "should" be (for instance: I look more carefully at my JHex files, at least to see how much width I ever used), and then use that for the width. Then, perhaps, one could see if the computer can do it with the width set one less, and repeat until we find, if not a minimal template, at least the minimal parallelogram.

----

Marley: Indeed, I didn't look too carefully at the papers, at least not today. When I first saw them, I think I looked a little more carefully, but remembered very little.

----

javerberg said: "I think we all can agree that to prove a template with help of smaller templates is a much more elegant solution that brute force. But I do belive it would be very hard to prove that a template is a minimal one with this approach."

I don't know if it would be so hard to prove a template is minimal by hand, once you have the alleged template. Finding the minimal template by hand is what I think would be both hard and time-consuming. But once you have it, if it truly is minimal, you just have to show each of the cells in the template is necessary. To do that, put a stone in that cell and let Blue (the defender) go again, and show how Blue can connect the left and right edges (including, as I mentioned before, parts of the top edge into the left and right edges). Most of those would probably not be too hard. But I'm willing to be proved wrong. It may be hard to verify some of the cells near the edges of the template are necessary.

i belive one stone template works for any row on an infinitely wide board. it is still my belief only. i hope one day it will be prooved.

6th and 7th rows works for sure;)

well, na_wspak's opinion is just enough to change my feelings ;)

I'm nearly sure na_wspak is right, and came here to post the same thing. I'm glad someone who can actually play this game said it first. Consider the case where this supposition is false. That would mean the defender can establish an infinite-length chain must pass through a finite-width isthmus. Such an assertion seems far less plausible than na_wspak's.

Dvd: I'm less convinced. Remember that the attacker has only one piece of the edge at the top. As the board gets wider, the attacker gets a larger target at the bottom, but the defender also gets a larger target at the top.

For a fixed-height (m), infinite-width board, the defender must 'merely' connect one edge to the top while passing through the isthmus (of height n <= m). I grant that might be possible for some m and n. For an infinite-height board, I maintain it should not be possible, regardless of n.

Actually, with the finite m, neither end of the defender doesn't need to connect to either end. I loop around the attacker's initial stone would suffice, as would a connection from top to top, encircling the initial stone with help from the top. (I think we're heading into Lazo of Havannah territory here.)

The top and both sides form one effective edge and it's the defender's task to encircle the initial stone, where that edge may form part of the encircling path.

If the board is of infinite height, the defender must either encircle the stone with no help from the edge, or connect edge to edge, passing through the isthmus. I still say that shouldn't be possible.

Dvd: I think it suffices to connect (the left edge or the left top) to (the right edge or right top), instead of insisting on connecting edge to (edge or top).

But there might be a difference between "infinite" width and "arbitrarily large width"! For instance, the defender might easily build a ladder to the top row that is guaranteed to connect to either the left top or the left edge [equivalently for right top and right edge, of course], as long as the board is finite. In such a case, I would think we would declare that the template does not exist (or at least that branch of the game tree is a "win" for the defender, or at least that it's not a win for the attacker).

So if our goal is to find templates, we should be careful about our use of infinite width, though I certainly understand it as a shorthand for a first order description of the problem.

BTW, I forgot to say this before: If na_wspak says there's a 7th row template, I believe it. Similarly, na_wspak's opinion that there's a template for any row carries a lot of weight for me, though I still hold out some doubt, as described above.

Yes, you're right.

I'm not that good as na_wspak but I'm less convinced there is a 6th or 7th row template.

Perhaps there is, but I tend to believe there is a number n such as there is not an nth-row (1-stone) template. Whether this n is 6 or 7 or 66 I have not a clue.

I only got interested in hex a week or two ago, and started this thread with a rather naive question. I am slightly surprised that it there doesn't seem to be an answer which is universally accepted amongst the experts.

In my mind, javerberg's first picture (the black and white one) summarises the problem well (in the form I initially intended it---of course there are other interesting and related problems that one could ask). Dvd Avins' comment is also pertinent. With notation as in javerberg's b/w picture, all white has to do is to connect his 2 groups, and looking at things that way, it seems not unreasonable to expect that this is going to be possible with a template if the black pieces are sufficiently far from the edge. One could try and computer-solve positions like in javerberg's first picture, thus constructing templates for black (if they exist, i.e. if black has a win) and one could also try and computer-solve analogous positions with columns of black stones filling the remainder of the 1st and last column, thus looking for a template for white to connect the two long rows. At least this would provide some way of getting a machine to resolve the original questions. If white can connect his two lines (with the extra black columnns inserted at left and right) then black provably has no template!

yes. I also think of a 6th row template as exposed by Javerberg (with, perhaps, some empty spaces surrounding the black stones). And thought it that way when I claimed my feelings about non-existence. I guess we should make it more explicit if we want to find some proof (even more if it will be by computer).

Still, if Javerberg's Problem (let's see if the name stick :P ) is solved for the 6th row, I have the same feeling as Ypercube; there must be a N for which for any number n greater than N there is no solution for Javerberg's n-Problem.

(wccanard, not quite a naive question) :)

Whatever the answer is, it would give quite a practical result, or a deeper understanding of the game of hex (not to forget a publication in some journal).

:D

@Art, the handmade proofs constructed by combining smaller templates can be used to prove something that is more or less obvious in an elegant way. A 6:th row template may be proved in such a fashion since itâ??s a rather short distance, but to prove that defender wins is more complicated. This is of course just my opinion, and would be happy to be proven wrong.

Would love to present a minimal 6:th row template with the help of my program, but that will have to wait a bit since my program is at the moment unable to handle big boards (a tradeoff to gain a bit extra speed on smaller boards). Hope to fix this within a few days.

Is it possible to prove the lack of a n:th row template with the help of a computer? If a 7:th row template does not exist on a board 1000 cells wide, could such a template exist on board that is 1001 cells wide?

Btw, I think it would be more fair to call it wccanards problem. It was he who started this thread. But thanks! :)

"Is it possible to prove the lack of a n:th row template with the help of a computer?" Yes! If we define an n:th row template as being a win for black as P2 in the (obvious analogue of the) first picture you posted, and if one could prove that P1 as white has a win in the game that you get from the picture by putting extra columns of black stones in the vacant spaces in the first and last columns, for some sized board, then this proves that no n:th row template exists, because it would prove the existence of a different template, linking the two rows of white stones. The two templates can't co-exist.

I, too, think of a 6th row template in the same way as Javerberg. And with this definition, I disagree with na_wspak: I'm sure there is an n such that there does not exist a winning template from the n-th row on any size board, that is, there exist a board sized m such that white is winning.

However, whether or not a template exists for the 6th row is a different question. I'm not sure. But I think that n is in the area 6-8.

@Marius:maybe there is such n, maybe not...

what i am sure of is fact that there is 6th row template (i will try to find the minimal field required which shouldn't be hard)

and i am pretty sure that there is a 7th row template but i worry that it needs some 8th row empty fields... i have to work on it with my brother. he always has a fresh look at my hex-thoughts. i tend to make silly simplifications.

and please don't treat what is above as it is a proven fact. those are only my yet unproved loosy thoughts.