How many different games of Go are actually played?

Question

Go is known for having a vast space of possible board positions, which was one of the reasons why computers weren't able to compete for a long time.

I wonder how many of these board positions are actually used by humans. Go is absolutely deterministic, and it could seem reasonable for a person to always react to the same board position, in the same way, thus not exploring any new positions when the opponent does the same. Of course, one will try to explore new positions after losing a game to improve in the next round.

Still, humans often act the same in similar situations and are not good at doing something completely new. For example, humans usually cannot choose good passwords even when they try to avoid common mistakes that weaken passwords, so computer-generated passwords are way more random than what humans can come up with.

Are there any analyses about how many board positions are relevant, i.e., will be reached in many games, and what positions may never be reached because there is no way to reach them that would make any sense to the players? How many of the positions really matter when looking at the vast number of legal positions?

Answer 1

I kind of disagree with the statement humans often act the same in similar situations. I know that my reaction to the same opening moves depends on my mood, what I ate earlier, the moon phase and the shoe size of my opponent modulo Pi. In other words, most players try to explore new moves and ideas at least some of the time. (I agree that humans suck at thinking of new passwords, but generating, say, 4 bits of entropy per digit when a true random source could generate 6, is still spanning a large space.)

The Tromp paper gives an upper bound. Naturally, this number will not (and cannot) ever be reached.

Practically speaking, the answer to how many positions are reached probably depends on the number of games played almost exclusively. I'm not aware of a proper scientific approximation, so I'm attempting an educated guess. Suppose there have been 100 million active players for 1000 years. Each player plays 30 games a day, and year has 333 days. Suppose each game lasts 200 moves, and half of them are uniquely new positions. That leaves us with 100,000,000 * 1,000 * 30 * 333 * 200/2 = 100,000,000,000,000,000 = 10^17 unique positions. Certainly more than one could ever hope to analyze.

Looking at it from another angle, in my experience there are usually only a handful (1 to 10 or so) options per move that seem worthy of consideration (*). The mode (most common value) is surely 1, i.e. there is only a single move as an option. The median (center of distribution) is probably around 2, and for the average I would guess around 3, but let's say just 2. So when playing a game, the number of reasonably reachable positions should be around 2 to the power of the move count. At 100 moves per game, that's around 10^36 positions.

The number of positions that is unlikely to be reached is the upper bound minus that, i.e. most of them.

(*) This is similar to what I (vaguely) recall about players in the game of chess and in other, more abstract situations (e.g. Newell & Simon, 1972: Human Problem Solving). It is also similar to the number of moves typically suggested by modern Go AI. A while ago I used this to losslessly compress the policy output of AI programs from 724 to just 8 bytes, which was required to keep large game trees in memory.