Go! That's more complex than chess, we're up to 1^10*170, so we're approaching Planck volumes.

There's nearly not enough room in the universe to ever theoretically solve Go, even assuming perfect technology. Surely we can only store one "bit" of information in a Planck volume. I'm making that assumption.