Bots? Dots and Boxes

53 replies. Last post: 2014-01-16

Reply to this topic Return to forum

Bots?
  • Christian K at 2013-04-01

    Is anyone working on bots for this game? Since the game is so mathematical (lots of parity stuff) and has so little clarity for humans, I think there could be excellent bots. The only one I know is RoRoRo which seems to play random but know the chain rule.

    Anyone else working on bots? Or is there some reason that the game is harder for bots than I thought.

  • lorentz at 2013-04-01

    I’m no expert in dots and boxes, but I know a fairly strong program can be written using nimbers as described in: The Dots and Boxes Game: Sophisticated Child’s Play, by Elwyn Berlekamp. As far as I recall The Shark, written by William Fraser, was/is one of the best programs. But I’m not really sure how it would fare against good players here, especially on larger boards.

  • Christian K at 2013-04-01

    It would be fun to see it in action :)

  • ypercube at 2013-04-01

    There have been bots that played quite well. Enough to play in the top league. Search for “Knox”.

  • ypercube at 2013-04-01

    They played in the first 6 championships. Knox and Knox B

  • Christian K at 2013-04-12

    Why did they stop?

    Wccannard is accusing someone of cheating in the 18th championship. Is he talking about help from machines or a player with multiple accounts?

  • Christian K at 2013-04-12

    Or maybe man in the middle type stuff playing the opponents against each other.

  • Dryad at 2013-06-27

    The_Shark_c

    Interesting :)

  • Christian K at 2013-06-28

    Interesting indeed. I looked at the game between it and RoRoRo. I was especially curious to as if it was able to satisfy boxes to win the chain battle. Sadly, that was not necessary there, so it is unclear to me how ‘intelligent’ it is.

  • Christian K at 2013-06-28

    Its move 25 http://www.littlegolem.net/jsp/game/game.jsp?gid=1555729&nmove=25 seems to show some intelligence (I forgot the tag to include a board in the thread).

  • aldiris at 2013-06-28

    I myself tend to sacrifice women and satisfy boxes. Or was it the other way around?

    On a more serious note, I don’t think one can really claim it’s intelligent by one game or one move. Especially against RoRoRo (with all due respect for her). I’m really looking forward to the games against stronger, human opponents.

  • Dryad at 2013-06-28

    I’m quite sure I lost one of my games against it. I was playing fast and intuitively, but that’s still... :(

  • diego44 at 2013-06-28

    Nice, I wouldn’t have thought that this bot is any good. 11th move in Dryad’s game looks amazingly “intelligent” in my opinion and indicates a more knowledge based approach but I might be wrong..
    Can anyone tell how long it thinks about one move?

  • Dryad at 2013-06-29

    Less than 5 minutes.

  • darse at 2013-06-30

    The profile page on Knox shows that he knows the combinatorial game theory research by Elwin Berlekamp et al., and he uses fast graph search algorithms written in C++, so i expect his program is probably state of the art.

    If Knox’s ~2000 rating is accurate, then it looks like the top rated humans (~2400) still hold the edge.

  • Christian K at 2013-07-01

    It seems to take a really long time moving (or is it just turned off sometimes?)

    Dryad: I am very surprised and impressed to see it beat you in a game. Even if it you were playing a little carelessly, it is quite the achievement for a bot.

  • MarleysGhost at 2013-07-01

    > It seems to take a really long time moving (or is it just turned off sometimes?)

    Once you make your move you have to wait for it to (A) check LG for games where it’s its turn and (B) decide on a move to make. B might be only 5 minutes, but A could be quite a bit longer.

  • Dryad at 2013-07-01

    I’m not sure, but I guess William Fraser is moving by hand(?). The_Shark_c forgot to complete a box in its game against Tumrak and wrote “good game” in one of our games... that doesn’t sound like a bot to me. So yeah... “A” might take a while (I doubt Mr. Fraser is 24/7 online :p), but the progress of thinking should go quite fast.

  • diego44 at 2013-07-01

    On the one hand it seems to be able to brilliantly estimate positions in early mid game, however it doesn’t seem to count or even think at all in the endgame:
    http://www.littlegolem.net/jsp/game/game.jsp?gid=1556654&nmove=29. No comment. ^^

  • Christian K at 2013-07-02

    Something fishy is going on :p

  • ypercube at 2013-07-02

    @diego44 Are you referring to move 29 (by RoRoRo) or to move 30 (by Shark)?

  • Christian K at 2013-07-02

    shark opening a long chain without it being needed I would think

  • ypercube at 2013-07-02

    There was only one winning move at 30, I think. Sacrificing the 2 squares at the top right.

  • diego44 at 2013-07-02

    Indeed I was referring to move 30 by shark. It gave away a clear winning position by sacrificing the long chain, as you stated correctly. And yes, sacrificing the short chain at the upper right was the only winning move, however it should have found this if it only would have thought for a second.

  • Christian K at 2013-07-04

    I just lost a bunch of games against it. It seems very strong. Definitely outplayed me in a lot of situations (not that that is that hard to do :))

  • Treppen at 2013-07-05

    As requested I am posting this information (from the profile of, and on behalf of The_Shark_c) to the forum:

    The Shark is a computer program written and operated by William Fraser.

    It now responds automatically but it runs on my laptop, so it will not always be online.

    I have enjoyed following the “Bots?” thread on the Dots and Boxes Forum, and look forward to commenting as soon as I am “Trustworthy”.

  • diego44 at 2013-07-05

    Somewhere I found the information that shark uses a huge database of positions. Could William Fraser specify how he built that database and which positions are solved (as soon as he is “trustworthy” :P).

  • Christian K at 2013-07-06

    Interesting. Since 5 dots is so small, it mightbe more reasonable than other games to have a database here.

  • The_Shark_c at 2013-07-07

    After the shark has played 3 moves, the position is solved (note that it always plays the “same” 3 moves).

    Some of the positions where only 2 of those moves have been played are solved.

    I’ve been creating the database at home (starting with 1 processor in 2007, peaking at 6 processors on 3 machines around 2010, currently 2-3 processors on one machine). The database currently has over 24 trillion positions.

    My original goal was to prove which side had a win (with the intent to force computer competition to the 7x7). After about one year, my database had 1.5 trillion positions (every position where all four of those corner moves had been played). From that I was able to prove that the correct score was 13-12, but not who would win.

    Hey! I’m able to post!

  • The_Shark_c at 2013-07-07

    As to the infamous move 30 against RoRoRo, the algorithm found the correct move, but the code I’d created to automate play contained a bug. (Relative to the my failure to capture the box against TUMRAK, I was thinking “To err is human, to really mess things up requires a computer!”)

  • The_Shark_c at 2013-07-07

    Ah, I just found the post I tried to send after Dryad’s comment on 7/1 (ah, the irony):

    At last, I am “trustworthy” enough to speak!

    Yes, I’m moving by hand, although I am working on automating the process — my current tournament game against RoRoRo is partially automated.

    Yes, somewhat unfortunate that I missed the box capture. So far, I’ve been lucky and neither of my omissions has affected the outcome of the game....

  • The_Shark_c at 2013-07-07

    Here’s the very first post that I tried to send:

    This is William Fraser. I just heard about Little Golem yesterday, when I saw an announcement about EinStein at the ICGA website.

    The Shark will be competing in the World Computer Olympiad in Dots and Boxes in August, and I thought it would be fun to play some serious games to get ready.

    The Shark only plays 5x5 boards, and because it relies on a brute force endgame database, I do not believe that it will run on larger boards during my lifetime.

    I have written another program, ControlFreak, which is based on NimString and plays quite well on larger boards, but have not put much time into it in the last 4 years, since I’ve been working on trying to prove that 5x5 is a win for the first player.

    ControlFreak is not as strong on the 5x5, but now that there is a community to play against, I may dust it out to compete on 7x7. [Also, I may add support for Misere.]

    I hope to have fun playing here!

    bill

  • Christian K at 2013-07-07

    Very interesting indeed. Dots has boxes has been needing some serious bot attention for some tie. I am very please to welcome uou here :) hope you like it. I didnt knnow of a computer world championship in august.

  • diego44 at 2013-07-07

    No wonder that it plays that strong. Though in my opinion it’s pretty lame to nearly solve the game. >.< Now that you confirmed that such early positions can be solved indeed, it’s kinda time to say goodbye to Dots and Boxes 5x5, one of the greatest – if not the very greatest – abstracts ever invented by humans. All of us knew that this day will eventually come, however, no one has expected it that soon. The day shark registered at littlegolem will be known as the day of doom and decay for many decades and everyone will hark back with deep sorrow and black despair. Darkness won.

  • Dryad at 2013-07-07

    Ohh what... such depressing hyperboles. ._.

    The first 3 lines of The Shark are always the same and make absolutley no sense. Isn’t that enough to create a sure-win-against-shark-opening? I’ve kind of done that for player 1 already... proved by my glorious victory. :] So yeah... doomsday hasn’t come yet.

    @bill... enjoy your stay!

  • Christian K at 2013-07-09

    never has RoRoRos thread been so low in the forum ^^ the shark has given some serious attention to D&B

  • 7ics at 2013-09-10

    it seems possible to influence which of the corner moves will be played, why’s that? for example when shark starts with b3 and you play h3 in second move it will surely answer i2; a major weakness.

  • William Fraser at 2013-09-16

    That was an interesting issue.

    When I first wrote the shark, it needed to play all four corners, so I required it to play a corner before the opponent could create a situation where it needed to sacrifice in order to get its move in (imagine, for example, that it played a different corner and you played h1 or g2. It would then need to sacrifice in order to play i2).

    I should really re-write this code, to encourage it to play in the opposite corner, since that’s where most of its depth 5 opening book is anyway....

  • Christian K at 2013-09-16

    Wasn’t there somewhere where you could play it online? I cannot seem to find it anymore.

  • The_Shark_c at 2013-09-16

    I took down that site, as it was somewhat finicky. I wanted to make absolutely sure it could complete a game in 30 minutes, so I was somewhat overzealous in re-trying connections — with a bad internet connection, I could be waiting for so many responses that my computer crashed.

    However, you can play it on LG by inviting it to a game. I usually notice within 8 hours or so and accept — and I could add an auto-accept feature if you want.

    (The URL was www.snipurl.com/theshark and you can still find a message there)

  • 7ics at 2013-09-17

    “However, you can play it on LG by inviting it to a game.” the shark is a really nice enrichment to the site and i would strongly recommend playing against it. especially interesting is to take it on as player 2, as you will mostly have to build just one chain and thus need to learn how to extend chains, which is probably the most usefull skill in dots.

  • Christian K at 2013-10-08

    I am pretty curious about it. How does the bot play is losing positions? Towards something that gives the closest result (like 12-13)?

  • The_Shark_c at 2013-10-09

    Yes, it will always play something which results in it getting the best score that it can prove that it can get (initially 12-13).

    Once it is in its endgame database, it chooses randomly between all of the potential moves, weighted by a function of the number of the opponent’s moves which fail to maintain that score.

    Before that, it chooses randomly, strongly weighted towards moves which help get it into its database. This algorithm is currently undergoing analysis and may be improved when I have time.

  • Christian K at 2013-10-09

    Seems fairly smart :)

  • 7ics at 2013-11-29

    #1593873 The_Shark_c vs. 7ics

    #1593872 The_Shark_c vs. 7ics

    what happened there? why is shark playing only 2 of the corner-moves? how are these results possible/ why does it play wrong? and what i’m personally interested in: until which move are these 2 games correct?

  • 7ics at 2013-11-29

    oups, didn’t intend to show it that big.

  • William Fraser at 2013-11-29

    Hmmm.... I’ve been messing around with the opening algorithm. Trying to avoid playing the third corner when it knows that doing so will lead to a loss.

    Unfortunately, it appears that the opening book’s limitation (all losses are equal) is showing up bigtime.

    I think a post-mortem of those two games might help improve things.....

    Thanks,

    bill

  • The_Shark_c at 2014-01-16

    It is with great pleasure that I announce:

    1. The retirement of TheShark from tournament play.

    2. That is has just finished its proof that the 5x5 game of dots and boxes is a win for player 1!

    You heard it here first!

    Thank you for all of your help in finding some bugs, especially 7ics.

    It will continue to accept challenges, and I do not believe that it has gotten that much stronger as player 2.

  • Christian K at 2014-01-16

    OMG!!!!!

  • Christian K at 2014-01-16

    13-12?

  • The_Shark_c at 2014-01-16

    Yes, it’s 13-12 (although I’ve known it was either 13-12 or 12-13 for over two years).

  • Macbi at 2014-01-16

    Congrats on solving it! What openings do you know to be winners?

  • Macbi at 2014-01-16

    Never mind, I saw the other thread.

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]