1002: "Game AIs"

[jjcote]

If there were a non-turn-based "Speed Scrabble", where you can play as fast as you can come up with plays, it would take me about five minutes to program an AI no human player could ever touch.)

Bananagrams. Yeah, a program could make short work of humans.

[Proginoskes]

Othello/Reversi is not solved, although it might be within reach before too long. If there is some powerful new trick or algorithm or optimization discovered that gains a fundamental speedup, it might be doable right now. Otherwise with no such improvements, from what I can find out online, there are still an estimated several orders of magnitude difference between solving Reversi and solving Checkers (maybe somewhere between 10^4 and 10^8).

The people who "solved" checkers said that Othello/Reversi would probably be the next well-known game to be solved by computer.

[atrahasis]

Actually I don't think you should say even now that chess computers are consistently beating the top humans, not as conclusively as one would like to be able to say it at least. The last of these matches was between Vladimir Kramnik and Deep Fritz in 2006, with four draws, and two wins to the computer.

But it appears Kramnik missed a win in the the first game, and in the second game, from a probably winning position, he made probably the biggest blunder ever made by a World Champion, missing checkmate by Deep Fritz on its next move!

Considering the brute processing power of Deep Fritz, and taking into account the mistakes, it doesn't feel like a conclusive loss for humanity, which is astonishing.

You're saying that if a human makes no mistakes at all it can't be beaten?

How incisive.

[meerta]

No.

[Armadillo Al]

Just a quick point of order on the status of "Jeopardy" ...

Ken Jennings, the reigning top human player at Jeopardy, as brilliant and entertaining as he is on a daily basis (@KenJennings), was demolished by Skynet IBM Watson in an epic competition. Jeopardy has been conquered for inhuman-kind.

http://en.wikipedia.org/wiki/Ken_Jennings#IBM_Challenge

While Watson thrashed Ken (and Brad) on the first day of the two-day total points affair, Ken kept the scores close enough on the second day that, had the two been scored separately, Watson would have been required to get Final correct.

Since they had to build a whole separate studio in the IBM facilities to accomodate Watson, the buzzer timing was slightly off from what is usually required, and Ken needed time to adjust to it. Were the match held in Sony's studios, I would suspect the scores would have been close enough that it would be impossible to declare Watson unbeatable (as he clearly was not on the final day of the exhibition match).

The UIUC "Beer Pong" robot can be seen here:

http://www.youtube.com/watch?v=HkhMCCOHFmM

The throwing of the ping pong ball starts at about 00:28.

You see my friend Aaron at 1:48.

I am simultaneously awed, yet not at all surprised that my alma mater was the one to build a beer pong robot.

[lightvector]

Othello/Reversi is not solved, although it might be within reach before too long. If there is some powerful new trick or algorithm or optimization discovered that gains a fundamental speedup, it might be doable right now. Otherwise with no such improvements, from what I can find out online, there are still an estimated several orders of magnitude difference between solving Reversi and solving Checkers (maybe somewhere between 10^4 and 10^8).

The people who "solved" checkers said that Othello/Reversi would probably be the next well-known game to be solved by computer.

Right, if "well-known" includes mostly just the top classic abstract strategy games, then there aren't any well-known (deterministic) abstract strategy games whose complexity lies precisely between that of Checkers and Reversi. Most games are either easier by many orders of magnitude, such as Connect 4, or harder by many orders of magnitude, like Chess.

Reversi's likely the next "major" game to be solved, but that doesn't mean it will be solved tomorrow. There is a slim chance it might, but more likely it will take a while.

[W3ird_N3rd]

I was kind of disappointed The Game wasn't somewhere on the list. Although I have to say, Calvinball is pretty difficult. Still, I spent quite awhile trying to decide where The Game should sit in the chart before I realized I'd lost at least 5 times, and decided to give up on trying to place it.

I was thinking the same thing! Lost too, though.. Randall's forum harddrive/SSD, however, has now lost permanently!

How do AIs fare nowadays at "I spy with my little eye"?

[baf]

Computers have a higher probability of winning against humans in a Snakes and Ladders tournament if there are more computers than humans. And since computers are easier to create than humans...

