Feed any MC-UCT program the position after White B1, at move 195, and ask the
probability of a black win. Repeat until the program corrects its estimate.
It would be interesting to determine just how many simulations are needed to
solve this problem - which is obvious to double-digit kyu players.
Terry McIntyre <[EMAIL PROTECTED]>
----- Original Message ----
From: ivan dubois <[EMAIL PROTECTED]>
To: computer-go <computer-go@computer-go.org>
Sent: Wednesday, January 23, 2008 7:17:17 AM
Subject: Re : [computer-go] Bent four in the corner was:Scalability problem of
play-out policies
Hello,
After thinking a bit more about it, I came to the conclusion that the
so called "Bent four in the corner" shape, is not such a serious
scalability killer (I like this term).
Nor is the situation that appears in your game.
Let me explain why :
It would indeed be a scalability killer if Mogo was 100 % sure that
some group is dead, when it is actually alive. However what happens is
that it has some doubts about the situation. It may think for example
it is 60 % alive and 40 % dead. Of course it would be better for him to
know the reality, but having some persistent doubt on it is not that
much detrimental. For example if he has perfect information about the
rest of the board, he will play perfectly on the rest of the board.
I propose a chalenge to this list : Find a real scalability issue with
Mogo or any other actual UCT program. (And prove it)
Ivan
----- Message d'origine ----
De : Harald Korneliussen <[EMAIL PROTECTED]>
À : computer-go@computer-go.org
Envoyé le : Mercredi, 23 Janvier 2008, 15h31mn 20s
Objet : [computer-go] Bent four in the corner was:Scalability problem
of play-out policies
Ivan Dubois mentioned the bent four in the corner shape as a
scalability killer, a situation where more playouts doesn't help
(much), because playouts systematically misevaluate it. As I
understand it, it could be corrected in the tree, but this is very
unlikely to happen until the very end of a game, by which time it may
be too late (Mogo having worked the entire game for that solid 0.5
win, which turns out to be a solid loss instead because of the
life-and-death misevaluation)
I recalled a KGS game of Mogo I'd looked at, where something very
similar happened, and with a little digging I found it again:
http://files.gokgs.com/games/2007/12/1/Ardalan-MoGoBot3.sgf
It turns out it's not the "bent four" shape, but I suspect it's
another such shape, where more playouts only confirm that "these moves
aren't worth including into the tree", so that UCT catches them very
late, if ever.
If these situations can be reliably created by a human, then indeed
they put an upper limit on the "real world" scalability of a program.
If I should propose a hackish heuristic to deal with such situations,
this is it: At one point, when the problematic shape appeared, the
human must have done a move that to the computer seemed horribly bad.
"Why did he do that? Doesn't he see that my shape is alive?". When
such situations occur, there are two possibilities:
1. The bot is playing a weaker human player, and the move is indeed
bad.
2. The bot is playing a stronger human, and the move is actually good.
I think it may be a good idea to do something with the weighting in
these situations, so that the relevant moves are added to the tree. In
worst case, a lot of effort is wasted in proving a bad move bad - but
this should not be so serious, as the bad move will likely mean the
opponent has poor chances of winning anyway. In the best case, the
program's blunder is revealed after the fact. This may still leave
little chance of winning, (if the l&d error was severe) but at least
the program's counting won't be off for the rest of the game. Since
today's programs don't care for winning margins, counting errors by
even a single point will spell disaster.
I believe this heurtistic would be cheap in terms of computational
cost, but hard to evaluate/tune. Self-play would not be very
effective...
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_____________________________________________________________________________
Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo!
Mail http://mail.yahoo.fr
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
____________________________________________________________________________________
Looking for last minute shopping deals?
Find them fast with Yahoo! Search.
http://tools.search.yahoo.com/newsearch/category.php?category=shopping_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
