Announcement: 5x5 dots has been strongly solved Dots and Boxes

12 replies. Last post: 2017-06-20

Reply to this topic Return to forum

Announcement: 5x5 dots has been strongly solved
  • The_Shark_c at 2017-04-28

    On Friday, April 28, 2017 at 8:40 am, I finished my final calculation.

    I am going to be sharing a bit more information in the coming days, but will be very sparing in my release of information which will impact play.

    But here's the teaser…..

    All first moves are winning for Player one, but no matter which one you choose, player 2 has at least one reply which make it is possible to make a losing play on move 3.

  • The_Shark_c at 2017-04-29

    Here is the rest of the information that I am going to share prior to the discussion of how much Shark analysis should be distributed:

    Of the 60x59x58/6 = 34220 positions after three moves, 1276 or 3.7% are winning for Player Two, the other 96.3% are winning for Player One.

    However, these are not evenly distributed among Player One's possible opening moves.

    Taking into account symmetry, there are 9 different first moves by Player One.

    Against Player One's strongest move:

    • 52 of Player Two's responses leave Player One without a losing move
    • 5 of Player Two's responses leave Player One with only 2 losing moves (in one case, both of those moves involve sacrificing a box)
    • 2 of Player Two's responses leave Player One with only 4 losing moves (two of which sacrifice a box)

    Against Player One's weakest move:

    • 8 of Player Two's responses leave Player One without a losing move
    • 21 responses leave 2 losing moves
    • 4 responses leave 4 losing moves
    • 4 responses leave 5 losing moves
    • 5 responses leave 6 losing moves
    • 2 responses leave 7 losing moves
    • 4 responses leave 10 losing moves
    • 2 responses leave 11 losing moves
    • 2 responses leave 12 losing moves
    • 2 responses leave 14 losing moves
    • 1 response leaves 16 losing moves
    • 2 responses leave 27 losing moves
    • 2 responses leave 32 losing moves

    If there is interest in a similar breakdown for the remaining 7 classes of opening moves, I'm willing to provide that, too.  I will probably be including specific details about the opening 3 moves in a forthcoming paper.  (Now, I've made the commitment publicly.  I'd better write something by the end of 2017.)

    And, finally, a result which refers a specific move.  The Shark's favorite opening move is neither the weakest nor the strongest move.

  • Tobias Lang at 2017-04-29

    congrats William and thx for sharing!

  • Carroll at 2017-04-29

    Fantastic William!

    Please make a few backups of the database!

  • The_Shark_c at 2017-04-29

    I've got 2 copies of the each file in the dataset, and 3 copies of most of it.

    Unfortunately, I've only got one 24TB hard drive array, so there's only one copy that can connect to a single USB port.

  • shinnosuke at 2017-05-06

    Wow! Congrats! BTW, how big is the database?

  • _syLph_ at 2017-05-06

    Congrats. I'm gonna dare a guess and assume that 1.d3 is the worst move while 1.f5 is the best (second guess would be 1.f1 for the best). Probably better to not reply; buuut fuuuuck, I'm curious.

  • The_Shark_c at 2017-05-09

    @shinnosuke

    The database is roughly 24 TB (Just under, luckily!).

    @purgency

    Your guess is noted.  I won't be revealing the moves for a while, although I do intend to so in my paper, and may do so sooner, depending on how the other thread goes.

  • _syLph_ at 2017-06-18

    can the database be used for the_shark to play misere dots and boxes?

  • Carroll at 2017-06-19

    In a losing position, does the Shark play a move which allows for the opponent the most possibilities to make mistakes?

  • Sighris at 2017-06-19

    Congrats William…  and tnx for sharing! :)

  • The_Shark_c at 2017-06-20

    @purgency.  No, it cannot.  In fact, I suspect that misere cannot be solved at this time.

    @Carroll.  Thanks for reminding Bill to re-visit my tie-breaking algorithm.  His intention was, as you suggest, to play the “hardest to respond accurately to” move.

    My basic algorithm is to choose randomly among all moves which guarantee the current score, but to assign them different weights.  The idea behind this was to provide a greater variety of games, so that I don't get stuck in a rut (which could be exploitable).  Also, the humans I play against seem to find variety enjoyable in its own right – go figure.

    There was a bunch of code which involved making sure I could make “my moves” in the opening even if there were “better” moves out there.   It did this by assigning weights of 1; 10,000; 1,000,000;, and 100,000,000 to various moves.  (This applied during the first 8 moves.  Bill is going to modify it so that it  applies during the first 8 moves only when the position is not in the database, which should be never).

    If I am behind, I assign higher weight to moves as the number of losing moves by my opponent increases (2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96,…).  I am happy with this one, despite the fact that it is possible that someone could find a line against me which not only wins but where I am likely to play it again next time.

    If I am tied or ahead, I give all moves equal weight.  An additional advantage to not always playing the trickiest move here is to avoid discouraging people by running up the score.  Bill could also add a “bloodthirsty” mode which assigns weights in the same manner as when I am behind.

Return to forum

Reply to this topic