There is an interesting post on Reddit in the DataIsBeautiful board, in which the author produced a visual representation of the evolution of go openings over time as a decision tree. The lack of labels makes it difficult to see what the openings are, but the data is certainly beautiful.

The post is located at https://www.reddit.com/r/dataisbeautifu ... ame_of_go/

Thanks Philip for sharing this. Indeed it's beautiful and fascinating. It's part of a larger research paper, "Opening strategies in the Game of Go from feudalism to superhuman AI" by Bret Beheim: there's a preprint at https://osf.io/preprints/psyarxiv/cewst_v5, and code at https://github.com/babeheim/go-learning-eras.

It's a type of evidence-based research that I'd like to see more of, but I'm frustrated by some of the methodological choices in this particular study. It's a shame the author didn't collaborate with an expert (high dan or professional) go player.

The overall theme is to measure how innovation happens slower or faster depending on "infostructure" (information infrastructure): it's not just about having large group of people doing something, but it matters how they're organising and exchanging information. There's reference to literature suggesting that innovation sometimes happens in slower groups.

The paper uses GoGoD as a dataset, and derives some numerical measures of "diversity" in opening play over time. Specifically, a go game is represented in SGF notation -- so, for example, the Shusaku fuseki is "qd;dc;pq;oc;cp;qo;pe;" -- and two openings are "similar" if the Levenshtein edit distance between them is small. Notably, terminology such as "3-4 point" is completely absent from the paper, and there scarcely a go diagram to be seen.

To my mind, this leads to two major problems. Firstly, openings are classified into "families" based on the first few moves, sometimes literally on the first two moves. So, for example, - - and - white 'a' - are treated as different families. And in general, transpositions (same position reached by different move order) are not accounted for properly.

Click Here To Show Diagram Code

[go]$$c Not accounting properly for symmetry/transposition
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . 2 . . . . . , . . . . . 1 . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . , . . . . . , . . . . . , . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . a . . . . . , . . . . . 3 . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]

Secondly, common formations (san-ren-sei, low Chinese, Kobayashi fuseki, taisha joseki, etc) won't appear as single clusters in the dataset, but will get split up according to the different contexts in which they appear (low Chinese against two 4-4 points is, by these measures, quite different from low Chinese if white has played a 3-4 point).

This means that the patterns in the various graphs, although nice to look at, don't map at all to how I conceive of the opening in go. A stronger player might disagree with me: but I would like to see that articulated in the paper! From a machine learning perspective, you need to get your feature selection right before plunging into the analysis.

So the abstract says "Surprisingly, the influence of AI has produced only a modest, short-lived disruption in opening move diversity, suggesting human-AI convergence and incremental, rather than revolutionary, change." And I think this reflects the fact that AI has a strong preference for 4-4 points and early 3-3 invasions, but the analysis is not picking up the explosion of new variations arising from the 3-3 invasion, AI's greater willingness to tenuki or to sacrifice, the re-evaluation of thickness and aji...

And later on: "It was not at all obvious before AlphaGoZero whether SAI would rediscover human opening play, or simply show us that we’d been doing it wrong the whole time. A similar phenomenon occurred in Chess when AlphaZero bootstrapped its ‘understanding’ of the game and converged on many of the preferred human openings e.g. d4, e4, Nf3, c4, in roughly the same proportions (McGrath et al., 2021). Such convergence is a major success for our collective problem-solving abilities." It's not spelled out, but the implication seems to be: go-playing AIs choose 4-4 points or 3-4 points just like humans do, therefore humans' understanding of the opening was already pretty good before AI came along. Personally, I think AI has in fact shown us that we were doing plenty of things wrong the whole time.

Despite these quibbles, the paper is worth reading. It's certainly thought-provoking, and I hope to see more of this sort of analysis over time. The reference list covers a lot of ground, pointing to research on cultural evolution across many different domains, not just go. (I'm expecting John Fairbairn to pop up and object to too many numbers. Download the paper and go to the last five pages: there are plenty of words to be found as well.)

I agree the paper might have benefitted from conferring with expert Go players.

I also have a critique on the mathematical side of things. The author writes:


Certainly in many regards this is true. Even without any mathematical analysis it's pretty clear to anyone who studies pro game records from different eras that the popularity of the first move alone being 3-4 vs 4-4 vs others has fluctuated over different times and places in pro play.

Their method by which they come up with this clustering and thereby draw the conclusion about the significance of the first two moves is, in rough terms, looking at the sequence of moves for each game and applying a levenstein-distance metric on those sequences, and then doing a two-dimensional fit that is sort of like finding the two principal components that best explain distance. They notice this the result has a lot of clusters that correspond to combinations of the first two moves and conclude that the first two moves are very important.

