After how many moves does a game become unique (statistically)?

#1

Does anybody have any thoughts, feelings or statistics for how many moves it takes on average for a game to become “unique” (likely never played before)? Is there a way to analyze the OGS game database for this?

(I’d appreciate if a mod could let me know if this is in the right subforum.)

1 Like

#2

It’s as good a guess as any. Of course your question is not quite translatable “into statistics” because in order to calculate any kind of reasonable estimate, we have to make assumptions. In this case, we would have to assume that all Go games are essentially independent from all other Go games (because otherwise we’d have to get into dependent probabilities and that’s just nasty). This is unrealistic for lots of reasons, mostly because we only have so many humans and by definition every game they play is not independent from any other game they’ve played before or will play in the future (as their moves will largely depend on individual factors).

They will also not be independent because players of equal strength will almost always play each other instead of playing everyone else with equal probability.

But let’s assume.

I think you’re basically asking “at what point does the rate of growth of probable_games exceed the rate of growth of played_games by a factor at least as large as the difference between the two?”

Edit: Changed “possible_games” to “probable_games” because we all know lots of moves would never be played… but yea, for a more naive estimate, user the former.

My math is a little too rusty to properly calculate that right now. :stuck_out_tongue:

1 Like

#4

I think the answer might depend on the skill, style, knowledge and experience of the players, so it’s a bit hard to objectively measure, without fixing a particular group of players of interest. I think weaker players might be more likely to play novel moves, while more skilled players might lean on their knowledge and replay the first N moves of well-known fuseki or certain pro games.

I guess one way is to take a very large set of games that were played by a population of interest (e.g., pro games on gokifu, or amateur games across a particular server), then look at the statistics of what move number each game becomes unique from all others (including rotations/reflections). That would just be a programming exercise to process a ton of SGF files efficiently. Maybe some clever use of hash tables, bloom filters, etc. could tackle that without too many cycles.

0 Likes

#5

‘I think you’re basically asking “at what point does the rate of growth of probable_games exceed the rate of growth of played_games by a factor at least as large as the difference between the two?”’

Thank you, that’s a very good way of putting it. :slight_smile:

0 Likes

#6

"I think the answer might depend on the skill, style, knowledge and experience of the players, so it’s a bit hard to objectively measure, without fixing a particular group of players of interest. […]

e.g., pro games on gokifu"

Yeah, professional play (and/or top AI games) would probably be the most interesting strength level to look at.

0 Likes

#7

Waltheri stops at 20, but I vaguely remember a page on senseis mentioning two games being identical until move _8, I believe 28. Can’t find it for the life of me.

1 Like

#8

Maybe you’re thinking of this:

Extended quotation

argybarg: I found myself wondering today: What is the greatest number of moves into a game that two different professional games have been identical? In other words, game A and game B unfolded identically until, say, move 8. If I had to guess, I would say it would have to be 12, but perhaps someone with a very sophisticated pattern search could find out.

A similar question: What is the farthest into the game that two professional games have resulted in an identical position? This could be later than with the first – say, move 16.

And my last is one for pure speculation: If we had full access to the record of every game played, anywhere, what would the results be for the above questions, only with games played by anyone? Leaving out games played intentionally the same (i.e., replays), I would guess that no two go games have been identical after move, oh, 26.

unkx80: 1st world female tournament, finals games 2 and 3, Rui Naiwei vs Feng Yun. These games are identical in the first 34 moves.

Between the two games, 35 differs by one line, and then 36 to 47 are identical again.

Mef: Looks like unkx80 gave a nice definitive answer to some of your questions, and I think if you compiled a database of every game ever, you’d actually find quite a few similar games. In fact I wouldn’t be suprised if there were games that were the same out to move 50 or more. The problem is that some people play deliberately the same as a previous game because it’s a position they’re comfortable with. For instance, many people always play the low chinese, or maybe they always play the same pincer against the nirensei. Also I know sometimes when pros play a series of games against each other they like to use the exact same opening play as the last time, except that they will try and put their post-mortem analysis to good use, changing the first move in the game they thought didn’t work.

1 Like

#9

This is extremely interesting and exactly the kind of information I was looking for. Thank you so much! :slight_smile: (And please people, keep contributing more answers if you’ve got 'em :slight_smile: )

2 Likes

#10

So the key idea here, is what population, and what are the players like

If we assume that the player is a random bot with 1,000 games, and we want to find the point where it is more than 50% likely that the bot hasn’t played this move, then even if we count on rotational symmetry, then the first move is 55 for the first move, 360 for the second, and 359 for the third.

so the first move happens with an occurrence of 1/55, so the probability that this random bot has played this move is almost 100% in 1,000 games

the first and second move occurrence is 1/19800, then the probability that the bot has played both of these moves (in that order) in 1,000 games is 49.2%, so we’ve probably found a unique game

But I suppose some people want some level of significance, so we’ll go until 5% or less

So the third move is 1/7108200, and so the probability that the bot has played it (in that order) in 1,000 games is 0.01%, so you almost definitely have a unique game after three moves.

In order to make any further inquiries, we need to have a specific data about the population in question, which usually implies having either a) a complete database of all the games in question or b) some assumptions about how people actually play.

