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.

What notation should we use for this board? Can we name the cell of the black stone A0, with A-F going from top to bottom, and -inf to +inf going from left to right?

Looking at it now, it certainly seems like there exists a 6th row template.

I created an article on hexwiki trying to repeat and summarise what is said here. It's called Javerberg-wccanard_problem ! Feel free to improve it now and when the discussion achieve more results.

Well, it's rather easy to prove that all replies outside the triangle beneeth the 6th row stone is losing for white (one can place all pieces outside this triangle, at ONE side, that is the entire 1 row, as white's first move, and see that black is still winning with c-1, using the suggested notation). With symmetry, that leaves only 11 possible replies for white. I've looked at a few of those, and they are losing too. I'm guessing that using JHex, it should not take too long to try all 11 replies.

Why not just call it the “n'th row template problem” and, if you really want, redirect Javerberg-wccanard_problem to that. The advantage of giving the problem a “descriptive name” is that it's much easier to guess what it's about when browsing around. Indeed “n'th row template problem” is a very natural description of the problem.

well, not everybody accept that problem is the same as finding a n-th row template. A negative answer to javerberg-wccanard problem doesn't mean your isolated stone in the n-th row is not connected to the edge.

I agree with you Gregorio that there is more than one question here. But that is not my point. My point is that it would be much more sensible to have a page with a _descriptive_ title, like “n'th row template”, where one could mention several problems (e.g. “a related problem, raised by wccanard at etc etc”), than a page with a highly non-descriptive title, like we have now, and that no-one would ever find with e.g. a google search etc.

ok, i understand, i agree. be bold and change it in hexwiki ;)

Gregorio, I don't find “your” template problem very interresting. If I can connect, but have to go higher than the n-th row and back, that's something different. For that problem, I agree with na_wspak: I believe there exists a template for any n, as long as you make the board big enough. Can't prove it, though. But for that problem, finding a general proof seems more interresting than examining a particular case :-)

I didn't talk about “interestingness” (:P), I just said that javerberg-wccanard problem is not a general solution to connecting an isolated stone.

I agree JW Problem is more interesting and, why not, funny.

Anyway, Marius, finding a minimal area, i.e a template, for particular rows is highly useful for actual play.

I agree with calling this the “n-th row template problem”, and then giving credit to javerberg and wccanard on the hexwiki page (and other descriptions of the problem).

There are also apparently two possible version of this problem. In the first version, the template cannot rely on any spaces above the n-th row. (So the n=6 case corresponds to javerberg's diagrams, both the black/white and red/blue diagrams, I think.) This is the formulation I prefer to focus on: it is more elegant, and more useful.

On the other hand, the second version, the template may rely on spaces above the n-th row. (For instance, on the hexwiki page, templates IV1c and IV1d.) This version is interesting and useful, too! For instance, I think the 6th row template will rely on these 4th row “templates” (especially IV1c), since they essentially code the idea of the parallel ladders, which I think are necessary for the 6th row.

I propose (feel free to agree or disagree) to call the first version the “n-th row template problem” and the second version the “generalized n-th row template problem”. Although I suspect the first one is more interesting, only time will tell.

By the way, this raises another conjecture I find interesting. So far, the only 1-stone templates on the hexwiki page that do use spaces above the 1 stone (i.e., templates that are solutions to what I propose to call the “generalized n-th row template problem”) only use spaces one row higher than the original stone. How much higher could this go? Could there be an n-th row template (1 stone on the n-th row) that requires spaces on the (n+2)nd row? (n+3)rd? (n+k)th for any k? I suspect that k is at most 1 or maybe 2. In other words, I don't think there are any n-th row templates that need the (n+3)rd row or higher, and I am doubtful about n-th row templates that need the (n+2)nd row. I think this would be very hard to prove (unless there's a counterexample).

wccanard:

“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.”

You are absolutely right, didn't think of that. Unfortunately your second “if” is a big if, I believe too big for your theorem to be of practical use.

Tried out my hex program on the 6:th row template problem, but the problem proved to be more complex than I first thought. Even to prove that no such template exist on an 10x10 board takes time, since it has to be proved that white wins no matter where black starts. When 8x8 hex is solved (maybe end of January if I'm lucky) I will try to put a bit time on tuning the program for bigger boards, but I doubt that I will be able to press it much beyond 14x14 (still referring to the 6:th row template problem).

Btw, would there be any interest in a hex playing bot at LG?

i'd be interested :)

…a lot.

…and by “a lot” i mean a huge lot :)

