Skip to content
Little GolemMake your next move.

Connectivity puzzle

Public forum discussion.

#1 · FatPhil

29 Nov 2013

Assuming an unbounded hex grid with a non-necessarily-axis-aligned equilateral triangle of pieces of one colour already in place. If the purpose for that colour is to connect any two of the three vertices of that triangle, and for the opponent to block that, what triangle sizes/orientations are a win for the triangle-maker? (This of course can depend on whether he's p1 or p2.)

For small triangles, it's clear the triangle will be made, but it's not clear for larger sizes, even though I can't come up with a strategy for the blocker. Like Havannah, loops become important (for the blocker), but two of them are required (or a Y that you can prove can be grown indefinitely).

#2 · shalev

29 Nov 2013

Problems like this are usually either impossibly hard, or they can be solved by a symmetry argument. For example, the question

"if, on an infinite Hex board, one player tries to surround a starting stone and the other player tries to block this, who wins?"

can be solved by a symmetry argument, while the question

"if, on an infinite Hex board, one player tries to connect a starting stone to an infinite wall of stones, and the other player tries to stop this, who wins?"

is the notorious "n-th row template problem".

#3 · David J Bush

30 Nov 2013

Uh... If this triangle consists of tokens of the same color, then aren't all three vertices already connected?

#4 · Doctor_Strange

30 Nov 2013

ah, FatPhil, that is elementary....

the angle of the dangle is equal to the heat of the meat...

#5 · Johannes Waldmann

30 Nov 2013

@shalev: about the "n-th row template problem" - what exactly is the problem?(existence of n-th row templates for some (large) n?) what is currently known? can you give a reference?

#6 · shalev

30 Nov 2013

@David Bush: I think by "equilateral triangle" FatPhil meant "three hex pieces that are equidistant from each other (i.e. they form the vertices of an equilateral triangle)".

@Johannes Waldmann: The n-th row template problem asks whether a Hex piece which lies on row n is connected to the bottom row on an infinite Hex grid. The original thread where this was discussed is

http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=339

For some reason, that thread mostly discusses the version of the problem where the (n+1)-th row is blocked. Anyway, in this thread the 6th-row template was verified by hand and later by computer. You can find a partial verification here:

http://www.trmph.com/hexwiki/Defending_against_intrusions_in_template_VI1.html

Beware, I believe the "remaining third row intrusion" section is mistaken. The template is still valid though (there's simply a mistake in the analysis).

There's been some partial work on the 7th-row template problem, but so far no one has managed to prove that it exists or even to suggest a plausible candidate. Here's a thread for 7th row:

http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=364

For what it's worth, I believe there's always an n-th row template, but I think not all top players share this belief. My intuition comes from the fact that, as Maciej says in the 6th-row thread, it seems to be the case that the 4,2 double ladder trick generalizes to 5,3 and 6,4, and therefore maybe to all double ladders.

#7 · FatPhil

1 Dec 2013

I can believe that some things can become impossibly hard in general. However, like the n-th row template problems, each size/arrangement can be considered individually.

At would size would the best players be prepared to play the edge-connecting player?

#9 · FatPhil

2 Dec 2013

My depth of knowledge isn't enough to know how many of the moves in your sequences are forced moves for the loser, but thanks for contributing some useful data points. That's a pretty narrow "possibly interesting" band you've narrowed it down to already.

The next size up from 4 seems to be this:
http://www.trmph.com/hex/board#19,g12a1l10a2j7

The next size up after that, seems to be a win for the edge-maker if he's given the first move:
http://www.trmph.com/hex/board#19,g12a1l11a2k7b1j10
I would guess that symmetry (j10) would be least bad for blocker if he's given the first move too
http://www.trmph.com/hex/board#19,g12a1l11a2k7

whether any of those remaining ones sits interestingly on the line between quick win and quick loss, I don't know.

#10 · shalev

2 Dec 2013

On
http://www.trmph.com/hex/board#19,g12a1l10a2j7
and
http://www.trmph.com/hex/board#19,g12a1l11a2k7
blocker will win if given the first move.

If the edge-maker gets the first move, he wins on edge length 5:
http://www.trmph.com/hex/board#19,k7a1f12a2k12a3h11j10i9j8k8j9i12j12k11j11l9
but not on edge length 6, I think. I'm least sure about edge length 6.

The size 5 and 6 ones where the edge-maker gets the first move seem to be the most interesting, but they're still small enough to solve by hand.

What's the motivation for this problem?

#11 · FatPhil

3 Dec 2013

I have no idea what made me think of it. I suspect it could have just been some symmetrical shape I saw on a board, with the idea that if X connected to either Y or Z, then there'd be a victory, (but that Y to Z was useless). The triangle stuck, and the the edges of the board disappeared - and tada, the idea was born.

Axis-aligned size 6 has a naive distance of 6 between corners. (Smaller) distances of sqrt(27), sqrt(28) and sqrt(31) are possible too, if blocker's job is too hard. Not that Hex necessarily respects Euclidean distances at all.

Thanks for your input, I hope you're getting something out of this little challenge too.