Complexity of Chess versus Go

[RobertJasiek]

In my opinion, a single match does not prove anything about complexity.

For theoretical measures of complexity of go, see

https://en.wikipedia.org/wiki/Game_complexity
https://en.wikipedia.org/wiki/Go_and_mathematics
http://home.snafu.de/jasiek/rulesfaq.txt

For practical measures, these two parameters give a good hint: average game length (number of turns) L, average number of a player's legal next moves M. Then M^L is a very rough estimate for practical purposes.

The theoretical or practical measures put the complexity of Go above that of Chess.

A different view can measure how long it takes to master the game. For Chess and Go, "a lifetime" is a reasonable answer. Therefore, from the POV of skill required to become a world champion, both games are essentially easily demanding.

Yet another view describes the relative impact of strategy, tactics, positional judgement, psychology and time management. Go seems to emphasise strategy and tactics equally; Chess emphasises tactics over strategy. However, neither is more complex than the other. We can simply say roughly which fraction of thinking must concentrate on which aspect.

Computer - human matches rather say something about the complexity of designing particular kinds of AI. More complicated AI is more complex than simpler AI from the POV of the researchers. Or we might compare the "design complexity" of an AI versus the human brain.

EDITED the exponent.

[Krama]

It is easier to make a mistake in chess (not a blunder) and lose the game than it is in go.

If we are not talking about blunders that it is since in go if you blunder a huge group you probably lose the game.

Also since chess games are shorter each move has more weight to it.

[topazg]

I fail to see the logical corollary that "more and broader branching available moves" = "game is more complex".

I suspect the smaller number of available moves and narrower branching makes it easier to program an effective AI for chess, but as remarked my Krama, a single inaccuracy in chess can end the game much more easily than in Go (excluding large blunders which can be fatal in either). There are many ways that you could judge complexity, but I don't think there's any particularly convincing argument that leads to a natural conclusion that either game is objectively more complex.

[Jhyn]

In my opinion, a single match does not prove anything about complexity.

I think this is the good thread to put a few ideas I had about the notion of complexity that I see thrown around so much.

As you mention, combinatorial complexity (the number of possible games) is easy to define but is not particularly relevant to the difficulty of actually playing go, i.e. most possible moves are immediatly discarded even at the beginner level and the game finishes way earlier. Moreover one can easily imagine a game with very high combinatorial complexity but where perfect play is trivial to find.

The apparent complexity i.e. the number of possible games where the moves are considered reasonable by a player of reasonable strength, looks more promising but is actually almost impossible to define properly in a way that includes "reasonable mistakes" as well as pro-level myoshu, etc.

In my opinion, the good definition of complexity in the meaning that people have been using it would be the algorithmic complexity of playing at a certain level, which mathematician will know under the name of Kolmogorov complexity: what is the size (in bytes) of the simplest algorithm yielding a go/chess/etc. engine able to play the perfect game / world champion level / club player level / etc.? Of course it is not obvious how to check whether an algorithm plays at the world champion level (except by playing an extensive match with the current world champion), but at least we have a reasonable rough approximation.

