The Probability of a Monkey Defeating Yi Chang-ho

General conversations about Go belong here.
speedchase
Lives in sente
Posts: 800
Joined: Sun Dec 04, 2011 4:36 pm
Rank: AGA 2kyu
GD Posts: 0
Universal go server handle: speedchase
Has thanked: 139 times
Been thanked: 122 times

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by speedchase »

Akura wrote: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.
User avatar
Exologist
Dies with sente
Posts: 109
Joined: Tue Jun 29, 2010 8:50 am
Rank: 2k Kaya
GD Posts: 0
IGS: Exologist
Kaya handle: Exologist
Location: Arizona, United States
Been thanked: 3 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by Exologist »

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!
User avatar
Bonobo
Oza
Posts: 2224
Joined: Fri Dec 23, 2011 6:39 pm
Rank: OGS 13k
GD Posts: 0
OGS: trohde
Universal go server handle: trohde
Location: Lüneburg Heath, North Germany
Has thanked: 8262 times
Been thanked: 924 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by Bonobo »

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
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: The Probability of a Monkey Defeating Yi Chang-ho

Post by hyperpape »

Exologist wrote: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.
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.
User avatar
Laman
Lives in gote
Posts: 655
Joined: Thu May 06, 2010 10:24 pm
Rank: 1d KGS
GD Posts: 0
KGS: Laman
Location: Czechia
Has thanked: 29 times
Been thanked: 41 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by Laman »

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.
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by topazg »

Exologist wrote: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.


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 ;)
User avatar
Exologist
Dies with sente
Posts: 109
Joined: Tue Jun 29, 2010 8:50 am
Rank: 2k Kaya
GD Posts: 0
IGS: Exologist
Kaya handle: Exologist
Location: Arizona, United States
Been thanked: 3 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by Exologist »

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!
User avatar
quantumf
Lives in sente
Posts: 844
Joined: Tue Apr 20, 2010 11:36 pm
Rank: 3d
GD Posts: 422
KGS: komi
Has thanked: 180 times
Been thanked: 151 times

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by quantumf »

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?
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by topazg »

quantumf wrote: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.
User avatar
quantumf
Lives in sente
Posts: 844
Joined: Tue Apr 20, 2010 11:36 pm
Rank: 3d
GD Posts: 422
KGS: komi
Has thanked: 180 times
Been thanked: 151 times

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by quantumf »

topazg wrote:I'd pick the 20k


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.
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: The Probability of a Monkey Defeating Yi Chang-ho

Post by daniel_the_smith »

You guys are crazy. :)

Random play will beat the *20k* far less often than the 20k will beat you, given that random play is no better than 50k and that rating systems seem to work.

I have this to say about the post referenced at the beginning. If you do the same math problem two different ways and get two different answers, you must've done something wrong one of the times. Rating systems are defined to answer the sort of question that the piece is asking; i.e., What is the chance of player a beating player b? His second answer was (probably) much more accurate than his first answer, because he vastly overestimates how strong random play is likely to be.
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com
User avatar
quantumf
Lives in sente
Posts: 844
Joined: Tue Apr 20, 2010 11:36 pm
Rank: 3d
GD Posts: 422
KGS: komi
Has thanked: 180 times
Been thanked: 151 times

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by quantumf »

daniel_the_smith wrote:Random play will beat the *20k* far less often than the 20k will beat you, given that random play is no better than 50k and that rating systems seem to work.


But I don't think random play is the same as 50k, and my thought experiment proves it, I think. Sure, I'd rather play a genuine 50k player than a 20k player if my house depended on it, but I definitely do not want to play a genuine random move player if I could rather play the 20k player.

I suspect that a truly random player has no meaningful rank.
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by topazg »

daniel_the_smith wrote:You guys are crazy. :)

Random play will beat the *20k* far less often than the 20k will beat you, given that random play is no better than 50k and that rating systems seem to work.

I have this to say about the post referenced at the beginning. If you do the same math problem two different ways and get two different answers, you must've done something wrong one of the times. Rating systems are defined to answer the sort of question that the piece is asking; i.e., What is the chance of player a beating player b? His second answer was (probably) much more accurate than his first answer, because he vastly overestimates how strong random play is likely to be.


That the rating system seems to work vis a vis predicting the outcome of a future game is a logical flaw. The rating system that calculates chance of winning with variation in rank is effectively based on mathematical models extended by extrapolation. Find me 100,000 games where a 1d played a 20k in a serious game, and find me a single one where the 20k wins. I suspect if you had 100,000,000 games, I really believe you also wouldn't find one. In fact, if you have enough games to get one win by the random bot, I still don't believe you'd find one between 1d and 20k players.

Ironically, it's the lack of randomness of the 20k that makes them considerably more likely to beat the randombot, but perversely less likely to beat the 1d. You can't model the application of knowledge by the linear or exponential mathematical formula in this way with human beings (or, if you think you can, I'm interested in a proof ;))
User avatar
HermanHiddema
Gosei
Posts: 2011
Joined: Tue Apr 20, 2010 10:08 am
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
Location: Groningen, NL
Has thanked: 202 times
Been thanked: 1086 times

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by HermanHiddema »

topazg wrote:That the rating system seems to work vis a vis predicting the outcome of a future game is a logical flaw. The rating system that calculates chance of winning with variation in rank is effectively based on mathematical models extended by extrapolation. Find me 100,000 games where a 1d played a 20k in a serious game, and find me a single one where the 20k wins. I suspect if you had 100,000,000 games, I really believe you also wouldn't find one. In fact, if you have enough games to get one win by the random bot, I still don't believe you'd find one between 1d and 20k players.

Ironically, it's the lack of randomness of the 20k that makes them considerably more likely to beat the randombot, but perversely less likely to beat the 1d. You can't model the application of knowledge by the linear or exponential mathematical formula in this way with human beings (or, if you think you can, I'm interested in a proof ;))


I think the chances for the randombot of winning against a 1d are indistinguishable from 0, in the order of 1 game every 110 100. The chances of the 20k are infinitely better, though still indistinguishable from 0. Everyone seems to be wildly overestimating the strength of random play.
User avatar
topazg
Tengen
Posts: 4511
Joined: Wed Apr 21, 2010 3:08 am
Rank: Nebulous
GD Posts: 918
KGS: topazg
Location: Chatteris, UK
Has thanked: 1579 times
Been thanked: 650 times
Contact:

Re: The Probability of a Monkey Defeating Yi Chang-ho

Post by topazg »

HermanHiddema wrote:I think the chances for the randombot of winning against a 1d are indistinguishable from 0, in the order of 1 game every 110 100. The chances of the 20k are infinitely better, though still indistinguishable from 0. Everyone seems to be wildly overestimating the strength of random play.


I'm not over-estimating it, as I said, I'd be very happy with either. I think the randombot chances are non-zero, but almost indistinguishable from 0. I think the 20k's chance is actually 0.
Post Reply