Willemien/solving 7x7go

Sub-page of Willemien

This page is still in draft and under development but do feel free to add comments at the end.

I am getting addicted to 7x7 go and think it is time to puzzle about how to solve it.

Table of contents Index of sub-pages

Introduction

Why is 7x7 go interesting?

Go till 5x5 has been solved but on 5x5 White cannot create a living group if black plays optimal.

On 7x7 the situation is different (again asuming optimal play) both players will create a living group. the difference is just the komi. (see later under optimal play and komi) It is an interesting testbed for rules comparison. (although i have not seen a superko in 7x7 yet) and is maybe a good pilot program for solving 9x9 Go. (What is there to do if 9x9 becomes stronger than the strongest human player)

What is solving a game?

A two player game can be "solved" on several levels:

Ultra-weak
In the weakest sense, solving a game means proving whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This can be a non-constructive proof (possibly involving a strategy stealing argument) that may not actually help determine this perfect play.
Weak
More typically, solving a game means providing an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game.
Strong
The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on both sides.

see[ext] http://en.wikipedia.org/wiki/Solved_game

Some examples

Hex without the pie rule. Hex is ultra thin solved for any size of board, it can be proven that draws are not possible, so one player must win, and the first player has the advantage of the first move so he will win. If it were a second player win the first player could just start with an useless move. and after that he is the second player (this is not the proper explanation needs some more) This tells you nothing how to win. therefore it is only ultra thin solved.

[ext] Checkers (8x8[1]) has been weakly solved. There is a computer program [ext] Chinook that is unbeatable when playing from the starting position. It doesn't mean that there no posttions where this program will play the wrong move.

connect4? has been strongly solved for small sizes. This means that there are programs that know the best move given any position.

Weaker than weakly solving

A weak solver is still a strong (unbeatable) player. so there are still lower levels from strong to weak

  • Over champion : stronger than the strongest human player
  • World champion : comparable in strenght to the human world champion
  • Grand master : Comparable in strenght to professional player
  • Amateur : Comparable to a skilled amateur player

all these strenghts have the ability to lose against the comparable player.

And now how about Go?

in [Artificial Intelligence 134 (2002) page 277- 311 Games solved: Now and in the future | [ext] http://www.fdaw.unimaas.nl/education/4.2ZT/Literature/GamesSolved.pdf] it was prognosed that in 2010 the strongest go playing program on 9x9 would be comparable with the world champion and that on 19 x19 it would be on amateur level.

From world champion to weakly solved is I think a big step. (for checkers it took 10 year) But as preparation i was thinking about a projest of weakly solving 7x7 go

What makes Go so more complicated than Checkers?

Similarities both end in draw.

Checkers on 8x8 has been weakly solved in the program Chinook and if both players play optimal it ends in a draw.

In Go the komi is to evenout the advantage that Black has of playing first and therefore optimal play of both side should (in my opinion) by definition end in a draw. (if optimal play doesn't end in a draw, the komi is wrong and should be adjusted) for 7x7 it is thought (but not proven , that is what the solver will prove as well, that the komi should be 9 points.

Rules certainty vs uncertainty

I was planning to keep this as last point, but i need to talk about it before the next point.

In checkers there are some distinct variations (can normal pieces man capture backward, what moves are obliged)

But in go it is worse. and it is probable that the ruleset influences the result see 7x7 article by J. davies who has the last move is inportant under area scoring while not under territory scoring I think the most interesting it to find (and use) the ruleset that gives the least jigo positions. (while playing optimal) , but in itself finding differences between them is interesting (I hope)

Later thinking about thought me that Area scoring is much easier than Territory scoring this is because under area scoring all scoring information is in the (full) board position, it doesn't matter how many captures there have been made on the way to this position. while under territory scoring it does matter.

Convergent vs divergerent game

Checkers is a convergerent game the number of positions near the end of the game decreases. (in checkers the number of pieces reduces) This makes it possible to have the advantage to create endgame databases. and by retrograde analysis create a less difficult game to solve. Chinook has an endgame database for all positions of 10 pieces or less. this is a huge databas it contains 39,271,258,813,439 positions

An endgame database is made up a bit like the following make a list of final positions. if it is a win an opponent move that created this legal end position on the board. and so backward to the starting position

Go on the other hand is said to be a divergerent game. Although there is no proof of this, the number of end situations is astronomical. and it is probably futile to try retrograde analysis

Retrograde analysis looks a bit like this. start with an end position. (list of played moves from strat till finish ending in an position on the board + prisoners, eeven who played last is inportand) if it is a jigo end position Remove a stone from the last player Could the last player do a better move? If there is no better move this position is also jigo. If there is a better move. (a move that leads to a win?), this position is a loss for the previous player) and so back to the empty board.

How to solve 7x7?

The first start is to make a strong player that uses a database to store positions and games and that can play against humans and other go bots. It needs routines to store positions and games, learn from his games. (and maybe from other games that can just be fed into it) The database will be in the form of a big transposition table. There are some problems witgh relations to ko's and passes but i think the best idea is to keep the database as simple as possible. per position it needs to know the best 2-4 moves. Allknowledge of ko and so is not in the transposition table but in the games themselves (who are also stored).

This player needs to be able to play all manner of opponents.

The problem is that this program will run out of storage space. So we need to remove games and powsitions from the database. The idea is to remove all positions that can only be reached if both Black and white have made a mistake and to remove games where black or white made an obvious mistake. (obvious to a internal weak bot)

For the moment my idea is to program it in Java, mainly because it is a save language and lots of open source (Gogui, OregoGo? is allready freely available)

Notes

[1]: Note that since Checkers is only played on the dark squares of the checkerboard, it is effectively played on a 4x8 board.


Comments

Herman: Interesting project! :-)

