Heikki Levanto wrote: > On Wed, Jan 30, 2008 at 03:23:35PM -0500, Don Dailey wrote: > >> Having said that, I am interested in this. Is there something that >> totally prevents the program from EVER seeing the best move? I don't >> mean something that takes a long time, I mean something that has the >> theoretical property that it's impossible to every find the best move, >> even given eternity? >> > > Someone, I think it was Gunnar, pointed out that something like this: > > 5 | # # # # # # > 4 | + + + + + # > 3 | O O O O + # > 2 | # # + O + # > 1 | # + # O + # > ------------- > a b c d e f > > Here black (#) must play at b1 to kill white (O). If white gets to move > first, he can live with c2, and later making two eyes by capturing at b1. > > Depending on the definitions, b1 can be seen as an 'eyelike' point, and will > not be considered in any playouts. No amount of UCT-tree bashing will make > the program play it. > You are totally incorrect about this. First of all, saying that "no amount of UCT-tree bashing will discover this move" invalidates all the research and subsequent proofs done by researchers. You may want publish your own findings on this and see how well it flies.
You probably don't understand how UCT works. UCT balances exploration with exploitation. The UCT tree WILL explore B1, but will explore it with low frequency. That is unless the tree actually throws out 1 point eye moves (in which case it is not properly scalable and broken in some sense.) There are two cases. In the first case, it doesn't matter whether black plays the right more here or not, black has a won game even if he lets white live with c2. The other case is that black MUST kill the white group to win the game. UCT will "eventually" discover the game is lost in all other lines, and start giving more attention to b1. UCT will do this as a natural consequence of the way it works. What you guys don't seem to grok is that not matter what game you want to consider, it's possible to construct arbitrarily difficult positions. There is nothing special about go in this sense except that it's easier to find these positions than for many other games. But so what? I'll grant you that some positions are more difficult than others. I'll grant you that you can construct positions that are difficult for computers but easy for humans. You can do this in chess too. You can do this in any non-trivial game but it is a lousy argument against scalability. If you can show me a proof or position that cannot be eventually solved, then you at best have an argument that this could hold it back from reaching perfect play, but you can only guess about where the ceiling is. Based on what Gian-Carlo Pascutto says, "strength doesn't work that way", a program can be remarkably strong even though it has weaknesses that might even seem "unfathomable" to us. It's certainly not the case that because someone is weaker than you in some area that you MUST be a stronger player. They could be so superior in many other ways that you might as well resign before you even start. There is a story about a chess grandmaster who didn't understand one of the fine points of castling. This is a very common move in chess and it's almost unfathomable that he didn't know the rules. Somehow, this did not prevent his rise to the grandmaster levels. In the right position a beginner who knew the rules could outplay him. But do you think there is any realistic chance that a beginner would beat him in a serious game? - Don > In random playouts, it is 50-50 who first egts to c2. But it does not matter, > as white lives in any case (at least as long as he has some outside > liberties, I think). > > As I mentioned earlier, it is possible to get around that by allowing even > eye-filling suicide moves in the UCT tree, even if not allowing them in the > playouts. Even then, the UCT tree has to extend to the point where this kind > of situation can occur, before the program can see it. > > > > > - Heikki > > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
