On Fri, May 22, 2009 at 10:19 PM, Dave Dyer <dd...@real-me.net> wrote:
> At 06:31 PM 5/22/2009, David Doshay wrote: > >there are no chains of size 30 on a 5x5 board, > > I'll concede for a 5x5 board, but I think my point > is valid for "sufficiently large" boards, probably 7x7. > > Almost any strategy other than playing out all legal moves > involves a lot of hand waving that is unlikely to be > accepted as a proof. There are just too many cases where > a pitch inside a captured space has global effects. There is no need to explore every cycle to get your proof. I have noticed before that you don't understand how basic alpha beta minimax search works. Here is how it works. Construct an iterative deepening recursive search that returns one of 3 values, it's a win for white, a win for black, or the result is undecided. Do a 1 ply search. If the score returned is -1, the opponent wins and only needed 1 ply. If the score is 1, the side to move wins and only needed 1 ply to do it. If the score is zero, it did not terminate. So you then do a 2 ply search with the same logic. Continue adding an extra ply until the search returns with a non-zero score. We are assuming some half point komi. Ridiculous cycles will be avoided, because the winning player is going to find the shortest proof with iterative deepening. There is no need for the winning side to entertain off-beat lines beyond the current depth goal. You seem to have this idea that because it's possible to have ridiculously long cycles, that they all have to be searched to whatever depths is required to learn the truth. The longest line that needs to be explored is the length of the shortest game that proves who the winner is. Now it could be the case that in some position with a good defense the game can be delayed a few moves with some trick, but it's nothing like the picture you paint where the opponent can take you on infinitely long wild goose chases. You have as much control of the game as your opponent so there is no need to explore a 10,000 move line when a 20 move line wins. You are just thinking about this all wrong and I think you just have a fundamental misconception about how search works. I think with 5x5 this is almost feasible or will shortly be so. Was it Erik who did the 5x5 solver? From what I remember of the paper on this, it sounds like this was pretty close to a proof, or at worst a good outline of how a proving program would work. - Don > > _______________________________________________ > 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/
