I've put a lot of thought into this. 5x5 is about the largest feasible board size (currently) for creating an "endgame database" which is a table of all possible positions with the resulting score. I don't know if anyone has done this, but I know that this board size can be solved with brute force search using hash tables - chess program style. Even a "small" problem like this takes a lot of resources doing it in this way and being able to evaluate endgames with Benson's algorithm is apparently important to make it possible on current hardware.
To go beyond 5x5, say 7x7 would require an endgame table with 3**49 entries or 239299329230617529590083 entries. This can be reduced by about 8x if you remove symmetrically equivalent positions. This is pretty intractable, won't happen any time soon. Nor is it likely to be searched by brute force methods. But time and space can be traded off. You could substitute an evaluation function for the endgame database table. Suppose you only wanted win/loss data for any supplied position assuming some komi. You write some evaluation function that takes some position as input and returns a boolean indicating whether it's a win or loss. See how easy to solve this problem! Of course this is absurd, such a function seems to be impossible to write. But suppose we had the ability to write a GOOD function that returned the correct result a very high percentage of the time? Then we only need to build an exception table that tells us when the function is wrong! Nevertheless, we still have many difficulties. Not the least of which is to build an evaluation function that is correct a large percentage of the time. When we say "large percentage" we mean HUGE. The exceptions have to fit in a table, so we have to be able to cover 3**49 with only a few billion exceptions! This seems almost as difficult as writing a perfect evaluation function. Another difficulty is that even if you could do all of this and have the space, it's not clear how to BUILD the initial table. But the only thing that gives hope is that such a database has extremely low Kolmogorov complexity (which means it can be expressed with a very short program.) I suspect the table is extremely compressible if expressed correctly. Although it's computationally difficult to build such a table, It's not too difficult to test an evaluation function probabilistically. If you have a function that returns win or loss for any supplied position, then a 1 ply search should return the same score as a 2 ply search and so on. If it doesn't, the function is imperfect. You could try a large number of positions doing a few ply per position and see if the alpha/beta search is consistent. The more positions that are searched, the higher your confidence that it is correct. The only problem with such an approach is that it can be self consistent but wrong. (self delusional.) But it could be tested on known wins and losses. (if it returns that black always wins no matter what on any position, it would be self-consistent, but wrong!) You might be able to try to build a good binary evaluation function with some kind of trial and error process. Using this as a test, you can evaluate the quality of the evaluation function in some kind of probabilistic fashion. So you could use a learning algorithm, such as genetic algorithm or such. The fitness test is what percentage of positions return a self consistent result - but with a mechanism to prevent it from being self-delusional. Even if you were able to produce an evaluation function that "seemed" to pass this test, I think it's computationally difficult to prove that it is correct. It might be wrong 1 out of a trillion times but no matter how many positions you tested it on, you couldn't prove is was admissible unless you tried every single position! My conclusion is that we won't be able to solve 7x7 any time soon in a provably correct way. I don't even think we will be able to build a program that is "believed to be perfect" any time soon, even in 7x7. But it might be possible to build a 7x7 program that is really quite strong - I think we already have this. - Don Ben Lambrechts wrote: > > I want to create a perfect player on board sizes 3x3, 5x5 and maybe > 7x7 and beyond. > > But I have no idea how to start. How do I create the move database and > how do I select the perfect move for every position? > > > > I know Go is solved on boards 5x5 and smaller, but there is no program > that plays by this perfect moves. > > > > Has anyone did this before or has anybody thoughts about this? > > > > Ben > > ------------------------------------------------------------------------ > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
