Two Laptop Bag*
The moose likes Meaningless Drivel and the fly likes Why computers suck at GO Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Why computers suck at GO" Watch "Why computers suck at GO" New topic
Author

Why computers suck at GO

Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
Rather interesting story: http://technology.guardian.co.uk/online/insideit/story/0,,1835570,00.html

Eric
[ August 04, 2006: Message edited by: Eric Pascarello ]
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
From the article:
But computer chess games don't understand chess; they just got better at crunching moves. Won't brute force do the job on Go, as it did in other games? No, says Bob Myers, who runs the Intelligent Go website. "A very rough estimate might be that the evaluation function [for computer Go] is, at best, 100 times slower than chess, and the branching factor is four times greater at each play; taken together, the performance requirements for a chess-like approach to Go can be estimated as 1027 times greater than that for computer chess. Moore's Law holds that computing power doubles every 18 months, so that means we might have a computer that could play Go using these techniques sometime in the 22nd century."


For writing an article about computing power, the author doesn't display much knowledge about powers of two.

Let's use 1997 (when Deep Blue beat Kasparov) as the starting point, and double computing power every 18 months. Won't we have something 1024 stronger than Deep Blue after only ten 18-month periods? Let's see, 10*18 is 180 months or 15 years. So by 2012 (what the heck, let's say 2014 to get well OVER 1024 times the computing power), we should have a pro level Go program.

...or did I just just royally stick my foot in my mouth?
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8801
    
    5
Thanks for the link. It's a "kind of" good article...but it has a lot of small factual errors - although I'd say it gives a fairly accurate high level view.

But let's start with one example. The article says something like "the branching factor is 4x more in Go". I understand that the typical number of available chess moves is 40 and the typical number of available Go moves is 200 - so that would be 5x, but that's not really too important. What's important is that in order to look ahead using brute force, you have to take these factors (40 vs. 200) and raise them to powers of themselves. Let's take an example:

In order to look ahead 4 moves (white plays, black plays, white plays, black plays) the rough number of positions to consider for chess would be:

40 ^ 4 ~= 2.5 million

for Go would be:

200 ^ 4 ~= 1.6 billion.

So, at a really simplistic 4 move look ahead level we're at 1000 times difference...

When we get to a more realistic 8 moves ahead (which is still not good enough to play at a strong level) the difference is:

6.5 x 10^12 vs.
2.5 x 10^18

Now we're up to a million times more computational overhead - and that's assuming that the static functions are equivalent, and the article says that Go's static function is probably 100x slower (which seems likely).

So, at 8 move look ahead the Go computer has 100 million times as much work to do... I'm not holding my breath for 2012 :roll:

I think that's great news!


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
Originally posted by Bert Bates:

So, at 8 move look ahead the Go computer has 100 million times as much work to do... I'm not holding my breath for 2012 :roll:

I think that's great news!


Ok, so tack on another 17*18 months or 25.5 years. So 2037 will usher in a new age of computer Go.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8801
    
    5


How about a more realistic 12 moves ahead...

BTW, aren't you supposed to be thinking of a move yourself?
Mani Ram
Ranch Hand

Joined: Mar 11, 2002
Posts: 1140
Computer Wins a Game Against a Go Master

During the Go Tournament the MoGo artificial intelligence (IA) engine developed by INRIA running on a Bull NovaScale supercomputer, won a 9x9 game of Go against professional 5th DAN Catalin Taranu. This was the first ever officially sanctioned 'non blitz' victory of a 'machine' over a Go Master.


Mani
Quaerendo Invenietis
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11139
    
  16

The MoGo artificial intelligence (IA) engine... won a 9x9 game of Go against professional 5th DAN Catalin Taranu.

Isn't that like saying a computer beat a human at chess on a 4x4 chessboard?

