Life In 19x19

So, I've been thinking about how Go has been played for 4000 years or so. And a question popped into my head: What is the likelihood of two games being exactly the same? If I were to ask without thinking about it, I'd say no. It's impossible.

Or is it?

Think about it. The game has been played for a rather long time. It seems very likely to me that there can only be so many combinations on a board with 361 points. And of course, I don't mean players who take a past game and purposely repeat it exactly.

Anyway, what opinions do y'all have on this?

(Note: Sorry if this has been asked before, but I didn't see it, so I figured I'd go ahead and ask!)

361! is a VERY big number. You could probably play games constantly for the next billion years and not repeat one.

Of course, its possible! How would it be impossible? Does some giant hand come out of the sky and knock your board over if you are about to repeat a game?

daniel_the_smith wrote:361! is a VERY big number. You could probably play games constantly for the next billion years and not repeat one.

Yes 361! is a very big number, but (at least to an extent) is discounting optimal play.

I can't remember what game it was, but two pros were playing a few years ago and the commentators made the observation that one of them had made a move that was "new" in the opening (within the first 15 moves or so). On a side note: they thought it was not optimal and I think he did go on to lose the game.

So the problem set is reduced by a decent amount because of current strategies in the game. This doesn't mean we're guaranteed to have a "repeat" game - but at least it pushes games closer in that direction.

As anecdotal fun, choosing the most popular move each turn in GoGoD gives you a 41 move tree before reaching a branch point where no two games choose the same continuation. The 41 moves are below, if anyone is interested. Whilst this may not be the longest sequence, I'd be surprised if there is one much longer. Unsurprisingly, the general pattern whilst clicking around is that the extremely popular and well researched openings have the most identical paths.



This also seems like a good place to mention my favourite statistic; if you shuffle a deck of cards well, the probability is about 1 that nobody has ever had a deck of cards in that order before.

Edit: Here's a slightly longer dual path; 42 moves starting with the famous Shusaku opening. There are only 2 games throughout the lower right sequence, though.

The chance of two games of random moves to be identical is extremely low, of course. But pros are likely to chunk several moves into common sequences (eg. joseki). So the actual probability of a duplicate is a little bit better.

But still, I'd bet that no two pro games are identical, and it'll probably be that way for a long time.

I'm also pretty sure no two games played on internet are exactly alike (except on purpose). The probability of that happening is still low enough

Theoretically (with access to the database of a go server), it shouldn't be that hard to check

No two games have ever been the same, except in cases where both players deliberately set out to reproduce a game.

Suppose we consider only "good" games, allowing us to hugely reduce the size of the game tree. For arguments sake, lets suppose that, on average, there are only two "good" moves that can be played at any point in the game. And suppose that the average game lasts about 270 moves (this is roughly the actual average for professional games). That means that our game tree contains only 2^270 games. Which is an 81 digit number.

Now, suppose every person in the world suddenly finds themselves with the ability to play good games, to find one of those two (on average) good moves within 2 seconds and play it. This means that two such players can finish a game together in about 10 minutes. So every pair of players, doing nothing but sleeping, eating and playing, can play about 100 good games per day. With 7 billion people, that means we are producing 350 billion games per day, 125 trillion per year. 12 quadrillion in a century.

The chance that two of those 12 quadrillion good games are the same is about 0.0000000000000000000000000000000000000000000000001 %

HermanHiddema wrote:No two games have ever been the same, except in cases where both players deliberately set out to reproduce a game.

Suppose we consider only "good" games, allowing us to hugely reduce the size of the game tree. For arguments sake, lets suppose that, on average, there are only two "good" moves that can be played at any point in the game. And suppose that the average game lasts about 270 moves (this is roughly the actual average for professional games). That means that our game tree contains only 2^270 games. Which is an 81 digit number.

Now, suppose every person in the world suddenly finds themselves with the ability to play good games, to find one of those two (on average) good moves within 2 seconds and play it. This means that two such players can finish a game together in about 10 minutes. So every pair of players, doing nothing but sleeping, eating and playing, can play about 100 good games per day. With 7 billion people, that means we are producing 350 billion games per day, 125 trillion per year. 12 quadrillion in a century.

The chance that two of those 12 quadrillion good games are the same is about 0.0000000000000000000000000000000000000000000000001 %

First, the question was not "has two games ever been the same?" But, is it POSSIBLE? You have a non-zero result. It is possible. You might say I am arguing semantics but the possible/impossible choice is stated multiple times in the OP.

Second, somewhere your statistics are flawed. Baduk is not a random process, even between two moves. How many times during lectures does somebody say "This is the only move?" Let's do another analysis.

amnal was kind enough to look up the GoGoD database and find two games that had the same first 41 moves. The way he searched for it doesn't even guarantee that it is the longest sequence in the database... but lets say it is.