Go on 19x19 will never by weakly solved, it is physically impossible. The same goes for go on 9x9, IMO. But 7x7 might just be possible. I think it is still beyond current technology, but may be technologically feasible in the future.

Stickleback: Eternity is a long time to come up with something creative. Never say never.

Herman: As John Tromp has shown, the lower limit for the possible number of games on 19x19 is 10^(10^48). (To image how big that is: Write down a 1, then write a 0 behind it for every single atom in the planet earth). You need to store all those variations, but the visible universe is estimated to contain only about 10^80 atoms (most of them billions of light years away). As I said: physically impossible. :-)

ThorAvaTahr: I was not going to bring this up, but since you are insisting on this line of thinking, I feel I need to comment on your statement. Although I agree with you, that is in my opinion go will never be solved, the fact that the size of the gametree is beyond human imagination does not necessarily mean that go cannot be solved. There might be an algorithm for us to find that can be proven to result in optimal play without having to actually test it against all possible game trees. However, at this point in time I cannot imagine such an algorithm, leave alone proof of it to be optimal.

Herman: True, although since go is EXPTIME-Complete, the existence of such an algorithm basically requires P=NP. And although it is unproven, the general consensus among scientists is that P≠NP. :-)

ThorAvaTahr: I did not know that go is EXPTIME-Complete with the game-tree. Since this is at least as big complex as P-SPACE, that means that your argument holds. Any algorithm that solves go will have to have an amount of memory that is (at least!!!) polynomial with respect to the game tree, which in turn is at least 10^(10^48). Ouch. I have been unable to find the full-text of Robsons article, if anybody can provide it to me, I would be very happy.

-- Willemien I guess 7x7 go has about the same complexity as checkers, (just a wild guess) so i think it is, it is more to investigate what the problems are and how to overcome them.

-- emeraldemon I think these numbers are way off. To strongly solve go requires knowing the correct move for each possible board position. Tromp gives [ext] http://homepages.cwi.nl/~tromp/go/legal.html an estimate of about 10^170 positions. This is still way more bytes of information than we have any hope of storing, but it's also quite a bit less than 10^(10^48). To weakly solve go will require much fewer positions. Tromp gives about 10^12 positions for the 5x5 board, which is about 1 terabyte's worth. But the 5x5 board was solved by searching only about 10^7 positions, and I'm sure the final solution can be stored in a much smaller space than that. I wouldn't write off a weak solution to 19x19 go as completely impossible, although it's way beyond our current technology.

-- Herman: The 10^(10^48) is also given by John Tromp, and is based on the fact that John found an algorithm by which he could theoretically play a superko-legal game of about 10^48 moves. So it is a lower bound (there may be longer games). He also gives the upper bound as 10^(10^170), which is based on the fact that the longest possible superko-legal game would be a sequence that visits every one of the 10^170 legal positions without repeating any of them. So the 10^170 is just the number of positions, not the number of games. Now a naive solution to strongly solving go would be to find the best move for any of the 10^170 positions. But that is not enough. The best move from a position may be illegal because of superko. So in addition to the position, you need to know the history of the game. And that's where it gets complicated ;)

ThorAvaTahr: Please mind the fact that multiple 'solutions' are bound to exists. 7x7 Go is game that maps a game tree of (more than...) ((7x7)!) posibilities to an result set containing 99 solutions (black wins by 1-49; white wins by 1-49 or jigo). One cannot exclude the possibility that multiple 'optimal' algorithms lead to the same result[1]. In fact, I believe these must exist.

[1] Naturally, i mean this in addition to the symmetries.

willemien dou you mean outcomes/ scores? (the points difference for both players) or optimal games? (sequences of moves from start till finish where neither player has a bettter move)

I don't see the relevance of the first. For the second I think there are more optimal games ,I even think that the number of them can be as high as 10.000 (excluding symmetries and passes but including transpositionings, (useless) forcing moves and so)

Thanks for your comments.

ThorAvaTahr: The meaning of my comment is closer to your second point. But in fact, I would like to stress not only the fact that there are multiple optimal games, but also multiple optimal strategies. For example, let A1 be an algorithm that provides optimal play. When A1 plays a game against another instance of A1 there might be several optimal games, perhaps opening on a star point leads to the same result as opening on 3-4. I am implying that there might also exist another algorithm A2, which also provides optimal play. This means that when matching A2 against A2 as wel as A2 against A1 (either white or black) will all have the same result. However the algorithms can have a difference in "playing style" as A1 may be more territory oriented and A2 might like to build moyo's. In addition there might be an A3 and an A4 and so on. All of these algorithms have different playing style but all when matched against an another algorithm produce the same result.


Willemien/solving 7x7go last edited by HermanHiddema on May 31, 2010 - 15:23
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library