After thinking about their particular choice of metric, I'm a bit concerned about that old idiom/adage of "looking for your keys under the streetlight" or something to that effect. You find a real phenomenon and focus on it mostly because that's the main effect that your particular choice of analysis method or metric would be capable of detecting. But you don't spend a lot of time to analyze or discuss the limitations of the method, the other major and real effects the method might tend to be incapable of detecting.

In particular, I tentatively think this is going to inherently favor clustering based on the first few moves rather than anything else. So I would hesitate to assign much significance to the fact that it does so in Go, without evidence and comparison with other games. My mathematical/statistical intuitive guess right now is that you'd tend to find a similar clustering based on the first several moves on almost any abstract strategy game played at a high level - that this isn't a thing that's unusual or special about Go, or that is necessarily indicative of special importance of the first two moves, but rather it's an tendency of the methodology itself.

Why? Because, in almost any abstract strategy board game, the situation of the initial board position is the only situation that is common to *every* game and which is also universally aligned at the same point in time (i.e. it occurs at the same index within the sequences being levenstein-compared, namely index 0). Therefore, naturally, what the first few moves are will have an outsized effect on the levenstein distance metric of that game relative to the population of other games, compared to any other feature of the game. For example, even if there would be a huge historical shift in players consistently choosing move A vs move B in some followup shape, if that shape occurs later in the game the effect of that on this kind of levenstein metric will be heavily dampened. As games branch exponentially you will get many more games where that situation might not occur, or where it occurs but in a different orientation or transposition leading up to it (and this won't be recognized as well as a similarity), or where it occurs with the same orientation and same transposition, but at a different point in time. And in that last case of an A vs B choice following a matching subsequence but a different point in time, while levenstein-based clustering would detect this a little, I would expect it to be often poorly because levenstein edit distance will also penalize for all the operations necessary to add or delete surrounding moves to try to align the subsequences with each other to the same index in the sequence. The first few moves of the game are the only case when you are also universally aligned in time, so I think one can expect inherently this metric to favor measuring the first few moves diversity and the degree to which future moves correlate with the first few moves, and measure anything else much less.

For sure, change over history in preference of the first two moves is real, and future joseki choices, do, of course depend on the first two moves. For example, it's not surprising that 3-4 point joseki occurring soon depends greatly on if the first two moves are 4-4 than if they are 3-4 points, and that this changes the course of the opening. Metrics that detect this are useful.

Still, I would have liked to see more exploration of other metrics and ways of probing evolution of openings and playing styles. For example, perhaps methods that look at correlated shifts in frequency of followups across Go history from common local symmetry-normalized patterns, regardless of when that pattern occurs in time (really trying to capture stuff like joseki choice and joseki followups). Or basic coarse metrics like the frequency of play of different points on the board relative to turn number (e.g. crudely capturing tendencies towards low vs high moves over time). Or perhaps a possibility for measuring rate of style change: take a neural net trained/conditioned on games from a certain era (e.g. a given couple decades) and look at the the distribution of KL divergences between the net's predictions and the move distribution in games in the from the next era. (measuring the degree to which a net from one era is "surprised" by the moves from the next era).

Looking at the first four moves at least could be reasonable enough when the goal is to explore cultural evolution. The first few moves aren’t very concrete and are often something of a habit and possibly a group behavior, that players copy from each other. Other aspects of the game, like joseki and their follow ups, could be too concrete to allow much insight into the cultural aspects. It basically doesn’t mean much if players from one period played one way in a joseki than players from another period if the whole board position was always completely different. The first few moves are also sometimes discussed as openings. For example, Go Seigen in his Black/White Opening makes some general comments about the opening at this stage and I recall that he says Shimamura Toshihiro was a specialist in cross fuseki. This seems to support that there is some significance to the first moves that warrants investigation. Beyond this it is also something simple, something that doesn’t require much of an explanation, and in a certain sense it is complete as it can apply to every game, there is not a need to find games that fit a special form.

However, as mentioned above this paper only looks at the first two moves. Maybe this isn’t much different from looking at a few more moves but it begs the question.


About the pretty figures and the conclusions:

I take figures 4, 5, and 6 to just be different pretty views of the same thing. Honestly, these figures don’t tell me a whole lot of things. I’m not sure if I’m able to clearly see that there is a discernable change in the clusters between periods in figure 6. What I can clearly see is a change in the frequency of different openings and I can see some hints of a change in the dispersion of the clusters (which could likely be attributed to the change in the number of examples of each opening).

Figure 7 is the most interesting one but I’m not sure I understand what it is that is being shown. What are the “speed of trait evolution” and “observed standard deviations in aggregate frequency changes each year”? There appears to be one paragraph introducing this and it talks about the “annual frequency changes for all variants at the first and second node of the decision tree” but this isn’t clear enough for me.

I don’t always see a clear connection between the evidence (from the rest of the paper) and the arguments and conclusions in the discussion section.