I need to dig out my books and start reading them again. One of these days I'll start playing...
[ April 14, 2008: Message edited by: Fred Rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18486
    
  40


From the article:
But computer chess games don't understand chess; they just got better at crunching moves. Won't brute force do the job on Go, as it did in other games? No, says Bob Myers, who runs the Intelligent Go website.


The other issue is that this is a "software" problem that is being solved as a "hardware" problem. The reason chess programs are in such good shape is the ridiculous large "opening books", "middle game", and "end game" algorithms. Modern chess programs aren't just more hardware. They are much better designed than they were decades ago.

IOWs, the chess algorithms may be "brute force", but they are much much better "brute force" than they were in the past.


[EDIT: Oops. I didn't realized that this is an old thread risen from the dead. Sorry.]

Henry
[ April 14, 2008: Message edited by: Henry Wong ]

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[Mani]: The MoGo artificial intelligence (IA) engine... won a 9x9 game of Go against professional 5th DAN Catalin Taranu.

[Fred]: Isn't that like saying a computer beat a human at chess on a 4x4 chessboard?


Roughly, yes. A 9 x 9 board will have far, far, far fewer permutations of moves possible than a standard 19 x 19 board, and so it's inherently much more amenable to a brute force approach. Also most of the standard strategies and tactics that the human has learned would become invalid on such a small board. Playing on a 9x9 board seems strongly biased in favor of the computer. So while this victory may be indicative of some sort of progress, it's nowhere near the end of humans' dominance of the standard game.


"I'm not back." - Bill Harding, Twister
Mani Ram
Ranch Hand

Joined: Mar 11, 2002
Posts: 1140
True. But couple of years back, I read an article saying that programming a computer to defeat an amatuer, even in a 9X9 Go board would take another decade. Now that a computer has defeated a 5th Dan [Go Master? ] looks impressive.

Agreed, 19X19 is still long way to go.
[ April 14, 2008: Message edited by: Mani Ram ]
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8801
    
    5
Hmmm...

Here's a crude analogy to try to get the feeling of a 9x9 vs. a 19x19 board. It's kind of like saying that you've built a golfing robot that's really good at putting, but that's all it can really do. So, while putting is a necessary part of the total solution it doesn't really predict progress in other aspects of the game. In a similar fashion, playing well on a 9x9 board is, kind-of, a necessary aspect of Go, it completely ignores most of the complexities that occur on a 19x19 board. Go is a lot less "brittle" than chess. It's often true in chess that if one player captures as little as one extra pawn, that player can reduce the game by making even exchanges from there on out and win in the endgame. In other words, once you've lost a pawn the game is often decided. In Go, a local loss can often be leveraged into an advantage in other parts of the board. None of this kind of strategy is really possible on a 9x9 board.

Usually at the U.S. Go championships they will have a fun 9x9 tourney. People who have prepared for 9x9 games can succeed with predetermined strategies that work more or less independently of the opponent's opening. More specifically, the black player (who moves first), can usually establish an opening framework that will win regardless of white's opening strategy.
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Originally posted by Bert Bates:
What's important is that in order to look ahead using brute force,


Brute force is not efficient.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41017
    
  43
Brute force is not efficient.

As a blanket statement that's not correct. It may in fact be very efficient in terms of developer time (it's much faster to program a brute force algorithm than a more intelligent algorithm).

What brute force doesn't do is scale when applied to a problem that grows exponentially (like chess or Go).


Ping & DNS - my free Android networking tools app
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8801
    
    5
Hi Ankur,

I think you've pulled my quote out of context - I was by no means advocating brute force searches, I was simply discussing them. I suspect that most good Go players use a combination of pattern matching to reduce the size of the area to be searched, and then use some form of simplified brute force when picking the best move within that restricted search space. The thing is that while it might not be efficient, in many cases, within a narrow search space, it might be necessary. If you pick up any of a thousand Go books that present "Life and Death" problems (which are themselves an essential element of the game), you will see that some sort of modified brute force approach is often necessary.

hth,

Bert
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Originally posted by Bert Bates:
Hi Ankur,

I think you've pulled my quote out of context - I was by no means advocating brute force searches, I was simply discussing them. I suspect that most good Go players use a combination of pattern matching to reduce the size of the area to be searched, and then use some form of simplified brute force when picking the best move within that restricted search space. The thing is that while it might not be efficient, in many cases, within a narrow search space, it might be necessary. If you pick up any of a thousand Go books that present "Life and Death" problems (which are themselves an essential element of the game), you will see that some sort of modified brute force approach is often necessary.

hth,

Bert


Thanks Bert. I got your point.
Amit Ghorpade
Bartender

Joined: Jun 06, 2007
Posts: 2716
    
    6

Well I know very little of AI,
but I think that a better approach would be elimination of invalid results first, so that one does not need to backtrack and then use brute force so
there may be an average 30% speed up.


SCJP, SCWCD.
|Asking Good Questions|
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11139
    
  16

What do you mean by "invalid results"? In Go, there are (on average) 200ish legal moves per turn. Non are invalid. What do you want to eliminate?
[ April 16, 2008: Message edited by: Fred Rosenberger ]
Amit Ghorpade
Bartender

Joined: Jun 06, 2007
Posts: 2716
    
    6

Well what I've said applies more to Chess rather than Go,
and by invalid results, I mean illegal moves.
If a program for example say a chess engine knows well in advance the moves that are illegal, it can discard them right in the beginning instead of backtracking. This might facilitate a good look ahead.
But it seems that Go requires more of visualization than programming.

siva kumar
Ranch Hand

Joined: May 02, 2004
Posts: 120
GO is a game of combinational explosion�. Where there are really lot of permutations and combinations, the ideal approach to games like go is to not solve them at micro level, but to attempt to solve them at macro level. � This is exactly how nature solves problems where combinational explosion is a concern.

In fact human brain works on large scale patterns to try and attempt fit a particular pattern to a scenario, and then refine the pattern to the nearest possible solution.

I really wonder if there is any attempt to develop a GO playing machine which uses ANN (Artificial Neural Networks).
The best strategy is to develop such a machine with enough neurons and ensure that the machine is trained enough to defeat any champion.

Frankly�. I think this is all funny� even if somebody develops a good GO playing machine it would be far from being intelligent.

If Ai is attempting to produce machines which are supposed to be intelligent , Then is a pointless trying to design machines which plays games.
Amit Ghorpade
Bartender

Joined: Jun 06, 2007
Posts: 2716
    
    6

If Ai is attempting to produce machines which are supposed to be intelligent , Then is a pointless trying to design machines which plays games.

Why? Isn't learning or training of an ANN symbolic to coaching for playing games.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11139
    
  16

I think there are two goals here... making intelligent machines, and making a machine that can play games. both are worthy goals. and, i think they actually overlap to a large degree. what you learn from working on one will help you with the other.
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
It is practically not possible to make human like machine.

Let�s say there are 10 humans on earth and 10 situations. Assume each person can react by 10 different ways for a situation. So there are 10*10*10 = 1000 possible combinations.

Suppose we capture all the patterns (1000 in this case). How can a machine decide which way to act on a situation (there are 10 in our case, if human and situation is input to the machine).

And sure there would be many other things to consider...

[ April 17, 2008: Message edited by: ankur rathi ]
Amit Ghorpade
Bartender

Joined: Jun 06, 2007
Posts: 2716
    
    6

Suppose we capture all the patterns (1000 in this case). How can a machine decide which way to act on a situation (there are 10 in our case, if human and situation is input to the machine).

Thats what training/learning is meant for,anyone who knows ANN can easily say that. Then there are heuristics and adaptive learning.
So the machine may get it wrong for the first few trials, but then it adapts for the future ones.

Kelahcim Kela
Greenhorn

Joined: Aug 17, 2007
Posts: 29

Suppose we capture all the patterns (1000 in this case). How can a machine decide which way to act on a situation (there are 10 in our case, if human and situation is input to the machine).



The question, in fact, is: how do people make a choice and how can we be sure that the choice is the optimal one.

Another issue here is, that we expect a person to be fully independent agent while in fact we (as human) are just a sum of our experience. Shouldn't we expect AI to have a chance for some adaption as well?
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8801
    
    5
The whole left brain / right brain theory has been blown out of proportion, but let's say for the sake of argument that one part of our brain is really good at seeing patterns, and that another part is really good at detailed analysis.

Given that, Go is a really interesting problem because to be successful, you need to do both of the above, most of the time. In other words, the thought process for a given move is often something like this:

1 - What are the implications of my opponent's last move? Did the last move change the status of any of the local or remote situations on the board?

2 - Given the new balance on the whole board, which region is most important?

3 - Given the most important region, what would be the best strategy in that region.

4 - Given that strategy, what's the best move to initiate that strategy?

It's likely that steps 1 and 2 could be handled with some sort of neural-net-ish approach. It's likely that step 4 ought to be handled with some sort of exhaustive search approach. Step 3 exists in a kind of awkward middle ground.

In any case, the fact that at this point there probably isn't a single known AI strategy for Go makes it a really cool problem.
Amit Ghorpade
Bartender

Joined: Jun 06, 2007
Posts: 2716
    
    6

Yes I agree with Bert,seems he has given the exact decomposition of the problem.
But for the third part can be tackled to some extent by pattern matching, as they use in face recognition techniques.
Although it may be argued that n number of patterns exist, but can handle at least some percent of them.
 
wood burning stoves
 
subject: Why computers suck at GO
 
Similar Threads
.Net vote rigging illustrates importance of Web services
C# try to be Java sneaky!
This weeks Giveaway
SDLC
Patent absurdity - European parliament to vote on software patents