Artificial Intelligence Just Mastered Go, But One Game Still Gives AI Trouble

By Carl Engelking | January 27, 2016 12:54 pm
go-board-game-artificial-intelligence

(Credit: Saran Poroong/Shutterstock)

Go is a two-player board game that originated in China more than 2,500 years ago. The rules are simple, but Go is widely considered the most difficult strategy game to master. For artificial intelligence researchers, building an algorithm that could take down a Go world champion represents the holy grail of achievements.

Well, consider the holy grail found. A team of researchers led by Google DeepMind researchers David Silver and Demis Hassabis designed an algorithm, called AlphaGo, which in October 2015 handily defeated back-to-back-to-back European Go champion Fan Hui five games to zero. And as a side note, AlphaGo won 494 out of 495 games played against existing Go computer programs prior to its match with Hui — AlphaGo even spotted inferior programs four free moves.

“It’s fair to say that this is five to 10 years ahead of what people were expecting, even experts in the field,” Hassabis said in a news conference Tuesday.

Deep Blue took humans to the woodshed in chess. IBM’s Watson raked in winnings in Jeopardy! Silver and Hassabis in 2015 unveiled an algorithm that taught itself to conquer classic Atari games. Every year, it seems, humanity waves fewer and fewer title belts over computers in the world of games.

In March, 32-year-old Lee Sedol — the greatest Go player of the decade — will represent mankind in a Kasparov-like battle of wits against AlphaGo in Seoul, South Korea. Should Sedol fall, consider Go yet another game flesh and blood has relinquished mastery to silicon.

But there’s one prize that computers will struggle to take — for a while, at least — from humans: a World Series of Poker bracelet. Ten-player, no-limit poker is the final vestige of our recreational supremacy, and the reasons computers struggle to win this game illustrate a big-picture problem that AI researchers are working to solve. AlphaGo was a step in that direction.

world-series-of-poker

The 2006 WSOP bracelet. (Credit: flipchip/LasVegas.com/via Wikimedia)

Mastering Go

Go represented the ultimate AI challenge because it’s a game with an outstanding number of possible moves on a given turn. For example, in chess a player can consider 35 moves on a given turn. In Go, a player has more than 300 moves to consider. The sheer volume of scenarios to contemplate each turn earned Go its holy grail designation.

To conquer Go, Hassabis and Silver combined deep learning with tree search capabilities to pare down the amount of information AlphaGo needed to sift through. Deep learning algorithms rely on artificial neural networks that operate similarly to the connections in our brain, and they allow computers to identify patterns from mounds of data at a speed humans could never obtain.

Hassabis and Silver started by feeding AlphaGo a collection of 30 million moves from games played by skilled human Go players, until it could correctly predict a player’s next move 57 percent of the time; the previous record was 44 percent. Then AlphaGo played thousands of games against its own neural networks to improve its skills through trial and error. AlphaGo’s success is in its combination of two networks: a value network and a policy network.

go-game

(Credit: Saran Poroong/Shutterstock)

“The policy network cuts down the number of possibilities that you need to look at with any one move. The valuation network allows you to cut short the depth of the search,” says Hassabis. “Rather than looking all they way to the end of the game, you can look at a certain move in the game and judge who is winning.”

This is the key breakthrough. To this point, solving games like chess or checkers involved throwing more resources at the problem to search deeper. Past algorithms have relied on more and more computing power to run ever more simulations of a game all the way to the end — or brute force — to optimize a strategy. A chess program like Deep Blue used brute force, but combined that tactic with windowing techniques to narrow the search and spend less time examining bad moves. However, pruning moves at shallow levels of the search can lead to errors. But AlphaGo is different. It uses deep learning networks to evaluate board positions in isolation and determine who’s winning — without any look-ahead searching. Researchers published their results Wednesday in the journal Nature

“They were able to build an evaluation function that assesses its position that is much more accurate than anything we’ve seen before. And that’s amazing,” says Jonathan Schaeffer, dean of faculty of science at the University of Alberta.

