Some basic conjectures on infinite hex boards

Here are some closely related conjectures. I think the propositions - at least 1b and 1b' - are more or less "obviously true" for experienced hex players, and I'm sure they are not new, but I don't remember reading about them.

In the following diagrams, the edges are to be ignored, and the pattern in the center is supposed to go on in all directions.

Conjecture 1:

On this infinite hex board, let S be the set of all cells c for which holds: c lies above the "center row" i.e. row 11 in this diagram, and if black placed a piece on c, then c would already be virtually connected to the infinite chain of black pieces (on row 11).

Let d ("diagonal") be the short diagonal, i.e. the line that goes through j10 and k9.

Then S is exactly the set of all cells that lie above the "center row" and on d or to the right of d.

Conjecture 1 consists - more or less(?) of two conjectures:

The short diagonal is a subset for s, or equivalent Conjecture 1a: For every n, there exists a single piece nth row template, that doesn't contain any cells "left from the short diagonal", but may contain cells above the piece, like this 4th row template.

j9 is not in S, which is more or less(?) equivalent to the following Conjecture 1b: On this infinite hex board, black cannot connect the two infinite black chains.

A similar conjecture is Conjecture 1b': On this infinite hex board, black cannot connect the two infinite black chains, either.

I attempted to prove 1b and 1b' by pairing up cells, similar to the winning strategy on a nx(n+1) board, to no avail.

My impression is that 1a is certainly not known, may be hard, and not every strong player believes it to be true. But I agree that these are interesting questions. The word "conjecture" used to mean "something that is undoubtedly true but there is no proof yet", rather than the more general "question", which is something which people are less sure about and which may go either way.  I think though that nowadays people are throwing questions about and calling them conjectures; the distinction seems to have gone away. Are you 99.9% sure of your conjectures?

On 2009-01-22 in this thread, na_wspak raised the possibility that any stone placed on the short diagonal is connected to the bottom, after Maciej Celuch (also on 2009-01-22) had just claimed that this is true for a stone on the 6th row. I think that this might be an even stronger version of your conjecture 1a.

Interesting questions! My impression is that no-one currently has the tools to study them. na_wspak tried to get a general formalism going with a parallel ladder trick (for the general problem of connecting a far-from-the-edge stone to the edge) but gave a line in that thread that seemed to refute it.

Oh. No I'm not 99.9 percent sure of these propositions. Maybe 95% sure.

With respect, wccanard, urmaul's use of the word conjecture is completely correct.  The term carries no implication whatever of percentage certainty, except insofar as the conjecturer, having taken due thought, cannot at the time of writing see a refutation - it's simply an educated hunch thrown 'out there' as an implicit challenge for proof or disproof.

As a noun, it's exactly equivalent to 'hypothesis', and, as a verb, to 'hypothesise'.

My source for the claim about a conjecture being "surely true" was Professor Sir Peter Swinnerton-Dyer, who was at the time complaining that conjectures are not what they used to be. He made a famous mathematical conjecture in the 1960s. I think Swinnerton-Dyer would be happy with 95% though :-)

Actually, whatever Sir P S-D thought a conjecture should or shouldn't be doesn't greatly signify.  He was a mathematician.  History is full of people who painted brilliant pictures but couldn't necessarily have given you a reliable definition of art.

Speaking of proving things, can anyone even prove the basic claim that ladders don't connect by themselves? In other words, that black can't connect the stone to the bottom edge here (with black to move, on an infinite board)?

shalev: I guess not. Seems related to part b of -theorem- hypothesis 1, or more exactly that pieces immediately left from d can be countered by playing next to it on d, like this (don't know if this is new information). I wonder, can anyone prove that black can't connect when white gets some additional stones, like this? :-) ...Maybe this one is easy to prove, but at the moment I don't see how.

Let me raise some even more basic questions.

First some notation. A cell is a hexagon on the board (it can be occupied by a black or white piece, or empty). The boundary of the cell are the six sides of the hexagon. Let's say two cells are adjacent if they share a boundary. The distance between two cells is the smallest number of boundaries that you have to cross in order to get from the centre of one cell to the centre of the other. For example, adjacent cells are distance one apart. On a 2x2 board the two cells on the long diagonal (i.e. the cells in the two acute corners) are a distance two apart. On a 3x3 board those acute-corner cells are distance 4 apart. And so on.

Let's say a cluster is just a collection of cells on a board (the board and the cluster can be finite or infinite). The cells in the cluster don't have to be connected or anything -- a cluster is just a collection of hexagons. We can define the distance between two non-empty clusters A and B to be the smallest distance from a cell in A to a cell in B. Here's an example.

