The Probability of a Monkey Defeating Yi Chang-ho

[speedchase]

We can assume Random But Not Stupid Monkey who will pass if and only if all legal moves fill an eye.

No we can't, it will decide at random. otherwise it isn't a random monkey, it is a almost random monkey.

[Txewì]

We can assume Random But Not Stupid Monkey who will pass if and only if all legal moves fill an eye.

No we can't, it will decide at random. otherwise it isn't a random monkey, it is a almost random monkey.

That's like saying it's only random if it can play illegal moves, or if it can play between the points, or if it can fling mud instead of playing, or ...

We constrain the monkey to play legal moves because otherwise it isn't go. If we don't also relieve it of the obligation to eventually make all of its groups killable, it's not Random Monkey, it's Loses Every Game Monkey, about whom nothing interesting can really be said.

Edited to add: actually, Resigns On Its First Move Monkey would have a rating of ∞ kyu (since it wins 50% of games against itself and 0% of games against everyone else), which is somewhat interesting.

[speedchase]

It could still win 50% of the games if handicapped well. if you starting making it do things besides just following the rules, it is no longer random

[palapiku]

Of course the game has to end at some point so the random monkey needs to be able to pass. So what should the probability of passing be? 1/361?

[Akura]

Of course the game has to end at some point so the random monkey needs to be able to pass. So what should the probability of passing be? 1/361?

First idea: If there are N legal moves on the board, each one and the passing move should have probability 1/(N+1).
Second: As passing is actually a mere expression of "I think we're done", the monkey is not allowed to pass, but Yi Chang-ho says when to stop the game.

[speedchase]

It has to be the first, because otherwise Chang-ho could always just pass, and then the monkey would have to fill in an eye.

[palapiku]

It has to be the first, because otherwise Chang-ho could always just pass, and then the monkey would have to fill in an eye.

But the game stops when he passes.

[Mivo]

Does the monkey jump?

[Mef]

It has to be the first, because otherwise Chang-ho could always just pass, and then the monkey would have to fill in an eye.

But the game stops when he passes.

Lee could play until the only legal move remaining is for the monkey to fill one of his own eyes, then then pass and claim the dead group. It would change things from a monkey beating him at go to "a monkey achieving a position that is both winning in a regular game of go and winning in a game of no pass go" as essentially they would now be playing a skewed form of no pass go (a version where one side may choose to end the game with a pass if it is favorable).

[speedchase]

Lee could play until the only legal move remaining is for the monkey to fill one of his own eyes, then then pass and claim the dead group. It would change things from a monkey beating him at go to "a monkey achieving a position that is both winning in a regular game of go and winning in a game of no pass go" as essentially they would now be playing a skewed form of no pass go (a version where one side may choose to end the game with a pass if it is favorable).

But if he did this, he would have to fill his own territory, and it would become a battle of whether who had more territory too see who could afford to not pass longer.

[lemmata]

The monkey can be understood to be a proxy for something that approximates the lowest complexity algorithm with the lowest memory requirements that has access to a randomization device (e.g., a coin) that has a nonzero probability of beating Yi Chang-ho in an even game. As long as the outcome cannot be predicted, the monkey is playing the game randomly. Monkey might play a non-random move near the end of the game, when there might be only one move in the set of moves that his algorithm generates as possibilities. However, this does not change the fact that the monkey plays the game randomly. If you read the excerpt, the author says that he can assume that the monkey's first move will not be on the first and second line, so we can assume that the monkey knows some minor things.

Nevertheless, I imagine that most human beings who have learned the rules will beat this monkey most of the time. However, I am confident in saying that a KGS 1 dan, which might beat the monkey 99.99999999999+% of the time, has exactly zero probability of beating Yi Chang-ho in an even game. So something seems amiss in the author's view of go ranks.

By saying that an amateur 1 dan player (let alone a monkey) has a nonzero probability of beating Yi Chang-ho in an even game, the author is implicitly suggesting the following model of go player ranks:

• Let ps stand for the set of next moves that are considered by a player of strength level s (where higher is better) in position p.
• Let P be the set of all legally reachable positions in even games and let S be the set of all strength levels.
• Player in position p whose strength level is s generates the set ps and chooses randomly from it.
• For all p in P and for all s, s' in S such that s > s', ps is a weak subset of ps'.
• For all s, s' in S such that s > s', there exists at least one p in P such that ps is a strict subset of ps'

This is a model of go ranks in which weak players are weaker because they haven't eliminated enough bad moves from their repertoire and go players of all ranks never exclude good moves from their repertoire.

However, don't you find that weak players often don't consider any good moves in many positions? For a given (p,s,s') where s > s', there may not be a subset relationship between ps and ps'. The sets ps and ps' might even have an empty intersection. The moves in ps might be superior to ps' in enough positions p that s' has zero chance of beating s.

None of this might be relevant to the larger point being made by the book, which is unknown to me because I have not read it. If the only point that the author wants to make in this short excerpt is that it is difficult to move up one rank. I agree with the author's conclusion, even if I don't agree with his reasons, so I'd be more interested in his next, more important point that this conclusion presumably sets up.

[Fedya]

Nevertheless, I imagine that most human beings who have learned the rules will beat this monkey most of the time. However, I am confident in saying that a KGS 1 dan, which might beat the monkey 99.99999999999+% of the time, has exactly zero probability of beating Yi Chang-ho in an even game. So something seems amiss in the author's view of go ranks.

My understanding is it implies the 1d amateur has a non-zero probability of beating Yi Changho if he plays randomly.

Or, as I prefer to call that style of play when I play it, "wild guessing". Not that it would help be defeat Yi, of course.

[speedchase]

A random monkey MUST be able to beat Yi a non zero amount, because there are sequences of moves that would lead to Yi loosing, and the probability that each sequence is played is 2*(180-n/2)!/361!
where n is the number of moves in the game.

[tchan001]

In a way, the random monkey reminds of of the monte carlo tree search algorithms used by computer go programs which have had some very good success within the real go world against amateur dans. It's like mining the results of a very large series of games by blitzing random legal monkeys.

[Akura]

...the probability that each sequence is played is 2*(180-n/2)!/361!
where n is the number of moves in the game.

So n is the number of legal moves on the goban when it's the monkeys turn? Could please describe, how you came up with this term (or rather with the numerator), because I just cannot see it?