Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

I would think that on a 9x9 board, the number of possible moves is small enough that computers could exhaustively search all possible permutations and compute a line of play that always wins by moving first. If so, by how many points are you guaranteed to win by?

Has this been done, and was it determined where the perfect move is for a 9x9 board to guarantee a win when going first. Can you guarantee a win even with some number of handicap due to the perfect first play?

share|improve this question

3 Answers 3

up vote 20 down vote accepted

Go was solved up to 5x6 only as of 2009. This table by Erik van der Werf and Mark Winands shows how many points komi to give white such that the solution is a draw for boards up to that size. For instance, on a 5x6 board White should be given 4 points; on a 5x5, White should be given 25 points.

Notice that 25 points is the size of the 5x5 board; ergo, White cannot make a living group on a 5x5 board given optimal Black play (which, I'm not positive, but I think can begin with play in the center). With the 25-point komi, using territory scoring, it becomes optimal play for Black to begin by passing, as it is the case that if Black places a stone, White can win by passing.

I would imagine that with the current state of algorithms and processing power, we're not too far off from solutions for 6x6 and 7x5 Go. But to give a sense of how the problem scales, their 2009 paper about solving 5x6 Go states:

The question now is when would 6×6 be solved? In 6 years time we went from a surface of 25 (i.e., 5×5) to a surface of 30 (i.e., 5×6) of solved Go boards. This was not only because of better hardware but also due to a better search engine.

We can try to predict when MIGOS II would be able to solve 6×6 in a reasonable amount of time by extrapolating the current results....

An optimistic extrapolation suggests that on current hardware MIGOS II would require a few years to solve 6×6. However, we could easily be underestimating by a factor of 100. Nevertheless, we believe that with some effort αβ-based solvers, such as MIGOS II, should be able to solve 6×6 within the next 5 years, especially because significant improvements in the evaluation function are still possible.

share|improve this answer
    
Thanks, I guess this partly answers my Deep Blue question. –  Forkrul Assail Nov 12 '11 at 11:43

No. 6x6 is the largest actually solved. 7x7 has a solution that is believed to be correct but is not proven to be correct. 9x9 is not anywhere near solved yet.

share|improve this answer
1  
Here's a reference of 7x7 unsolved: senseis.xmp.net/?Willemien%2Fsolving7x7go. Here is a copy of what is believed to be optimal: goproblems.com/prob.php3?id=12825&pths=1 –  Joshua Nov 9 '11 at 2:31
    
Sorry that I wasn't explicit, but I was wondering about why Daniel mentioned 6x6 as unsolved while you mentioned it as solved. Well, it does not really matter as the question is about 9x9 and Daniel says it will happen somewhere soon; but it would be nice to have a reference about 6x6... :) –  Tom Wijsman Nov 9 '11 at 2:37
2  
Correct Komi on 6x6 is listed as known to be 2.0. This is equivalent someone having solved 6x6. Here's one reference where it's handled as a known fact: mail-archive.com/computer-go@computer-go.org/msg09447.html –  Joshua Nov 9 '11 at 2:48
    
+1 for providing references, thank you! :) –  Tom Wijsman Nov 9 '11 at 2:54
    
The computer-assisted human solutions by Ted Drange for some smaller boards turned out to be in error when they checked using the MIGOS. So Ted's opening & response trees for the first few moves on the 6x6 and 6x7 may turn out to constitute a partial solution in the sense that each branch ends with "left as an exercise to the reader" and is correct, or there might be errors. –  Daniel Briggs Nov 9 '11 at 16:23

Almost...

In 2009 (looks like it was a good year for computer go) a program called MoGo managed to beat 9p and 5p players on a 9x9 board with no handicap. The program uses Monte-Carlo tree searching and ran on a research grid.

share|improve this answer
4  
This is not an answer to the question at all though. Chess bots beat pros all the time yet chess is still far from being solved. –  mafu Nov 10 '11 at 14:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.