Forget the white stones. Imagine the black stones as two connected clusters -- one of size 3 and one of size 4. These clusters are distance 4 apart, because if you choose any stone in the top cluster and any stone in the bottom cluster, the distance between them is at least 4, and conversely there is a stone in the top cluster and a stone in the bottom cluster such that the distance between them is exactly 4.

Now let's say we have two non-empty disjoint clusters of cells in a board (possibly infinite). Call them A and B. A template for those two clusters is the following. It's an actual hex position. It's a collection of cells, that contains both clusters and probably other cells too. Each cell in cluster A and cluster B has a black stone in. Other cells not in A or B can have stones in too -- either black ones or white ones -- or they can be empty. But this template has to have the following property: if we play a game of hex on this collection of cells, with white to play first, then black can always establish a connection from a black stone in A to a black stone in B.

All this is, is just setting up terminology. Standard edge templates that every reasonable player knows are templates which connect a one-cell cluster to an edge, and the edge can be regarded as a cluster which is just a line of cells.

Now here's a positive result: given any positive integer n, it's possible to come up with a template which has two clusters in, A and B, and no other black stones at all, and such that the distance from A to B is n.

In particular I am saying that it really is possible to prove results of the form "this area connects to this area even though they're a long way away".

The proof is simple once you see the trick: it's just a re-interpretation of the standard result that hex on a parallelogram with one pair of sides bigger than the other pair is always a win for the person who has to travel the shortest distance, even if they start second. Here's an example. Ignore everything above the top row of black stones.

 Imagine the two lines of black stones as two connected clusters. Even with white to play first, black can connect these clusters. Of course this is obvious to any experienced player, but here's a proof which works however far apart the lines are, as long as the lines are longer than the distance between them: connecting the clusters here is asking black to win a game of 13x8 hex, and even if black plays second black can win using a mirroring strategy; black divides the board into two triangles (and an irrelevant area here, which we throw away; it would be two triangles exactly if it were 13x12) and plays a reflected move at each stage.

So this example gives us hope that we can connect clusters which are a long way apart.

*However* I want to raise the following question. I don't think I've ever seen a template which has all these properties:

a) it has no black stones in it apart from those in the two clusters

b) one of the clusters only has one stone in

c) the distance between the two clusters is large.

By "large" I mean something like "at least 15". However if someone promptly replies to this post with a hex position containing one black cell in the middle and then a gigantic hexagon of side length 16 around it, plus a proof that the centre can be connected to the outside, then I will just change my definition of "large" to mean "at least 25". Basically we are trying to play the following game: black has one stone, and black is trying to connect to something a long way away, and white is trying to get a ring of stones around black's stone. Let's call this the "encircling game".

Here's a question then. Is it true that however large N is, black always wins the encircling game?

Here is a picture of the distance 8 encircling game.

No, there is no picture, because this forum is crappy. Here is a link to the distance 8 encircling game.

encircling game

Ignore the white stones. White plays first; black has to connect the centre stone to any of the outer stones.

That looks really easy, don't you think? But what about the distance 100 encircling game? Who wins this? General theory says that someone has to win; either white can encircle black or black can make it to the end.

Probably experts will believe that black always wins the encircling game, however large the board is. Maybe a proof is easy! However until we have a proof of this, it is clearly impossible to prove any of the statements above in this thread that involve assertions involving connecting things which are an arbitrary distance apart.

What I am saying is that I am trying to formulate the easiest possible assertion that involves connecting one single stone to a collection of stones a very long distance apart. If we can't prove this, we can't prove anything and in some sense there's little point wondering about more general questions.

I have no idea why I can't post a picture of the encircling game of size 8.

I should say that I think I've seen this encircling question raised elsewhere -- either on the internet or in Cameron Browne's book. It's only as I've written this post that I understand the significance of the question.

JH. Conway...  Angel and Devil problem on an hex board.

Here is the forum where it was discussed  https://www.google.fr/url?sa=t&source=web&rct=j&url=http://www.littlegolem.net/jsp/forum/topic2.jsp%3Fforum%3D50%26topic%3D415&ved=0ahUKEwj-xfXQ4azMAhULDxoKHTF1C10QFggdMAE&usg=AFQjCNHarUYrhaS_1ACzmKvNfX6yaoxzUg

Or https://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=415

I have not re-read it all...

It's related but different. In angel and devil the angel moves around (typically via some bounded amount). Here we're just playing hex. It's clearly related but I think it's a little different. The fact that it's related to a hard problem might mean it's also hard.