Gregorio: why not just play against six, if you want a computer opponent?

Can you play Six on Mac?

first of all, i cannot play six on mac. Secondly, playing turn-based and being able to check the game whatever computer i'm on, it's great :)

I'd also be interested in hex bot at LG. In many papers it is said that computer Hex matches intermediate players but not more. It could be proved, or the contrary could be shown !

Gregorio: can't you use ab's Hexgui with the gtp version of Six ?

Art, I'd not be too surprised if on large boards, you might require nk rows above, where k might be sqrt(2)/2, for instance. Or maybe even 1 or something above 1, though that would surprise me.

@Gregorio, thank you for your encouraging with the hex-bot.

Since I miss the possibility to play hex on my cell phone, I'm also considering a j2me application that plays hex. Since cell phones do not have enough capacity for a decent AI it has to be connected to a server that does the actual thinking, and this will unfortunately limit the maximum number of players. But it would be a fun thing to try.

well, as i connect to internet via my phone many times a day, a bot in LG would be just perfect :)

Another advantage is to measure its rating by playing a lot. And perhaps currently LG is the best way to expose a bot to a lot of human players :)

Will try to make a hex bot for LG, but don't expect it to be ready soon. There is a lot of things I would like to try to improve the strength, and I don't have a lot of time on my hands right now. Not even for a fun project as this…

Again I forgot to relogin before writing a forum post…

I started putting the solution to the 6th row template on hexwiki. For now it is on the “Javerberg-wccanard problem” page, though I'm sure it should go someplace else eventually. It's really just a start, using just the easy template IV1a to narrow Blue's response to 18 possibilities (really just 10, taking symmetry into account). Please, continue to improve on this!

The sooner someone changes “javerberg-wccanard problem” to something more descriptive and sensible, the less trouble there will be when I myself get around to working out wikis work and try to do it myself thus breaking links everywhere :-/

agree. and the most troublesome part of it is that I initially called Javerberg Problem to something slightly different to what hexwiki states ;-)

the problem is: given the nonnegative natural numbers n,m,j the question is: does black connect her upper stone (in the diagram of 2009-01-01 by javerberg) in a diagram of n hexes of height, m hexes to the right and j hexes to the left?

of course, it is related to the general problem of a template, but in this case no n+1 row stone is allowed.

not sure if anybody agrees with my vision of the problem :D

As per wccanard, I changed the name of the wiki article to “Sixth row template problem”. The generalization I called the n-th row template problem. My wiki editing skills are not great, so please feel free to clean up and improve the links, and other technical stuff. For that matter, please make any changes to make it better.

I also changed the language to reflect what I think we've been talking about: n is the height and m is the width. (This doesn't incorporate Gregorio's latest suggestion, of the width being different on the left and right, sorry.)

[thanks Art]

@Art, well… about different width on the left and the right,,, it just occured to me as I was writting :)

i made a 6th row connection jhex file tonight. if anyone is interested i can e-mail it. it is not perfect though.

i also added a minimal empty field required to connect a single stone from 6th row after opponents move. i added it on Hexwiki

i will be glad if u tell me of any mistakes or omissions i unintentionally made. (well i must admit i did all thing in a hurry and it was a bit late;])

Impressive work!!

answer to original wccanard's quesstion is: board must be at least 18 hexes wide.

Are you SURE all these hexes are necessary, na_wspak? I've not looked at it in JHex yet, but it just seems like it would be possible to use fewer hexes.

What would you say is the “best” first move for the defender?

The template is, unfortunately, a bit too big to be possible to verify with my program within reasonable time. The program claims the attacker has an overwhelming advantage, but fails to see to the end.

However, it would be fun to let the program play a game as defender. Any taker?

Marius if u want i can send u my jhex file. i tried to defend in my analyses in a way that takes the attacker the most free space. in that way the best first defending move seems to be (suppose 19x19 board): 1.L14 2. K17 (or J17 as symetrical move).

oops.. ;\| i was careless while doing analysis. i missed one good move for attacker. my brother just realised me that. one but crucial omission.

