Simple Sure Win Strategy for White Human Player vs GnuGo 3.8

For discussing go computing, software announcements, etc.
hyperpape
Tengen
Posts: 4382
Joined: Thu May 06, 2010 3:24 pm
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
Location: Caldas da Rainha, Portugal
Has thanked: 499 times
Been thanked: 727 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by hyperpape »

Mike Novack wrote:
jts wrote: Glofish may be 1d, but the instructions he came up with are not 1d instructions.


Who suggested that they were? (1 dan instructions)

But are you willing to agree that they are perhaps 6-8 kyu instructions? Gnugo isn't supposed to be anything like as strong as 6 kyu.

The instructions are (in effect) to coordinate one's separate positions so that they have a combined effect, that gnugo has a weakness in that it will not attempt to contest this. But isn't that sort of coordination precisely the sort of thing human players as weak as gnugo have trouble with?

To demonstrate that this is a method that human players significantly weaker than gnugo could use to easily defeat gnugo need to have games between players of those strengths an gnugo. Since there are a number of bots using gnugo, all we should have to do is wait and see if there is a noticable decline in the rankings of these bots.


1) I think a substantially weaker player could execute these instructions. They require judgment about when cuts can happen that might cause problems for a 15 kyu, but I think a 10 kyu could do it. It would be nice to have someone try.

2) Your point at the end depends on their being ratings arbitrage on KGS. It is easy to imagine that this would not happen (I wrote about this a tiny bit: viewtopic.php?f=18&t=2646&p=43981&hilit=arbitrage#p43981).

3) What is remarkable about GnuGo's errors, as opposed to those of a human, is that they lend themselves to an easily taught strategy to get a win. Every human makes strategic errors. But I don't think you can typically play a 10 kyu, diagnose their errors, then give another 10 kyu a recipe to beat them. Glofish has shown that you can do that with GnuGo.

I think this point goes a bit beyond deterministic play. What you have to teach the 10 kyu in order to beat GnuGo is not general principles of Go, nor do you need to show them a game tree. You can teach them a few tricks, and they can use those to beat the bot (assuming that my claim that you could do this is right).

4) A question out of curiousity: how consistent are current MCTS systems' evaluations of a position/move? That is, if you give them reasonable time controls & hardware, do they tend to give the same moves high ratings? I suppose the most interesting case is a game that is fairly even, and not in the endgame, but the other cases might be interesting.
Mike Novack
Lives in sente
Posts: 1045
Joined: Mon Aug 09, 2010 9:36 am
GD Posts: 0
Been thanked: 182 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by Mike Novack »

hyperpape wrote:
4) A question out of curiousity: how consistent are current MCTS systems' evaluations of a position/move? That is, if you give them reasonable time controls & hardware, do they tend to give the same moves high ratings? I suppose the most interesting case is a game that is fairly even, and not in the endgame, but the other cases might be interesting.


They are making fundamental use of probability in the evaluation. Even though they may be playing out a great many random moves so "large numbers involved probability doesn't work the way most people think it will*.

1) The greater the difference between the (top) moves they are evaluating the greater the probablity they will select the same) better move. Like when a human expert looking at a game situation sees some particular move as "the only move" they will be extremely probable to select the same move again if you repeat the situation. The greater tha amount this move is better than any of the others being considered the more likely it will be made the next time around. But it is not certain.

2) But if the difference between the top moves is less, one only somewhat better than the other, the sort of situation where an expert evaluating the position says "I give this move 100% but these others move, perhaps playable, only 80%" then the next time around might or might or might not select one of the other moves.

I would be suspicious of the "adjustment" or "randomness" of a MCTS program if is seemed always to select the same move but you could see some alternate way to play. These programs have only pseudorandom generators but it would be possible to work in true random factors as the game progresses (how many microseconds for the opponent to make the last move for example -- so reset random every turn and that wouldn't be the same when game repeated).

3) The game has to be relatively even or the bot ahead for the MCTS algorithm to work properly. As they are currently designed, if hopelessly behind they have no choice between "resign" and "suicidal counterattack" (and so will make some rather bad moves). I believe it would be possible** to modify these programs to play more humanlike in this situation (to play "resigned to a modest loss") but it is probably too early for developers to consider work on that option unless there is strong user demand for it.

* example --- if we flip an honest coin 10,000 times we should not expect to get 5,000 heads and 5,000 tails. This is indeed the most likely SINGLE outcome but there are a large number of possible outcomes gradually becoming less and less likely as we get farther and farther from 50-50. Because so many more possibilities out in the "tails" even though each unlikely we can expect that our outcome will be within about 5,300 - 4,700 (either heads or tails in the lead) and outside that division (less even a split) about half the time.