1 Like

#11

^ Thanks for the clarification. I’d like to hone in on pro games then, if anyone knows how to.

That World Female Tournament example is astonishing to me. Two games with 47 identical moves except for one at move 35, played right after one another. Psychologically I wouldn’t hold up to the pressure as either side. Losing side: “She must think I’m an idiot because I’m replaying a lost game.” Winning side: “I guess she was winning right until the end, I should try something new.” No idea if pros think this way :slight_smile:

0 Likes

#12

Could you provide me a link to the database of the kifu from that tournament, or should I just do some reasoning based on samples from ps.waltheri.net?

0 Likes

#13

Oh the second paragraph wasnt meant to be related. No idea of where to find kifus, and one tournament is probably a small sample size :slight_smile:

0 Likes

#14

Well, maybe I can help with that. The commentary for those matches, published in the British Go Journal, was written by Feng Yun herself. You can download the issue right here:

Piece of her thoughts

35: Up to this move this game was identical to the second game. It is unusual for professional players to repeat a game but we both felt that this opening was good for us. Black played A before but I played here this time. Apart from this the game continued to be the same as before.

45: Black plays this bad move again. I wouldn’t play like this now that I have had time to think about it.

[…]

Enjoy. :slightly_smiling_face:

Round 2

Feng Yun (7p) vs. Rui Naiwei (9p) - 1995-01-23.sgf (2.2 KB)

Round 3

Feng Yun (7p) vs. Rui Naiwei (9p) - 1995-01-24.sgf (1.6 KB)

1 Like

#15

This thread got me thinking and, being the 9x9 fanatic that I am, a question about the 9x9 popped into my head. Nick Sibicky stated, in the review of his US Go Congress 2018 9x9 championship match (link, 16:43 - 16:51), that for high level players the game is decided by move 8 on the 9x9 board.

Considering that the opening is the part of a game that is most likely to see identical plays in various game records, is the 9x9 too small to have “unique” gameplay? I think most people assume that it too small if asked (without any research before answering).

So I did a little Sensei’ing and my favorite Go fanatic, John Tromp, had something to say about the possibilities of different sized Go boards. And clutches his chest, the math doesn’t lie :star_struck:. I know the board is small but the number of legal positions on a 9x9 is still ridiculously large:

One Hundred Three Undecillion
103,919,148,791,293,834,318,983,090,438,798,793,469

I read this and geek’ed out :woozy_face:. Just thought I would share it with the group :smiling_face_with_three_hearts:.

2 Likes

#16

Though in that particular game, white already blundered at move 2. Also, Nick said “this is where the game gets decided, you know, at move 8”, after move 11. ;D

Also if you like big numbers, check out Tree(3).

2 Likes

#17

@Mulsiphix1 Yeah I remember a while back on the thing of the legal positions, as someone loves to play the 9x9 board I would say a “normal” game can have alot of repeating fusekis as it typically takes 10-20 moves to get out of theory. Personally that number for legal positions is big but lots of moves can be eliminated as many of the moves are impractical and ko’s can lead to lots of more moves than needed. Also for the link game I would say the 2nd move is not the best but not a “blunder” as smurph stated.

1 Like

#18

@smurph and @Deep_Scholar
Out of curiosity, what move would you suggest for White at Move 2? I rarely see Dan level play on 9x9’s, but in the double digit Kyu world where I’m a 16K, that is a pretty common response. Though I mostly see 4-3 played for Black on Move 1. Perhaps White is trying to secure a corner? I tend to play 3-3 when I’m making a grab for a corner though, so I’m not sure.

Question
While I’m pointing out the 3-4 point I have a quick question. Are both 3-4 and 4-3 called Komoku? The 81 Little Lions book only definitively states Komoku for 3-4.

That is a very interesting point. I wonder what the number of “likely unique legal Go positions” is :thinking:

1 Like

#19

@Mulsiphix1 in the higher dan games you will likely see after 4-4 this position pic%201
also 2nd move e4 and f4 are good moves at least I have had good success with d4 I also know Shibano Ryunosuke 1p likes to play as black and white when we played so I learned alot from him. yes 3-4 and 4-3 are Komoku if flip a board they are the same such as called (transpositions) which I don’t remember if John Tromp took transposition into account or not as the first move in go 9x9 has 15 options to choose not 81.

2 Likes

#20

Yes, 4-4 is the only move here imho. B 5-4 first is another one of those disgusting moves that force you to play mirror Go.

That’s why I like tengen. No way that’s gonna devolve into mirror Go.

2 Likes

#21

@smurph yep tengen is a fine choice after all Ohashi Hirofumi 6p pretty much only plays tengen first move as black when I play him and other records of him playing vs AI and humans, and he can be a pain to play against depending how you respond. :smiley:

2 Likes