Probably it’s already been discussed but math-programmer threads are not my stage, so…
That saying that possible Go moves are more than the atoms of the Universe.
I guess the possibilities wax and wane during a game since less positions are open, some moves would be illegal etc.
So, I was wondering (while I should be working) how a graph of this would look. “Possible moves available during a match”. Not a straight line because when is it ever, but not something neat like a U either.
I faintly recall this has been discussed, but I wouldn’t know how to look for it. Anyways, sorry in advance if this has been discussed ad nauseam and I missed it.
At any given board state, the number of possible choices for a move is just (361) - (# of stones on the board) - (# of illegal moves)
So at move 1, imagine a “decision tree” or flowchart, where you have 361 starting options. Then after picking one, you’re left with 360, and so on. Note that that is 360 nodes extending from EACH of the original 361 nodes.
It would look like a massive, convoluted spider web.
Note that given any legal position, you can come back to a state with just one stone one the board after a finite number of moves or passes: Black kills himself by filling his eyes, White captures everything, fills all empty spaces but one, and Black captures.
So given any two legal nonempty positions, it is possible to go from one to the other.
Do you mean the possible moves plotted at each given move/turn number.
I.e. on turn 1, there are 362 possible moves;
On turn two there are 361 or 362 possible moves;
On turn three there are 360 or 361 possible moves (or none if the first two moves were passes and the game is already over!)
On turn four…
On turn 8 there are 355, 354 or 353 possible moves depending on previous passes, if a ponnuki was made or neither of these things happened…
Etc…
I guess some clever maths people could plot such a graph with the ranges of possible numbers of moves each turn. Not me though. I’m probably already one or two out in thinking about the first few moves!
Is really the number of possible go moves supposed to be that high? I know that the number of possible positions is extremely large, and the number of possible game paths is even much larger.
For the purpose of counting them, how exactly would you define a go move? One could possibly say that a go move is either a pass or defined by two coordinates, but then there are only 362 of them.
Here is another recent thread discussing the combinatorics. Some numbers and references are provided within the first few posts.
What exactly do you mean by this? Do you mean “number of legal moves” at each turn? Or something more narrow, like “number of reasonable moves” at each turn?
The first is rather easy to compute given a game, and one could average those curves over several games to get a general idea. The second is a bit trickier to define, but perhaps one could use a bot to judge how many moves are reasonable at each turn (like by only couting those that do not lose too many points).
I think if you wanna get into the “reasonable” moves category, the alpha go paper is a good resource in that. I remember some images describing corner moves and the like.
I took her original question as “given that immensely large number reported sometimes (10^10^48 for the lower bound), how can we possibly visualize this?”
So you want to plot the sequence an=average of number of legal moves at the n-th move of a random game? Maybe a computer could do a simulation, generate 1 million random games and plot a graph.
If you don’t care about “reasonable moves” but just “legal moves” and don’t have rules forbidding positional repeat, then they will be infinite cycles if players just repeatedly fill from one end to another.
This one is about 4-digit PIN possible combinations and it’s already too complicated for me.
I don’t dare to imagine how a Go graph with 300+ moves per move would look like!
One could use some of the 27 million OGS games that have been collected into a public data set in order to analyze such statistical questions relative to real games.
If we talk about legal moves, I think the chart should be pretty straight, because there are very few moves that are illegal in any board configuration:
suicide moves (not even illegal in some rulesets)
ko
what else?
How many moves like that do you find in a game? Even in endgame, a handful.
So I’d say that Gia’s chart for legal moves is very similar to a right triangle.
If we push that to completely filling the board without coming to self atari, maybe the point of that triangle could be blunt because there are a couple of forbidden moves for each living group. So in the very end there could be less than 20 intersections not really available without falling into a loop (I atari myself, you capture, we start playing again inside the hole).
That brings us to a different concept: counting reasonable moves instead of legal moves.
But the definition of reasonable move can be tricky. Are they reasonable for a TPK or for a professional? And what about AI?
If we put a threshold on winrate, let’s say we count as reasonable only moves better than -2% winrate (or something) then we should be able to use a bot to check a good amount of games and draw some chart.
My guess is that the chart in that case should be pretty flat, since after fuseki I expect to have just a handful of reasonable moves for each turn.
The beginning of the game could be different, having many possibilities with first moves.
But actually, even with an empty board, AI still focuses on a handful of moves: mainly 4-4 and subsequent joseki.
So my guess is:
legal moves: right triangle
reasonable moves: horizontal line
human average player: mayhem Probably some sort of gaussian: few standard moves to begin with, then messing up josekis, then useless fighting, then stubborn endgame.
I have no idea what it’s saying so I have no idea if it applies at all, but… someone here might actually understand it? There might be like, one person in all of OGS.
I thought about it and the most I can comfortably do is to say something like this:
I think the game would be fairly linear, (the red line) resembling a simple y=361-n, where n is the move number, for the opening and first half of the midgame.
After that, there should be places in the midgame where illegal moves take away possibilities, increasing as more illegal moves (suicide, ko) begin to populate the board state, resulting in the lower dotted blue curve.
However, large groups could be captured, resulting in more positions being opened (something I didn’t account for in my first post for some reason), causing the upper dotted blue curve.
Since I am inclined to believe, off of nothing more than intuition, that the number of illegal moves would on average outweigh the number of gained moves from captures, I think the solid blue line more accurately represents what you want.
Although any single game would look jagged as you drew in your picture, the average would be a smoother curve.
I think reasonable moves for human players have a lot to do with the styles of play. We humans tend to associate moves to particular “groups”, and treat tenuki like a fork that either create another “group” or continue as part of the previous groups. Hence, certain styles of constant invasion and split will naturally create lots of “reasonable” local moves, while certain style thick and territorial will reduce the followup to limited groups and options (and the extreme of semeai fight or complicated joseki that dominate the game with just one reasonable move). People don’t just magically rank top 5 or top 10, but a dynamically changing local candicates and settled them throughout the game.
Probably some sort of gaussian: few standard moves to begin with, then messing up josekis, then useless fighting, then stubborn endgame. 
)))