Artificial intelligence challenges to the human once again

Twenty years ago, a chess-playing computer called Deep Blue, developed by IBM, challenged to russian World Chess Champion, Garry Kasparov. The match took place in Philadelphia, and Kasparov managed to defeat his AI opponent by 4-2. Although Deep Blue lost the match, it recorded the first victory of computer against human world champion. A year later, Deep Blue rechallenged to Kasparov, and the match took place in New York City. In the end, the computer finally defeated its human opponent by 3½-2½. The final game only took 17 moves, and computer showed intriguing movement from that match; sacrificing its knight to block Kasparov's castling.

Tomorrow, an artificial intelligent called AlphaGo, developed by Google DeepMind, will challenge Go(also known as Baduk) match against Lee Sedol, one of the greatest korean Go players. The match will take place in Seoul, and you can watch live stream of that match on Youtube. If you're interested in Go, or "Man vs. Machine" match, then you definitely should check this out.

I haven't played go in ages, but this should be interesting. If I'm not mistaken, go players are generally discouraged to play such matches.

EDIT

Sorry, I forgot to add, it seems also that computers aren't that good at go, as it seems it's a more complex game than chess.

Zed said:

I haven't played go in ages, but this should be interesting. If I'm not mistaken, go players are generally discouraged to play such matches.

EDIT

Sorry, I forgot to add, it seems also that computers aren't that good at go, as it seems it's a more complex game than chess.

AlphaGo is something different. It's the first computer to defeat a professional human Go player without handicaps. Last year, it defeated the European Go champion Fan Hui by 5-0. The Elo rating of AlphaGo is considered as 3140, while Lee Sedol's current Elo rating is 3532.

Since Go has simpler rules and more combinations, shouldn't the computer algos for Go be more powerful than chess algos?

VGA said:

Since Go has simpler rules and more combinations, shouldn't the computer algos for Go be more powerful than chess algos?

Mmmhh, now that you mention it, maybe my memory is failing me and I was thinking about shogi.

EDIT: Nope, it seems go is also harder than chess for an AI:

https://en.wikipedia.org/wiki/Computer_Go#Performance

VGA said:

Since Go has simpler rules and more combinations, shouldn't the computer algos for Go be more powerful than chess algos?

Even chess have "too many combinations" that computers can't rely exclusively on the strategy of "computing every combination of moves and picking the best winning ones for itself", because such computation would take too long time (and if it was managable, computers would never lose when playing as a particular one of the colors, which doesn't apply in reality, as far as I know). Go has a much larger playable area than chess and the rules include both adding and removing pieces from the board in very variable extents, which makes the "number of all combinations" way too high to even consider.

The interesting thing about Go is that the best players in the world got that good by learning what a strong position looks like. They can't even begin to predict what their opponent will do, and so their goal is to just make the board as visually appealing as possible. And that's where the challenge lies with Go A.I. Traditional approaches to A.I. are useless because the program could evaluate a billion different moves, only be able to see a couple of moves ahead, and have absolutely no way of knowing which of those moves eventually lead to success.

The current strategy with Go A.I. is to try to get the computer to develop its own aesthetic preferences based on trial and error. It's like trying to teach a computer to be a superficial, judgmental asshole, and who knows, the inroads from Go A.I. might lead to computers scouring Facebook to find the next generation of cheerleaders and supermodels.

After Go, they should make a computer challenge the Magic: the Gathering champion.

The first round was finished a few minutes ago, and the AlphaGo took the first victory. I'm honestly surprised. We still have 4 more games to go, though.

By defeating its opponent three times in a row, AlphaGo assured its victory in the Go match against the human professional(9-Dan) for the first time in history. Lee Sedol couldn't get a single victory against his AI opponent, and every people in Korea are shocked about this unexpected result. Yet, although it's certain that he lose the match, we have two more games to answer the new question: Can a human defeat the Google Deepmind artificial intelligent in Go?

This is by far more significant for our future as it seems. I am not sure if it is positive or negative, presumably only time will tell. Btw todays match was awesome and I (and a lot of experts) highly doupt any human has a small chance against alphago.