This has already been disputed several times, but I'd just like to add: No one has ever created a computer accidentally.

[pbacoustic]

"Calvinball" - I love it..............

[mutestorm]

http://www.google.com/trends/?q=calvinball

[marshmallowSDA]

Starcraft and Counter-Strike (SC and CS from here) definitely haven't been solved by AI and games like them probably won't be until there are machines very close to us. You can give a CS bot an aimhack and a wallhack and a can't-get-flashed hack but that's blatant cheating. Comparing these to board games or chess/checkers is a bit of a mistake since with the other games the only thing that matters is the raw output. Moving a pawn a certain way doesn't increase its effectiveness by 12%. SC/CS AI bypass the intended interface of the entire game, the mouse, keyboard, and to a lesser extent the monitor to achieve feats that are physically impossible and usually against the rules anyway and would result in bans if any human emulated them.

CS is also much more complicated game than "hur me shoot you die" and I'm not aware of any effort like with SC to make an AI team that can win in a 5v5 tournament. I would be quite interested in seeing such a thing. There's a money system, feints/fakes and dozens of strategies per map that interact with each other in subtle ways, throwing all the types of grenades in the most effective way, and that tricky teamwork thing. Programming AI how to use grenades on all the different walls from different angles depending on where you want it to go off would be a nightmare. Or trying to make decisions dependent on the intent of the other team.

[Fritzlein]

I would like to send Randall a complimentary copy of my book entitled "Beginning Arimaa". Does he want it? Where do I mail it?

Thanks,
Fritz Juhnke

[boyceaz]

If memory serves, Amanda Donohoe is the reigning human champion of Snakes and Ladders.

[OP Tipping]

Would this be an appropriate place to air my Calvinball related yonkoma?

http://cheezburger.com/Daz_Voz/lolz/View/5718543360

[Glenn Magus Harvey]

I am disappointed that it took until the second page of posts for someone to finally give Randall a penalty card.

That said, I am too lazy to look further; please take penalty cards that are due to you.

*hands people a pile*

And yes, I love the card game named after a certain Chinese dictator. A good friend and I really like to play it in such a way that doesn't encourage hazing but instead encourages all sorts of creative rule-making. The fun in that is to find out how all sorts of new rules--with extra hands, extra discard piles, and extra conditions--interact with each other.

[dcbandicoot]

Since its a game with luck it should be impossible for the computer to get a 100% win rate over. A over 50% win is still surprising to me.

Tournament Scrabble has no probabilistic features* - everyone has exactly the same tiles and makes moves on exactly the same board; only the person who wins each round gets to place 'their' word on the board everyone plays on for the next round.

Domino14: Can you provide a reference? It would be interesting to see whether they played Tournament or not.

* Other than "what tiles come up next turn", of course.

This is only true of Tournament Scrabble in France (afaik). The rules of Tournament Scrabble in the USA (and the rest of, or vast majority of the rest of the world, anyway) are 2-player scrabble against one another. To that end, Quackle also plays the way the World plays, and assumedly this comic refers to that form- otherwise, Tournament Scrabble would be "solved" by Quackle.

The consensus of most Tournament Scrabble plays is that Nigel Richards is a stronger player than Quackle. Quackle has two main flaws. The first is that it routinely rules out superior plays as inferior because what it does is analyze a single spot and rules out players that a worse based on its "superleave" file- that is, it has a rating for every "leave" possible based on how many points you are likely to recoup in the ensuing turns with those tiles on the rack.

Here is a great position to see the concept of "leave"s at work: http://cross-tables.com/annotated.php?u=9979#15

This is based on early and middle-game play. As the game progresses, the computer "sees" more tiles - but doesn't adjust its "leave" valuations to adjust which plays it rules out. At the end of the game, it is often considerably harder to bingo, but there are more scoring hot spots on the board- so higher-point tiles, except the Q sans U/I- very hard to spot on tight boards- become worth much more.

It also fails to change its leave valuations for ruling out plays when the bag is vowel-heavy or consonant-heavy. For example, see here: http://cross-tables.com/annotated.php?u=9979#19

It also has a few pre-endgame flaws which I won't profess to know the specifics of- I've heard many-a-rumor. The point, more or less, is that top players know the whole dictionary and can play with few flaws- and Quackle is not yet at that level, though very close. I'd put it closer to where poker is now.

