The Mystery of Go, the Ancient Game That Computers Still Can’t Win
wired.com
wired.com
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.
http://www.computer.org/csdl/proceedings/afips/1969/5073/00/...
The transcribed game record is at:
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/). 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.
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.
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-1...
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.
He's not the author of the original post -- he's the author of the linkedin post he linked to.
With all of the marketing around things like big data, deep learning and other topics, it makes it seem like we're closer to cognizant AI than we really are.
At the heart of all this is still statistics and machine learning which in and of itself is just statistics with a lot more data used to achieve a set of tasks such as predicting a future value or labeling some thing (such as a fraudulent event)
Edit: I'd love to see some discussion on what people think we are close to.
We have to ask ourselves, what is AI and what is considered intelligent? Is it mimicking the human brain as closely as possible (with all the flaws that come to mind such as bias) or is it making the heuristically best decision given a set of circumstances (game playing AI, maximum likelihood learning).
Both of these mindsets can be beneficial. Let's just make sure we treat it for what it is: math and binary information.
>In fact, computers can’t “win” at anything, not until they can experience real joy in victory and sadness in defeat, a programming challenge that makes Go look like tic-tac-toe.
It seems like when it comes to AI advances, there's always a shifting of goalposts as soon as an AI is able to do a task that was once thought to be a defining characteristic of human cognition. Why does it matter if a computer "feels good or bad" at the outcome of a competition for that competition to be somehow valid?
Emotions are orthogonal to rationality, that's why you can devise rational plans to minimize or maximize your likelihood of feeling an emotion. In other words it's perfectly rational to act in such a way to prevent sadness or pain, if that's the value you want to optimize for.
You can imagine a creature (natural or artificial it doesn't matter) that feels emotions and nevertheless it doesn't start acting irrationally just whenever the emotion is strong enough.
I could argue that human beings are in many cases such creatures; even apparently irrational behaviour caused by emotional response usually is not a bad strategy in the original environment where that instinctive reaction was selected for.
I'm not sure it would be a good idea to create AI that simulate humans in all aspects, including unpredictability, just for the sake of it. But I understand some might be tempted to explore that area in order to research creativity, assuming it had something to do with unpredictability.
Perhaps we are just fooling ourselves into thinking that our very failures are what enables us to be so $special (put whatever aspect you prefer in $special). Unfortunately we don't have much means to compare us with something else.
EDIT: This fact has been used to argue against the 'enlightenment' era approach to solving problems. Unfortunately I am unable to find the relavant talk on youtube right now, since all the results for 'enlightenment' return mystic sadhu bs.
Consider the ultimatum game[0]. "The ultimatum game is a game often played in economic experiments in which two players interact to decide how to divide a sum of money that is given to them. The first player proposes how to divide the sum between the two players, and the second player can either accept or reject this proposal. If the second player rejects, neither player receives anything. If the second player accepts, the money is split according to the proposal. The game is played only once so that reciprocation is not an issue."
If you are rational and the other player offers you a cent, you will accept. But humans will become disgusted and angry and therefore refuse. A rational counterparty is hence forced offer more.
http://www.psmag.com/magazines/magazine-feature-story-magazi...
Emotions are not really unpredictable, just very limited in comparison to rationality. They essentially can't deal with unexpected or unprogrammed situations.
The idea of naive learning is very much a goal of most interpretations of what "Artificial Intelligence" encompasses. The scope of the self directed learning though I think is what distinguishes between narrow AI and AGI.
They're also not one of "the most basic concepts in philosophy of mind." They're a very pointed way of illustrating the Hard Problem of Consciousness, and specifically Epistemic Asymmetry, but it's the latter two that are fundamental to modern philosophy of mind, not zombies.
Do you somehow not see the fundamental disconnect between making an argument based on p-zombies and attributing internal state to someone else?
Usually it's because people all over the discussion fail to correctly distinguish between generally adaptive intelligence and specifically engineered "intelligence" (tool that appears to perform a task intelligently), and also between conscious and unaware mechanical intelligence.
A Go or Chess program isn't a goalpost for generally adaptive intelligence, it's a milestone for specifically engineered intelligence. And it isn't conscious, which is the writer's point, though the expression is imprecise enough it could be misunderstood as criticizing the more specific form.
:-)
"You just let the machines get on with the adding up," warned Majikthise, "and we'll take care of the eternal verities thank you very much. You want to check your legal position you do mate. Under law the Quest for Ultimate Truth is quite clearly the inalienable prerogative of your working thinkers. Any bloody machine goes and actually finds it and we're straight out of a job aren't we? I mean what's the use of our sitting up half the night arguing that there may or may not be a God if this machine only goes and gives us his bleeding phone number the next morning?"
"That's right!" shouted Vroomfondel, "we demand rigidly defined areas of doubt and uncertainty!"
> 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%20a...
Disclamer aside, I always thought this was a pretty hilarious alternative to real automation, in the spirit of the xkcd security wrench.
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.
It's an exaggeration but a pretty minor one.
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.
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.
Virtually all tabletop grognard games are perfect information games. I say virtually because there might be one I can't think of at this time, maybe a card driven game. I suppose the COIN series is partially imperfect information... Even a noob player can crush an AI trying to play grognard games so usually the computer cheats or is given a massive handicap, like, say, your human controlled division is up against two, maybe three AI divisions. I've played a lot of grognard games both computer and tabletop and I've never found a worthy evenly matched AI opponent although humans can kick my butt. Some computer implementations implement a fog of war which would certainly be imperfect information, but not tabletops or faithful reimplementations of tabletops. A "good" grognard scenario/game doesn't depend on FoW anyway, or at least many people share that belief.
You can model a stereotypical grognard game as "chess with a large hex board, more pieces, and wider variety of pieces". I guess that gives some idea what a computer-proof abstract game would look like. "GO" on a 171x171 grid, perhaps, or chess with 50 kinds of pieces.
How hard have people tried? I've never had the impression that tabletop wargames had a lot (or any...) programming/AI talent working on them. Too many, too unpopular.
If you study them mathematically, many of those games are actually quite a bit simpler than chess or go, because despite the large number of pieces, turn limits, order limits and very limited setup options will shrink the decision space in a major way.
Those games are also easier to solve because, often to provide a light semblance to how history actually turned out, the rules are set up so that entire avenues of approach are restricted.
So why are AIs worse? because when you make a videogame, getting the hardest AI possible is not really a selling point. We worry instead about not taking too much time, or, in case of a mobile game, not eating the processor alive. Those limits make entire sets of approaches to AI unworkable altogether. If a machine was allowed to think as long as the human does, and we had a reason to actually built said AI, you'd see humans losing a whole lot in wargames. You'd get a similar thing in Euros too, as entire avenues of playing just go away because they are mathematically inferior.
(I know you were probably joking; this is just in case anyone gets the idea that the "captcha game" is just as trivial in this respect as spin-the-bottle.)
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.
But the poster is wrong in saying that this means computers need to use heuristics. Indeed, the recent breakthroughs in Go-playing programs come from removing heuristics that previously helped the programs prune the tree space and instead just using Monte Carlo to simulate all possibilities.
There's a tricky balance, because incorporating too much knowledge/heuristic use can make the program miss good but surprising moves. Nonetheless, the trend seems to be heavy playouts.
One of the surprising results is that having stronger play between opponents in the rollout phase does not always equate with a successful search. Having a balanced strategy -- that is, one that does not introduce a bias for either player -- appears more important.
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.
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)
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 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.
The exact same thing can be done in go, scoring a finished game is trivial. The strength of the program simply isn't determined much by correctly identifying and scoring terminal positions, but the intermediate ones. And for both chess and go, one very much uses heuristics which are often wrong.
If the heuristics were never wrong, you wouldn't have to do the tree search part at all.
Endgame databases only have a tiny effect on the strength of chess programs (a common misunderstanding!) just because it's not very common for the game to be still "flippable" by the time they become relevant. In all the other positions, you need the heuristics.
The situation for checkers on the other hand, is very different. There the endgame databases were critical for solving the game, but due to mandatory capturing rules the search space reduces much faster.
Edit: Not sure why HN won't let me reply. But anyway: the error that you're both making is assuming that the positions in which humans stop and score are "endgame" or "finished" positions. That's not at all the case! A game is finished if there are no more legal moves besides filling one's own eyes. Counting at that point is trivial because all the life & death situations are "resolved". Monte Carlo programs play until those positions, not the ones where a human would stop the game.
(if you now bring up seki, you get half a cookie)
AGA Rules: 9) Ending the Game: Two consecutive passes signal the end of the game.
New Zealand rules: The game is finished when both players agree that there are no more worthwhile moves.
Humans agreeing on a score and outcome has little to do with what a program has to do to calculate this score.
I still don't see your argument. Humans and humans are capable of agreeing on a score with those rulesets. Computers are also capable of following the ruleset and agreeing on the score. Computer vs. human games are not playing by a different ruleset. By that ruleset, the game is over when both sides pass.
I've also encountered this bug. Please bring it up with dang.
Click the [link] link to get a reply box quicker.
Would that be pretty much impossible with Go on current hardware and software?
If true, does it mean a computer (or an Human) could win by just not conceding?
"Conceding" means passing. If you don't pass, you have to play. If you play when the game is effectively over, you either play in your opponent's territory and get captured, or your own, which reduces your score. If you play in your own territory enough then you can actually end up losing your eyes, and then be captured.
"Graham and Rothschild (1971) also provided a lower limit by showing that N must be at least 6. More recently, Exoo (2003) has shown that N* must be at least 11 and provides experimental evidence suggesting that it is actually even larger."*
In this case, I think it is safe to claim that the answer is at least 361!/8, though (but that may already include many truly silly games with suicidal moves in the opening or games that continue way past the time experienced players think they are over)
As for infinite games, they don't really happen much; in rulesets that make it possible for them to happen, the game is usually called "no result", and this has happened only very few times in hundreds of thousands of recorded games. Modern rulesets have "patched out" this by implementing superko or similar rules: playing a stone that would put the board in a state it was in previously (positions of the stones and which player's turn it is) is an illegal move.
If one player would never concede you would keep playing until the board is full except for the unfillable eyes of the player that wins. Obviously that would take a long time and many negative moves of the losing player.
So you stop playing when both players are confident the game is over and agree on who has won.
By the way, the Chinese rules let solve neatly all those cases handled by special rules in the Japanese rules. The bent four in the corner is the most notable one. Playing it out with the Chinese rules is a neat explanation why that corner is defined to be dead: the surrounding player defends any weakness without losing points and starts the ko. The other player has no ko threats and dies. Those defensive moves lose points under the Japanese rules so they have to make a special rule for that shape and many others.
The only problem with the Chinese rules is that scoring takes longer and completely destroy the shape of the game: you fill in the territory of one player, take out the other's stones and count by grouping the stones in convenient shapes. Furthermore if you want to count during play you must remember how many stones have been captured because prisoners are returned to their bowl and are not stored in plain view (the score penalty is paid by not having those stoned on the board). Japanese rules are a shortcut that makes scoring easy but the tradeoff is the dictionary of special cases at the end of the game.
For each of the (several) traditional rulesets there are positions that the ruleset can't deal with. So in order to allow a mathematical or computer analysis the rules often need to be tweaked.
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.
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.]
(EDIT: This one is going to be especially tricky, since everyone from the generations around ours and younger has been inundated with TV and movies from the US, and the "Chess Player is a genius" trope is all over that.)
First paragraph of article body: "Chess was introduced to Persia from India and became a part of the princely or courtly education of Persian nobility."
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.
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.
The situation with regard to the opening is quite different from chess.
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.
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.
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.
I had to do a genetic algorithm for my HS AI class, and I found that checkers opening through middle was quite amenable.
Late-middle to end-game of checkers is easy to evaluate positional strength, which allowed a very good fitness function. This meant I was able to create a genetic program to learn to play the first half of the game fairly effectively.
http://www.newyorker.com/online/blogs/elements/2014/03/the-e...
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.
If you meant a student studying to be a professional, then 4 stones would probably be true for an even chance game.
Nothing farther from the truth, there are emotion-less people (alexithymia), and that doesn't mean that they can't win or lose.
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.
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.
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.
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.
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
1. http://en.wikipedia.org/wiki/Zobrist_hashing
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.
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 ..)
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.
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.
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- still-doesnt-understa/
Anything bigger than 2 letters and having a name that's not a (very) common word should be fine.
R you sure about that?
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)
You're right, they must have tuned something.
Interestingly, the DDG results feature a precis block where Go the game is first and GO the language is second.
However, english-speaking go players are adapting to this problem. Go is the japanese name for the game--- and we're starting to google for "baduk", the korean name for the game, instead.