this means board has to be 16 hexes wide.

sorry for mess i made.

i have already upgreaded jhex file.

ah man i ment 14 hexes wide ;]

Ah, now it looks just how I'd expect it too look! Defending close to the opening stone, and attacker using the parallell ladder trick at the end. Still, 14 hexes wide means it's not gonna be of much use, even in Hex19. And I doubt it's possible to make it any smaller now.

Is there any reason not to believe that 3n-4 width is a general solution?

I haven't looked yet at the proof for template VI. Therefor I cannot judge if the proof for template VI can be generalised. If the generalisation is not obvious, I ask “is there any reason to believe that 3n-4 width is a general solution”!

Yes, I have no proof but I do have reason. It seemed to me even before the this template was shown that this was the shape being tended toward as the initial stone got further from the edge. Needed, if I'm right, is a series of bridges on moth the left and right sides, leading down to the third row. From there, the template heads straight to the edge.

The question is whether that shape is indeed a limit which is reached at the sixth row and then maintained, or merely a notable shape that is reached and then becomes insufficient.

1. hexwiki update: I've put in an outline for dealing with the remaining 6 intrusions. I'm pretty confident I've solved 5 of the 6 (and you could, too, as long as you remember the parallel ladder trick). But what's called on the hexwiki page “The remaining second row intrusion” is not so obvious. I still think Red wins, but it will take longer to be sure to check every possibility.

I looked at na_swpak's JHex file (well, the one from a day ago), and I don't think he put all the details of the second row intrusion in there, either. To *prove* a template is correct, we have to really look at all the possibilities, which will take a bit more effort, at least for this second row intrusion. Or maybe someone is more clever than I am (not hard to believe).

I don't think the move I'm thinking of is the K17/J17 na_wspak mentioned a few posts above. If I'm counting right, it's I18 that I'm thinking of.

2. hexwiki, part 2: Please, feel free to fill in the outline I've set up, and also to change the organization of the page. We're down to 5th-level subsections, and in some sense that was leaving out one level that would have made more organizational sense. Also, does anyone know how to get rid of the stub designation. I don't think it's a stub anymore.

3. I do like the shape na_wspak and brother (Maciej, right?) have come up with. I had originally thought it would be hard to establish that whatever template we found was actually minimal, but seeing the proposed shape, I can just about convince myself already that each and every cell in the template is necessary. Good job!

4. javerberg: I would take on your program :)

Art, this should be fun! Would you like to create a thread for it, or do it more in private?

I will play rather slow, at least the first few moves.

Stub designation removed.

Art 2: I created a new article specifically to deal with the hand-written proof. I also reorganized it a wee bit. Are you happy with that move ?

thank you very much, wccanard, for your “naive” question; and for bringing this excitement to the hex community :D

and of course to all you masters who enrich our knowledge about hex :)

halladba: Yes, this is an improvement! Template VI1 does now deserve its own page. (Note: I'm looking at these only quickly, as I only have a little bit of time in the morning before getting ready for the day.) Thanks to both you and yper.

javerberg: I think in public. But I have no idea how to handle the technical details. If you can set that up, I'll play. Of course, since it's against a computer, we can all discuss the moves – we won't be giving anything away to the program! :)

Nice work to everyone to discover this new template that will be of more than academic interest to people who play 19x19 :)

I have another “naive” question: a hex on the 5th row provides a ladder escape to all ladders of the 4th row or lower. Is there a similar ladder escape from the 6th row? Or does it require more than one hex?

JJ

Art: You are right, of course. We can discuss the moves without restraints, and I will start right now.

My program, HexDruid (still didn't make up my mind about the name, but HexDruid will do for now), have proved that all but four opening moves will lose the game. The remaining moves it asserts as favorable for the attacker for the attacker, but can't say for sure.

What do you say, what move will HexDruid pick? I will let it think over the night and submit the move tomorrow morning.

Art: Don't worry about setting it up, I will just post a new picture of the board for each move.

Note: I do see the symmetry, but HexDruid does not.

This is what I love about Little Golem. A question (in this case, about edge connections) can generate nearly 100 intelligent replies. What other forum can say that? (If there is one, let me know about it.)

IMHO HexDruid should choose C/D move. Anyway it has no chance at all no matter what it choose. :)