The encircling problem is a win for black by a symmetry argument (assuming you're asking what I think you're asking). Black simply plays the following strategy: for any stone white plays, he plays the reflection of it across the center stone, like this.

shalev -- this is great! What I am trying to do is to find the simplest "natural" question that we can't answer and you've answered this one. I fear that the next one is one that I raised on this site in about 2008 and which still seems to be open -- is there a template which connects an infinite (in both directions) line to a stone which is a distance n from it? As far as I know this is still open for n=7 although a conjectural solution has been posted on this site. I've had benzene working on the verification of a variant of this for about a week now but it's very slow going.

I also asked the encircling question to myself not long ago, and I didn't think of the mirror strategy. Now, what happens if white gets an additional piece in the starting position, and it's mirror image, like this? The mirror strategy won't work anymore for black, no matter how far the additional white pieces are away. So, does anyone know a strategy for black to prevent white from encircling the center when white gets two additional pieces, 1000 cells away from the center?

In my mind if player A could encircle player B then also player B could encircle player A which is impossible. Obviously one could encircle another given big enough X stones of advantage and X is positively correlated with the size of the board. From experience we know that as play continues the single stones' impact decreases, so I would imagine both players trying to encircle a particular stone of each other would eventually form two parallel shapes. Regarding the problem of connecting a single stone to an infinite board edge - my intuition tells me it is possible to connect for every given distance (and it is related to my above imagination of parallel shapes), but I think there is no global pattern for doing it.

wccanard, welcome to hex, our silly game... i advise you to play with arek on iggamecenter, i'll come there next month...

first of all, let me say that i like your point that "conjecture" should be something we believe in actually!

second, I believe a single stone on the short diagonal can always be connected to a side of the board, if the side is sufficiently large, but I actually don't remember if the moves on the left of the short diagonal are needed or can be safely ignored.  I would say that probably they're needed in the general case.

third, don't waste too much time on the study of large templates, because in actual games they do not happen in games played on reasonably sized boards. What deserves to be studied are the "templates" with few well played stones... and indeed it's very hard indeed to find what to study without playing vs strong players...

Oh. When I wrote "The short diagonal is a subset for s, or equivalent Conjecture 1a: For every n, there exists a single piece nth row template, that doesn’t contain any cells “left from the short diagonal”, but may contain cells above the piece, like this 4th row template". I made the mistake of allowing moves on the left side of the diagonal in the first proposition and disallowing them in the second. I believe the pieces on the left are not needed, but... now I feel far from 95% sure.

With "pieces" on the left I mean cells.

Hi lazyplayer. We played a couple of games of hex at iggamecenter in around 2009, when I was at my peak in dots and boxes and knew absolutely nothing about hex.

Here are my thoughts about studying large templates. We have to put these things into context -- I had probably played about 10 games of hex in my life at the beginning of 2016 and I've decided I want to give it a go and learn something about it. From reading the theory I've realised that general template problems are something I find quite interesting. But I find them interesting for more than one reason. Firstly there is the theoretical aspect to it all -- e.g. is a stone on the 1000th row connected to the edge on a hex board of size 1000000? It seems that no-one knows this. But there's a much more practical side to my interest too. Already I found that I had to learn how to connect a 5th row piece to a large edge and that this happens in practice on the board. And then I realised that much more complex things happen too, involving a piece on the 5th row and a few other pieces dotted around, and then I realised that the strong players were just playing these areas intuitively and I guessed that this was because they had seen all of, or perhaps the vast majority of, the "tricks" involved in making a connection. So I decided to learn these tricks by working through all the templates I could find. I'm in the process of doing this now, working through Dr King's site and making a personal collection of extra edge templates which aren't on that site but which I can prove are templates (either by hand or by computer analysis). And the idea is that ultimately I'll just get to the stage where I can play these templates intuitively because after a while the details will fade a little and turn into general principles which I can apply.

Now I suspect that even with a question like "is this 6th row piece connected to the edge via a gigantic template", there is some merit in thinking about this problem, because you start to get more of a feeling about what is possible. There seem to me to be lots of tricks. Here is an example. you have a piece that wants to go to the edge, but there's another piece directly in the way. So you "peep" one way around this obstructing piece, the opponent has to respond, and then you run the other way and the "peep"ing piece is the crucial ladder escape or what have you. I am only now learning the basic variations on this theme; some "peeping" moves look equivalent to others but are not because they can be met with a response which blocks the immediate threat as long as the longer-term one. I need to learn a lot of these ideas and I need to learn them as quickly as possible, so I need to play through all these templates until I have understood the general principles.

