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!)

_________________
Slava Ukraini!

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

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com

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?

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.

_________________
KGS: schultz [?].

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.

_________________
be immersed

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 %

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.

_________________
Occupy Babel!

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.



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.



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

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?"



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.



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?"

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com

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

_________________
Spilling gasoline feels good.

I might be wrong, but probably not.

I was referring to the Original Post. The first one, the one where hailthorn explains what he means with his question.



Of course there is perfect play. But, given that there are at least 10^(10^48) possible games, and that there are only 723 possible scores (under area scoring, anything from B+361 to W+361), there are a mindblowing number of games that will result in each score. The number of perfect games is extremely high.



No, because the size of the set, 2^41, is complete and utter nonsense. So that number, 0.1% is completely meaningless.

The important thing, the only thing that is of any meaning at all with respect to the 40 move common openings found, is that pro games are not independent. Therefore, applying statistics to calculate the probability of a common opening is impossible.

There are two more interesting games (if I can get this to work), which also involved mirror go and Go Seigen. Here's the first:



And the second:



Best wishes.

_________________
No aji, keshi, kifu or kikashi has been harmed in the compiling of this post.
http://www.gogod.co.uk

I find it interesting that white won the first game, yet was the first to deviate from the original record (and he ends up losing the second game!). Perhaps he felt he found a trap in the post-mortem that he wanted to avoid walking into?

With the number of players in it and the number of repetitions being done in its advantage, I would say that there is probably a few games that have been repeated already, or how they were played.

Though when you think of it vis-a-vis, the idea seems to far fetched but when you get to it statistically, there is a probability, but not something close to having confidence over.

After giving it some more thought....I think there's actually a reasonable chance there have been two identical games, but I think it would only be possible with an early joseki trap. For instance - four 4-3 points get played, black makes a fatal mistake in the first corner sequence, then resigns. Once you get past early corner sequences, I think the likelihood of unintentional identical games will quickly drop to essentially zero. It's hard enough when two players are intentionally trying to replicate a game to get all the moves in the right order (example - reviewing it after playing) especially once you get into endgame.