8x8 hex –The solution

I'm currently trying to solve 8x8 hex. With "solve" I primarily mean to settle the game theoretic value of all opening moves.

So far I managed to calculate the game theoretic value of three unique opening moves.

The stone in each one of the none empty cells shows who win with perfect play if white moves first into this cell.

Forgot I was logged on as nanobrain. Sorry for that.

Well, A1 is a proved losing first move on any size. ;-)

True! And some other opening moves are solved too. I do however aim to solve even the previously solved moves.

8x8 is by the way harder than I first thought. 7x7 I can solve in a few hours on a single computer, but for 8x8 I so far have had about 10 computers working for several days.

By the way, I have been interested in solving normal and double-move Y on the following board for a long time:

Would that be feasible?

I'm afraid I don't have any good answers to give. I believe I know the rules of the game, but I have never played it.

With that said, the game do looks possible to solve. The game is more complicated than hex, but there is rather few cells. Very tempting to give it a try, but my hex solution algorithm would need some serious modification and I do feel a bit short of time at the moment :(.

@isometry: what's the proof that 1.a1 is losing?

1.a1 wins on a 1x1 board ;-)

Yes, I forgot to single out that case. I remembered just after posting.

I don't remember the exact argument, but I think it is something along these lines: Suppose the board is at least 2×2, and that

(a) 1. A1 winning.

Then it follows that

(b) 1. B1 is winning.

But then white can counter 1. A1 with 2. A2, which must be a win for white by (b).

Update: Four more opening moves got solved. We now have 7 solved unique opening moves.

About A1: The computer consider this as an almost certain losing moves, but have not yet been able to prove it.

Have you solved the 1.H1 case?

Any bets, anyone, on the outcome?

In the above argument, I assumed that black moved first.

Agree, H1 is an interesting opening move and I look forward to the solution. However, the solution is rather far away, and the program still judges both sides close to equal.

My understanding from talking to some people at iggamecenter was that on smaller boards (2x2 up to 7x7), A1,B1,C1,... all lose for player 1, right up until the "obtuse corner", which is a winning move. So if I were a betting man I'd guess that on an 8x8, with the above notation, 1.H1 will be a win for white.

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

I don't think the 10×10 moves are proved?

I bet H1 is winning. In fact, I think any opening move on the short diagonal is winning on any size board.

http://www.cs.ualberta.ca/~queenbee/openings.html

gives solutions for hex-with-swap up to 6x6. isometry: what is the source for the hexwiki 7x7 board in the above link? Is this just "what is generally believed" or is this computer-checked? The hexwiki is very unclear at this point as to whether it is making proven statements or statements of the form "this is what everyone thinks".

I don't know the source, but I've heard somewhere that 7×7 was solved (and presumably not by queenbee), so I would guess the info for this size is true.

7x7 is solved. Check here for details.

Update:

Now my program agrees that A1 is a loosing move. :)

According to this page:

http://www.ee.umanitoba.ca/~jingyang/

Hex has been solved up to 9x9.

To my knowledge both 8x8 and 9x9 is unsolved for all but a few openings. The page you refer to claims that the middle cell in 9x9 is a win for the first player, but says nothing about the other openings.

javerberg: sorry, i didn't look carefully at the links.

Art, you got me worried for a few moments. :)

Here is next update:

Sorry for the lacks of updates. Solved a few more opening moves, but there is still much calculations need to be done. Very hard to estimate how much time is needed, but I do have hopes it will be done within a few weeks.

On Little Golem, the first player moves North/South, whereas you have choosen East/West, Javerberg. That is a bit confusing. And it becomes directly wrong on the wiki, as for sizes 1-7 the first player moves N/S, one must assume the same is true for 8x8. Would it be much trouble for you to rotate the board? At least for me, that would make it much easier to percieve (here, the common a3 opening is suddenly c1). Otherwise, great work!

I second Marius' suggestion, except I think the board should be *reflected*, not *rotated*, to also keep the same geometry as LG.

I also second the congratulations of javerberg's work here (as well as with the 6th-row template).

:-)

You are both correct, of course. When I post the final solution I will make sure the vertical player starts the game.

Any progress ? Anyway, thanks for the good work done so far. As a side question, do you keep the refuting moves in memory when the opening is losing (at least one of the moves)?

The program completed earlier this week, and I will present the result here today or tomorrow. I will also update the hexwiki article for Small_boards.

Hallabada, I saw you already transferred the results from the figure about to this page. Thanks! You forgot to reflect the board (See Marious post above), but I fix this when I post the rest of the result.

I did keep the refuting moves, but note that I only have the top part of the tree saved (a few tens of millions positions). The bottom part was handled by the clients, and never reached the server.

Halladba, sorry for the misspelling of you name. My bad.

Shall we wait until tomorrow for the 1.h1 case/bet?

Marius and I bet that it's a win for the first player. Noone bets on the loss outcome?

@Javerberg: Will you publish your result in an academic journal? It was only in 2005 that a solution for 7x7 Hex was published. Note: This is for starting from an empty board. The proof that Hex is PSPACE complete starts from a board with arbitrary content. http://www.cs.ualberta.ca/~hayward/publications.html, http://www.cs.ualberta.ca/~hayward/hex7trees/

@ypercube: Because the short diagonal contains only winning first moves on the 7x7 board, I'm with you and Marius.

@javerberg:

Please, hang it in already today.

The tension is unbearable !!!

Ingo.

Thnx for the suppost Marley!

I would be in the opposite site of Marius though, were it for the 88x88 board!

Solution:

H1 *is* a winning move! So ypercube, Marius and MarleysGho are all correct!

As you can see at this hexwiki page the 8x8 solution is very similar to the 7x7 solution.

So exactly half of the cells are winning!

Yes, noticed that too. Wonder it that's true for some other sizes than 2x2 and 8x8... :)

Good job, Thank a lot!

*Thanks a lot!

Great work, javerberg!

H3 looks funny ...

thanks for the good work :)

Congratulations, javerberg!

No wonder I lose so often when I start with 1.a3 ! :)

Great work, javerberg!

Will you start on the 9x9 case now? :)

Very cool. I'm surprised F2 loses.

Great work indeed! Yeah, F2 surprises me too, David.

Thank you all for all the encouragement!

It's very tempting to try 9x9, but with same algorithm and hardware I believe it would take at least a decade. Beside it's 10x10, the old playsite size, I really would like to solve.

Also tempting to try to turn the program into a strong engine for 13x13 hex. However, on the top of my list is to try out some algorithm improvements. Most likely they will not give any thing extra, but if they do I can try to use them both for the 13x13 engine and 9x9 solving.

Tim, h3 looks as funny as g3 in the 7x7 solution :)

For me a4 is a big suprise;)