[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 ld 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/
Re: [computer-go] Bent four in the corner was:Scalability problem of play-out policies
On Wed, 23 Jan 2008, Harald Korneliussen wrote: 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. Just a quick note that an algorithm how to evaluate bent four like positions with a minimax search is given in http://lie.math.brocku.ca/twolf/papers/bent4.pdf Thomas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bent four in the corner was:Scalability problem of play-out policies
From: Harald Korneliussen [EMAIL PROTECTED] 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 Thanks for the example! That's the infamous square four - under any ruleset, it is absolutely and irrefutably dead. Mogo mis-evaluated the group as alive, and believed the score to be a win by 6.5. Since the group was dead, Mogo actually lost by 15.5 ( by area counting ) A white play at B1, move 195, was predictable. Had Mogo correctly anticipated and evaluated this nakade, it could have created a more robust shape. Terry McIntyre [EMAIL PROTECTED] 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/
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 ld 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/
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 ld 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/
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 ld 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
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 ld error was severe) but at least
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
Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
I disagree. If the opponent's estimate of the rest of the board is at least as good as program XXX, but the opponent knows a particular group is 100% dead, where program XXX thinks it might live, the opponent is likely to win, with a probability approaching 1.00. Program XXX will be basing its decisions on provably false information. The opponent will spend just enough effort to keep that group dead, and will otherwise play as well as program XXX on the rest of the board. We have all seen that Mogo is not greedy - it will play suboptimal moves while it thinks it has the win. I've read many an argument about how Mogo is actually maximizing win probability; this is total fantasy. When obvious yose ( endgame ) plays or life-making plays are passed up in favor of tossing random stones into perfectly secure eyespace, that is a losing strategy. Better yose handling can ( and often does ) make up for earlier mistakes. Random stones in one's own area will not help. Under area counting rules, playing the da me ( neutral points ) would be better. Terry McIntyre [EMAIL PROTECTED] “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] - Original Message From: ivan dubois [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 23, 2008 7: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
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
By the way, my argument still applies when there are no outside liberties, because the eye filing itself is a long enough UCT trap (a sequence of moves that appears to be just like null moves). I gave a theoretical argument, but actualy it is not very surprising. Did you ever wonder why Mogo, being now so strong, could still exhibit so basic and stupid blind spots ? The explanation is very simple : Those blind spots reveal the fact that some aspects of its understanding do not scale as fast as the other aspects. Actualy for some aspects, it does not scale at all, from a practical point of view. Ivan - Message d'origine De : Michael Williams [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 20h38mn 32s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies ivan dubois wrote: 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). How are you arriving at this conclusion? It makes no sense to me. ___ 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/
Re: Re : Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
ivan dubois wrote: Hello, - Message d'origine De : Michael Williams [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 20h38mn 32s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies ivan dubois wrote: 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). How are you arriving at this conclusion? It makes no sense to me. Actually this is not true for this exact situation, but I think it is true if the black group has enough external liberties. Suppose it has 10 outside liberties, to make things very clear. For the simplicity of my argument, suppose also that the big eye is almost entirely filled with white stones (minus 1 liberty) Here is my reasoning : Starting from the root, there are some playouts where the black group dies, and other where it lives. Let us note X the proportion of playouts that end with the black group having been captured. Now is there any move A, starting from the root, that will change this ratio if you start the random playouts just after A ? I think clearly, the answer is no, do you agree with that ? The only relevant possible move would be to fill a liberty, but since all liberties will be filled anyway during the playouts, this will not change anything to the scenario. The only thing that matters is wether or not white plays first at the vital point every time the eye is reduced during the playouts. Using the same argument, there exists no sequence of less than 8 moves that can change the value of X. This means all these sequences of liberty filling will be considered to have exactly the same value than playing a null move. I think it implies that uct will never (of course in theory it will at some point but I say it would require absurd computing time) find the sequence that captures the group with 100% confidence, because this sequence begins with 8 apparently useless moves. You speak to imprecisely for me, sorry. When questioned, you reverse position. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
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
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
I gave you a proof of what I am claiming, I really dont see what I can do more. Anyway we all now all this is just a waste of time for pleasure. People who are really working on a UCT engine (I dont anymore) will find solutions to these problems as soon as they become relevant to playing strength. You speak to imprecisely for me, sorry. When questioned, you reverse position. ___ 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/
