I apologise if this has been asked before.
Does anyone know the computational complexity of dots and boxes?

Wiki has a nice list
http://en.wikipedia.org/wiki/Game_complexity
but I cannot find it there

It's NP-Hard. http://www.sciencedirect.com/science/article/pii/019667749090001U And presumably brute-force-search forces it to be in PSPACE.

ok, but is it known if it is in NP? or if it is Pspace hard?

Why do you want to know this Christian?

Did you read http://arxiv.org/pdf/cs/0106019v2.pdf ?

They argue citing Berlekamp Winning Ways:

“Suppose that you have gathered several coins but your opponent gains control. Now you are forced to lose the Nimstring game, but given your initial lead, you still may win the Strings-and-Coins game. Minimizing the number of coins lost while your opponent maintains control is equivalent to finding the maximum number of vertex-disjoint cycles in the graph, basically because the equivalent of a double-deal to maintain control once an (isolated) cycle is opened results in forfeiting four squares instead of two. We observe that by making the difference between the initial lead and the forfeited coins very small (either −1 or 1), the opponent also cannot win by yielding control. Because the cycle-packing problem is NP-hard on general graphs, determining the outcome of such string-and-coins endgames is NP-hard. Eppstein [Epp] observes that this reduction should also apply to endgame instances of Dots-and-Boxes by restricting to maximum-degree-three planar 14graphs. Embeddability of such graphs in the square grid follows because long chains and cycles (longer than two edges for chains and three edges for cycles) can be replaced by even longer chains or cycles [BCG04, p. 561].
It remains open whether Dots-and-Boxes or Strings-and-Coins are in NP or PSPACE-complete from an arbitrary configuration. Even the case of a 1 × n grid of boxes is not fully understood from a Combinatorial Game Theory perspective.”

What is the status of 1xN Dots and Boxes and Icelandic 1xN Dots and Boxes as Stated in C1(51) of Richard Guy Unsolved Problems in Combinatorial Games (that is with lef and top walls).

I would think one can compute the value with only left and right walls by recurrence on 1xN but haven't checked out…

I am just curious. I like complexity theory and I like dots and boxes.

..and thanks for the link :)

Does it really matter as obviously P=NP ?

well pspace could still be different :)

My advice is never to play on an arbitrarily large board, that way complexity theory doesn't enter into it!

For some games like David Smith's Trax (http://en.wikipedia.org/wiki/Trax_%28game%29) or Spangles, you have no choice as the board grows when you play ;)
Anyone know Spangles on LG and where we can play?

Well, I think of the complexity as describing how much harder the game gets when the board grows, which I don't think is unreasonable. Therefore, it can still be interesting :) I am sure it would be nice to know if one thought of making the shark play on 7x7.

I was reminded you can play Spangles on Gamerz: http://www.gamerz.net/pbmserv/Ratings.php?Spangles please invite me to a game.

Christian, I remember that Bill mentioned another bot called “ControlFreak” which plays on 7x7… that might be an option if you're interested in Bots for 7x7. One might ask him nicely to “dust it out” :) However, I strongly doubt that any of us will ever see a bot like The_Shark, working with a database, for 7x7 as the board is just way to big.

thanks, I am more interested in if anyone has proved something on the computational complexity though :)

How efficient can end-games consisting of rings and chains be evaluated?

FatPhil has an algorithm for that, maybe he can tell…

Sort your chains, then your loops.
Start with either shortest chain or shortest loop, recurse, and when you have an order, you can easily compute value…

Hum, not sure that is polynomialy bounded…

Do you mean an endgame consisting of only isolated chains and loops? (because dippers and similar stuff are chains and loops also in a way)

The algorithm Carroll gave isn't polynomial, but there is a polynomial algorithm due to Kevin Buzzard and Michael Ciere, given here http://arxiv.org/abs/1305.2156 (the algorithm is in fact “constant time” except possibly for a logarithmic amount of time needed to read in the input).

Buzzard and Ciere both have littlegolem accounts, but I shan't say who they are in case they want to remain anonymous.

Eh, I suppose I mean a _linear_ amount of time needed to read in the input, although I suppose it depends how the position is specified.

Thanks for this pointer where I'm thanked by a certain volatile! :)

And congrats for your 100 tournaments and 500 games!

Thanks! I've stopped playing while I'm busy at uni, but I noticed I was stuck on 499 so I played one against RoRoRo. I should be playing here again next year.