A/B and C/D moves force the longest and the most complex attacking sequences. that's why i think HexDruid ain't concerned about them yet.

I belive you are right, but still I enjoy trying. HexDruid is actually very concerned about all four moves, but can't say for sure since it can't se all the way.

C and D are easy, and I think A and B are as well.

It's not completely symmetric, because the template is no longer symmetric.

I'm pleased to hear HexDruid doesn't want to try the cell below-left to C (or below-right to D), since that's the one I can't solve yet, at least not completely and thoroughly.

javerberg: thanks for making it easy, with the pictures!

The difference between establishing that VI1 is a template, and establishing that *some* sixth row template exists:

I was going to show tonight just how easy I thought responding to C or D is, by putting the response to those intrusions on hexwiki. And then I realized, my response doesn't work (at least nowhere near as easily as I'd thought) because I have so much less space to work with. In particular, I was counting on responding to C with A, threatening to make a bridge to either the left or right into a copy of edge template IV1d. But IV1d doesn't fit into what space is left on either side of VI1 ! So the job of filling out the details of VI1 is much harder than I'd thought it was. Even in cases where it will still be easy to play, it will take longer to describe carefully the game tree. (With infinite width, we're down to 6 moves to check, and 5 of them you only have to follow about 2-3 moves until it's reduced to a template.)

Also note that, because VI1 doesn't have reflection symmetry, we really do have to check both sides of the (almost) axis of symmetry.

I will still play your computer javerberg, and I still think I'll win, but it's not going to be the easy exercise I'd mistakenly thought it was.

I've added a little bit to the hexwiki about one of the easier intrusions (4th row), though it's not done yet. Then I was daydreaming a bit about the 5th row intrusions (A and B in javerberg's diagram). I think A and B are straightforward (at least from the human point of view, using parallel ladders when needed), and, also, the response to either one is easy – a Blue move into B forces a Red move into A, and vice versa.

I'm still not sure the best response to C and D, since my “infinite-width” response doesn't work in the confines of template VI1

@Art, the template looks completely symmetric to me…

To me as well…

Let the game begin!

It was not an easy decision where to make the first move. I wanted to try C/D, but HexDruid believe that A/B is the best moves (with a very small margin). In the end I decided to go for HexDruids opinion, but it would be fun to try C/D in a later game.

Art, is it ok for you if we play the game here, or do you think it would be better to move it to an own thread?

Yeah, it's definitely symmetric. And although it definitely requires some thinking, I'm quite sure you're gonna win, Art! :-)

Response to C should be to the right cell between B and D (if C is H5 in above board notation then response is J4) and response to D should be symetrical (I5 - H4). After this responnse there is enough space on the board to connect to bottom.

oops the notation has accidently changed:) Now this would be for C H4 and J3 for response and for D I4 - H3.

But anyway HexDruid want to lose in an other way:)

Sorry javerberg but i bet on Art:)

ooops – it *is* symmetric. As they say, “D'Oh!” And a sigh of relief to have my beloved symmetry back! :)

no time in the morning to look carefully at na_wspak's response to C. Maybe we should let na_wspak play against HexDruid starting with C in another game!

But, as I said earlier the response to HexDruid's first move is certainly I2. So that's my official response.

This thread is definitely getting large, with many subthreads going on, so we could move to a new thread, but I'll have to count on you, javerberg to do it, since I don't know how to make your nice diagrams.

I have a bit boring(?) news. HexDruid managed to confirm the template, with the help of Art and na_wspak. The initial position was too difficult, but two plies down it succeeded for both the A/B and C/D lines.

I actually had a small hope to find some defense Art, na_wspak and Marius missed. But no such luck.

For the moment HexDruid is not strong enough to find a 7:th row template, or verify that the 6:th template is minimal, at least not without either human assistance or automatic division of task into subtask (I use this to solve 8x8, but it's require rather much resources).

My next project is to tune HexDruid to play strong on 13x13, maybe this would also improve it's chances to find a 7:th row template. Btw, what is an acceptable thinking time for a 13x13 bot here at LG?

@Art, I have nothing against to continue our game if you would like to. HexDruid is not easily discouraged. I will submit a move in the evening.

That's not boring at all! That definitively answers one of the three questions I raised at the beginning of this thread! So only two left ;-)

So now in some sense there are (in my mind, which is less “tuned” to practical hex and more inspired by theoretical questions) two questions left, and they push in different directions:

1) Can the “parallel ladder” ideas which you can see in the proof of the 6th row template turn into a *proof* that an n'th row template (in my favourite sense: i.e. a win for black as player 2 in the obvious analogue of the black and white diagram above—the first of the diagrams in this thread) exists for all n? [and if so then what size board does it fit on? Does it grow linearly with n? Or exponentially??].