That's my plan anyway. I did this with dots and boxes and it worked really well. I started off by analysing nim-values of various positions, and playing through all the lines. When I was doing this I created a whole bunch of dots and boxes puzzles, which are still here on the dots and boxes forum although the general "change it a bit and hope it works better" nature of this site means that none of the diagrams that I painstakingly typeset in 2009 are now readable. Making those puzzles just made me understand more about the general principles of playing regions in dots and boxes, and after a while I would see a region and would have a really good feeling for it -- "the second player can force a chain but they'll need to sacrifice a box", and after a while much more subtle things like "there is a move in that region which turns it into an interesting region which has a nim-value of 2 but to change it to a nim-value of 0 one needs to sacrifice more boxes than to turn it into a nim-value of 1" (it turned out that these positions were quite rare and knowing when and how to use them was a subtle tool which occasionally was very useful). Just silly things. And everyone else was saying that working on nim-values was a waste of time. But it worked for me. Similarly I want to work hard on templates and if I get the hang of the small ones I want to work on big ones until I see what is happening. I don't want to be scared of a single stone on the 6th row and at the minute I'm terrified of it because I haven't seen enough techniques. And part of me would really like to resolve the 1000th row question by formulating a general technique. Some people seem to think that this is not possible, so how about proving instead that these questions are PSPACE-complete or something? There are lots of interesting questions here. But anyway, there are some reasons why I want to think about all templates, even big ones.

in fact i've just done some experiments on http://www.trmph.com/hex/board#19,f14 in IGG with wurmfaul, and the result is... i no longer find any hope for black...

wccanard, and... in general i totally admire your systematic approach!

but the analogy with dots and boxes is misleading because dots is a game with few possible endings, so it makes sense to start studying from the endgame... hex instead is a game with many endings, so it does not make sense unless you can somehow magically select the "realistic" endings among all possible endings...

indeed, the only "math theory" that somewhat applies to hex is graph theory, with the "Shannon switching game" applied on edges instead of vertxes...

and here is a nice puzzle i've built, taken from the 7x7 solutions:

http://www.trmph.com/hex/board#11,b2e3b5h1a8h2b8h3c8h4d8h5e8h6f8h7g8 :)

f4: Did you allow black to play north-west of the short diagonal?

