Re: [computer-go] Re: verifiable claims
Don Dailey wrote: I think the proof tree for both sides can avoid those nearly infinite loops. I do agree that there are some practical difficulties to doing this and being able to claim it's a proof. One might start with a weak solution that makes some presuppositions like Never play inside a two-eye-formation.. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
Don Dailey wrote: There is no need to explore every cycle to get your proof. Long cycles are a good example where one can start by making a weak solution. Just change your presuppositions. Invent a long cycle rule like A play recreating the position after 4+ plays ends the game (or your game tree branch of proof-play) immediately and exceptionally with the result tie.. You could even write 3+ instead of 4+; it would not be human-friendly (traditional) in a sending-2-returning-1 then but you don't care. Or add another rule: Ko-capturing in a basic ko is prohibited. Or use the Fixed-ko-rule. Then you can study Go without ko fights and solve it first. You avoid all your cycle worries! Worried about big captures? Make yet another presupposition: It is prohibited to make a play that captures more than X stones. When you will have solved Go under these simplifications, you can still release your restrictions iteratively. Start with X=0, then X=1, then X=2,... -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
Having made suggestions for how to start study by restricting tree depth, let me continue by making suggestions for restricted breadth. For decades everybody has been complaining about a too great branching factor. Cut it right at its source: Add presuppositions aka rules that restrict it. Examples: It is prohibited to atari a string while creating a ladder. The next play may not be farther than X intersections from the previous play's nearest strings. Condition C must be fulfilled for playing farther than X intersections from the previous play. You could also invent rules that depend on the structure of game trees! Do you notice a similarity? MC has done such. Not on the rules level but on the heuristic search level. MC is a way of creating weak solutions in a sense and it has been a bit successful. Why not also create weak solutions on the level of presuppositions and rules?! Just because we are too proud to solve anything less than Go under complete ordinary rules immediately? -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: verifiable claims
I've written dozens of games with alpha-beta searches, so I think it's fair to say that I have a basic understanding of the process. Your description is correct but incomplete. Alpha beta is good at eliminating lines of play once a strong outcome is known somewhere in the tree, but much weaker before that. If a big capture occurs at ply 30, but the shortest win is at ply 60, you still have to explore an enormous number of silly variations as you iteratively deepen between ply 30 and 59. The fact that you don't need to explore continuations of the silly moves past move 59 is cold comfort. The other half of the bad news is that while only the best move of the winning lines needs to be explored, generally all of the possible responses have to be explored. So the tree actually explored tends to be narrow for the winning line, but very wide as all possible responses to the correct move are explored. In the case of a big capture being the correct move, pitching into every one of the captured spaces will have to be explored. Alpha beta engines which do not use inadmissible (but probably valid) tricks waste exponentially more time than those that do. It's quite possible that 5x5 is on the sweet side of the equation with today's available CPUs, but at some point not much further away, you have to accept results that you believe but can't prove, as better than no result at all. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
On Sat, May 23, 2009 at 4:01 AM, Dave Dyer dd...@real-me.net wrote: I've written dozens of games with alpha-beta searches, so I think it's fair to say that I have a basic understanding of the process. Your description is correct but incomplete. Alpha beta is good at eliminating lines of play once a strong outcome is known somewhere in the tree, but much weaker before that. If a big capture occurs at ply 30, but the shortest win is at ply 60, you still have to explore an enormous number of silly variations as you iteratively deepen between ply 30 and 59. The fact that you don't need to explore continuations of the silly moves past move 59 is cold comfort. The other half of the bad news is that while only the best move of the winning lines needs to be explored, generally all of the possible responses have to be explored. So the tree actually explored tends to be narrow for the winning line, but very wide as all possible responses to the correct move are explored. In the case of a big capture being the correct move, pitching into every one of the captured spaces will have to be explored. Yes, it will have to be explored, but with iterative deepening it is not explored to the end of the game. Alpha beta engines which do not use inadmissible (but probably valid) tricks waste exponentially more time than those that do. It's quite possible that 5x5 is on the sweet side of the equation with today's available CPUs, but at some point not much further away, you have to accept results that you believe but can't prove, as better than no result at all. What we are talking about is solving 5x5 boards, nothing more. 7x7 is out of the question right now and probably for a very long time. I'm certainly not saying that you won't explore silly lines - you certainly will with full width alpha beta search. But the long cycles silly moves will be minimal because alpha beta with good move ordering will try the silly moves last and they will be mostly irrelevant and get cut off.Your search is NOT going to be dominated by long cycle KO moves where you explore every possible way to fill the same space over and over again. - 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/
[computer-go] Re: verifiable claims
Some lines of play involving large captures will effectively never terminate, even with superko rules in effect. I doubt it is possible to eliminate all these non-terminating lines of play in any way that is provably correct. .. So while claims of solution by exhaustive search might be very convincing, I doubt they can ever be proved. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
On Fri, May 22, 2009 at 5:47 PM, Dave Dyer dd...@real-me.net wrote: Some lines of play involving large captures will effectively never terminate, even with superko rules in effect. I doubt it is possible to eliminate all these non-terminating lines of play in any way that is provably correct. .. So while claims of solution by exhaustive search might be very convincing, I doubt they can ever be proved. You can just prove that you can make a large-enough chain that is unconditionally alive. I believe that's what Erik did. In practice, you cannot do an exhaustive search using superko rules because then hash table scores cannot be used. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
On Fri, May 22, 2009 at 5:47 PM, Dave Dyer dd...@real-me.net wrote: Some lines of play involving large captures will effectively never terminate, even with superko rules in effect. But both sides need not play into this to build a proof tree. By the way, an alpha/beta search IS IN FACT a proof, but it has to be constructed properly. I doubt it is possible to eliminate all these non-terminating lines of play in any way that is provably correct. .. So while claims of solution by exhaustive search might be very convincing, I doubt they can ever be proved. Of course it depends on the board size. I think 5x5 can be properly cracked open in the near future. I think the proof tree for both sides can avoid those nearly infinite loops. I do agree that there are some practical difficulties to doing this and being able to claim it's a proof. - 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/
[computer-go] Re: verifiable claims
You can just prove that you can make a large-enough chain that is unconditionally alive. I believe that's what Erik did. In practice, you cannot do an exhaustive search using superko rules because then hash table scores cannot be used. I don't think you can always do that. For example, if white is capturing a chain of size 30, how can you prove that black can never profit by continuing inside that 30 space void. In fact, in many cases you can demonstrate that he should. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
there are no chains of size 30 on a 5x5 board, and if after a large capture the remaining stones are unconditionally alive the void at the location of the capture cannot be very large. Do remember that we are talking about 5x5 with the first move in the center as the winning move. Cheers, David On 22, May 2009, at 3:15 PM, Dave Dyer wrote: You can just prove that you can make a large-enough chain that is unconditionally alive. I believe that's what Erik did. In practice, you cannot do an exhaustive search using superko rules because then hash table scores cannot be used. I don't think you can always do that. For example, if white is capturing a chain of size 30, how can you prove that black can never profit by continuing inside that 30 space void. In fact, in many cases you can demonstrate that he should. ___ 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/
[computer-go] Re: verifiable claims
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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: verifiable claims
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/