** What I would try is have a split "consider resigning" routine. If it estimates that its chances of winning are too low for the algorithm to work properly (none of the moves considered has more than a low probability) and this option is in effect, the first time make a dynamic adjustemt to the evaluation komi (it will lose by at least that amount but "thinks" it will win so can keep playing normally) but if it again considers resigning, resign. I think that would work to get the machine to play out losing games more normally.
User avatar
daal
Oza
Posts: 2508
Joined: Wed Apr 21, 2010 1:30 am
GD Posts: 0
Has thanked: 1304 times
Been thanked: 1128 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by daal »

Ok, I spent three minutes teaching the strategy to a 16k. Here is the game:

Patience, grasshopper.
GloFish
Beginner
Posts: 8
Joined: Thu Jan 27, 2011 1:09 am
Rank: 1d
GD Posts: 0
Been thanked: 1 time

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by GloFish »

daal wrote:Ok, I spent three minutes teaching the strategy to a 16k. Here is the game:


Heh, thank you for that nice experiment, it exceeds my expectations. :bow:

I hope that convinces Mike ;-)
User avatar
daal
Oza
Posts: 2508
Joined: Wed Apr 21, 2010 1:30 am
GD Posts: 0
Has thanked: 1304 times
Been thanked: 1128 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by daal »

Just to be fair, I also taught it to a 9k, who lost when gnugo played 5-4 corners. The player said that the territory he got in the center was just too small. :shock: I suspect he goofed somewhere, but unfortunately he couldn't find the game. He did however try again and won easily.
Patience, grasshopper.
User avatar
karaklis
Lives in sente
Posts: 797
Joined: Tue Apr 20, 2010 2:14 pm
GD Posts: 600
Has thanked: 93 times
Been thanked: 105 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by karaklis »

I taught it to my son (around 14-16k), and at the second try he made it. At the first try GnuGo tried an invasion (I don't know what caused the engine to try an invasion, maybe the reason is that I used GnuGo 3.9). After I taught my son how to kill the invasion, he made it on the second try.
abartos
Beginner
Posts: 1
Joined: Thu Feb 10, 2011 3:27 am
Rank: 16k
GD Posts: 0

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by abartos »

I'm 16k, and it was easy for me to implement this strategy against gnugo, even on level 16. The strategy also works in pretty much the same way against Many Faces of Go version 11, on level 10, and against Aya, on the strong setting.
User avatar
daniel_the_smith
Gosei
Posts: 2116
Joined: Wed Apr 21, 2010 8:51 am
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: daniel_the_smith
Location: Silicon Valley
Has thanked: 152 times
Been thanked: 330 times
Contact:

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by daniel_the_smith »

Wow, abartos, that's crazy!

Do monte carlo engines fall for this too? I would assume that they never would, but...
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
Mike Novack
Lives in sente
Posts: 1045
Joined: Mon Aug 09, 2010 9:36 am
GD Posts: 0
Been thanked: 182 times

Re: Simple Sure Win Strategy for White Human Player vs GnuGo

Post by Mike Novack »

I don't think so (that any of the MCTS evaluators would fall for this).

But first might be interesting to see if a current AI evaluator does. Folks really need to keep in mind that "just a couple years old" is a long time in the state of the art. And being dependent on the availablility of volunteer developer time the gnogo versions available now have to be considered on a par with somewhat older commercial programs. Don't get me wrong, I am a big fan/user of "free software" but mainly for uses where being a couple years behind the state of the art means little/nothing.

MFOG does use an AI move generator and below the top two levels also uses an AI evaluator to choose the move (from the generated set of plausible moves).

So try MFOG 12.022 at the 6 kyu level to see if its evaluator is still as bad deciding between local and global considerations (this "simple method to defeat" is the result of the evaluator not adjusting for the total cummulative effect of either territory or influence*).

To settle the question of whether a MCTS evaluator can be tricked this way then try the top two levels of MFOG 12.022 or any other MCTS program you prefer. I am not trying to tout some particular program -- simply know for some better than others how they function. I don't know if any of the other MCTS programs even have an AI move generator** let alone an AI move evaluator for the lower levels.

But really! Don't be telling us what MFOG 10 can't do or even MFOG 11 unless you clearly spell out for folks "this is only informational about what a very badly outdated/superceded program can or cannot do". The problem is that too many people assume that their exerience of how a program behaved a couple years ago remains valid for expectations of how it would behave today. Have to keep reminding them that in this game a couple years is a long time.



* Take gnugo for example. Version 3.8 offers a choice between evaluation based on local territory or global (the "cosmic" setting) but not an option where it sometimes will use one or the other method depending on "the state of the game" (or even randomly --- were I doing gnugo development for the AI only version that's what I would try first; a parameter that would set the probability of using either regular or cosmic evaluation for the next move).

** The effect of this (using an AI move generator) is to make the machine player "more human like". Won't be making an super strange moves, moves with no apparent purpose (though of course, these may be good moves down the road). The reason to use MFOG for the experiment is that in this case we do know it has an AI move generator so if this "defeat the program" method works against the lower levels (AI evaluator) but not the two highest level (MCTS evaluator) then we have determined that the problem is with evaluation, not move consideration.
Post Reply