As a side note, I think your formula M^L is not a good estimate of the combinatorial complexity (I wouldn't even call it an estimate) for a game where the number of possible moves vary a lot during the game ; you will miss the actual number by several orders of magnitude, even if you had a good estimate on the value of M and L. Taking the geometric average instead of the arithmetic average would make this a little better, although I'm not sure by how much.

[Uberdude]

Something which I think is a key issue in comparing the relative difficulty of Chess and Go but I don't often see mentioned is the following: the pieces in Go don't move whilst they do in Chess and this makes it far easier for a human to visualize and read ahead in Go than in Chess. So although Go has more move choices and longer games (and I believe Go players read more moves deep and maybe wide than chess ones for equivalent levels of skill), that reading is easier per move. So the two games are probably about the same difficulty for humans. On the other hand the fact the Go stones don't move doesn't confer the same advantage to computers trying to play Go so the much bigger complexity makes it harder for them (plus the harder evaluation function). So instead of saying Go is hard for computers we could say Go is easy for humans. It's worth noting that those Go positions in which the pieces are removed and we play where they used to be (under the stones) are much harder for us to read.

[Bill Spight]

On the other hand the fact the Go stones don't move doesn't confer the same advantage to computers trying to play Go so the much bigger complexity makes it harder for them (plus the harder evaluation function).

I think that the harder evaluation function makes a big difference for computers. A few hundred years ago a reasonable evaluation function for chess was developed, awarding a value for each piece. OC, it is far from perfect, but it has been improved. OTOH, after 40+ years of research nobody has developed a good evaluation function for go. Modern Monte Carlo programs use random or semi-random playouts. It seems like AlphaGo has come up with a good evaluation function, but it is not yet available in human readable terms.

One thing is for sure, more or less secure territory is not as good for evaluating go positions as piece values are for chess, until late in the game. It is only a start. One thing that I approved of in Redmond's commentary is that he avoided making more precise evaluations in terms of points than is reasonable. The error in estimation early in the game is rather large.

[Fearsclave]

IMHO the Chess vs. Go debate is best answered with "both". They're both wonderful, challenging, absorbing, rewarding and life-enriching games played on occasionally beautiful equipment... and I'd submit that the vast majority of players will never come anywhere near exhausting the possibilities and maximum complexities of either.

[Suji]

Yet another view describes the relative impact of strategy, tactics, positional judgement, psychology and time management. Go seems to emphasise strategy and tactics equally; Chess emphasises tactics over strategy.

I would argue that Go is more about the over-arching strategy of the game more than individual tactics. Whereas, Chess is all about the tactical considerations.

[RobertJasiek]

after 40+ years of research nobody has developed a good evaluation function for go. [...] It seems like AlphaGo has come up with a good evaluation function, but it is not yet available in human readable terms.

Evaluations functions for go are not what a Funktion is in German maths: from a given input, produce a single value as output. AlphaGo's good evaluation function is a mapping, as is mine. You should bury the past when there was none. What still does not exist is a program's implementation of a good evaluation mapping that program and humans understand equally well. The evaluations exist but a good translation between code and human language (or vice versa) is missing.

[Bill Spight]

after 40+ years of research nobody has developed a good evaluation function for go. [...] It seems like AlphaGo has come up with a good evaluation function, but it is not yet available in human readable terms.

Evaluations functions for go are not what a Funktion is in German maths: from a given input, produce a single value as output.

Indeed. Evaluations are only partially ordered, which is why their reduction to numbers, whether probabilities or territories/areas, is in theory impossible, as a rule, and in practice imprecise. We are left with estimates within a range that is wide at the beginning and only becomes zero at or near the end of play. That is why Redmond was right to avoid the appearance of too much precision.

Edit: No, that's not right. It is true that traditional go evaluations are only partially ordered. Evaluations based upon perfect reading which include who has the move are ordered: win > tie > loss. Whether probability estimates are only partially ordered or not is a question of their semantics.

[Krama]

Then again if you are playing chess and you feel like you can't win at least you can go for defensive, drawish positions and maybe get a draw.

In go if you are behind you can ether resign or start playing tricky moves or overplays hoping to reverse the game.

[mumps]

I think that the harder evaluation function makes a big difference for computers. A few hundred years ago a reasonable evaluation function for chess was developed, awarding a value for each piece. OC, it is far from perfect, but it has been improved. OTOH, after 40+ years of research nobody has developed a good evaluation function for go. Modern Monte Carlo programs use random or semi-random playouts. It seems like AlphaGo has come up with a good evaluation function, but it is not yet available in human readable terms.

I agree. I think this is actually the main AI advance that DeepMind has achieved - producing an evaluation function by using a Convoluted Neural Network.

[cel70]

I would argue that Go is more about the over-arching strategy of the game more than individual tactics. Whereas, Chess is all about the tactical considerations.

Western Chess has plenty of over arching strategy, more so than Chinese Chess, which almost purely tactical. (Shogi is more difficult to judge on that one!) The key is in the pawn structure mostly. In Xiangqi and Shogi pawns capture the same direction they move, in Western chess pawns often get locked together, and that can cause a semi permament feature of the board that influences the strategy of both players. Having pawns advanced further up one side of the board will give you a space advantage there, so you will most likely play on that side. You may not always know *exactly* what to do on that side, but you will have many of your pieces gather there for some attack. Not every move made in chess has an immediate, concrete effect. For example I might not like the position of one of my bishops, so I spend a couple of moves maneuevering it to a better square to exert influence on the center, or simply to aim towards either the king or queen side. That type of thing is more in the realms of strategy that tactics. Some players in chess history (such as Petrosian) can be almost absurd in the way they can sneak pieces around the board and avoid sharp tactics. The irony is though that such slow positional play is considered dull by many chess aficiandos, who much prefer sharp tactical play.

[hyperpape]

In my opinion, the good definition of complexity in the meaning that people have been using it would be the algorithmic complexity of playing at a certain level, which mathematician will know under the name of Kolmogorov complexity: what is the size (in bytes) of the simplest algorithm yielding a go/chess/etc. engine able to play the perfect game / world champion level / club player level / etc.? Of course it is not obvious how to check whether an algorithm plays at the world champion level (except by playing an extensive match with the current world champion), but at least we have a reasonable rough approximation.

How does this work? In both cases, I would think that naive depth-first search fits the criterion and probably has low Kolmogorov complexity relative to almost any software we use. The problem comes in because the time and space complexity of depth first search is rather high.

[Pippen]

Complexity ultimatively has nothing to do with difficulty. Things that are very complex can be simpler than vice versa. E.g. Chess might be simpler than Go complexity-wise but it is Go where we can at least prove that Black cannot lose while such a proof is not possible in Chess.