Complexity of Chess versus Go

[hyperpape]

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.

We didn't start with a particular definition of complexity in mind. Your comment is true for one measure of complexity. My comment was about whether that measure of complexity was the right one.

P.S. Does strategy stealing actually work for Go, since passing complicates things? I recall some discussions from before about it, but I can't remember what the verdict was.

[Jhyn]

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.

This is a good remark. To have a proper definition we would need to add a constraint on time or number of operations used per move. The intuition behind this notion is the amount of knowledge / information needed to play at a given level; obviously if you have the whole eternity to read all variations you need to know nothing in advance, so we have to fix an (arbitrary) limit on the number of operations. The actual limit is irrelevant as long as we are comparing two different games.

[Joelnelsonb]

...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.

I have found, from approaching both games with equal commitment, that in the beginning Go offers a player a wider strategic arena and has a good dose of tactics to follow it up. Chess, on the other hand, starts as an almost purely tactical game and the strategy (in comparison to go) could be called shallow. As you improve at either game, however, you'll find that this "gap" is balanced out and go becomes an insanely tactical game while the strategy of Chess becomes more rich and harmonizes nicely with the tactics. All this to say, I agree that Go promotes tactics and strategy together but I would disagree with someone who claims that Chess doesn't do the same and is primarily about tactics. Contrast this perspective with Teichmann GM who claimed that "Chess is 90% tactics" and you'll gain an appreciation for the seemingly infinite number of ways that a player can approach a given game.


To get to the actual question: I think that the depth of complexity for a particular game is dependent upon the specific player. Given how differently some people think about things, it only makes since that one game would click with someone more than another and vice versa for another player. It's like asking which is more complex: mathematics, music or psychology? Naturally, people will be brain wired for certain things more than others and given how vastly different the game play of Go and Chess are, it stands to reason that some people will find one game more simple while other understand the other game better. Personally, I find Chess to make far more sense and I get much more of a feel that I know what I'm doing whereas Go for me is far more mysterious and there's a much stronger sense of being in the dark.


If you're wondering about complexity from a purely mathematical stand point, I believe that some of my points made in the essay linked below are valid.

http://lifein19x19.com/forum/viewtopic.php?f=10&t=11864