14 ms·
The Mystery of Go, the Ancient Game That Computers Still Can’t Win
- nabla9 12y agoGo is very complex. How about game with much smaller search tree complexity first, like poker. We don't have computers winning professional poker players yet. They are quite good in heads up game (one to one), but full table is beyond them. The problem in poker is not the complexity of the game, it's in learning how your opponent thinks and how they adjust to your play.
- rockdoe 12y agoPoker is not a game of perfect information.
- hyperpape 12y agoWhile it's not perfect information, it's been studied quite a bit, and heads up play is getting very good for some games. Not sure if that's limit, no-limit or what.
- gabemart 12y ago> How about game with much smaller search tree complexity first, like poker. I presume you're talking about limit poker. In pot-limit or no-limit poker, the search tree is large, especially (as you say) for 6-max or full-ring. I don't have much of a frame of reference, but I'm tempted to say "very large". > The problem in poker is not the complexity of the game, it's in learning how your opponent thinks and how they adjust to your play. I don't understand this distinction. It seems to me that learning how your opponent thinks and how they adjust to your play are a central part of the difficulty in most deep games of strategy.
- aninhumer 12y ago>It seems to me that learning how your opponent thinks and how they adjust to your play are a central part of the difficulty in most deep games of strategy. For human players perhaps, but my impression is that most Chess playing software simply tries to find the strongest move, without considering the opponent to any great extent. The opposite extreme here is Rock Paper Scissors AI, where there is evidently no strongest move, and the only way to do better than a draw is to identify the opponent's strategy.
- aetherson 12y agoI think you may be talking past each other. Chess programs, for example, certainly "consider" the opponent. Indeed, they consider the opponent to the extent of mapping out tens of billions of possible opponent moves. What I believe you're saying is that they don't do is consider the opponent as a unique individual, rather than as a generic opponent to be brute-forced. They don't say, "Oh, well I'm playing against Kasparov, who plays aggressively, so I'll set a trap," versus "I'm playing against Karpov, who overvalues his knights, so I'll threaten them." (Note: these are not actual foibles of Kasparov or Karpov). Knowing your particular opponent is, it seems to me, a tree-pruning technique, in much the same way that the Monte Carlo approach that is highlighted in the article. If you can anticipate ALL possible opponent responses to an acceptable depth, that's clearly better than making assumptions about how your opponent will respond.
- aninhumer 12y agoYeah, they said they didn't understand the distinction, so I was clarifying. Poker leans a lot more towards the Rock Paper Scissors style of AI, where determining the best move becomes much more dependent on understanding your opponent's strategy.
- ronaldx 12y agoOne additional issue for computers is that humans don't play the game tree out to its conclusion - humans recognise winning and losing positions rather than playing a much longer (perhaps infinite) prove-out game. A naive game theory strategy runs into a disasterous problem - the game tree is extensively longer than the 200 moves that a human will play. So, a computer has to recognise a winning position, in a heuristic way, as well as the best players do. But, even as a total beginner, it's easy to notice Go programs sometimes get the end-of-game scoring totally wrong. Once you've overcome this first problem, you've reduced Go to "just" a 200-move game tree.
- hyperpape 12y agoI don't know what you're trying to say. Monte Carlo based programs play out entire games, and evaluate them by scoring the end of the game--no heuristics needed for the evaluation, only for the playouts. And yes, they can accurately score a completed game.
- ronaldx 12y agoI'm trying to express why Go is a difficult problem to solve. I'm saying this (scoring, play-out) has been a difficult problem, which was not solved even a small number of years ago, and is still not considered straightforward. Even if it is solved correctly now, that's only a start. I would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal.
- rockdoe 12y agoI would also note that Monte Carlo is by definition a heuristic method - it is statistical and not guaranteed to be optimal. So is the endpoint evaluation in chess programs. This isn't a difference between Go and the other games. (In fact, pretty much nothing in your original post is)
- ronaldx 12y agoAnyone who has a modest understanding of chess can codify very simple rules for identifying a winning endgame. There are extensive wikipedia articles on what constitutes a winning endgame in chess, as the board simplifies towards the end of the game: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase says "All chess positions with up to 6 pieces have been solved" So, I disagree. Even if you don't count this as a theoretical difference, it is a practical difference.
- hyperpape 12y agoOne falsehood in the article is that Go is the only game where computers "don't stand a chance." In fact, computers are substantially worse than the best humans at Go, Arimaa, Hex and maybe Havannah [1], to take some games that I know. Arimaa is underexplored for both humans and computers, but there are several programmers working on it, and there is a modest prize available. Hex and Havannah are less explored, but they also have academic work done on them, and their human communities are also small, which means that we're not getting the best humans can do. [1] Havannah has a pretty good bot, Castro, but I think it's still quite beatable.
- rockdoe 12y agoOne of these games was designed to be hard for computers, the others are way less popular than go and have far less history, and hence competition/interest. It's an exaggeration but a pretty minor one.
- hyperpape 12y agoYes, but as I pointed out, there's also less human interest in those games. That affects both humans and computers. No one is a grandmaster at Arimaa, Hex or Havannah. If those games were more popular, then both computers and professionals would be better. As far as the quality of the exaggeration, I think it is misleading. Shogi programs are just catching the best humans in 2013-2014. Go may not resist artificial intelligence for another ten years. That's a noticeable difference, but also not that grand of one. I'd just like a little accuracy: we may not be dealing with more than moderate differences in difficulty.
- hajile 12y agoShogi programs only match up in the standard 9x9 board. They fall far behind the moment you introduce a larger variant. As to go, computers have a hard to time with 9x9 and a handicap. 13x13, 19x19, or larger is even further out of the question. The fundamental issue is that the problem must be solved entirely with heuristics. We have trouble modeling cat brains. We are a long way away from human-level pattern recognition heuristics.
- coldcode 12y agoThe problem is inherently parallel but not obviously what each task should be doing. The experienced brain clearly can see the whole board and recognize what to do next but a computer can't right now. If I had more time this would be a lot of fun to work on. My approach would be to find some way to evolve a Go player. People clearly learn over time by playing a lot, which is basically programming their brain to recognize state and options.
- dlecorfec 12y agoDamn game, because of it we are forced to use "golang" in search engines.
- thaumasiotes 12y agoRight, because "go" doesn't occur outside of the context of the game or the language...
- dlecorfec 12y agowoosh.
- raverbashing 12y agoDarn those who call their languages something ungoogleable by itself (yes R I'm talking about you) Anything bigger than 2 letters and having a name that's not a (very) common word should be fine.
- dvirsky 12y agothe golang alias works pretty well, but until you learn this trick it's annoying as hell.
- datashaman 12y agohttps://www.google.com/#q=R https://www.google.com/#q=R R you sure about that?
- raverbashing 12y agoThe bubble may be helping, but see this: https://duckduckgo.com/?q=go https://duckduckgo.com/?q=go Also, I think there might have been some tuning by search engines/web pages (a couple of years ago I remember it was more difficult getting a good result)
- datashaman 12y ago
- deleted 12y ago[deleted]
- mickeyp 12y agoI've always wondered if it's possible to inductively teach a computer to play Go using some form of machine learning by playing tens of thousands of games; perhaps games with annotations by humans following a simple format to guide the fledgling AI: "Good move", "Bad move", etc. I used to play Go but stopped a long time ago. It was a game where you had to train your brain to recognise patterns and act on them.
- rockdoe 12y agoIt depends on what you consider "teach to play Go". Priming the pattern databases using existing games is a pretty typical strategy.
- itry 12y ago"teach a computer to play Go using some form of machine learning" It would work. Even unsupervised. Let random programs play against each other. Let the losers die and the winners breed offsprings with mutations. If you let that run long enough, i tend to think that the new world champion would arise with certainty. The question is how long "long enough" is. Probably "too long" on current hardware. Would be nice to let this experiment run and draw a graph showing the elo of the best program over time.
- sp332 12y agoRandom? Like code with random logic statements? Random for-loops, and random data structures initialized with random values, and random exit codes?
- itry 12y agoYes. See "Genetic Programming" by John R. Koza for empirical research and in depth analysis of this approach.
- sp332 12y agoYeah, I know what genetic programming is. But your programs don't just have to beat each other, they have to beat expert humans. Since there isn't a way to "crossover" operations from human players to the next generation of programs, crossover is of limited use. That means the only way to progress will be through random mutation, which will take a very long time.
- rockdoe 12y agoThis is one of the best mainstream articles on the subject I have ever seen.
- mark_l_watson 12y agoThat was a good read! I wrote a Go playing program ("Honinbo Warrior") in UCSD Pascal on my Apple II in the late 1970s. I made some money selling it commercially, but it was mostly a hobby. Also in the 1970s, I had the privilege of playing the women's world champion and also the national champion of South Korea. They both gave me huge handicaps, and still easily beat me - I am not a very strong player. Go really is a great game. I bought Crazy Stone for my droid phone, and it really is a fine program.
- thangalin 12y agoA paper written by Albert Zorbist contains a Go record of the very first human-computer Go game. http://www.computer.org/csdl/proceedings/afips/1969/5073/00/50730103.pdf http://www.computer.org/csdl/proceedings/afips/1969/5073/00/... The transcribed game record is at: http://eidogo.com/#3BfnBvgMz http://eidogo.com/#3BfnBvgMz I have asked Albert if he can find the old ALGOL code, as it is of some historical value. The code might be stored on tape, which can be read by Scotch brand IBM tape drives (http://3480-3590-data-conversion.com/ http://3480-3590-data-conversion.com/). He's going to look for his old dissertation, as well, to see if the listing was included. Otherwise, the tapes will be mailed for a data dump.
- mark_l_watson 12y agoReading Zorbist's paper on computer Go sparked my interest in Go playing programs. It would be great to have his old code, papers, etc. on something like github for a historical record.
- ogig 12y agoTangential curiosity I didn't knew, > The first chess programs were written in the early fifties, one by Turing himself When readed that I wondered in what computer could possibly that chess program ran. The amazing answer is: nowhere. Turing executed himself the orders of the program he wrote acting as cpu. http://chessprogramming.wikispaces.com/Alan+Turing#Chess%20and%20Go http://chessprogramming.wikispaces.com/Alan+Turing#Chess%20a...
- fduran 12y agoA chess-playing computer had been suggested as early as 1864, and the first machine able to carry out a "program" was invented in Spain in 1914 by the engineer Leonardo Torres-Quevedo and called Ajedrecista http://en.wikipedia.org/wiki/El_Ajedrecista http://en.wikipedia.org/wiki/El_Ajedrecista
- jfoutz 12y agoSite in general is NSFW, this specific comic has some swearing. Disclamer aside, I always thought this was a pretty hilarious alternative to real automation, in the spirit of the xkcd security wrench. http://media.oglaf.com/comic/theautomaton.jpg http://media.oglaf.com/comic/theautomaton.jpg
- deleted 12y ago[deleted]
- nbouscal 12y agoIf you're going to correct someone, you should do so correctly. You're missing the word "you" in "I hope you won't mind". You're missing the word "I" in "When I read that". It should be "what computer that chess program could possibly have run on". The "could that" order only works in a question.
- mark_h 12y agoKasparov played a game against that program too, for the Turing centenary celebrations: https://www.youtube.com/watch?v=wrxdWkjmhKg https://www.youtube.com/watch?v=wrxdWkjmhKg
- btbuildem 12y ago> Caught between atheism and a crippling fear of death, Ray Kurzweil and other futurists feed this mischaracterization by trumpeting the impending technological apotheosis of humanity, their breathless idiocy echoing through popular media. An unexpected jab in the second-last paragraph, seems the author has some strong opinions about AI. I wonder how he'd respond to Hawking's recently newsworthy worries.
- agibsonccc 12y agoFWIW, it's meant for people not necessarily in the AI field, but here's a general post on it[1]. (disclaimer I'm the author). A lot of people have strong feelings about where cognizant AI could be, I don't think fearmongering is the problem we should be focusing on. I think it should be more focused on the problem solving potential of these systems and how they will become more relevant as computers get better. [1]: https://www.linkedin.com/today/post/article/20140506213247-158494375-response-to-hawking-ai-helps-us-understand-a-world-we-endangered?published=t https://www.linkedin.com/today/post/article/20140506213247-1...
- com2kid 12y ago> Caught between atheism and a crippling fear of death So is that line really necessary? It seems to do not but make assertions about the motives and beliefs of others, and to do such in a negative light. It adds no value to the article, but creates a negative impression in the reader's mind without giving any evidence as backing.
- bostonpete 12y ago> So is that line really necessary? He's not the author of the original post -- he's the author of the linkedin post he linked to.
- com2kid 12y agoAh, confusion. Thank you for the correction.
- thewarrior 12y agoThis only deepens the mystery of humans are able to do it. I really hope I live long enough to learn how human intelligence works.
- hasenj 12y agoKeep in mind it's only the "Top" professional players who have spent hours every day for several years studying the game. The best "Bot" when I last checked was 5dan level; at this level it can probably beat > 90% of human go players? (I don't actually stats ..)
- matthewwiese 12y agoLoving the article so far, interesting read and makes me interested in reading more into the AI Go scene. Any HNers have links that would an excited learner make? also > computer game theory genius Alfred Zobrist I couldn't help but laugh, because I read this an entirely different way than the author intended. I assume he just meant 'game theory' without the computer prefix
- alasarmas 12y agoI see on the Wikipedia article for Zobrist hashing[1] there is a reference to Albert Zobrist, who doesn't appear to have a Wikipedia page, but has pages at [2] and [3]. 1. http://en.wikipedia.org/wiki/Zobrist_hashing http://en.wikipedia.org/wiki/Zobrist_hashing 2. http://chessprogramming.wikispaces.com/Albert%20Zobrist http://chessprogramming.wikispaces.com/Albert%20Zobrist 3. http://senseis.xmp.net/?AlbertLZobrist http://senseis.xmp.net/?AlbertLZobrist
- michaelochurch 12y agoCaught between atheism and a crippling fear of death, Ray Kurzweil and other futurists feed this mischaracterization by trumpeting the impending technological apotheosis of humanity, their breathless idiocy echoing through popular media. Wat. Why was this bit of out-of-place and mostly off-topic divisiveness dropped into an article about Go? I don't expect "the Singularity" to come in my lifetime, although smaller victories in "AI" have already proven themselves very useful; but let's leave God out of AI debates. Whether there exists a God or gods (all "atheism" means is not believing in gods, and nothing either way about life after death), whether there is life after death, and what AI can do are orthogonal matters. The one that we can do something about, is the last of these. For me, I'm a huge fan of AI and would love to see more research in that vein, but I don't dread or fear my eventual death. I don't intend to bring death on prematurely, but my curiosity has me looking forward to it. I certainly don't expect to see a "Singularity" by 2045. That said, if I could program a computer to (say) cure cancer, or extend the human lifespan, I would do it in a heartbeat. The stereotype that all AI researchers are "atheists" (as if that were a negative, or even a meaningful category) driven by a "fear of death" is (a) untrue, and (b) irrelevant. The great thing about science is that it doesn't matter what your religious beliefs are, and it seems to work regardless of whether gods exist.
- nova 12y ago> "Death is bad," said Harry, discarding wisdom for the sake of clear communication. "Very bad. Extremely bad. Being scared of death is like being scared of a great big monster with poisonous fangs. It actually makes a great deal of sense, and does not, in fact, indicate that you have a psychological problem." -- HJPEV
- trendoid 12y agoNot sure why he put atheism bit but considering how many pills Ray Kurzweil takes per day(200?) to increase his age by keeping himself young, it wont be surprising if he has a genuine fear of death. Some of his claims are quite ridiculous and PZ has done a good job of pointing out why so : http://scienceblogs.com/pharyngula/2010/08/21/kurzweil- http://scienceblogs.com/pharyngula/2010/08/21/kurzweil- still-doesnt-understa/
- shmageggy 12y agoDoes anyone have a link to more information about the percolated fractal and how it relates to Go positions? A quick googling wasn't satisfying.
- ivanca 12y ago>In fact, computers can’t “win” at anything, not until they can experience real joy in victory and sadness in defeat Nothing farther from the truth, there are emotion-less people (alexithymia), and that doesn't mean that they can't win or lose.
- conanbatt 12y agoFirst of all, let me share that what Remi achieved with bots is incredible for Go players. When I was 16, the best bots out there were 6kyu, 5 ranks below the median rank for Go players. Now, CrazyStone and Zen achieved 5d consistently on Go Servers, thats 5 ranks above the median. I have played Zen once, and I was utterly impressed by the quality of its play. However, my game with the bot confirmed to me how bots WILL NOT beat professionals in a LONG LONG time. The bot excelled at tactical situations, and endgame. Maybe almost professional level. But the strategy is so weak, that the game turns into taking advantage in the first stage of the game, and then not losing it in the rest of it. Until the computational power is strong enough to develop new openings, computers will always lag behind professionals in Go.
- sanxiyn 12y agoI don't agree with this. You can handle openings by using a pre-computed book. If you think about it, this is actually how humans handle openings. There is an opening theory, to which huge amount of analysis(pre-computation) was done. Even professionals don't do impromptu opening analysis over the board. On the other hand, in my opinion computer tactics are nowhere close to professional level. Not even close.
- hyperpape 12y agoOpenings can't be handled by a pre-computed book. What we humans call the opening can be 40 moves, and professional games often feature unique moves within the first 10-20 moves. The situation with regard to the opening is quite different from chess.
- cynicalkane 12y agoOf the corner opening patterns alone (called joseki), there are 10000s of them, and it's very common to use novel ones. Many joseki, like the well known 4-4/3-3 invasion, can range from great plays to disasters depending on board position. And there are four corners.
- conanbatt 12y agoThe approach of trying to repeat the human process for pattern recognition is probably the main reason why bots were so weak until it was decided by a few computer scientists that Go should also be battled with brute force. In one of the Zen vs Takemiya(?) or other professional games, the bot manages to kill a group by the professional with razor-sharp precision, including several tesujis. They excel at local tactical situations, and in terms of killing groups in a big board, they are excellent at poaching eyes.
- wtbob 12y ago> Crazy Stone and Nomitan are locked in a game of Go, the Eastern version of chess. Ummm, the Japanese version of chess is…chess. It's called shogi. There's also a Chinese version of chess, xiangqi. There are, I believe, Vietnamese, Korean, Burmese and perhaps other varieties of chess. There's certainly no common 'Eastern version of chess' any more than there's a common 'Easter version of food.' Go is a Japanese game of considerably greater complexity than chess.
- jamesli 12y agoThumb up on the comments on "the East Version of Chess". Go is not a Japanese game, though. It was originated in China more than 2000 years ago. It is very popular in both China, Japan, and South Korea. [I don't know how it is in North Korea.]
- hyperpape 12y agoNorth Korea has a number of strong players--probably better than those in Europe and the US. They've competed in a few international events.
- squidfood 12y agoAs "an abstract strategy game that is considered culturally to be a symbol of intelligence, deep thought and deep tradition", the analogy works for me.
- stcredzero 12y agoChess as an indication of intelligence is an American cultural quirk. In other parts of the world, people just think that means someone is good at chess.
- squidfood 12y agoI can't speak to the rest of the world, I was honestly thinking more of Turkey than America (where I spent hours and hours ruining my college career through this game, a national obsession second only to backgammon).
- RRRA 12y agoMy impression was that recently Go had fallen too... http://www.newyorker.com/online/blogs/elements/2014/03/the-electronic-holy-war.html http://www.newyorker.com/online/blogs/elements/2014/03/the-e...
- DerpDerpDerp 12y ago> The victory was not quite a Deep Blue moment; Crazy Stone was given a small handicap, and Ishida is no longer in his prime. As I heard the story, the computer received something like 4 stones (a moderate handicap), and was playing against someone who no longer was top-of-the-world, but was still a strong player. This is very different than beating the world champion in a fair game.
- karamazov 12y agoA four-stone handicap is not small: a beginning professional player could give any top Go player (there are several major championships) a run for his money with 4 stones.
- NhanH 12y agoJust to clarify: a beginning professional player (as in, a player who is considered of professional rank in the Go world, but just in the beginning of their career) will beat any top Go player with 99%+ certainty at 4 stones. The difference between professional players are far less than 4 stones. If you meant a student studying to be a professional, then 4 stones would probably be true for an even chance game.
- microtherion 12y agoThat was with a handicap, not an even starting position.
- civilian 12y agoObviously we should teach Octopi how to play Go! https://news.ycombinator.com/item?id=7730808 https://news.ycombinator.com/item?id=7730808
- h1karu 12y agoHIKARU!!!!!!!! NO GO!!!! http://www.youtube.com/watch?v=E-LHI1MC6Gc http://www.youtube.com/watch?v=E-LHI1MC6Gc
- captaincrowbar 12y ago"It is neither daring nor original to predict that within decades the world's best chess player will be a machine ... Other games such as Go are presently less susceptible to machine analysis, a fact which sometimes provokes incredible displays of intellectual snobbery from Go players who like to denigrate chess as a child's game. When in due course a machine also becomes the top Go player, such people will no doubt move to games like snakes-and-ladders where computers have no detectable advantage." -- David Langford (1979)
- S_A_P 12y agoIsn't this really mis-titled? "Computers" don't win anything. The software is what cant "win" right now. Even though Im sure there is a lot of effort by various companies, academia and individuals into AI, is there really much development being put into beating a go grand master?
- CurtMonash 12y agoSome years back, I played a lot of Igowin on my home PC. At that time it was restricted to a 9x9 board. I'm not a very good go player at all, but I actually had one game in which I gave it a 5 stone advantage and managed to beat it. I should add that the current IOS Igowin seems to be decidedly better than I am, or than I was then.