edge connections

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?]