[OP Tipping]

French Tournament Scrabble is awesome.

[Sophokles]

Surely I'm not the only one who sees Numberwang written all over this? I imagine the AI would blow away the human competition until a Numberscoff round, placing its difficulty near calvinball.

[domino14]

Since its a game with luck it should be impossible for the computer to get a 100% win rate over. A over 50% win is still surprising to me.

Tournament Scrabble has no probabilistic features* - everyone has exactly the same tiles and makes moves on exactly the same board; only the person who wins each round gets to place 'their' word on the board everyone plays on for the next round.

Domino14: Can you provide a reference? It would be interesting to see whether they played Tournament or not.

* Other than "what tiles come up next turn", of course.

You're thinking about "Duplicate" Scrabble, which is only played in France, and is a ridiculous form of the game. In the rest of the world, tournament Scrabble is one-on-one matches. The player who did this is a top 10 player who logged all the games, and played 1-1 with the Quackle AI on "Championship Player" mode. I could play 10 games against it and probably win somewhere between 3 and 5 if you want to see.

[Garrett]

So first of all, since this is my first post here, hello to everyone.

Now to cut to the chase. The topic of AI in non-chance games is very interesting and seeing chess and go put in here I can't help but to be a little disappointed in an omission of shogi in comic strip as well as in this whole topic. Is it that none of you are interested in this game or maybe there is just no metion worthy data on AI taking top players in shogi?

[Proginoskes]

So first of all, since this is my first post here, hello to everyone.

HELLO!!!

Now to cut to the chase. The topic of AI in non-chance games is very interesting and seeing chess and go put in here I can't help but to be a little disappointed in an omission of shogi in comic strip as well as in this whole topic. Is it that none of you are interested in this game or maybe there is just no metion worthy data on AI taking top players in shogi?

Let's see what Wikipedia says:

Shogi has the highest game complexity of all popular chess variants. Therefore, Shogi is the hardest of the popular chess variants in terms of programming the computer to beat the highest rated player. Computers have steadily improved in playing shogi since the 1970s. In 2007, champion Yoshiharu Habu estimated the strength of the 2006 world computer shogi champion Bonanza at the level of 2-dan shoreikai. Tools used by shogi programmers are the GUI Shogidokoro, shogi server Floodgate and the annual computer tournaments. The Japan Shogi Association prohibits professionals from playing computers in public without prior permission. After some 35 years of development, a computer finally beat a professional player on October 12, 2010, when the top ranked female champion Ichiyo Shimizu was beaten by the Akara2010 system in a game lasting just over 6 hours. On July 24, 2011, computer Shogi programs Bonanza and Akara crushed the amateur team of Kosaku and Shinoda in 2 games. The allotted time for the amateurs was 1 hour and then 3 minutes per move. The allotted time for the computer was 25 minutes and then 10 seconds per move. The highest rated player on Shogi Club 24 is computer program Bonkras, rated 3335 on December 2, 2011.

So maybe a program will be able to beat any human at shogi in 10-20 years?

[Garrett]

Dang, I need to read wiki more thoroughly.

So, where should we put shogi on the comic strip? Before or after arimaa (because I guess go is undisputed champion)? Arimaa was specificaly made to be hard for AI. Starting with a pieces pattern of your choice, having four moves per turn and pushing/pulling a piece instead of simply capturing it undoubtedly increases difficulty. But does it compensate for bigger board, more pieces, ability to reuse captured pieces and optional promotion of pieces? I have little doubt that in few years starting patterns that are generally good, no matter the opponent pattern, will appear for arimaa (if there is no now). It is also quite young so there is a lack of high level opening and end game databases. So which one will be harder for AI to learn consistent competitive play?

[Proginoskes]

So, where should we put shogi on the comic strip? Before or after arimaa (because I guess go is undisputed champion)? Arimaa was specificaly made to be hard for AI.

Omar Syed is offering a man-vs-machine challenge, but only until 2020 ... This suggests that it might be as difficult as suspected.

I think shogi should be put after Arimaa, and before Go. Between Arimaa and shogi is a good place for Crazyhouse, if you ignore Starcraft and Poker.

