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.

Does the monkey jump?

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.

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.

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.

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.

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.

_________________
http://tchan001.wordpress.com
A blog on Asian go books, go sightings, and interesting tidbits
Go is such a beautiful 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?

In the equation, N was the number of moves in the entire game. looking back at the math, I think I made a mistake, but I was on the right order of magnitude.
basically, at any given time, the chance that the monkey plays the correct move is 1/X (where x is the number of legal moves). at the beginning of the game x = 361, and decreases by 1 every turn (with some exceptions, but these are minor in the grand scheme of things). The probability that the monkey will follow the winning path again is x at the first move times x at the second move ... all the way to x of the last move. this is 361*360*359.....*(361-n) (where n is the number of moves in the game. this makes the probability of the monkey following the path 1/(361!/ (361-n)!), which equals (361-n)!/361!). There is a twist though. The monkey doesn't have to play all of the moves, only half, which makes it much more likely for him to win. that is what I was trying to calculate, but basically what I have is enough to prove that it is possible, albeit unlikely for the monkey to win. Also, this does overlook that there are many possible ways to beat Yi, however that is easy to calculate. Just multiply the result by Y (the number of ways to win.

Is it really a 0.0039% chance that an 8d would beat a 9d? Although perhaps if it is an 8d amateur vs a 9d pro I could see that, but if you are talking 8d pro vs 9d pro, I'm sure they win more likely than that.

Technically, if you won 45% of the time against a certain rank, you are lower rank (since it is not 50%), why the 25%?

Nothing to say for the monkey. I think it'd be very slim chances random moves of a monkey could even beat a 30k.

_________________
TucsonGo.org - Play Go in Tucson
We meet twice a week, visit us!

I must say that I perceive this thread as quite discriminatory against monkeys.

<g,d&r>

_________________
“The only difference between me and a madman is that I’m not mad.” — Salvador Dali ★ Play a slooooow correspondence game with me on OGS?

Ranks are continuous. If I am a 9d (god, I love hypothetical examples) and you're 8d, I can give you a stone's handicap. But there are players I can beat more than 50% of the time to whom I cannot give a one stone handicap.

_________________
Occupy Babel!

i am intrigued... what are chances for a 1d to beat a 9p (P1)? and are they better or worse than those for a random monkey vs 9p (P2)?

clearly P2 > 0, as there are ways to beat a 9p.

it is tempting to claim that P1 > 0, but i see no simple argument (dis)proving this. but i think it is a safer bet to say that a 1d can beat a 9p, contrary to lemmata's opinion few posts higher ("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.")

and, P1 < P2 or P1 > P2? if i was the 9p, i would without much thinking choose the monkey as an easier opponent. indeed, the monkey usually lose even against the 1d and most likely i wouldn't have to unleash anything of my super-9p-powers and win effortlessly. but i am still not sure about the 1d... he could avoid huge majority of pitfalls beating the monkey, but he would also miss some of the winning paths due to his limited vision.

so, who is better off in the end? i can't decide and this is my third attempt to formulate my questions into a post, finally good enough to my satisfaction

_________________
Spilling gasoline feels good.

I might be wrong, but probably not.

A 0.0039 probability is a 0.39% chance.

That aside I intuitively consider a KGS 1d has a greater chance of beating Lee Changho than the monkey does of beating the KGS 1d. However, I may be mistaken - for sure, I think that a 20k player has literally no chance of beating Lee Changho, whereas the monkey does have a non-zero chance. The reason for this is the very non-randomness of the human brain will predispose the 20k player to repeatedly make mistakes. The monkey has access to the entire tree of Go possibilities, whereas the human will attempt to apply what knowledge and reading is available to him to make superior moves, and therefore both increase his overall performance compared to the monkey, but almost completely remove his ability to play a game devoid of mistakes.

All of it makes the theoretical rank argument rather moot - it's an abuse of mathematical probabilities. Probabilities like this are only going to be vaguely realistic without any external factors influencing the outcome. With humans in involved affecting the outcome by making decisions, this is not the case. Probabilities do not predict the future with any more accuracy than the complexity of the model on which they're generated.

I really thought Roger Federer was going to beat Andy Murray in the Olympics at Tennis. If I looked at history (both vs and generally against other top players), I could have created a fairly arbitrary (although mathematically pseudo-justified) % winning chance for Roger and Andy. However, what if Roger woke up that morning with a terrible migraine and was feeling under the weather the whole match. Probabilities based on historical data do nothing more than mathematicall model the past in the hope that they give some insight into future possibilities - assuming that a 4.2% chance of winning based entirely on historical data gives a 1/25 chance of winning the next game between two individuals with permanently fluctuating internal factors is ... foolish IMO.

