Life In 19x19
http://prod.lifein19x19.com/

Complexity of Chess versus Go
http://prod.lifein19x19.com/viewtopic.php?f=10&t=12868		 Page 1 of 1
Author:  RobertJasiek [ Thu Mar 17, 2016 5:44 am ]
Post subject:  Complexity of Chess versus Go
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.
Author:  Krama [ Thu Mar 17, 2016 9:03 am ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  topazg [ Thu Mar 17, 2016 9:51 am ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  Jhyn [ Thu Mar 17, 2016 10:21 am ]
Post subject:  Re: Complexity of Chess versus Go
RobertJasiek wrote:
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.
Author:  Uberdude [ Thu Mar 17, 2016 10:45 am ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  Bill Spight [ Thu Mar 17, 2016 4:20 pm ]
Post subject:  Re: Complexity of Chess versus Go
Uberdude wrote:
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.
Author:  Fearsclave [ Thu Mar 17, 2016 4:37 pm ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  Suji [ Thu Mar 17, 2016 7:56 pm ]
Post subject:  Re: Complexity of Chess versus Go
RobertJasiek wrote:
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.
Author:  RobertJasiek [ Thu Mar 17, 2016 11:27 pm ]
Post subject:  Re: Complexity of Chess versus Go
Bill Spight wrote:
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.
Author:  Bill Spight [ Fri Mar 18, 2016 2:16 am ]
Post subject:  Re: Complexity of Chess versus Go
RobertJasiek wrote:
Bill Spight wrote:
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.
Author:  Krama [ Fri Mar 18, 2016 7:57 am ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  mumps [ Fri Mar 18, 2016 8:10 am ]
Post subject:  Re: Complexity of Chess versus Go
Bill Spight wrote:

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.
Author:  cel70 [ Mon Apr 04, 2016 9:28 am ]
Post subject:  Re: Complexity of Chess versus Go
Suji wrote:
RobertJasiek wrote:



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. :D (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.
Author:  hyperpape [ Mon Apr 04, 2016 9:43 am ]
Post subject:  Re: Complexity of Chess versus Go
Jhyn wrote:
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.
Author:  Pippen [ Mon Apr 04, 2016 11:40 am ]
Post subject:  Re: Complexity of Chess versus Go
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.
Author:  hyperpape [ Mon Apr 04, 2016 1:48 pm ]
Post subject:  Re: Complexity of Chess versus Go
Pippen wrote:
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.
Author:  Jhyn [ Tue Apr 05, 2016 12:14 pm ]
Post subject:  Re: Complexity of Chess versus Go
hyperpape wrote:
Jhyn wrote:
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.
Author:  Joelnelsonb [ Thu Apr 07, 2016 12:04 pm ]
Post subject:  Re: Complexity of Chess versus Go
RobertJasiek wrote:

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

viewtopic.php?f=10&t=11864
Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/