NYT Story On Go Programs And AI 246
mykej writes: "The NYT (registration required, blah blah) has a story on Go, the hardest game for computers to play. From the article: 'Programmers working on Go see it as more accurate than chess in reflecting the ineffable ways in which the human mind works. The challenge of programming a computer to mimic that process goes to the core of artificial intelligence, which involves the study of learning and decision-making, strategic thinking, knowledge representation, pattern recognition and, perhaps most intriguingly, intuition.' There are a few throwaway lines about Nash from 'A Beautiful Mind,' although they don't mention the game he invented after getting frustrated with the inconsistencies of go."
History on Go (Score:5, Informative)
It also has instructions on how to teach Go, if you're interested.
A tidbit about Go (Score:4, Informative)
For starters, Go in its pure form is played on a 19x19 board as supposed to an 8x8 board. Chess's famous plays, games and styles have all been archived, whereas Go's strategies are largely abstract and can only be learned by repeated play. The game only begins to take structure after 30 to 50 moves. According to this [well.com] site, Go has approximately 10 to the 750th power of possible board positions. This makes it a very hard game for computers to learn.
On the historical side, Go is a complex game that originated in China close to 4000 years ago and has remained constant to its' original form despite being introduced to many southeast Asian countries since.
Re:Go is harder or.....? (Score:3, Informative)
Go programs (Score:2, Informative)
OT: Nash's game, Hex (Score:3, Informative)
Re:A tidbit about Go (Score:5, Informative)
>Go in its pure form is played on a 19x19 board as supposed to an 8x8 board
So? What has the size of a board got to do with it? In chess you can move pieces around, in GO you cannot.
>Chess's famous plays, games and styles have all been archived, whereas Go's strategies are largely abstract and can only be learned by repeated play .sgf files that you can study to your hearts content. THere are many clasic moves to make in certain positions, etc.
Not really true. There are masses of games available as
>The game only begins to take structure after 30 to 50 moves.
Again, not really. THere are masses of standard opening patterns (fuseki), and also many standardised plays (joseki) that can go on during a game. A whole lot goes on in the first 20 - 30 moves to shape the rest of the game.
Go is a great game, it doesn't need imbalanced comparisons with chess to prove it, you just need to play the game a while to realise that. Maybe you should try.
Hikaru no Go (Score:4, Informative)
HNG was sponsored by the Japanese Go society as a way of making Go more popular, and Japanese Go schools are currently being swamped by new players. It's up to episode 38 already, so you'll have some catching up, but the fansubs are great. This link http://www.toriyamaworld.com/hikago/ has some of the original manga if you're interested.
Go and find out more about Go!!!
Yes, go is harder (Score:3, Informative)
First, there is the board size and the fact that you can play (almost) anywhere on the board, which accounts for the large branching factor (number of possible moves in each position) for the search tree.
Next, there is the fact that games take more moves to finish (about 300 ply, i think, for about 80 for a chess game), which makes the search tree even more staggeringly big. Many many millions of times bigger than that of chess, even when you do a shallow search.
Then there is the difficulty of deciding when the game is over. In go, this happens when both players pass, so this means you have to know when there are no sensible moves anymore. This turns out to be a major problem, whereas in chess the end of a game is more clearly defined.
In fact, it is even very difficult to determine the score for a game when both players have passed. Especially in human expert games, end positions require a great amount of understanding of the game to determine the score.
These, and many other reasons, make Go a very difficult game for a computer. Many (brute force) search/evaluation methods we use in chess and checkers are really not up to the task of playing Go. So we try and figure out some more 'intelligent' methods...
BTW, I have not read the NYT article, but i really doubt they can say anything sensible about 'intuition'. We don't know what intuition is, and even if we would, I think the strenghts of computers lie elsewhere. Let people do what they are good at (intuition, fuzzyness), let computers do what they are good at (count really really fast)...
Chess is not dead yet (Score:2, Informative)
It was a great day for AI but in retrospect a sad day for chess. However it's going to a long time before Chess engines play chess with attitude, emotion and an individual style. If Chess engines just used minmax, alphaBeta pruning, the quality of play would not be very high. Storing opening lines and end game rules makes it a much tougher opponent.
However when these programs are able to store every combination of every possible game and then based the outcomes move up the tree to decide what move to make Then chess will truly be dead.
That will take more than a few EMC boxes! - More like (~35 options per move (starting with 20), ~100 moves per game) = 35^100 = ~2.55e+154 positions. Roughly assuming each position uses 64 bits = 1.85e+143 TB (> a googol Tera bytes!) When you have this 'database' 'populated' you can tell what moves ensure sucess by looking at the end node outcomes.
But for now Go play chess !
Re:Hikaru no Go (Score:2, Informative)
Dr. Smoe
Why Go Programming is Difficult (Score:5, Informative)
Re:Go is harder or.....? (Score:2, Informative)
1. The game space is much larger, perhaps 220 half moves with typically a dozen plausible alternatives per move, compared with, say, 100 half moves and typically fewer plausible alternatives. This alone comes to dozens of orders of magnitude.
2. At various times in the game, quite different strategic issues become most important, sometimes accurate reading, sometimes strategic placement, sometimes choice of board area, sometimes choices between "attack" or "reduce area", etc. Programs tend to be bad at this sort of planning.
3. The large branching factor and the interplay between openings in different corners mean that the opening book, while vast, is much less stereotyped than in chess. A corner opening which is good in one situation can be bad in another, the difference being the presence of a stone or two in remote areas of the board.
4. The fact that the stones, once played, pretty much stay put means that it is relatively easy for humans to visualize long sequences. Even a week-end player may need to visualize the result of "ladder" sequences 50 half-moves long, and can do so in a few seconds. Forcing computers to deal with this search horizon all the time -- or figure out when not to -- makes the searches even more of a bottomless void.
In conclusion, though chess is much higher profile in the west, considerable effort here and in Japan and to some extent China has been put into go. There are many reasons why go is indeed harder to program -- much harder.
The strongest programs in the world are currently a bit better than 10 kyu on the Japanese scale. This is a level which is exceeded by more than 80% of the entrants at the US Congress. (Which will take place in Chicago next week, for anyone interested in seeing real go.)
-- David Erbach
Re:History on Go (Score:2, Informative)
Other information about Go - Links-a-plenty (Score:5, Informative)
k5 had an article [kuro5hin.org] about go which is what initially piqued my interest and got me started in the game.
Kiseido Go Server [kiseido.com] is my favorite place to play online, and very newbie friendly.
Some great introductions are available from Kiseido [kiseido.com] The Interactive Way to Go [playgo.to] and Tel's Go Notes [telgo.com]
Uligo [g0ertz.de] and Goproblems.com are great places for learning how to play in common situations.
If you prefer a phyiscal board and stones check out Samarkand [samarkand.com] and Kiseido [kiseido.com]
Also, anyone in the Chicago area should check out the Evanston Go Club [easyaspi.com]
A word of caution, if you decide to learn go, expect to lose most of your first 50-100 games. It's a long road, but once you start making progress, you'll grow quickly. I know I sure have. Anyone who's up for a game look for 'jjarmoc' on KGS.
Re:Versions of Go (Score:2, Informative)
One of them is Go Moku - a children's game mostly - played on the same board, otherwise known as "five in a row."
There are minor rule variations in modern Go, but these do nothing to change the basis and play of the game except to a very, very minor extent.
Perhaps these other games are interesting, but don't confuse them by putting them all in the same category. They're not.
Re:Nash and hex (Score:2, Informative)
telephone invention (Score:2, Informative)
thomas edison did not invent the telphone.
he had nothing to do with it,
It was Alexander Graham Bell, a Scotsman living in Canada, who invented the telephone.
There WAS a race for the patent, because at least four different researchers were indpendently working on the same project at the same time.
Download an intro to Go program for Windows (Score:2, Informative)
It provides a nice taste of go for noobs.
My only thought is that if computers are no good at Go, then I must really stink since I can't even beat the free intro version most of the time.
Britain Go Association and the BBC (Score:3, Informative)
The BBC had a story in their CBBC kids section about Go just yesterday or the day before.
http://news.bbc.co.uk/cbbcnews/hi/world/newsid_21
I'd never heard of the game before I saw this story. I've obvsiously never played it, but they way they described it, it seemed like games could take a very long time when you use the larger board. I could see how this could be very complicated.
IGS is also good (Score:2, Informative)
-- nyri
US has one too (Score:3, Informative)
Re:Hex (Score:2, Informative)
Massachuetts Go Association (Score:2, Informative)
Generally, a newcomer would start off on board with a 9x9 grid and progress from there to a 13x13 and then a 19x19. The great thing about go is that since each piece (stone) is precisely the same as any other stone, it is quite straightforward to handicap a strong player so that an equitable game can be found vs. almost anbody simply by giving the weaker player position on the board before the game begins.
It's a fantastic game, and without being too bombastic (I hope), it can teach the player quite a number of things entirely outside the scope of the game itself.
Re:Go on the Palm Pilot (Score:3, Informative)
AIGO [so-net.ne.jp] is a shareware Go game for the Palm. It has a stronger AI.
Re:Go vs. Chess in Humans (Score:1, Informative)
1. A very fast evaluation function that produces some kind of score for the value of the position (positive is good, negative is bad). Many chess engines can produce 200.000 evaluations and up per second on an ordinary PC.
2. A search method that enumerates all possible moves, from the starting position, enumerates all moves from these, and so on, and then evaluate the positions at the leafs of this search tree.
Well, that's the basic theory. Of course, if you look at the details there are many many optimizations that you can do so that you won't have to look at all the end nodes. The process itself is called minimax search because you try to maximize your score and the opponent tries to minimize it. The basic optimization is called alphabeta cuts and it works by cutting of a large chunk of the tree once you have found that one move is refuted by an opponent move. You don't have to search for more refutations once you have found one. There are more sophisticated optimizations but they are not interesting here. See http://www.xs4all.nl/~verhelst/chess/programming.
Anyway, the effectiveness of this search is heavily dependent on the so called branching factor, i.e. how many moves are possible to do at a certain position in the game. For chess, this is around 35, for othello somewhat lower (20ish?) and so on. Go has a branching factor of more than 200 almost all of the game. Naturally you can't search as deep when you have to take into account 200 moves as you can when you are only looking at 35.
The next problem with go is that there is no fast evaluation function. In chess everything interacts with everything else very closely. In go, the board is so big that there can be isolated small fights which don't interfere with each other. However, most of the time they do, and in very intricate ways. It is said about go that you can lose every local fight in a whole game and still win the game, just because you managed to lose the local fights in the right way. The canonical example of this is that you let the opponent invade all the corners and live small and then you get a big territory in the center.
Gnu Go (http://www.gnu.org/software/gnugo), a program that I have been working on, evaluates a position exactly once for each move. There is no global search with moves played and unplayed. Instead there is a big pattern database that suggests interesting things to try, like building territory, attack a weak group, defend your own groups, invade, escape, etc. But all these are local goals, and there is indeed search to see if these goals can be fulfilled. But once we know which local goals can be fulfilled and which can not, the real difficulties begin.
The program has to decide which move to actually make on the basis of the global side effects of the moves that satisfy the local goals. In the end, something called Combinatorial Game Theory (invented by a guy named Berlecamp) can be used, but early in the game you have to use thousands and thousand of hand crafted lines of code just to try the combinations that the programmers anticipated.
So to summarize:
1. There is no fast evaluation function in go
2. Minimax search is difficult because the branching factor is too high.
3. Local fights interact in non-trivial ways to create a mess of threats and possibilities that nobody yet has managed to sort out.
Inge Wallin
Member of the Gnu Go team
Re:How to build a Go program (Score:1, Informative)
do and it plays pretty good already.
Sorry for posting as anonymous but i'm too lazy to create a new account now