Real life prevented me from seeing the matches, but from the comments I saw on the first two matches, it was pretty obvious this was going to be the result (and I'm willing to bet Lee is gonna loose the next two as well).

So, I guess that's it.

Next step, shogi.

termrork said:

......I (and a lot of experts) highly doubt any human has a small chance against alphago.

Today, Lee Sedol finally scored his first victory against his AI adversary. His move 78 from that game was just brilliant, making AlphaGo to make mistakes continuously.

This is really interesting stuff! This is somewhat on-topic, so I figured I'd share for those of you who may not have read it: http://observer.com/2015/08/stephen-hawking-elon-musk-and-bill-gates-warn-about-artificial-intelligence/

antares031 said:

Today, Lee Sedol finally scored his first victory against his AI adversary. His move 78 from that game was just brilliant, making AlphaGo to make mistakes continuously.

I don't understand go beyond the basics, so I can't judge, but does that mean he did something cheeky with which the "taught" or "inferred" algorithms couldn't deal? Maybe playing untraditionally from the start would give him the edge... for now?

Zed said:

I'm willing to bet Lee is gonna loose the next two as well

antares031 said:

Today, Lee Sedol finally scored his first victory against his AI adversary.

This is why I shouldn't speak too early.

dew said:

I don't understand go beyond the basics, so I can't judge, but does that mean he did something cheeky with which the "taught" or "inferred" algorithms couldn't deal? Maybe playing untraditionally from the start would give him the edge... for now?

The commentator said he played quirky moves in the first game and it didn't work out.

dew said:

...but does that mean he did something cheeky with which the "taught" or "inferred" algorithms couldn't deal? Maybe playing untraditionally from the start would give him the edge... for now?

I believe Michael Redmond (9-dan professional) will explain about move 78 way better than me. Not only Lee Sedol striked one of the weakest points of black, but also, for some reason, AlphaGo started to play bad or unusual moves, such as 79, 87, 97, and even 101.

antares031 said:

I believe Michael Redmond (9-dan professional) will explain about move 78 way better than me.

Wtf, did these guys memorize every move in these games?

Good go players just can remember their recent games almost perfectly. I don't know how they do that, but someone told me that this skill develops automatically with the playing skill itself. It's quite fascinating I think.

Good chess players can hold the entire state of the chess board in their head, so it's not so surprising.

...or 46 boards:

Lang set the world record a year later in November 2011 once again in Sontheim by playing 46 opponents simultaneously and blindfolded, with 25 wins, 19 draws and just 2 losses.

^ What was the goal of that "world record"? If it was to win as many games as possible, it would be odd, as it depends on the opponent's skill AND willingness to even try to win at all more than the tested person's skill. If the tested person was forbidden to attempt to make illegal moves and even if the whole record attempt would be over for him in case he made a single one, the opponents would still greatly influence his success by making him play either long or short games.

I assume that the goal was to have a good time. :) You probably don't need to analyze it so strictly.

VGA said:

Since Go has simpler rules and more combinations, shouldn't the computer algos for Go be more powerful than chess algos?

The actual number of moves needed in order to think ahead in chess is in the tens of millions. So it's not a big feat for a supercomputer do calculate that. But for go, you'd have to think ahead by so many moves that it actually far exceeds the number of particles in the universe by many orders of magnitude. So instead of doing raw number crunching, the supercomputer plays against itself until it begins to learn pathways that lead to success. This type of thinking is much closer to what humans do--trial and error--than what has been achieved in the past. It's a really important milestone for AI research because it demonstrates a profound ability for a computer to learn and adapt.

GoatLord said:

The actual number of moves needed in order to think ahead in chess is in the tens of millions. So it's not a big feat for a supercomputer do calculate that.

No, the "actual number of moves needed to think ahead" would be much higher than that, and chess actually hasn't been solved yet - in other words, "perfect play" is not yet known even to the best computers.

VGA said:

Since Go has simpler rules and more combinations, shouldn't the computer algos for Go be more powerful than chess algos?

Disclaimer that I don't know much about Go, but:

Computer players traditionally work by calculating several possible moves ahead, assessing the state of the board after those moves, and choosing which one looks the best.

In the case of Chess, the possible moves are determined by the pieces on the board. For example, a pawn has up to four possible moves (move ahead 1 or 2 squares, or take diagonally in either direction), a rook has up to 14 possible moves (7 squares either vertically or horizontally), etc.

In the case of Go, the possible moves are instead determined by the spaces on the board (since you lay down pieces rather than moving them). That's an order of magnitude more possibilities, and from AndrewB's description it sounds like it's also far harder to algorithmically describe what constitutes a "strong position" once you've calculated them.

Basically if you want to look n moves ahead, the number of computations required is O(x^n) in either case, but x is much higher for Go than it is for Chess; x is a function of the board size rather than the number of pieces.

BTW, interesting comment I read a few days ago about how computer chess has developed over time. It's a complicated subject, and it seems that chess masters have still been recently (ie. in the past decade) been finding flaws that they can exploit in the algorithms. The Hikaru Nakamura game is quite funny.

Next target: Starcraft. I see a lot of cheesing in their future, heh.

fraggle said:

In the case of Go, the possible moves are instead determined by the spaces on the board (since you lay down pieces rather than moving them). That's an order of magnitude more possibilities, and from AndrewB's description it sounds like it's also far harder to algorithmically describe what constitutes a "strong position" once you've calculated them.

Yes, Go is a lot more complicated to brute-force than chess.

In fact there's a Wikipedia page on the topic:
https://en.wikipedia.org/wiki/Go_and_mathematics

I'll just quote this:

The exact number of legal 19x19 positions was computed by Tromp and others in early 2016 as 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935.

And that's just the number of legal positions, which only represent 1.196% of possible positions on a board this size.

I've added spaces as thousands separators because the unbroken number broke the forum.

I figured Go was more brutal than Chess. This Thread inspired me to research the game and I felt intimidated just watching the early moves. It feels like there are countless possibilities that can be rather overwhelming.