Chinook, the unbeatable checkers-playing computer

Computer scientists have solved the game of checkers, showing that if two players play perfectly, the game will result in a draw. No human can beat their machine.

Topics: Artificial Intelligence,

Scientists at the University of Alberta report that they’ve built an unbeatable checkers-playing computer. Their machine, Chinook, has solved checkers: It proves that if two players play perfectly, making no mistakes, the game of checkers will result in a draw.

The proof required analyzing 500 billion billion checkers positions — 5 x 1020 — a computational process that began in 1989 and has been running on hundreds of processors almost continuously since. Chinook now knows everything about checkers, the perfect response to any move, and the best that any human can do is drive Chinook to a draw. You can never win.

Checkers grandmasters have long suspected that perfect play would result in a draw, but until now, there has been no definitive proof. The first checkers-playing computer was created in 1963 by the artificial intelligence pioneer Arthur Samuel; the computer managed to win a single game against a human.

In 1989, Jonathan Schaeffer, who now heads the computer science department at Alberta, created Chinook with the aim of marshaling parallel processing and lots of storage to take on the world’s best players. In 1990, Chinook became good enough to enter the checkers World Championships, and in 1992, it faced off against the world champion — and the best checkers player who ever lived — Marion Tinsley. Tinsley narrowly defeated Chinook. Then, in 1994, the pair had a rematch, but Tinsley took ill and withdrew in the middle of the game. He died of pancreatic cancer a short while later.

“The unfinished Tinsley match left the question unanswered as to who was the better player,” Schaeffer and his colleagues write in this week’s issue of the journal Science, where their paper is published. But now the answer is clear: “As great as Tinsley was, he occasionally made losing oversights — he was human after all,” they say. Chinook will not make mistakes, and thus becomes the greatest checkers player of all time.

The research makes checkers “the most challenging popular game to be solved to date, roughly one million times more complex that Connect Four,” which was solved in 1989 (if two players play Connect Four perfectly, the first player will always either win or draw).



Their work also highlights the utility of raw computing power in intense artificial intelligence applications. In the early days of A.I. research, Schaeffer and his colleagues note, scientists often tried to make computers mimic human thought. But this approach led to difficulties, and they found that “human-like strategies are not necessarily the best computational strategies.”

A better method for solving complex tasks like checkers, A.I. theorists discovered, was “brute force” — rather than trying to master human strategies, computers would rely on “limited knowledge” of the specifics of the game, and instead use superior processing power to search and analyze all possible moves. That’s the approach taken by chess-playing computers — such as IBM’s Deep Blue, which beat champion Gary Kasparov in 1997 — and it’s also what Chinook does with checkers.

That their machine managed to solve the game, the researchers say, “provides compelling evidence of the power of limited-knowledge approaches to artificial intelligence.” This method will become even more powerful as computers themselves get faster and cheaper, they note. But solving games as complex as chess is still far off.

“Checkers has roughly the square root of the number of positions in chess (somewhere in the 1040-1050 range),” they write. “Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology.” But disk-flipping game othello — solving that is possible, they say. The effort “will require considerably more resources than were needed to solve checkers,” but soon we’ll have an unbeatable othello-playing machine, too.

You can play against Chinook here.