And

2) conversely, can one find a proof that *no* n'th row template exists, by finding some n>=7 and some board like the black and white diagram above, but with black stones filling all the vacant hexes in the 1st and last column, and where white (playing first) has a win?

after analysing some paterns of position given here on second graph, i have to say that i strongly doubt there is the one-stone-7-row template.

it suprises me, as i belived there is some algorythm that alows to connect a stone from n row to edge

i was hoping that what u call “parallel ladder” (i don't like the name BTW) is going to be also helpful from 3rd and 5th row but i was wrong…

Javerberg: regarding na_wspak's comment above, perhaps now is the time to do some naive computer searches with the following modification of the black and white picture above: first, add an extra row on the bottom. Second, fill in all the open hexes on the left and right columns with black stones. And last, shrink the entire board so that it's only e.g. 5 hexes wide. Now solve, with white playing first. This position will no doubt trivially be a win for black. But now increase the width to 6 and continue. What will happen first: a win for white, or timings becoming so long that the procedure becomes impossible to continue?

Heh. That's fun to hear, na_wspak. Earlier in this thread I guessed that the smallest size without a template would be size 6, 7 or 8. I'll look at size 7 when I get the time. It will be a lot more difficult than size 6, but I think using some hours with JHex will get you a long way. If the parallell ladder trick doesn't work, perhaps other tricks, using more space will? Seeing how easy it was to connect the 6th row stone, I assumed the 7th row would be possible, and 8th row would not.

In order to prove that a template does NOT exist, I assume proving the following would be helpful: Given a board with two blue stones adjecent at the lowest row, and one red stone above and between these stones (could someone draw this? I'm not that good friends with html yet…), it is impossible for red to connect that stone to the bottom, no matter how large the board is.

I can't prove yet that it's true, but it very much seems so to me. In fact, it nags me that I can't prove it yet. I think if we can prove this, we might use the result to prove that a certain template does NOT exist.

At the beginning of this topic, many players, including me, were convinced that no 6th row template existed. Now with all that have been done, we can say that there IS, actually, a 6th row template.

So what I want to say is : I'm now convinced that there exists a 7th row template, and even, there exists a nth row template for every n :)

Actually, I just took a look on the position that na_wspak is talking about and it seems to me that if blue just makes red laddering (on 3th and 5th row), he loses. Red just has to use the “parallel ladder trick” twice.

I had never thought about it before but this “parallel ladder trick” seems to be very powerful (but maybe not in actual play since it requires lot of space). What it basically does is transforming parallel ladders of rows n and n+2 into a parallel ladders of rows n-1 and n+1. So if you have parallel ladders of any row and enough space, you are connected to the edge. This fact convinces me that there exist a template for any row (of course it proves nothing).

alda: this “parallel ladder trick” from rows 3. and 5. can be easily stoped.

Here is an example (notation from 19x19 board):

1. H13 2. G14

3. H14 4. G16

5. I15 6. I16

7. H16 8. G18

9. K16 10. J17

11. L15 12. J18

ooh sorry moves sequence is hardly readable

1.H13 2.G14 3. H14 4.G16 5.I15 6.I16 7. H16 8.G18 9.K16 10.J17 11.L15 12. J18

Yes, double ladder trick is not as simple as what I thought before. When you are not in 2nd and 4th row, blue has more possibilities of defence.

But in your example after 1.H13 2.G14 3. H14 4.G16 5.I15 6.I16 7. H16 8.G18 9.K16 10.J17, I play 11.H17, and then it can be 12.H18 13.L5 or 12.H19 13.J15. I played a few possibilities after this and I think it's ok for red, but it would be too long to enumerate every possibility…

And there's a typo : I meant 12.H18 13.L15 of course

After 11.H17 blue play 12.J18 and it's pretty same situation as in my post above

13.L15 14.J16 or 13.H19 14.H17 15.J15 16.J16

I see no possible way for red after 8.G18. The 9th move should be somewhere on 4th or 5th row (to the right or left from G18). i tried few reasonable moves and i always find a way for blue.

But i may be wrong. Or i may not see something important;)

oops i thought it was 11.I17 sorry - change 11.H17 into 11.I17 in my previous post

yes, your responses seems nice. :)