The GoGoD database has 68,127 games in the latest version. I will assume amnal has that version.

Lets use your assumption that there are two moves. 2^41. The chance of two games like this appearing in the GoGoD Database are really small, like 0.0000000003%. About the same if you hit a millions jackpot on your first try. I really doubt GoGoD got that lucky

(EDIT: Especially since there's ANOTHER two games with 42 moves.)

Because it's so trivially possible, I think people are eager to get on to the slightly more interesting question of how likely it is. And that makes sense.

badukJr wrote:First, the question was not "has two games ever been the same?" But, is it POSSIBLE? You have a non-zero result. It is possible. You might say I am arguing semantics but the possible/impossible choice is stated multiple times in the OP.

Actually, the question was "what is the likelihood". The word possible does not even appear in the original post, the word impossible is used just once.

Second, somewhere your statistics are flawed. Baduk is not a random process, even between two moves. How many times during lectures does somebody say "This is the only move?" Let's do another analysis.

My statistics are very flawed. Realistically, the tree of good games is many orders of magnitude bigger. Although there are points where there is an "only move", there are also many points where there are a dozen choices that are equally valid. The concept of miai is not nonsense.

amnal was kind enough to look up the GoGoD database and find two games that had the same first 41 moves. The way he searched for it doesn't even guarantee that it is the longest sequence in the database... but lets say it is.

The GoGoD database has 68,127 games in the latest version. I will assume amnal has that version.

Lets use your assumption that there are two moves. 2^41. The chance of two games like this appearing in the GoGoD Database are really small, like 0.0000000003%. About the same if you hit a millions jackpot on your first try. I really doubt GoGoD got that lucky

(EDIT: Especially since there's ANOTHER two games with 42 moves.)

I don't know what calculation you used, but assuming every game is a completely independent event, the formula for calculating the probability that two games out of 68000 are the same in a set of 2^41 possible games is:

1 - e^-(68000^2/2^42)

Which is about 0.1%

This is called a Birthday attack in cryptographic terms. The reason that 68000 gets squared here is because each game can match each other game, so there are 68127*68126 pairs of games that might be the same.

Of course, professional games are not independent events. Professionals study each other's games, play the same joseki or fuseki, they copy each other. That makes the probability of matching openings much higher.

I believe even if two game would be completly the same from order of moves and time to used in thinking at every move there would still have been other thoughts ins the players mind. Therefore it's impossible for me to think of 2 games which are alike.
Sorry if that's off the questions but that's what jumps to my mind while thinking about it

HermanHiddema wrote:Actually, the question was "what is the likelihood". The word possible does not even appear in the original post, the word impossible is used just once.

No, I don't think so


I don't see "What is the likelihood" at all. It is "Do you think it is possible that 2 games are alike?"

My statistics are very flawed. Realistically, the tree of good games is many orders of magnitude bigger. Although there are points where there is an "only move", there are also many points where there are a dozen choices that are equally valid. The concept of miai is not nonsense.

Maybe. Or maybe there is perfect play. We don't know yet. Looking at CrazyStone analysis, typically he strongly prefers only one move most of the time. I think as bots get stronger this becomes very interesting area of research.

I don't know what calculation you used, but assuming every game is a completely independent event, the formula for calculating the probability that two games out of 68000 are the same in a set of 2^41 possible games is:

1 - e^-(68000^2/2^42)

Which is about 0.1%

This is called a Birthday attack in cryptographic terms. The reason that 68000 gets squared here is because each game can match each other game, so there are 68127*68126 pairs of games that might be the same.

Of course, professional games are not independent events. Professionals study each other's games, play the same joseki or fuseki, they copy each other. That makes the probability of matching openings much higher.

Still, don't you think its quite interesting that something that has only a 0.1% chance of happening has happened twice within the set? And maybe more?

Pro games are not independent, so no, that's not very surprising. Especially since some of the joseki in those games are one-way streets. (Thanks, Herman, for doing the math!)

The question was "possible", which is so trivially "yes" that people (including me) have been answering the much more interesting question, "how probable is it?"

badukJr wrote:Still, don't you think its quite interesting that something that has only a 0.1% chance of happening has happened twice within the set? And maybe more?

i am too lazy to do any math now, but i believe that if you want to argue about exact wording, Hermann Hiddema said "... the probability that two games out of 68000 are the same in a set ...", which was not even close - the found games had 42 common moves, they were not the same

to the topic: i played many games that were similar to each other. but i think that number of possible moves is so high that we won't ever encounter two same games. maybe between some strictly deterministic bots or with use of some unconstructive strategy like manego, but not in an ordinary game. it is nice when you realize during the game that you are somewhere where no one was ever before you and no one will ever get there again. it makes you feel responsible for your moves

EDIT: typo correction and the last sentence got few more words