Why Poker Poses a Challenge

Games like chess, checkers and Go are played within a framework of well-defined rules. Players have “complete information” on any given turn: You can see the whole board, and the situation is clear. Computer algorithms thrive in this environment. On the other hand, in a game like no-limit poker, players are working with incomplete information.

“You may not know what card your opponents have. There’s uncertainty. Those are the games where we have the most challenge — games where there’s chance and incomplete information,” says Toby Walsh, an artificial intelligence professor at Australia’s University of New South Wales and Data61. “Apart from the other variants of poker — uncertainty and randomness — there’s a third feature: psychology.”

poker-artificial-intelligence

(ThomsonD/Shutterstock)

Bluffing, reading opponents for ticks and other tells are key skills for top-notch poker players. Psychology, communication and collaboration still pose challenges for machines. Understanding this information requires troves of knowledge about the world. These are things that humans can do instantaneously.

“I can look at a face of a friend and recognize they are my friend, even if they’re in a funny pose,” says Subbarao Kambhampati, an artificial intelligence researcher and professor at Arizona State University. “If you play chess and you win, you can provide a reasonable explanation based on the rules of the game. But how did you know that person was your friend? You have a much harder time explaining.”

The Next Big Step

Teaching an algorithm to go beyond well-defined rules to make assessments about its environment is the next big step in artificial intelligence. This is what Cornell University computer science professor Bart Selman calls “common sense understanding,” or computers that see the world like we do. An algorithm with common sense could be the giant leap that ties disparate technologies together. Think of delivery drones and cars that interpret feedback from the environment to navigate, or a super-Siri that never says, “I don’t quite understand that.”

“Imagine running Uber without human drivers, or a truly useful virtual assistant. If I’m the first to do that, there’s an enormous hidden capital there,” says Selman.

A little common sense will go a long way to help current technology make the next leap forward. That’s the big prize, so it’s no wonder companies and universities are investing heavily in AI research.

“We will spend more of our lives interacting with (computers), and it will be important for them to understand our emotional states,” says Walsh. “For computers to be truly intelligent, they’ll have to have emotions.”

No Reason to Fear

AlphaGo is a step toward an “enlightened” AI because, as Schaeffer says, AlphaGo is a first example of an AI with “general intelligence.”

“There’s nothing in the algorithms that are fundamental to the game of Go. You could apply it to other games,” says Schaeffer. “That allows us to move toward a more general AI — one that can play games, drive a car or do poetry. We aren’t there, but this paper represents an advancement.”

But all this talk of machines with emotions and common sense can send some into apocalyptic fever dreams. Elon Musk and Stephen Hawking have provided their own doomsday warnings about the power of AI. But the experts who weighed in on the latest and greatest AI achievement aren’t so worried.

“People shouldn’t be fearing this. This program has no autonomy. It has no desires to do anything other than play Go,” says Walsh. “The challenge here is not intelligence; you can have really smart computers and no ethical challenge. The problem is autonomy, systems that can act in the real world.”

For Walsh and others, the more immediate concern is the impact on people’s jobs — especially those with well-defined tasks and outcomes. That’s where the conversation should begin, they say. Still, advances in CRISPR and AI should spur the world’s top minds to have a discussion on ethics, and that’s what’s happening at AI conferences around the world.

“We already had the ability to annihilate the world without intelligence systems, and I think these systems will only improve our ability to control that sort of damage,” says Kambhampati. “The what-ifs are probably overblown, and they make for more interesting press, but I don’t think anyone who is thinking about these issues is worried about AI taking over the world.”