some time ago i did an analysis (but didn't feel like it was right) that go like this: 11.H17 12.H19 13.I18 14.I19 15.J18 16.J19 17.K18 18.K19 19.N17 20.M18 21.O16 22.M17 23.N15 24.L16 25.M14 26.L15 27.L14 28.J15 29.K13 30.I14 31.J12

like u can see it need 8th row.

Anyway i belive it is not perfect.

well alda's responses seems much better than mine:)

BTW this thread is getting loooong. maybe we could start new one like “7th row template”

agree, maybe with some images????? ;) thanks

javerberg: I'm glad to hear you program solved the problem. That's quite an accomplishment. I would still like to keep going with hexwiki, and demonstrating exactly why it doesn't work (you know, identifying the possible obstructions, showing how to respond at each step, etc.) I hope you and HexDruid will contribute to this effort. We don't need to continue our game.

I second the call for a new thread on the 7th row, with pictures. Note that hexwiki has tools for easily typesetting Hex boards, at

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

@wccanard. If I understand you correctly you are talking about something like this:

I tend to agree that a white win here would prove the lack of a 7:th row template. However, it's my belief that black win regardless of width and height.

@Art. I formally resign on HexDruids behalf. It was a rather short but intense, illustrating and enjoyable game.

“However, it's my belief that black win regardless of width and height. "

But it's my understanding that not everyone thinks this ;-)

Let's stick with height 7, and always white plays first.

Imagine you start with width 5. Do you have a computer program that analyses a “general” position such as this? [non-standard board size, some counters already on the board]? Presumably it would very very quickly find a win for black. I'm hoping that we're talking about under a second, at this point. Now go to width 6. How much longer does it take to find a win for black? Now width 7? What is happening to the timings? Are they increasing quickly? Are they increasing so quickly that it looks like it would take an infinite amount of time to find a win for black by width 25? Is that an indication that black doesn't win any more?

Much of the clue lies in analysing the parallell ladder trick. na_wspak, do you have a JHex-file on this? If it actually IS possible to go from 6,4 to 5,3 to 4,2, that is, one can always go from n+2,n to n+1,n-1, then I'm sure we can prove that a template exists for all heights. However, if we are able to prove otherwise (my belief), then I think such templates can not be found above a certain height.

@wccanard: I suppose time would increase quickly. I'd say exponentially, but it's only a guess, and it's only true if the program is naive (perhaps there is no not naive program possible though). The time increasing is of course no indication that black does not win anymore. Just have a look at original Hex: winning strategy is found within seconds for size 5, within minutes for size 6, but it takes a lot of time to find one for size 19, however, the player does have a winning strategy!

Marius: my jhex file about parallel ladders is underdone yet. i did a bit of work on 5,3 to 4,2 (alda's comments were very helpful here) transition(?) and it seems like working well but i'm not for 100% sure it can be generalised for n +2, n to n +1, n-1 and then from n +1, n-1 to n, n-2 and so on… I don't have time to work on it now. I'll try to solve this problem in february, as i'm interested in it too. I originally thought (it was in fact certain to me then) that parallel ladder escape is going to be solution to n-row problem. Then i found some difficulties. Anyway i haven't worked on the problem for long.

Btw: I just found on 19x19 board “f14” is 100% connected to the bottom.To block it from bottom i analysed “f15” “f16” “f17” “e16” “e17” and “d18”. All of them are loosing. ;)

na_wspak: 5,3 to 4,2 transition exist and what is more 6,4 to 5,3 exist. I don't have the time now to look 7,5 to 6,4.

what i was trying to say is:

suppose 7,5 to 6,4 exists. do 6,4 to 5,3 and 5,3 to 4,2 and 4,2 to bottom exist after 7,5 to 6,4 transition, or at least one of them can be stopped.

