SolvingGo/Discussion-Lmax

Taken from general discussion at SolvingGo/Discussion:

Pashley There's an obvious upper bound for L. Since a point can have only three states (black, white or empty) and there are 361 points, there cannot be more than 3^361 positions.

Actually, slightly more if you need to mark the last stone played so you know if a ko can be taken, but not enough to matter. This gives 3^361 * 361.

Of course this is ridiculously high and includes lots of illegal positions.

Morten: I also believes that it is not correct - for every position, there are several ways of arriving at that position. So your question 'How many legal games' does not equal 'how many legal positions'. Hence, the upper bound is much larger than what you write above.

Pashley 3^361 is about right for possible positions. For games it is indeed much larger. 361 possible first moves, 360 2nd moves for each, ... gives 361!/(361-n)! for an n-move game. Even if we prune it so there are only 10 'reasonable' moves to consider at each point, we get 10^300 300-move games.

10^300 is an embarassingly large number. Even if we have a million (10^6) computers each examining a million (10^6) games a second, we still need 10^288 seconds. There are fewer than 10^9 seconds in a year, so we need something over 10^279 years. This exceeds the lifetime of the universe by a huge margin, so we might reasonably suspect that the solving go project is doomed.

Even with optimistic assumptions, it is still doomed. Say a 200 move game with only two choices per move. 2^200 games to look at, roughly 10^60 (since 2^10=1024~=1000=10^3). Now we need 10^39 years.

For a 9 by 9 or other small board, there might be some small hope. There are only 81 points, so perhaps consider 60-move games. With 10 reasonable choices a move (high?) this gives 10^60 seconds again, still wildly impractical. If we can get it down to two choices a move, though, it's 2^60 ~= 10^18 which might be soluble territory.

Morten: How is this for another futile attempt at not really giving any useful result: Assume that everyone (6 Billion people) have 10 PCs, each of which has a 1THz processor which 'solves' (whatever that really means) one position (game?) each clock cycle. That means that each second, 6E+24 'solutions' are found, which equates to roughly 2E+32 'solutions' per year, or 1E+42 before the sun turns into a white dwarf in 5 Billion years (?)... (Of course, we do not have that amount of processors available and they will take more than one cycle to 'solve', but hey, a factor 1E10 more or less makes little difference to the end result here...)

Either way, this is absolutely peanuts compared to the numbers you are likely to get for L or R (>1E300). Even if we have escaped the sun, the big crunch / big rip (...insert favourite end of universe theory here...) will happen before we get "the answer".

I suppose that what I'm saying is that the brute force method will not work. Some intelligence must be used - however, the more intelligent your program, the more time each 'solution' will take. (Yes, and the greater the risk of missing the true solution -Jared)

Look up Drake's equation or Fermi's paradox if you're interested in similar excercises with large numbers...

Malweth: Wouldn't the ko state be a valid state for any point, though not in any position as it is dependent on the surrounding stones. In this case, the limit for L would be 4^361, though its actual value must be much lower.

nachtrabe: I believe the assumption is that the ko state is valid for any point, but only one point at a time. Thus it only requires 361 possible states representing whichever place on the grid has a ko restriction (though technically that should probably be 362: 361+no ko restriction present).

Just to throw a reality check on solving things though: Bruce Schneier, in applied cryptography, mentions that there is a minimum amount of energy to increment a counter and says that if we built an ideal dyson sphere around the sun to power an ideal computer we would have enough power to increment a 192-bit counter through all of its possible states (2^192 or a little over 3^121) after 30 years. That's just to iterate through the counter, not to do any calculations other than iteration. Thus, if you want to "solve" Baduk for any meaningfully sized board it will require dramatically reducing the search space.

Jared: Yes, and I hope that the question 'How many legal games' gives a much smaller search space than 'how many legal positions'. Very interesting comments already. I still think it would be fun to come up with a time estimate, even if that is on the order of light-years. Morten - Tsk tsk. A light-year is a measure of distance... you may be looking at Yotta-aeons instead :-) Jared: Haha you are completely right about light-years. Thx for the correction. I feel silly.