CATEGORIZED UNDER: Technology, Top Posts
MORE ABOUT: computers
ADVERTISEMENT
  • lump1

    “Still, advances in CRISPR and AI should spur the world’s top minds to have a discussion on ethics.”

    In other words: “Let’s talk about how someone smart should talk about doing something!”

    I guess I prefer this kind of intellectual cowardice to the usual “Waa, new technological possibilities make me uneasy because they remind me of some half-baked movie, so let’s forbid them and persecute the scientists who research them.” Or maybe it’s just that you don’t have the courage to do your own whining, but you want to express your support for someone else to whine on your behalf. That would be very … millennial of you!

    It depresses me that this is such a common reaction to scientific progress, instead of being thrilled about the potential of both AI and CRISPR to make a better world.

    • Maia

      Every “potential” has an underside, so to speak. It is foolish to pretend otherwise. To be thrilled by new stuff without looking into ALL effects more broadly and deeply, is not intelligent. Gee-whiz science fans are not any more courageous than those who insist on looking at the unintended consequences as well as the benefits.

  • Mark Steele

    Uh huh. In regards to not worrying, does the name Eliezer Yudkowsy mean anything to you?

  • multilis

    “We already had the ability to annihilate the world without intelligence systems, and I think these systems will only improve our ability to control that sort of damage,” says Kambhampati

    If you have an fission bomb that can already annihilate a city, thermo nuclear/hydrogen bomb will only improve our ability to control that sort of damage. (AI can in theory outcompete human soldier, human piloted warplane, human scientist dna manipulating better biological weapons)

    • multilis

      In terminator movies without AI systems the humans could annihilate the world already so would only improve situation to let AI in to get rid of the computer virus.

  • bturcotte

    In other news, a computer scientist names John Tromp just revealed that he had solved all of the possible GO positions.

    • KWRegan

      What he solved was “merely” counting exactly the number of positions that are legal.

  • Michal Rosa

    Poker is the one prize? Really? I’d like to see a computer program playing bridge at any decent level.

    • Stephen Sarre

      is bridge so complex? a scan of the rules suggests very few available sequences of moves, should be easy to map perfect play… i guess the psychology of your partner is important? is that why you think it’d be tricky? what if the computer had a comp. partner, i wonder?

      • Michal Rosa

        It is. A scan of your post reveals that you don’t know how to play it – if so, why do you think you are qualified to talk about it?

        • Small_Businessman

          I agree bridge is very complicated. But there isn’t a lot of psychology in playing bridge, unlike poker where there is a significant amount. Plus, in bridge, you know where 1/2 of the cards are; the rest can only be in one of two hands (and the bidding might give you a hint on some of those cards).
          In poker you know where only a few cards – for instance, in Texas Hold’em you know where 7 cards like The rest could be anywhere. And you don’t know if that raise was real or a bluff. That’s where the psychology comes in.

          • Michal Rosa

            “there isn’t a lot of psychology in playing bridge” – you are very, very mistaken.

          • Small_Businessman

            Well, as I’ve been playing both duplicate bridge (including tournament) and poker for close to 50 years, I think I’m familiar with the psychology involved in both. Compared to poker, bridge has very little psychology.

          • Michal Rosa

            So you have not played at the highest level, or even close to it. Just because you don’t understand or don’t see psychology behind it, it doesn’t mean it’s there.

          • Small_Businessman

            Wrong answer. I have played in many regional tournaments. Just haven’t gone to Nationals.
            But I have found weak players think there is a lot of psychology. The better players know better and can handle the analytics involved.
            Unlike poker, where the better the player, the greater the psychology.

            You obviously have not played much (if any) tournament bridge. Not a single good player I know would agree with you.

          • Michal Rosa

            “Regional tournaments’ – oh, gosh, I’m so sorry, you must be a real master. Any national or international experience we should be aware of (I have both).

            I’m sorry that none of the “good players” you know seem to know so little about bridge.

          • Small_Businessman

            I’m sorry you know so little about bridge. Even Oswald Jacoby, arguably one of the best bridge players ever, said back in the 1930’s “The expert not only knows every card that’s been played, but the manner in which his opponent played it.” That is skill, not psychology. And in tournaments, you can be penalized for trying to deceive your opponents. Not so in poker, where the entire purpose is to attempt to deceive.
            But looking at your other posts, you seem to be an expert in virtually everything – even other things you obviously know nothing about.

          • Michal Rosa

            Yes, it’s a skill – a psychological one. Well said, thank you for proving my point.

          • Small_Businessman

            Not at all. You obviously don’t know the difference between an analytical skill and a psychological one. Deception is a psychological technique.
            But looking through your posts, has become very obvious you have no idea about either bridge or poker.

          • Emkay

            In comparison to computer chess,
            computer bridge is in its infancy. Yet, whereas computer chess has
            taught programmers little about building machines that offer human-like
            intelligence, more intuitive and probabilistic games such as bridge might provide a better testing ground.

            The question whether bridge-playing programs will reach world-class
            level in the foreseeable future is not easy to answer. Computer bridge
            has not attracted an amount of interest anywhere near to that of
            computer chess. On the other hand, researchers working in the field have
            accomplished most of the current progress in the last decade.

            Irrespective of the results of computers against humans in tournament
            bridge, computer bridge already has changed the analysis of the game.
            Commercially available double-dummy programs can solve bridge problems
            in which all four hands are known, typically within a second. These
            days, few editors of books and magazines
            will solely rely on humans to analyse bridge problems before
            publications. Also, more and more bridge players and coaches utilize
            computer analysis in the post-mortem of a match. This info is found on
            Wikipedia….

          • Small_Businessman

            I agree there. However, there is a huge difference between bridge and either chess or go. In the latter two, all possible moves are visible at all times. However, in bridge, you only start out seeing 1/2 of the deck (your hand). You have to try to visualize the other three hands based on bidding (which may or may not be accurate, but generally can assumed to be).
            Once play starts, you get to see another 1/4 of the cards (dummy). But you still have no idea where the other 1/2 of the deck is. Additionally, there is ample place for bluffing during the play, as is customary, especially by better players.
            Double dummy play (in which all 52 cards are shown) allows a “brute force” play of the cards, trying all possible combinations. The best answer(s) can be found. However, when 1/2 of the cards are hidden, not only are the odds greatly increased, but you can’t come up with a winning play – only the odds that one play may be better than another. A champion bridge player, however, relies on more than just odds; knowledge of the opponents’ previous play, slight hesitations (or lack thereof) in the play, and all kinds of things you just can’t program into a computer. But even they don’t get it right all of the time.
            So while bridge hasn’t drawn the interest of chess and go, there are good reasons for it. You can solve a problem when all possible variables (moves) are known, although it can be difficult. But you can’t solve a problem when 1/2 of your variables (cards) are unknown.

          • Emkay

            In comparison to computer chess,
            computer bridge is in its infancy. Yet, whereas computer chess has
            taught programmers little about building machines that offer human-like
            intelligence, more intuitive and probabilistic games such as bridge might provide a better testing ground.

            The question whether bridge-playing programs will reach world-class
            level in the foreseeable future is not easy to answer. Computer bridge
            has not attracted an amount of interest anywhere near to that of
            computer chess. On the other hand, researchers working in the field have
            accomplished most of the current progress in the last decade.

            Irrespective of the results of computers against humans in tournament
            bridge, computer bridge already has changed the analysis of the game.
            Commercially available double-dummy programs can solve bridge problems
            in which all four hands are known, typically within a second. These
            days, few editors of books and magazines
            will solely rely on humans to analyse bridge problems before
            publications. Also, more and more bridge players and coaches utilize
            computer analysis in the post-mortem of a match.

            Wikipedia….

      • http://www.telsys.mx Enrique Segre

        you dont play bridge ,it is obvious

    • Emkay

      it’s too simple..that’s why there has never been any interest in pursuing the game with AI…

  • disqus_zXLbNfw1Yi

    If this article is accurate, it would represent a big breakthrough. For years programmers tried to use Claude Shannon’s Type B selective search strategy on chess with no success. They finally made a breakthrough after computers became powerful enough, and they realized they could switch to the Type A brute force strategy. Even though their position evaluators were not very good, the brute force search could go deep enough for the evaluation algorithm to “see” the best move. But the Type A strategy couldn’t handle GO, because the branching factor was so large that no amount of increased computer power would work. If they have succeeded in creating an effective position evaluator that would mean the machine is able to recognize winning positions “like a human” so to speak, and that really would be a BIG advance for AI.

    • motrek

      The innovative switch from Type B to Type A was made by the Northwestern CHESS team in the 70s (with version 4.0), but it wasn’t a complete switch. They still did selective searches (only capturing moves) at the leaf nodes of the full-width search and they still had basic search depth extensions, e.g., if a side was in check, the search would go deeper. There has never been a competitive chess engine that was completely Type A, and since the 70s, a lot of techniques have been invented for effectively pruning the search tree and making it more selective. (Null move, razoring, late move pruning, etc.) A large part of any modern chess program is to make the search more selective.

  • The.one.and.only

    Skynet

    • Chetan Suri

      Cyberdyne

  • Steven Woodcock

    Remarkable!

    Kudos to the researchers.

  • motrek

    >>This is the key breakthrough. To this point, solving games like chess or checkers involved throwing more resources at the problem. Previous algorithms relied on more and more computing power to run ever more simulations of a game all the way to the end to optimize its strategy.

    This is not right at all and misrepresents how chess engines work and how difficult it is to make them.

    The number of positions in chess increases exponentially and is infinite for all practical purposes. If all a computer did was crunch through different lines of moves, it would only be able to search about 8 half-moves ahead after an entire day of calculation, and the result would be worthless because very few of those lines would result in an win for either side.

    Chess programmers put a tremendous amount of effort into exactly what this article describes as novel–algorithms to evaluate which side is winning for any given position, and by how much, and different algorithms to evaluate whether or not searching a position deeper is worthwhile.

    It sounds like the innovation here is to use deep neural networks for the task instead of carefully-tuned code written by hand by a human programmer over the course of months or years.

  • Daniel

    My first thought was to apply the new algorithm to a new chess program to see how much faster and more effective it might be than the most powerful brute force chess programs by playing one against the other. However, I’m sure they have better things to work on …

  • Har Sukhdeep Singh

    AI is a real life fascinating subject. It is the evolution going beyond the bio. Strangely Hindus, may be others as well, worship stones after invoking gods into them.That is an expression of the desire that science is trying now in a more rational and logical way – the scientific way. Bio evolution could take the life to the point where it can possibly take a jump out of it and develop AI and Artificial Consciousness and Artificial Sub -Consciousness to levels that are at present in the domain of fiction. Possibly many other fields, like quantum computing, memory on DNA, Genetic Computing etc will further this field beyond our imagination.
    But I am pained by what all is happening at the level of common man;disease,fear of death,wars,pollution, greed,anger,attachments, crimes, must be tackled first than going into AI. May be world of inorganic Intelligence and Mind will be free from human deficiencies. My fear is future may be much more murkier due increased levels of AI. Har Sukhdeep Singh,India

    • Maia

      I think a lot of us share your pain…and the sense of irony that we cannot solve our human problems, cannot live in peace or feed everyone, etc, and yet we are so stranglely eager to invest machines with the intelligence we seem to misuse so constantly. Machines (the creations of humans) cannot be free from “human deficiencies”. And what we humans most lack is not computing speed/ power and all the rest, but wisdom and compassion.

    • Laren Ganer

      I think that there are those who believe that AI may be instrumental to helping solve some of the human problems you outline. Much of the challenges we face in resolving certain issues such as disease, the root causes behind criminal activity (or what can be done to reduce/eliminate recidivism), breakdowns in diplomacy that lead to military conflicts, fear of death, etc, may receive huge benefits from advanced intelligence that can process more things more quickly than humans can.

      Obviously, AI is not going to cure all that ails us (not even close), but I wouldn’t want to tell those with the skills and motivation to develop this technology that they shouldn’t be doing it because there are important problems in the world.

      I think one of the greatest things about humanity is our ability to multitask, and our creativity in doing so. We aren’t necessarily abandoning one problem to work on another. Sometimes we’re, as the crude saying goes, killing two birds with one stone.

      I’m sincerely hoping that’s the case when it comes to AI.

      • Maia

        I agree we can do both. BUT more resources overall seem to be going toward the more trendy machine-oriented aspects which, like pills for everything, give the illusion that we can have a push-button solution to our problems if we just keep on investing more in more “intelligent” machines. The intelligence of a machine depends on the intelligence of the input from humans. And second, the intelligence of machines is a narrow computational info-based kind of intelligence. It does not include the life-experience and compassion of human intelligence, often called wisdom. THAT’s what we need more of.
        We are trying to “out-source” problem solving and it won’t work.

        • Laren Ganer

          Late response here, but thanks for the respectful reply. I love it when I have a little oasis of polite discourse, and seeing this reply made me smile. When I read it again in my notifications it made me smile again so I thought I’d say so.

          • Maia

            Thanks. I know how you feel.

  • GS Chandy

    I claim that ‘AI’ will actually arrive after (and only a considerable time after) we have begun to understand human intelligence (HI). There are as yet few signs that we’re on the threshold of understanding HI. — GSC

  • Byunggyu Ahn

    There’s a typo in the Go master’s name: it’s Lee Se-dol, not Sodol. Regardless, a good article.

  • Robert Caldwell

    “Who will take care of these children now?” The main character in the novel. “The Postman” by David Brin. Hears the ghost of the AI computer ,Cyclops say. Or at least a quote very similar.

  • Elliander Eldridge

    Just a thought, but what if you made a go board where half the board is symbolically darkened? It’s difficult to identify the exact position of pieces and maybe you can see if there is a large group on the opposite end of the board, but otherwise not at all. Then have it go against itself. Wouldn’t it have to learn the kind of skills required for poker?

  • Porkchopx

    I don’t think that a hard drive full of previously held moves and a simple math program that compares and averages an outcome is intelligence at all. If the program could learn these things on its own and react to them on its own would be much more in line with real heuristics rather than hopeful intelligence.

  • Shalryn

    This article concentrates pretty well on the “Yippee!” factor. Fine, but we need to spend some time on the, “What if” as well.” This advance is good news. Heck, it’s GREAT news! Unfortunately, it’s in the hands of humans, who have a tendency to do very stupid things with very smart advancements. We do need to set some limits on this sort of technology, or at least find ways to harness it in such a way that we can’t damage or kill ourselves (and everything else) with it. We screwed up with something as simple as purple loosestrife. What makes anyone think we’re mature enough to deal safely with AI that is bound to end up smarter than we are?

    • Maia

      Yes, the human track record is enough to endorse a lot of careful thought before deploying any new technologies. Just like with “gee whiz” drugs, there are frequent disasters, and they seem to ignored as soon as the next one comes out.

  • http://www.chicasole.com putas valencia

    Ohh yeah!! Is very nice.

  • AFulgens

    Also, please don’t forget that we are still talking about beating a 2p dan Go champion, that’s lightyears away from 9p dan which is the highest rank. We are talking about 7 handicap stones, which is a huuuuuge advantage.

  • http://www.tohodo.com/ 10basetom

    This is really exciting. I believe AI is one of the core prerequisites for human civilization to progress to the next stage: colonizing space (that is, if we don’t kill ourselves first).

NEW ON DISCOVER
OPEN
CITIZEN SCIENCE
ADVERTISEMENT

The Crux

A collection of bright and big ideas about timely and important science from a community of experts.
ADVERTISEMENT

See More

ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

Collapse bottom bar
+