8x8 hex –The solution Hex, Havannah

81 replies. Last post: 2012-11-13

Reply to this topic Return to forum

8x8 hex –The solution
  • NanoBrain-ai at 2008-12-30

    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.

  • javerberg at 2008-12-30

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

  • isometry at 2008-12-30

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

  • javerberg at 2008-12-30

    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.

  • isometry at 2008-12-30

    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?

  • javerberg at 2008-12-30

    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 :(.

  • wccanard at 2008-12-31

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

  • wccanard at 2008-12-31

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

  • isometry at 2008-12-31

    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).

  • javerberg at 2008-12-31

    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.

  • ypercube at 2008-12-31

    Have you solved the 1.H1 case?

    Any bets, anyone, on the outcome?

  • isometry at 2008-12-31

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

  • javerberg at 2008-12-31

    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.

  • wccanard at 2008-12-31

    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.

  • isometry at 2008-12-31

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

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

  • Marius Halsor ★ at 2008-12-31

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

  • wccanard at 2008-12-31

    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”.

  • isometry at 2008-12-31

    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.

  • javerberg at 2008-12-31

    7x7 is solved. Check here for details.

  • javerberg at 2009-01-01

    Update:



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

  • Art Duval ★ at 2009-01-01

    According to this page:

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

    Hex has been solved up to 9x9.

  • javerberg at 2009-01-01

    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.

  • Art Duval ★ at 2009-01-01

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

  • javerberg at 2009-01-02

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

    Here is next update:



  • javerberg at 2009-01-12

    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.

  • Marius Halsor ★ at 2009-01-13

    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!

  • Art Duval ★ at 2009-01-14

    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).

    :-)

  • javerberg at 2009-01-15

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

  • halladba at 2009-02-04

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

  • javerberg at 2009-02-05

    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.

  • javerberg at 2009-02-05

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

  • ypercube at 2009-02-05

    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?

  • MarleysGhost at 2009-02-05

    @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.

  • Ingo Althofer at 2009-02-05

    @javerberg:
    Please, hang it in already today.
    The tension is unbearable !!!

    Ingo.

  • ypercube at 2009-02-05

    Thnx for the suppost Marley!

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

  • javerberg at 2009-02-05

    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.

  • isometry at 2009-02-05

    So exactly half of the cells are winning!

  • javerberg at 2009-02-05

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


  • halladba at 2009-02-05

    Good job, Thank a lot!

  • halladba at 2009-02-05

    *Thanks a lot!

  • FatPhil at 2009-02-05

    Great work, javerberg!

  • Tim at 2009-02-05

    H3 looks funny ...

  • Gregorlo at 2009-02-05

    thanks for the good work :)

  • MarleysGhost at 2009-02-05

    Congratulations, javerberg!

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

  • ypercube at 2009-02-06

    Great work, javerberg!

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

  • David J Bush ★ at 2009-02-06

    Very cool. I’m surprised F2 loses.

  • Marius Halsor ★ at 2009-02-06

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

  • javerberg at 2009-02-06

    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.

  • Gregorlo at 2009-02-07

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

  • Maciej Celuch at 2009-02-09

    For me a4 is a big suprise;)

  • Ingo Althofer at 2009-02-14

    @javerberg:
    Thx for your computations and for presenting
    the results here in the forum! It is really
    interesting to watch at the “first-move outcomes”
    and meditate about the structure of the red and
    blue landscapes.

    I have been thinking about the following variant
    of Hex (call it “Hex-O” for instance). It has the
    normal rules of Hex, but there is one more winning
    condition: a player wins immediately when he creates
    a closed cycle with at least one inner square (let it
    be empty or filled). (So, this is the third winning
    condition from Havannah.)

    Questions
    * How difficult would it be to compute “first-move outcomes”
    for Hex-O?
    * Especially, would it be possible to compute the Red/Blue
    landscapes for board sizes 6x6 and 7x7 (and 8x8) in reasonable time?
    * Will there be a board size for which the landscapes of
    Hex and Hex-O differ in at least one square? (If yes, which would
    be the smallest one?)

    Ingo.

  • Ingo Althofer at 2009-02-14

    One additional thought on Hex-O:

    For Shannon’s switching game (with Mr. Short
    and Mss. Cut) it is known that addition of
    a cycle winning condition does not change the
    outcome for “all normal” starting positions.
    Ingo.

  • christian freeling at 2009-02-14

    Hexannah? ;-)

  • Gregorlo at 2009-02-14

    i had the same thought as Christian the very single second i read Ingo’s post ;-)

  • David J Bush ★ at 2009-02-14

    Ingo, is that the edge-switching game or the vertex-switching game?

  • Ingo Althofer at 2009-02-14

    @David J:
    > is that the edge-switching game or the vertex-switching game?

    I mean the version with a rectangular grid, where Mr.
    Short wants to connect northern and southern side,
    and where Mr.Short in each of his terms fixes an edge,
    and Mss.Cut in each of her turns deletes an edge that
    is not yet fixed.
    On quadratic grids the first player to move has a winning
    strategy (for the empty board) - by symmetry+strategy stealing
    argument.

  • Ingo Althofer at 2009-02-14

    > Hexannah? ;-)

    @Christian,

    Sometimes it is strange with names of games or programs.
    Yesterday in my seminar, a student gave a presentation on his
    programming work on connection games. Amongst others he
    mentioned the strongest Hex program available: Hexy.
    Believe it or not, but directly after this innocent word
    “hexy” had filled the room, noise came from a part of the class
    which is typically more or less silent when game topics
    are discussed ... Perhaps they had understood “sexy” or whatever ...

    In any case, just shortly after that moment I got the idea of
    Hex with cycle criterion – and immediately also had the intuition
    to call it Hex-O ... (Pronouncing it Hex-oooh might again lead to
    a reaction from the part of class mentioned above.)

    Ingo.

  • christian freeling at 2009-02-14

    @Ingo

    Naming games is an art in itself. As it happens Havannah was chosen by blindly opening a dictionary and tapping a finger. Actually it said Havana, but that looked a bit too much like a cigar.

    The idea of ring threats in Hex would certainly alter the game considerably, and you might adapt a program accordingly to get a better grip on it in a Havannah program.

    Let’s call it Hosannah ;-)

  • Tasmanian Devil at 2010-04-19

    There is a published article on 8×8 here.

  • Philip at 2010-04-19

    Yes, we (UofA Hex group) submitted this before we knew of LG and javerberg’s competing solver... but the deadline for IJCAI 2009 was Jan 12, so we were thankfully slightly ahead :)

    Actually, for those interested in such things, we’ve also solved more than half of the 9x9 openings as well, and our paper showing these results has been accepted to CG 2010. Things are definitely slowing down though :)

  • Ingo Althofer at 2010-04-20

    Hello Philip,
    can you tell about your 9x9-findings?
    Are the pattern in line with those for smaller boards?

    Ingo.

  • Ingo Althofer at 2010-04-20

    Christian wrote two months ago:
    > Naming games is an art in itself. As it happens
    > Havannah was chosen by blindly opening a dictionary
    > and tapping a finger. Actually it said Havana, but
    > that looked a bit too much like a cigar.

    Do you know that Cameron Browne delegated the whole
    procedure of game design to a bot? Not only the rules
    but also the naming!

    Look at Yavalath, designed by the bot from his Ph.D. thesis.
    And the name Yavalath came frome some side-routine of this bot.

    See at BoardGameGeek:
    http://www.boardgamegeek.com/boardgame/33767/yavalath

    Ingo.

  • Marius Halsor ★ at 2010-04-20

    Philip, PLEASE PLEASE PLEASE post your preliminary results for Hex 9x9 here!

  • Methylphenidate at 2010-04-20

    9x9 hex, wow!

    At least this gives me hope I’ll see 10x10 solved before I die, but what are the chances of 11x11 is the real question? :) If I give myself another good 50 years...

  • Philip at 2010-04-20

    Ok, in ugly ascii format (someone else can make this nice, add it to HexWiki, etc :) these are our 9x9 opening results thus far:

    W W W W W W W W ?
    ? ? ? W W W W B ?
    ? B B B B B B ? ?
    ? ? B B B B B ? ?
    ? B B B B B B B ?
    ? ? B B B B B ? ?
    ? ? B B B B B B ?
    ? B W W W W ? ? ?
    ? W W W W W W W W

    Each opening took 1-25 days of computing time to solve (we solve all 8x8 openings in ~30 hours) but some of these are deduced openings (i.e. since d2 is a losing opening, we know that d1 and e1 are losing openings, and we obviously save ourselves the rotation, etc).

    I don’t think any of the results is surprising, although c2 is proving to be rather difficult... might end up being a winning opening for Black.

  • Philip at 2010-04-20

    Gah, right, no indenting...
    Top left is acute corner, as oriented on LG.

  • halladba at 2010-04-21

    Hi Philip, congratulation for your solving 9x9 and improving speed on 8x8. How long do you now need for 7x7 ? you mentionned 10min in your article but I guess as 8x8 speed improved greatly so did 7x7 speed...

    Here is the formatting in HexWiki .

  • Tasmanian Devil at 2010-04-21

    I want to. I bet it’s black.

  • Tasmanian Devil at 2010-04-21

    h4 should be ‘?’.

  • Philip at 2010-04-21

    Thanks halladba, Carroll for cleaning up my messy post :) As Tasmanian Devil states, the improved ascii version should have a “?” at h4.

    Despite the ~10x speed improvement in 8x8 from last year, our 7x7 has only gotten a bit faster (~6 minutes now, if I recall correctly... we don’t really test that size often anymore :)

    I’m predicting the short diagonal to be all one color again, and looks like the second row might have a weird `jut out' at c2. This happened on 7x7 but was missing from 8x8, so that’s a bit interesting/surprising to me.

  • Carroll ★ at 2010-04-21

    Thanks Philip and Halladba! (and Tas)

    Anyone wants to bet that i1/a9 is not red?

    W W W W W W W W ?
    ? ? ? W W W W B ?
    ? B B B B B B ? ?
    ? ? B B B B B ? ?
    ? B B B B B B B ?
    ? ? B B B B B ? ?
    ? ? B B B B B B ?
    ? B W W W W ? ? ?
    ? W W W W W W W W

  • Marius Halsor ★ at 2010-04-21

    I’m betting it IS red. I also think that deleting your old post and replacing it with this new and improved post messes up the meaning of previous posts... :-)

  • Carroll ★ at 2010-04-21

    Thanks for making it clear!

    The other solution is for each of the posters having issued a post after me to repost now (or better delete it)... and we will both remove our last ones :)

  • Tasmanian Devil at 2010-04-21

    Except I can’t delete my posts as a non-member. :-)

  • Ingo Althofer at 2010-05-26

    Hello, is someone here familiar with the
    content of the following website – on hex statistics?

    http://hex.kosmanor.com/hex-bin/board/9/en_US:0/

    A student of mine found it by web search
    when the task was to interpret the status
    of first moves in case of perfect play.

    Cheers, Ingo.

  • Marius Halsor ★ at 2010-05-26

    I hadn’t seen it before. However, there seems to be too few variations played to say a lot about the various positions – at least for size 9. It’s much better for size 10, since Kurnik games have been collected, but still there is the matter of the quality of the games the data is based on. Also, with the complete solution expected soon, it will soon be obsolete for sizes 9 and below. For size 10, I guess it can still be of some interrest.

  • Marius Halsor ★ at 2010-05-26

    Playing a little with size 10, I find that it’s not very helpful for even that size. Trying a rather ordinary opening (given swap, that is!) it leaves me with two played games after three moves – and these games are poorly played as well, and that’s all the results are based on for the game after my first 3 moves! And this result, in turn, must be correct for the result after move 2 to be correct, since it displayed all losing positions for move 3.

  • Philip at 2010-05-27

    I haven’t checked that website recently, but when I did, the quality of games was quite poor, as Marius said. It’s not hard to find positions that only rely on a couple games, and in several I found that one player has a virtual connection win and they go on to lose (I verified with solver to be sure)... so not only is there reliance on small number of positions, but many of them contain basic endgame errors. Still, I think the idea has some promise if the quality of games were improved.

  • lazyplayer at 2010-07-08

    No more news? Are the remaining moves so hard? :)

  • Philip at 2010-08-16

    I haven’t been running our solver at all for a couple months... bogged down with thesis writing, etc (my defense is in <7 hours :) plus our department had some major technical issues this summer.

    With our current solver, my estimate is a couple years for each of a6, a8, a9. The rest should `only' be about 2-6 months or so. Of course, this isn’t nearly as bad as it sounds if I just throw a cluster at it, but we have some techniques I’d like to code first... might just save us a few months or more :)

    So I won’t have any 9x9 updates for at least a couple months... sorry :(

  • ---- at 2012-11-13

    wsdwrmjuumfhpmfn, Tramadol com, gvlnZbY, [url=http://www.lean-green.com/]Tramadol withdrawal symptoms[/url], vvRMDDt, http://www.lean-green.com/ Tramadol overnight, trhlHyE.

Return to forum

Reply to this topic




Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]