1002: Game AIs

Explain xkcd: It's 'cause you're dumb.
Revision as of 18:07, 22 November 2012 by Waldir (talk | contribs) (Rename Category:Comics with charts to Category:Charts for consistency with other "comics by topic" categories)
Jump to: navigation, search
Game AIs
The top computer champion at Seven Minutes in Heaven is a Honda-built Realdoll, but to date it has been unable to outperform the human Seven Minutes in Heaven champion, Ken Jennings.
Title text: The top computer champion at Seven Minutes in Heaven is a Honda-built Realdoll, but to date it has been unable to outperform the human Seven Minutes in Heaven champion, Ken Jennings.


To understand the comic, you have to understand what the games are, so let's go (but first, the years in parenthesis in the comic are the year that the game was mastered by a computer):

  • Tic-Tac-Toe - (via wikipedia) Tic-tac-toe, also called noughts and crosses (in the UK, Australia, New Zealand, South Africa, India and the rest of the British Commonwealth countries), is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid.
  • Nim - (via wikipedia) a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.
  • Ghosts - (via wikipedia and Board Game Geek) a spoken word game in which players take turns adding letters to a growing word fragment, trying not to be the one to complete a valid word.
  • Connect Four - (via wikipedia) (also known as Captain's Mistress, Four Up, Plot Four, Find Four, Fourplay, Four in a Row and Four in a Line) is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid.
  • Gomoku - (via wikipedia) an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces (black and white stones) on a go board (19x19 intersections); however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game. This game is known in several countries under different names.
Black plays first, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.
  • Scrabble - (via wikipedia) a word game in which two to four players score points by forming words from individual lettered tiles on a gameboard marked with a 15-by-15 grid.
  • Beer pong - (via wikipedia) also known as Beirut, is a drinking game in which players throw a ping pong ball across a table with the intent of landing the ball in a cup of beer on the other end.
Here's the video of the University of Illinois robot mentioned in the comic.
  • Reversi - (via wikipedia) (also marketed by Pressman under the trade name Othello) is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player. The player's goal is to have a majority of their colored pieces showing at the end of the game, turning over as many of their opponent's pieces as possible.
  • Chess - (via wikipedia) Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. Each player begins the game with sixteen pieces: one king, one queen, two rooks, two knights, two bishops, and eight pawns, each of these types of pieces moving differently.
  • Jeopardy! - (via wikipedia) an American quiz show featuring trivia in history, literature, the arts, pop culture, science, sports, geography, wordplay, and more. The show has a unique answer-and-question format in which contestants are presented with clues in the form of answers, and must phrase their responses in question form.
Ken Jennings, mentioned in the title text is a famous Jeopardy champion.
  • Starcraft - (via wikipedia) a military science fiction real-time strategy video game... the game revolves around three species fighting for dominance in a distant part of the Milky Way galaxy known as the Koprulu Sector: the Terrans, humans exiled from Earth skilled at adapting to any situation; the Zerg, a race of insectoid aliens in pursuit of genetic perfection, obsessed with assimilating other races; and the Protoss, a humanoid species with advanced technology and psionic abilities, attempting to preserve their civilization and strict philosophical way of living from the Zerg.
  • Poker - (via wikipedia) a family of card games involving betting and individualistic play whereby the winner is determined by the ranks and combinations of their cards, some of which remain hidden until the end of the game.
  • Arimaa - (via wikipedia) a two-player abstract strategy board game that can be played using the same equipment as chess. Arimaa was designed to be more difficult for artificial intelligences to play than chess. Arimaa was invented by Omar Syed, an Indian American computer engineer trained in artificial intelligence. Syed was inspired by Garry Kasparov's defeat at the hands of the chess computer Deep Blue to design a new game which could be played with a standard chess set, would be difficult for computers to play well, but would have rules simple enough for his then four-year-old son Aamir to understand.
  • Go - (via wikipedia) an ancient board game for two players that originated in China more than 2,000 years ago. The game is noted for being rich in strategy despite its relatively simple rules. The game is played by two players who alternately place black and white stones on the vacant intersections (called "points") of a grid of 19×19 lines (beginners often play on smaller 9×9 and 13×13 boards). The object of the game is to use one's stones to surround a larger portion of the board than the opponent.
  • Snakes and Ladders - (via wikipedia) (or Chutes and Ladders) an ancient Indian board game regarded today as a worldwide classic. It is played between two or more players on a gameboard having numbered, gridded squares. A number of "ladders" and "snakes" (or "chutes") are pictured on the board, each connecting two specific board squares. The object of the game is to navigate one's game piece from the start (bottom square) to the finish (top square), helped or hindered by ladders and snakes, respectively. As a simple race game, this game occupies a limbo in which none of the categories in the chart are appropriate, but its placement at the border between "Computers still lose to top humans (but focused R&D could change this)" and "Computers may never outplay humans" provides insight regarding its state of computer-versus-human mastery.
  • Mao - (via wikipedia) (or Mau) a card game of the Shedding family, in which the aim is to get rid of all of the cards in hand without breaking certain unspoken rules. The game is from a subset of the Stops family, and is similar in structure to the card game Uno or Crazy Eights.
The game forbids its players from explaining the rules, and new players are often told only "the only rule you may be told is this one." The ultimate goal of the game is to be the first player to get rid of all the cards in their hand.
  • Seven Minutes in Heaven - (via wikipedia) a teenagers' party game first recorded as being played in Cincinnati in the early 1950s. Two people are selected to go into a closet or other dark enclosed space and do whatever they like for seven minutes. Sexual activities are allowed; however kissing and making out are more common.

And finally

Calvinball is a game played by Calvin and Hobbes as a rebellion against organized team sports; according to Hobbes, "No sport is less organized than Calvinball!" Calvinball was first introduced to the readers at the end of a 1990 storyline involving Calvin reluctantly joining recess baseball. It quickly became a staple of the comic afterwards.
The only hint at the true creation of the game ironically comes from the last Calvinball strip, in which a game of football quickly devolves into a game of Calvinball. Calvin remarks that "sooner or later, all our games turn into Calvinball," suggesting a similar scenario that directly led to the creation of the sport. Calvin and Hobbes usually play by themselves, although in one storyline Rosalyn (Calvin's baby-sitter) plays in return for Calvin doing his homework, and plays very well once she realizes that the rules are made up on the spot.
The only consistent rule states that Calvinball may never be played with the same rules twice. Scoring is also arbitrary, with Hobbes at times reporting scores of "Q to 12" and "oogy to boogy." The only recognizable sports Calvinball resembles are the ones it emulates (i.e., a cross between croquet, polo, badminton, capture the flag, and volleyball.)


Difficulty of Various Games for Computers

[A diagram. The left column describes various levels of skill for the most capable computers in decreasing performance against humans. The right side lists games in each particular section, in increasing game difficulty. There are labels denoting the hard and easy ends of the diagram.]


Solved - Computers can play perfectly Solved for all possible positions Tic-Tac-Toe
Connect Four(1995)
Solved for starting positions Gomoku
Computers can beat top humans Scrabble
Beer Pong (UIUC robot)
  • February 10, 1996 - First win by computer against top human
  • November 21, 2005 - Last win by human against top computer
Computers still lose to top humans

(but focused R&D could change this)

Computers may never outplay humans Snakes and Ladders
Seven Minutes in Heaven


comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!


Mornington Crescent would be impossible for a computer to play, let alone win... -- (talk) (please sign your comments with ~~~~) It is unclear which side of the line jeopard fall upon. Why so close to the line I wonder. DruidDriver (talk) 01:04, 16 January 2013 (UTC)

Because of Watson (computer). (Anon) 13 August 2013 (talk) (please sign your comments with ~~~~)

Could the "CounterStrike" be referring instead to the computer game which can have computer-controlled players? -- 15:49, 29 April 2013 (UTC)

I agree, this is far more likely. 10:21, 11 September 2013 (UTC)

On the old blog version of this article, a comment mentioned Ken tweeting his method right after this comic was posted. He joked that they would asphyxiate themselves to actually see heaven for seven minutes. I don't know how to search for tweets, or if they even save them after so much time, but I thought it should be noted. 07:11, 27 October 2014 (UTC)

I disagree about the poker part. Reading someone's physical tells is just a small part of the game. Theoretically there is a Nash equilibrium for the game, the reason why it hasn't been found is that the amount of ways a deck can be shuffled is astronomical (even if you just count the cards that you use) and you also have to take into account the various betsizes. A near perfect solution for 2 player limit poker has been found by the Cepheus Poker Project: http://poker.srv.ualberta.ca/.

~ Could the description of tic-tac-toe link to xkcd 832 which explains the strategy? 13:13, 27 January 2016 (UTC)

Saying that computers are very close to beating top humans as of January 2016 is misleading at best. There is not enough details in the BBC article, but it sounds like the Facebook program has about a 50% chance of beating 5-dan amateurs. In other words, it needs a 4-stone handicap (read: 4 free moves) to have a 50% chance to win against top-level amateurs, to say nothing about professionals. If a robotic team could have a 50% chance to beating Duke University at football (a skilled amateur team), would you say they were very close to being able to consistently beat the Patriots (a top-level professional)? If anything that underestimates the skill difference in Go, but the general point stands. (talk) (please sign your comments with ~~~~)

How about bearing one of the top players five times in a row and being scheduled to play against the world champion in March? http://www.engadget.com/2016/01/27/google-s-ai-is-the-first-to-defeat-a-go-champion/ Mikemk (talk) 06:18, 28 January 2016 (UTC)
However DeepMind ranked AlphaGo close to Fan Hui 2P and the distributed version has being at the upper tier of Fan's level. http://www.nature.com/nature/journal/v529/n7587/fig_tab/nature16961_F4.html
The official games were 5-0 however the unofficial were 3-2. Averaging to 8-2 in favor of AlphaGo.
Looking at http://www.goratings.org/ Fan Hui is ranked 631, while Lee Sedol 9P, whom is playing in March, is in the top 06:12 5 February 2016 (UTC)
Original poster here (sorry, not sure how to sign). Okay, you all are right. Go AI has advanced a lot more than I had understood. I'm still curious how the game against Lee Sedol will go, but that that is even an interesting question shows how much Go AI has improved. (talk) (please sign your comments with ~~~~)

Google's Alpha Go won, 3 games to none! Mid March 2016Saspic45 (talk) 03:06, 14 March 2016 (UTC)

Okay, for some reason they played all five games. Lee Sedol won game 4 as the computer triumphed 4-1.Saspic45 (talk) 08:44, 17 March 2016 (UTC)

Not shown in this comic: 1000 Blank White Cards, and, even further down, Nomic. KangaroOS 01:22, 19 May 2016 (UTC)

Is the transcript (currently in table format) accessible for blind users? Should it be? 10:48, 19 February 2017 (UTC)

At the very least the transcript needs to be fixed so that it factually represents the comic. Jeopardy is in the wrong spot with just a quick glance which is all I have time for here at work. 16:58, 24 August 2017 (UTC)