Featured Slide Shows

  • Share on Twitter
  • Share on Facebook
  • 1 of 7
  • Close
  • Fullscreen
  • Thumbnails
    AP/Jae C. Hong

    Your summer in extreme weather

    California drought

    Since May, California has faced a historic drought, resulting in the loss of 63 trillion gallons of water. 95.4 percent of the state is now experiencing "severe" drought conditions, which is only a marginal improvement from 97.5 percent last week.

    A recent study published in the journal Science found that the Earth has actually risen about 0.16 inches in the past 18 months because of the extreme loss of groundwater. The drought is particularly devastating for California's enormous agriculture industry and will cost the state $2.2 billion this year, cutting over 17,000 jobs in the process.

       

    Meteorologists blame the drought on a large zone (almost 4 miles high and 2,000 miles long) of high pressure in the atmosphere off the West Coast which blocks Pacific winter storms from reaching land. High pressure zones come and go, but this one has been stationary since December 2012.

    Darin Epperly

    Your summer in extreme weather

    Great Plains tornadoes

    From June 16-18 this year, the Midwest was slammed by a series of four tornadoes, all ranking as category EF4--meaning the winds reached up to 200 miles per hour. An unlucky town called Pilger in Nebraska was hit especially hard, suffering through twin tornadoes, an extreme event that may only occur every few decades. The two that swept through the town killed two people, injured 16 and demolished as many as 50 homes.   

    "It was terribly wide," local resident Marianne Pesotta said to CNN affiliate KETV-TV. "I drove east [to escape]. I could see how bad it was. I had to get out of there."   

    But atmospheric scientist Jeff Weber cautions against connecting these events with climate change. "This is not a climate signal," he said in an interview with NBC News. "This is a meteorological signal."

    AP/Detroit News, David Coates

    Your summer in extreme weather

    Michigan flooding

    On Aug. 11, Detroit's wettest day in 89 years -- with rainfall at 4.57 inches -- resulted in the flooding of at least five major freeways, leading to three deaths, more than 1,000 cars being abandoned on the road and thousands of ruined basements. Gov. Rick Snyder declared it a disaster. It took officials two full days to clear the roads. Weeks later, FEMA is finally set to begin assessing damage.   

    Heavy rainfall events are becoming more and more common, and some scientists have attributed the trend to climate change, since the atmosphere can hold more moisture at higher temperatures. Mashable's Andrew Freedman wrote on the increasing incidence of this type of weather: "This means that storms, from localized thunderstorms to massive hurricanes, have more energy to work with, and are able to wring out greater amounts of rain or snow in heavy bursts. In general, more precipitation is now coming in shorter, heavier bursts compared to a few decades ago, and this is putting strain on urban infrastructure such as sewer systems that are unable to handle such sudden influxes of water."

    AP/The Fresno Bee, Eric Paul Zamora

    Your summer in extreme weather

    Yosemite wildfires

    An extreme wildfire burning near Yosemite National Park forced authorities to evacuate 13,000 nearby residents, while the Madera County sheriff declared a local emergency. The summer has been marked by several wildfires due to California's extreme drought, which causes vegetation to become perfect kindling.   

    Surprisingly, however, firefighters have done an admirable job containing the blazes. According to the L.A. Times, firefighters with the state's Department of Forestry and Fire Protection have fought over 4,000 fires so far in 2014 -- an increase of over 500 fires from the same time in 2013.

    Reuters/Eugene Tanner

    Your summer in extreme weather

    Hawaii hurricanes

    Hurricane Iselle was set to be the first hurricane to make landfall in Hawaii in 22 years. It was downgraded to a tropical storm and didn't end up being nearly as disastrous as it could have been, but it still managed to essentially shut down the entire state for a day, as businesses and residents hunkered down in preparation, with many boarding up their windows to guard against strong gusts. The storm resulted in downed trees, 21,000 people out of power and a number of damaged homes.

    Debbie Arita, a local from the Big Island described her experience: "We could hear the wind howling through the doors. The light poles in the parking lot were bobbing up and down with all the wind and rain."

    Reuters/NASA

    Your summer in extreme weather

    Florida red tide

    A major red tide bloom can reach more than 100 miles along the coast and around 30 miles offshore. Although you can't really see it in the above photo, the effects are devastating for wildlife. This summer, Florida was hit by an enormous, lingering red tide, also known as a harmful algae bloom (HAB), which occurs when algae grow out of control. HABs are toxic to fish, crabs, octopuses and other sea creatures, and this one resulted in the death of thousands of fish. When the HAB gets close enough to shore, it can also have an effect on air quality, making it harder for people to breathe.   

    The HAB is currently closest to land near Pinellas County in the Gulf of Mexico, where it is 5-10 miles offshore.

  • Recent Slide Shows

Comments

0 Comments

Comment Preview

Your name will appear as username ( settings | log out )

You may use these HTML tags and attributes: <a href=""> <b> <em> <strong> <i> <blockquote>