f14 is a bit surprising for me to be connected to bottom on 19x19.

i wonder if any stone placed on short diagonal is connected to bottom on suitably wide board.

i wondered the same some days ago in this or another thread :)

I tried the setup above (see the figure from my 2009-01-16 post), and for a width of 13 Hexdruid finds a black win in less than a second. But for wider boards the time increase fast.

This is actually a rather hard position for Hexdruid. Due to all the black edges there are many positions in the tree with a huge amount of overlapping templates, and this cause a drastic slow down. This is mainly a tuning problem, but I'm unable to spend any time on it at the moment.

Defence against stone on short diagonal (for sufficiently large distances): Let it ladder down along the short diagonal until row 2. Then, turn and get a ladder along row 1 and 2. I BELIEVE that for a sufficiently large distance (maybe 8?), you will be unable to get any help from the starting stone, and the problem will be reduced to a single ladder along the bottom row.

Oh you mean I could haved saved the game 964204?

No, carroll, it's not the same. Marius means that Red cannot connect his stone in the diagonal; it says “nothing” about global game. In fact, in your game, Red couldn't connect his stone in the short diagonal… he connected another line ;)

You might have “saved” it; I haven't looked closely at the game. But like Gregorio says, that is not what we're discussing. We're talking about connecting the “starting stone” (g7 in your opponents case) to the edge. The ladder along the M row can never connect to g7 - just continue the ladder indefinitely (or until it reaches the edge, in a finite board. To connect g7 to the edge, your opponent would have to turn left, causing a ladder along the 1 and 2 rows.

I just did some work on the level-6 template on hexwiki, to fill in what appeared to be 3 unfinished variations (not deep stuff, I just had some time on my hands).

I think that template is now effectively finished.

Nice work, na_wspak.

Anybody for level-7?

Kevin, thanks for finishing off the 4th row intrusion to the 6th row template. But note that we're not done with the 6th row template, because there are still 5 other intrusions to deal with!

Also, for the long term, I'd like for us to show that this template is *minimal*, which may be hard, or at least time-consuming.

well, we only have to remove one empty space and see if it still connects. And this with every empty space. While you proved it's a template it was nearly evident it is minimal…

Yes, I noticed the lines that were incomplete earlier today. It's an awfully big page now, and going to get bigger. Since the organization wasn't clear to me, I didn't notice at first.

I have since worked out sufficient details for the lower-level intrusions to convince myself that it works.

Too bad hexwiki is down, or I'd put them in.

Okay, it came back up. I can't sleep anyway so I edited in one minor variation and marked 4 intrusions as stubs. Art Duval noted there were yet 5 to deal with; did I miss one?

Hello, I am a grad student from the University of Alberta researching Hex. We've verified your 6th row template by computer, and also verified that it is minimal.

We'll try and see if a 7th row one exists, but it's not high priority right now, sorry :)

Hello,

Thank you for the feedback !

Hey, thanks for that independent verification Philip! I guess you guys up there must now be bored of checkers ;-) Do you have any feeling about the other two questions at the top of this thread? [or whether n'th row templates should even exist for all n?]

Yes, checkers is `easy' now ;-)

I personally think that there is a limit on n for which nth row templates exist (one stone connecting to the edge) even if the side they are connecting to is infinitely long. However, I have no theoretical basis for this - just a gut feeling.

A couple years back I tried and failed to prove this… had trouble with defining the end of the game when the template could go (infinitely) above the nth row. Kind of reminded me of Conway's Angel problem, where an Angel win is an infinite game :) Anyways, the way you guys have defined nth row template (just use empty cells up to nth row) sounds more provable to me… although still far from easy.

If anyone is still interested in this, I would suggest that exploring 7th row templates might best be done in a contrary style: start by proving that there is no template in a 7x7 space, then in a 7x8 space, then 7x9 and so on. That should be doable, perhaps even by an algorithm. After a while the spaces will either find a template, or find the spaces are so broad it doesn't matter in any practical game size. I don't know if anyone is playing bigger than 19x19 at the moment, but go as high as you like.

You could also make it a bit more interesting, by looking for 2-stone, then 3-stone (etc.) templates at each level. I've got my own stuff I'm working on in my doddering old age, so I'll probably never get around to it.