About 30 minutes ago, the shark completed its proof that 5x5 dots and boxes is a win for the first player.

Next step:

Verification and writing something for publication.

Thanks to everyone here on Little Golem, especially those who played me, and especially especially 7ics!

Waoh great achievement, will you share with us before publishing?

RIP D&B?

Thanks to you :) happy that I managed to get a win.

Carroll, how would this change anything for human players? It was always conjectured by top players that player one had a 13-12 win.

I just can't stop smiling when I see this:

@
+ + + + + +

+ + + + + +

+ + + + + +

+ + + + + +

+ + + + + +

+ + + + + +

Score 0-0
Player one's turn.
The position is not in the database.
Upper bound: 1
Lower bound: 1
Player one is ahead by 1.
@

Knowing that there should be a win, and knowing the tree for this win are different to me…

Sure nobody will be able to remember the tree, but these lines will tend to be played more. What was fun in D&B was to have seemingly random moves for the first few moves and then to start to see where the chains could be or how many chains will evolve from the territories starting to emerge.

@William, how many first moves has The_Shark proven to be winning moves?

Congratulations! Perhaps we need a 6x6 championship now.

I agree - move to 6x6

Well done William! Is it 13-12 indeed?

I'd love more details on the quantity of data processed for this feat.

Congratulations, anyway!

hoh, this came very suddenly and unexpected. well, i guess thats what people expected and i honestly dont think this changes anything for human play, so we can technically stick to 5x5. though i'm not against trying 5x6 or 6x6 either.

well, congrats and also thanks for the shoutout, its my honor n_n

Congratulations! Nice achievement!

Congratulations!

@Carroll The shark has only proven eight moves to be winning (all the same move with symmetry), but I suspect that at least 48 moves are winning, and possibly all 60, based on how strong the player one position is in most lines.

@Tobias Lang. Yes, it is 13-12.

@FatPhill. Roughly 30,000,000,000,000 positions in the endgame database, with fewer than 400,000 positions in the opening book. I've been working on the database for about 8 years. On my new computer it would take about 1 year to re-create the database from scratch.

@7ics. I would suggest staying with 5x5 for humans. Although I am hoping to push the world computer olympiad to 7x7.

These 8 proven moves are quite easy to guess for all who played Shark quite a lot ;) But it will not improve my game ;)

That's a good point. I think there are very few players that actually play those moves, so I think we can relax and stick to the good old 5x5. Congratulations anyway!

@William, so yes that may be all 60…

Does any one know about worst moves than what The_Shark usually plays?

Why chose such moves? Would you have lost 8 years if it happened not to be a winning move, and wouldn't you have had the possibility to prune the tree more if there are in fact some better moves?

@Carroll Actually, I chose that move because I wanted moves which decreased the problem space the furthest. I tried various possibilities, and that looked the best. It had nothing to do with the D&B strength of the move.

If it had not been a winning move, it would definitely have been a set-back, but not a total loss. Also, much of that eight years was spent perfecting algorithms (as well as recalculating parts of the database after I discovered bugs and/or corrupted data).

William, this is just awesome work. Congratulations again and again. How much of the way are you to strongly solving it? Does your database have any insights into any of the contrived “puzzle” positions (e.g. 1, 2, or 4 whole board edges taken)

How many of the second player's replies to the first move are losing 12-13?

@FatPhil I'm not sure. I'll check when I get home.

@diego44 All of them lose by only one point. But I suppose I ought to be careful how much information I give away.

Congratulations!

It's interesting to see results like this, even for games that I know very little about. Congratulations!

@FatPhil The total problem space requires 82,188,581,754,034 positions, so I suppose I would be able to solve it in about 2 more Computer-years. But until the price of hard drive space goes down, that's not going to happen.

1 wall: +1/-1
2 adjacent walls: +1/-3
2 opposing walls: +3/-3
3 walls: +3/-1
4 walls: +1/-3

Where the numbers represent the upper and bounds for the player to move. In other words, none of them are decided games. Note that these positions are particularly hard for the shark, because, when two walls meet at a corner, the move which gets you into the database sacrifices a box!

Next year's computer will do it in one year!

Thanks for the bounds - I see there's still suspense!