edge connections

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.