(Crazyhouse is a combination of chess and shogi; rules are as in chess, except captured pieces can be put back on the board in place of a move. "Bughouse" is a 2-board, 4-player version of Crazyhouse, usually played with chess clocks set at 5 minutes.)

[SchighSchagh]

Randall forgot to include

Spoiler:

THE GAME

. Then again, it doesn't really fit in the chart. The only way computers can possibly do worse than humans is to acquire sentience because they obviously can't actually think about it without that. But once the hard problem of sentience is solved, computers will actually do much worse than humans for I suspect it would be as destructive as the "topological anomaly" Picard wanted to infect Hugh with to decimate the Borg.

[Pfhorrest]

Randall forgot to include

Spoiler:

THE GAME

. Then again, it doesn't really fit in the chart. The only way computers can possibly do worse than humans is to acquire sentience because they obviously can't actually think about it without that. But once the hard problem of sentience is solved, computers will actually do much worse than humans for I suspect it would be as destructive as the "topological anomaly" Picard wanted to infect Hugh with to decimate the Borg.

Nonsense.

To continue your use of Star Trek examples, lets imagine Data. He is informed of the rules of the Game. He decides he wants to win. He writes a program which deletes all memory of The Game from his databanks and filters all future references to it from his perceptions.

When you order Data to forget something, he forgets completely and thoroughly. There was even an entire episode which hinged on this ability.

[SchighSchagh]

He decides he wants to win.

You can't win the game. You can only lose.

When you order Data to forget something, he forgets completely and thoroughly. There was even an entire episode which hinged on this ability.

Which episode are you referring to? Surely not "Clues"? He's trying to keep the knowledge away from everybody else, but he certainly doesn't forget or stop thinking about it.

Also, what happens when Data discovers the filtering subroutine you propose? Keep in mind, he is sentient and performs self-diagnostics pretty much every time somebody asks "how are you?". He begins erasing his memory? Then he will only be doomed to discover the subroutine again when he notices inexplicably lost computational cycles during a self-diagnostic! (Again, much like how the crew figures out wtf is going on in "Clues".)

Since you like ST themed arguments, let's not forget the good Voyager doctor! He got himself caught in an ethical catch-22 over his subjective choice to save Tom Paris's life when Voyager was first pulled into the Delta quadrant. The crew tried to wipe all his memory of it and hide the truth from him so he wouldn't get stuck being completely preoccupied by the incident again. The morale is that such schemes can never work because it is impossible to account for every possible way you may ever encounter a certain piece of information again. The possibilities are infinite, so dealing with them, like the hypothesized anti-Borg "spacial anomaly", would become increasingly demanding computationally, leading to an inevitable demise.

[Pfhorrest]

When you order Data to forget something, he forgets completely and thoroughly. There was even an entire episode which hinged on this ability.

Which episode are you referring to? Surely not "Clues"? He's trying to keep the knowledge away from everybody else, but he certainly doesn't forget or stop thinking about it.

You're right there. I was thinking of another episode as well, I can't recall which, where Picard emphasizes to someone else that if he orders Data never to divulge something, then the information is as good as lost. That's not quite the same as forgetting it, though.

Also, what happens when Data discovers the filtering subroutine you propose? Keep in mind, he is sentient and performs self-diagnostics pretty much every time somebody asks "how are you?". He begins erasing his memory? Then he will only be doomed to discover the subroutine again when he notices inexplicably lost computational cycles during a self-diagnostic! (Again, much like how the crew figures out wtf is going on in "Clues".)

He could retain memory of having intentionally created a program to remove and avoid memory of something, without remembering what it is that he has forgotten. Something to the effect of "Note to self: You intentionally erased one of your memories here, and did not wish your future self to investigate the matter further. Signed, --You."

I actually thought a similar solution could be workable in "Clues", although convincing the aliens of that might have been a tricky matter. The humans' memories could have been erased, and afterward Data could have informed the captain that there is a danger in approaching that star system, which poses no threat so long as it is not approached, and the only way to leave alive once approaching causes memory loss, and that he has been ordered by the captain not to divulge further details, with some authorization code from the captain for proof.

