Two weeks ago, a Canadian team of computer scientists announced in a paper that they had created a computer program that has solved the game of checkers (BBC). It took nearly 20 years and 50 computers to sort through the approximately 500 billion billion different checkers positions necessary to solve the game, making it the most complicated game that computers have completely figured out. (It should be noted that a "solved" game often means that the program can never lose—a perfectly-played opposing match would lead to a draw). Which raises the question: Are there any games left that humans can still win?

Connect Four: The BBC article asserts that checkers is one million times more complicated than Connect Four. It's no surprise, then, that the disc-dropping game was solved in the relative Stone Ages of computers; in 1987, programmers James Allen and Victor Allis separately created programs solving the system.

Sudoku: Due to the finite nature of the 9x9 grid and the basic rule structure, the game is rather simple to solve. It can be solved by "backtracking" (in layman's terms, using particular properties of the game to eliminate solutions without having to thoroughly examine each one) or by "brute-force searching," which goes through the millions or billions of moves in a game and systematically checks them out until a procedure has been developed to solve the game (Wikipedia).

Othello: Othello computer programs can easily beat the strongest human players. With "only" 1,028 possible positions—distinct arrangements of pieces on the board—the eight-by-eight piece-flipping game may be the next game to be mathematically solved, according to Jonathan Schaeffer, the researcher at the University of Alberta who oversaw the checkers study (Scientific American).

Backgammon: Games like checkers and chess (see below) benefit most from brute-force searching. IBM programmer Gerald Tesauro's TD-Gammon, on the other hand, uses a neural network that lets the program learn the game by simply playing it over and over against itself. This strategy is not quite as effective for deterministic games like Go and chess that have no element of chance. Because the game has 10¹⁸ possible positions, scientists don't expect to actually solve backgammon anytime soon. The best backgammon programs, though, rank among the top 20 players across the globe.

Chess: We know from Deep Blue's well-publicized victory over chess champion Garry Kasparov in 1997 that computers are quite capable of beating humans. However, solving the game is a different question entirely: According to the BBC article, chess has "somewhere in the range" of 10⁴⁰ positions (InWap). It would take literally eons for our modern-day computers to solve it. "Checkers has roughly the square root of the number of positions in chess," the researchers from the checkers study tell the Associated Press. "Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology."

Scrabble: The best-known (and best) AI player is Brian Sheppard's Maven, first created in 1983 and regularly updated since then. Sheppard improved the program by repeatedly running it through simulations to maximize its point totals. He says that Maven beats humans 60 percent of the time and occasionally outperforms champion Scrabble players.
AI Scrabble has two distinct phases—the first phase starts at the beginning and ends when the last tile from the letter-bag is dished out. At this point, a computer program knows precisely what letters it has open and can act accordingly.

Crossword puzzles: In 1999, a programming team led by Duke University's Michael Littman designed "Proverb," a crossword solving program that is over 95 percent accurate, with each individual crossword puzzle completed in less than 15 minutes. The project was a direct response to comments made by New York Times crossword puzzle editor Will Shortz that computers could never compete with humans. Doctoral student Greg Keim, who worked with Littman on the program, agreed that many crossword hints involving puns and wordplay are too tricky for computers to handle. Nevertheless, the computer scientists were optimistic after finding that the program would have placed 147th in a field of 254 at the 1999 American Crossword Puzzle Tournament (Durham Herald-Sun).
Whereas the process humans use for crosswords is very back-and-forth—looking at clues, writing in potential answers, comparing information on the grid—Proverb compiles an extensive list of the best solutions to all the vertical and horizontal clues and then goes about determining the best grid combinations by trial and error. The program has a working knowledge of 400,000 crossword clues.

Go: Go is perhaps the largest and most complex game that humans have tried to solve, with a 19x19 board that results in a whopping 10,170 possible positions (InWap). Whereas an average chess position allows for 15 to 25 moves, Go positions allow approximately 250 moves. While the strongest Go computer programs are competitive with champion Go players on modified nine-by-nine boards, the complexity of the regulation boards is such that the programs can be beaten easily by even moderately intelligent children (AI Horizons).

Related in Gelf: A champion backgammon player told Gelf how he's trying to use the neural networking system behind TD-Gammon to revolutionize the statistically-backwards NFL.

Related on the Web: Schaeffer, the same man that helped solve checkers, also created a computer program to face off against two professional poker players (New York Times). While the bot system exhibited little in the way of tells, it eventually lost to the humans.