i.e.,
any case where discovering a particular position
would require making illegal moves during that
playout with respect to the move policy in place.
so for instance, if the only way to discover the death of a
group is to play inside one-point eyes, and there's a playout
policy that says to never play inside one-point eyes, then
the death of the relevant group will never be discovered, and
will have zero estimated probability of ever occurring. not that
it will have vanishingly small probability, but that it will have
p=0.
if this group is all that keeps two larger groups connected, for instance,
then this is a problem for the understanding of the whole board
situation.
this has been beaten badly to death, however, so i'll take any
responses off-list.
s.
----- Original Message ----
From: ivan dubois <[EMAIL PROTECTED]>
To: computer-go <computer-go@computer-go.org>
Sent: Wednesday, January 23, 2008 11:45:01 AM
Subject: Re : Re : [computer-go] Bent four in the corner was:Scalability
problem of play-out policies
Hi,
This is correct.
Do you think there will be no playouts where the group dies ?
I think there will be around 50% where the group dies. If you think
this is not the case, please explain to me.
Ivan
----- Message d'origine ----
De : steve uurtamo <[EMAIL PROTECTED]>
À : computer-go <computer-go@computer-go.org>
Envoyé le : Mercredi, 23 Janvier 2008, 17h22mn 35s
Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability
problem of play-out policies
it will only assign it a positive probability of being
dead if there are playouts where the group dies, right?
s.
----- Original Message ----
From: ivan dubois <[EMAIL PROTECTED]>
To: computer-go <computer-go@computer-go.org>
Sent: Wednesday, January 23, 2008 10:51:52 AM
Subject: Re : [computer-go] Bent four in the corner was:Scalability
problem of play-out policies
Hello,
I agree that the current implementation of Mogo (from what I know about
it) will not know for sure that the D17 black group is 100% dead.
It will think that it is X% dead and stick to that estimation,
whatever thinking time you give it. X is a constant that does not depend of
thinking time (no scalability).
However, and this can be surprising, I am not sure wether it is really
a scalability killer for whole board play, because after all, it doesnt
have to know with 100 % confidence the status of one group to play
perfectly.
----- Message d'origine ----
De : terry mcintyre <[EMAIL PROTECTED]>
À : computer-go <computer-go@computer-go.org>
Envoyé le : Mercredi, 23 Janvier 2008, 16h24mn 53s
Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability
problem of play-out policies
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.
Ne gardez plus qu'une seule adresse mail ! Copiez vos
mails vers Yahoo! Mail
____________________________________________________________________________________
Never miss a thing. Make Yahoo your home page.
http://www.yahoo.com/r/hs
_______________________________________________
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/
____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now.
http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