[Eternal Density]

Now that I know what it is, I see no difficulty for an AI to win at Mornington Crescent, it just wouldn't be any fun.

[RaceBandit]

I was thinking the same thing! Lost too, though.. Randall's forum harddrive/SSD, however, has now lost permanently!

This is why I now think Munroe missed the perfect opportunity to troll us all by putting "twenty dollars and my self-respect" below even Calvinball. Then again, even humans can't win unless they never know about this, so unless win rates are factored in, we could only outperform the AI by thinking about this as rarely as possible.

Using code such as this chat filter might help us, since people who don't know about this won't get the joke and therefore lose unintentionally.

[oldbushie]

Bit late, but relevant: http://www.aerobushentertainment.com/index.php?cat=games&id=2

I made Mao in Java for my Advanced AI final project a few years back. Just thought I'd mention it since I was catching up on XKCD.

[tckthomas]

So, where should we put shogi on the comic strip? Before or after arimaa (because I guess go is undisputed champion)? Arimaa was specificaly made to be hard for AI.

Omar Syed is offering a man-vs-machine challenge, but only until 2020 ... This suggests that it might be as difficult as suspected.

I think shogi should be put after Arimaa, and before Go. Between Arimaa and shogi is a good place for Crazyhouse, if you ignore Starcraft and Poker.

(Crazyhouse is a combination of chess and shogi; rules are as in chess, except captured pieces can be put back on the board in place of a move. "Bughouse" is a 2-board, 4-player version of Crazyhouse, usually played with chess clocks set at 5 minutes.)

This Arimaa player cannot disagree more. Omar placed that limit because he wants to have software beat humans, not just the hardware getting better and better. I agree that Shogi can be placed after Arimaa though. So far the top players are still able to beat computers easily, as they have a weak grasp on the strategy of Arimaa, which is very important, and also because of the large branching factor (roughly 13k unique moves). I think computers still have a long way to go.

[Marian]

First thing I thought of was Rock, Paper, Scissors.

Can't post a url, but worth a google, it looks like computers have humans beaten on this one.

Not sure that counts because they cheat:

http://www.k2.t.u-tokyo.ac.jp/fusion/Janken/index-e.html

[Kaiman]

While Watson thrashed Ken (and Brad) on the first day of the two-day total points affair, Ken kept the scores close enough on the second day that, had the two been scored separately, Watson would have been required to get Final correct.

Since they had to build a whole separate studio in the IBM facilities to accomodate Watson, the buzzer timing was slightly off from what is usually required, and Ken needed time to adjust to it. Were the match held in Sony's studios, I would suspect the scores would have been close enough that it would be impossible to declare Watson unbeatable (as he clearly was not on the final day of the exhibition match).

There is honestly no way to fairly test things out in Jeopardy, as there is no way to balance the buzzer-pressing issue even if we manage to solve the differing means of inputting the question to the human & computer contestants. Let's theoretically say we created a computer that is the exact duplicate of Ken's knowledge - he knows exactly what Ken knows and no more, receives the information through audio processing and parases the language with the exact same command of English that Ken has, and takes the exact amount of time to locate said information as Ken does to process his thoughts and come up with a conclusion. Ken would never score a point. Every single time they both knew the answer, the computer would buzz in sooner.

A good friend and I really like to play it in such a way that doesn't encourage hazing but instead encourages all sorts of creative rule-making. The fun in that is to find out how all sorts of new rules--with extra hands, extra discard piles, and extra conditions--interact with each other.

Then you are the only people in the world who don't play it just to feel smugly superior about how the other people don't know things that haven't been communicated to them.

You're saying that if a human makes no mistakes at all it can't be beaten?

That is still up for debate. And it's not really provable because one cannot always know for a certain if a reasonable-looking move is a mistake or not.

There was a Star Trek episode (Peak Performance) that addressed this concept as well, for what it's worth.

Not sure about all of you guys, but my greatest hope is to see the day when a computer program can consistently beat the greatest humans at go (kind of like chess, currently). That is truly the day that AI will have been perfected.

On that day, there will still be a large number of strategy games that computers won't be able to win at. Go is relatively simple compared to some of the more niche hobby games out there.