Go vs.Chess

        I recently got into a friendly argument with an acquaintence of  mine.He maintains that the ancient Asian board game called GO is  much more difficult and offers more possible moves than Chess.He also claims  that it is not possible that an engine could be developed to conquer the top Go human players as it has in chess and other games.Not knowing much about Go I couldnt rebut his claims however I instinctly doudt them. Can anyone help to clarify this situation?

This might enlighten you a bit: http://www.newyorker.com/online/blogs/elements/2014/03/the-electronic-holy-war.html?utm_source=tny&utm_campaign=generalsocial&utm_medium=twitter&mbid=social_twitter

      thank you Mazkor

Go is a great game.

"More difficult" is subjective, though I believe the game tree is "somewhat bigger".

"Not possible" is a bold claim... I'm not asserting whether it would be possible or not, just that the claim is "bold".

Imagine what the world was like before radio, telephones, television, aeroplanes, the internet etc.

Someone from that time being told what the world would be like today would have a hard time believing it... unless they were really gullible! 

But here we are... 

You are welcome. I strongly suspect your friend is wrong about computers never going to beat the best human players. Keep im mind, that article is at least a year old if memory serves me right.

You are welcome. I strongly suspect your friend is wrong about computers never going to beat the best human players. Keep im mind, that article is at least a year old if memory serves me right.

There is an excellent game about Go/Mathematics called "Chilling Gets The Last Point"... I assume it's excellent anyway, it's a bit above my head... interesting though.

Some mathematicians (self described as mediocre go players) were able to world some things out that were beyond top go players - not under game conditions of course.

Go is played on a 19x19 grid -- much larger than the 8x8 squares of chess. It is not susceptible to the brute-force min-max approach of chess engines.

The New Yorker article Mazkor links is the first I've heard of the "Monte Carlo" approach. Until now Go programs only managed to play at a strong amateur level.

The "Monte Carlo" program managed to beat a top Go player comparable to a chess grandmaster in his sixties. However, I note that it did so with a four-stone handicap, so computers have yet to dominate Go as they have chess.

Go is a deep, elegant game. Even if you don't know the rules, the patterns created on the Go board have an organic beauty.

This Android app autoplays Go games forward and in reverse. It's like watching time-lapse photography of plants.

https://play.google.com/store/apps/details?id=com.jacktrainor

The game tree for GO is ridiculously large if playing on a proper 19x19 board.

For starters, pieces aren't restricted to a set move patterns.  There are only a couple of rules about piece placement.

1) a piece cannot be placed such that it has no liberties.  This rule is similar to the rule about castling through check.

2) a piece cannot be placed such that it creates a previous game condition.  There are some variants on this rule as it is theoretically possible to revive a game condition that was dozens of moves prior...  After a while it just gets rough to remember so this rule is modifed to say an immediately prior situation.  This forces ko battles to be productive and not just a stalemate.

To date there is not a computer that can play a reasonable game of Go.  There are simply too many branches to be able to check any respectable depth.  As computing speeds increase, it'll come around, but then it'll be nearly undefeatable.

A second very obvious reason the game tree is so large is that pieces are not captured and the number of possible moves are not reduced as play goes on.  If player A makes a move to eliminate liberties from a large area of B's pieces, those nodes are back in play.  Although not necessarily all good moves for either side.

In chess, light has 20 opening moves to choose, and dark has 20 possible moves.  At the start of the 2nd move there are 400 different situations possible.

In Go, dark has 361 moves to start and light has 360.  When dark's second move begins, there are 129960 situations, although many of these will be rotations and reflections of each other which lead to idential branches whithin that rotation/reflection.  I believe that still leaves over 16,000 ways to begin the game.

Yeah. I'd have to say it's a matter of time now that programmers have a viable strategy.

The big win of the "Monte Carlo" approach is that it takes advantage of multiple CPU cores. Computers aren't speeding up the way they used but they are getting more cores, which you can think of as additional "computers" on the chip.

So as the number of cores increase and the Go programs are refined, I think we can expect the machines to blow past the best human players.

Exactly!

I see a computer playing Go at a master lever to dedicate specific branches of play to an entirely different processor...  at least to a depth of 3.  The main processor finds the branches worth exploring, then dedicates the exploration of each of those branches to other processors.  These processors do the same, if they find a branch that is non-trivial and not idiotic, they send it to yet another processor to explore while continuing.

It'd be a good distributed computing problem!  Anybody work with SETI@home? 

Chess every piece does different things. In Go the game is based on space and time, in chess the game is based on space, time and material. Therefore, chess is a more accurate representation of reality. Because as we all know, the world is composed of space, time, and energy(which is matter), resonating together.

This is the reasons computers cannot play Go. The fact that material exists in chess forms a sort of easy heuristics. The computer is mostly guided by static piece values. Unfortunately, this is wrong, piece values are constantly in flux relative to time and space. Just FYI.

I think I have a go board

I see a computer playing Go at a master lever to dedicate specific branches of play to an entirely different processor...  at least to a depth of 3.  The main processor finds the branches worth exploring, then dedicates the exploration of each of those branches to other processors.  These processors do the same, if they find a branch that is non-trivial and not idiotic, they send it to yet another processor to explore while continuing.

The problem with Go programming is there is no quick-and-dirty way to estimate the value of a position. In chess you count up material then tweak with advantages/disadvantages in pawn structure, piece mobility, king safety etc. There is no quick way in Go to decide what a good or bad position is.

So in the Monte Carlo method, for each position the computer plays ahead semi-randomly through thousands of games, then picks the move which leads to the most wins. Which sounds insane, but with enough cores and computer power it's a viable approach.

Go is a deeply abstract game, so the learning curve to get to a point at which a player can understand the subtleties may be greater than with chess. But your friend overstated it. Learning to play Go on a 9x9 board isn't vastly more difficult than learning to play chess, for instance. On a board that size, Go is often considered a tactical game with some strategic considerations. Go can be so beautiful that it's easy to understand players being driven to ecstatic hyperbole.

I've read somewhere that Go is one of the few board games that humans can still beat computers in. However, I think there are different approaches to both games and that's what makes each game "difficult". 

      I'd like to thank all of  you who have responded to my post.Although I didnt recieve a definative yes or no answer, I am greatly satisfied in the knowledge that there are no difinative answers to most questions . I think that my best course is to learn more about Go and fvorm my own opinion.YOur responses were educational  and informative to me and once again thank you all .

Chess is more beautiful and funny than GO.

The chess pieces are fun and cute; GO has those boring pieces looking like medicine pills.

       You have a good sense of humor Marco, I wish others myself included ,could emulate that. 

Go has vastly more possible positions than chess and it requires a different balance of tactical calculation vs. positional feel. But I wouldn't necessarily say Go is more difficult than chess. Both games are huge and overwhelm the human brain.

The New Yorker article is convincing that not only is it possible computers will conquer the top Go players, they are on their way to doing so. In chess terms the Monte Carlo improvement is comparable to jumping from an 1800 rating to a 2400 rating.