Bots?

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.

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.

It would be fun to see it in action :)

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

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

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?

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

The_Shark_c

Interesting :)

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.

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

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.

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

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?

Less than 5 minutes.

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.

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.

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

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.

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

Something fishy is going on :p

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

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

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

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.

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

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

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

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

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!

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!")

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

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

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.

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.

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!

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

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.

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

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

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)

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

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

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.

Seems fairly smart :)

Game #1593872

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?

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

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

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.

OMG!!!!!

13-12?