There's the argument that over time these all even out to match the percentage is also equally flawed (and here I'll stick to Go for why I think so, I promise!): People get older, married, divorced, have kids, go senile, whatever ... all of these factors influence what's going to happen, and rank in itself is, again, based primarily on analysis of historical data, and a poor metric for evaluating likelihood of future results (this is even worse in the pro world where ranks are not correlated directly to recent or lifetime performances in the way that something like online server ranks are).

Who here can relate to being person A, who always beats person B and always loses to person C (all being the same rank), despite the frustration that person B always seems to beat person C? This often isn't a statistical blip that will work itself out over time with more games (assuming the players don't improve over this time), it's a simple fact that modelling overall historic results across the spectrum of each player's opponents doesn't act as a good proxy for the probability of the outcome of a single future game between two people.

Like a number of papers I have the semi-pleasure of reading these days, it looks like a theory borne out of people's delight for what appear to be stats and proofs of cool sounding phenomenon (or an attempt to create a proof for some wider point like what a deep game Go is), but build on a foundation of false premises and weak understanding of confounding factors.

If Go was a solved game (as a 0.5 point win for White with perfect play, but a loss with any deviation from perfect play, for example), then you could model the chances of perfect play as Black being beaten by a randomly legal playing bot as White, and even then it would be somewhat governed by the rules given to the random bot player.

Having arbitrary rules like "first moves not on the first or second line" is also not only arbitrary but distortive. What person is going to develop any basic opening theory whilst otherwise playing completely random moves? I learned to stop atari-ing anything before I learned anything about 2nd/3rd/4th line opening dynamics.

I would rather the author didn't make the attempt to appeal to the audience by involving a monkey at all (which inherently drags people in at the idea of a monkey beating one of the greatest players ever to play Go). It's a purely theoretical mathematical argument on probability trees, and can be left in the domain of mathematicians that find it interesting. It doesn't correlate at all to the chance of a monkey beating Lee Changho, nor does it actually model the probability of any individual player with rank X beating another player with rank Y, and shouldn't be construed as such a proof.

I still enjoyed reading what I could though!

EDIT: The are also other statements that make me twitch, such as "For an absolute beginner who is learning weiqi at a natural pace, the journey is probably just a casual walk to get from the weak level probability P0 to a higher level probability P1. However, from the perspective of mathematics, we can see just how vast such a gap actually is." This is not logical. From a mathematics point of view, an improvement in an exam score from 0% to 1% represents an "infinite" improvement, which based on any basic fomula of knowledge increasing over time (maybe N1 = N*1.03 per week or something) would represent an improvement that is literally unsurmountably vast. In reality, the flaws of the argument are pretty intuitively basic, as it disregards anything to do with how learning actually works, and also assumes that {total amount of knowledge} correlates exactly with {winning percentage} (which it doesn't).

I promise I'll stop ranting now

Whoops, I saw that and meant to adjust it,but I forgot. I meant 0.39% in any case. hehe

_________________
TucsonGo.org - Play Go in Tucson
We meet twice a week, visit us!

Here's an interesting thought experiment. I'm aiming it at topazg specifically, because he nailed the problem of working with probabilities in the human sphere, but it can easily be rephrased for others.

Take your entire mortgage, or some other large sum of money, whose loss you would feel very keenly. You now have a choice - you can play this random move monkey, or you can play a 20k player. If you lose the game, you lose all your money. Which one would you rather play?

If it's an even game (and "not playing" really isn't a choice ), I'd pick the 20k, but that's under the basis that it's someone who's ability we know as 20k rather than a last professed rank. The random bot increases and arbitrary aspect of uncertainty that makes me twitch when something big is at stake, whereas I can't remember the last time I lost to a 10k in an even game, let alone 20k. I'll be honest, history of my games against other Go players trumps in my mind completely over mathematical models in this instance.

Despite the fact I've not played anywhere near enough games to have a reasonable chance of losing to a 20k on mathematically calculated probabilities, I actually suspect that a 20k simply couldn't win an even 19x19 game against me, whereas a bot could at astronomically tiny odds. In both cases I suspect I'm keeping my mortgage/other sum of money, so it wouldn't matter to me which one really.

Interestingly, I've played a couple of handi games against fuegobot on Kaya (7 and 8 stone), and find them much easier than a prospective similar ranked human. I think the way knowledge applies in contextual situations on a Go board is a far bigger swinging factor to the result. Hence a 20k who applies what they have in an honest attempt to win I consider to have a 0% chance to beat me in an even game, whereas a random bot could theoretically stagger on dazzling play through sheer chance, even though I'd probably not find that dazzling game in my lifetime even if I played it 100 times a day until I die.

Me too, which is an interesting illustration of how probability does not apply to human endeavours. We know that a 20k does not play slightly better random moves than the (infinite)k monkey, he in fact only plays 20k moves. It's also amusing to think how offended your 20k friends may be by this

As an aside, if the 20k human and Lee Chang Ho were to play enough games together, say, 1 billion, I'm 100% confident that the (ex)20k would have a 50/50 chance of winning that billionth game.