Templates: because I am just learning the game and I have three times now come up with "here is a ladder on row {2,3,4} -- can it connect to the edge because of that random piece on row 5?" (that's 3 games out of about 15) I think I need to understand that properly. I can't keep walking into the same situation again and again without knowing how to play it. I just need to think about a lot of things my way and then decide which stuff is important; only then will I understand the wisdom in your words!

Oh -- and math theory -- who knows what applies. That's the joy of math :-)

yes i allowed any play... i failed to solve this: http://www.trmph.com/hex/board#19,f14f16i14g14e16f15e15d18e17e19

This white move blocks black, so you'll need some cells on the 7th row (or more than 19 columns). Maybe that was already clear -- you need some cells on the 5th row to break through with a stone on the 4th row short diagonal, I believe.

wccanard: Maybe it wasn't clear, but the converse would have been very surprising. I'm pretty sure it's true that you need 5th line cells to connect to the bottom with a stone on the 4th row short diagonal. So, does anyone know a way for black to connect f14 to the bottom, after white f16, assuming there is infinite space towards the right side?  In the old thread that wccanard linked, Maciej Celuch wrote: "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”."

Black has to connect to the top somehow so all 6 hexes around f14 can't be part of the template as far as a hex solver goes (unless you hack the solver I guess). This position gives black 5 stones around the template -- shall I try to solve this?

The solver hasn't proved anything after 1 hour but the move that I think it seems most excited about is e16 currently. This may change. I am tempted to ask you what you would play after 1.f16 2.e16? If there's only one or two obvious responses then I could try and take it from there. The second-most exciting move is currently 2.e15 but the solver currently likes e16 far more.

link to trmph

After e16 there is only one move: d18.

Well, you can force at f15 first. That probably doesn't make any difference, but for me it's making the position simpler.  I don't know whether it makes any difference, but there should be white pieces from h1 to s1. I think the solver is not well suited for this problem, since it doesn't know heuristics like conjecture 1b. If I remember correctly, even this position seems hopeless for the solver on my hardware.

Oh yes, apologies: in the solver I remembered the other white pieces. trmph just insists that the players take it in turns so it's less easy to set up a random position. I don't know how to run the solver multithreaded so it might take months to solve this position, and there's a bug which means that the solver occasionally crashes, so there's every change it will never solve the position. I also left an analysis going of a single piece on e15 (no-one ever talks about that -- is it for some reason clear to the experts?) and overnight the solver refuted none of d19, d18, e16.

@urmaul: that 2nd row ladder position: is your point that "white obviously wins"? I don't see why -- this looks harder than the "does a single stone on the 7th row connect to the edge" question that still seems to be open (but perhaps the reason it's open is that the minimal template doesn't fit on a 19x19 board?)

wccanard: Yes, my point was that white obviously wins in the 2nd row ladder position. This is what conjecture 1b is about.

B ut you can't prove it, right? And probably the solver will choke if it starts considering random moves for black like i8, right?

About that 2nd row ladder position: As white, choose the following strategy: If black plays a stone that connects to his leftmost group, play to the low right of his rightmost stone in this group. If he does NOT, then expand your own group in the way that most encircles white (not very precise, I know, but this should always work, I think). Perhaps someone else can word it better, but I'm pretty sure this is always a winning strategy in this situation.

EDIT: (I wish I could edit my post directly...)

About that 2nd row ladder position: As white, choose the following strategy: If black plays a stone that connects to his leftmost group, play to the low right of his rightmost stone in this group. If he does NOT, then expand your own group in the way that most encircles black's leftmost group (not very precise, I know, but this should always work, I think). Perhaps someone else can word it better, but I’m pretty sure this is always a winning strategy in this situation.

I'll have a try:

- let call lowness of a black group the height of the highest pawn of the shortest path connecting it to the ground, for example in this position, the shortest path is e11-e12-e13,

so the lowness of black group is 3.

- to win, black group's lowness should go to zero from its initial value of one.

- if White plays this stone (in the position e11), Black can not decrease its lowness except if he has a knight move down right. But White by playing the highest moves in the shortest path would play two moves which would cut the knight move pawn from the group:

like here, increasing Black's lowness.

Marius and Carroll -- say black plays three or four more ladder moves, and then one or two random moves a long way from theri main group (note that black has a big perimeter now so according to Marius white is encircling this group but this will take a while -- more than two moves) -- and then black starts going upwards with moves like d10.  Something like this:

trmph

Now Marius' idea of randomly playing to the bottom right sounds very risky to me -- white should surely be playing random obstructing moves between black's pieces but black has had several moves in which to set up some more dangerous possibilities for linking to the bottom.

Not yet dangerous, but my very simple algoritm won't work, I agree. I think, however, we should be able to construct an argument along the lines of "if black in this position is enable to "encircle" white, then by some symmetry, white should be able to encircle black, which proves that black cannot encircle white". Now, the shaky part is "by some symmetry". This may not be easy, but I think it can be done. Maybe.

Maybe it can be done. I think that this question ("prove a second row ladder cannot connect if there is no escape stone") is another very interesting one.

One problem to finding some kind of symmetry strategy is that the starting positions of White and Black seem very different.

Another idea is to find some kind of measure of how bad the position is for Black, and prove that White can always answer Blacks moves so that the worseness of the new  position is higher than before black moved. A problem is that (I think) since hex is PSPACE complete, one cannot find such a measure for arbitrary hex positions. The measure would have to be restricted on some set S of positions, and one would have to prove that white can always simplify the position into a position that's in S. Which seems very difficult when black plays very far away from the initial white piece.

Here (Please ignore the edges, this is an infinite board) is an even stronger version of conjecture 1b, designed so that Black m8 barely doesn't work. Let's call it 1b'. I'm not sure at all black still cannot connect somehow in 1b'. Whether Black can connect or not, maybe this helps in proving 1b, somehow. Or maybe it doesn't help at all.

Yes, hex is PSPACE-complete but the proof involves some fairly complex positions. As far as I know the only reference is still a paper written in German but I've seen a sketch of some of the ideas. So yes it's unlikely that we will stumble upon some simple value function that works in general but as you say this doesn't rule it out in theory for simple positions. I wouldn't be optimistic though because what's stopping one player from playing towards a more complex position?

Black can connect 1b'

wccanard: Yeah, I'm not optimistic either.

shalev: I think you're correct. But I also think black must not play j12(n8 on the old board) too early. Actually I looked at similar variations before, but somehow came to the wrong conclusion, apparently. It was silly of me to claim m8 doesn't work.

I shouldn't have called this question 1b', since I already used that name in the first post of this thread. I propose calling it 1b* instead - just in case there is something left to say about it.

I'm not so sure about 1b*

regarding f14 against rest of the world I think solver isn't even close to capable of solving that. The way to go should be o14 or p15