Science News - July 21, 2007

(5 x 10²⁰) possible positions. Each player starts with 12 pieces on an 8-by-8 checkerboard, and he or she moves a piece by sliding it forward and diagonally one square. A piece captures an enemy by jumping diagonally across it into an open square. The last player with pieces on the board wins.

Beginning in 1989, Schaeffer used as many as 200 computers simultaneously to grind out the problem. He started with the endgame, putting just two pieces on the board and calculating every possible outcome for each position they might assume. Then he did the same for three pieces, then four, and so on up to 10. At that point, 39 trillion positions were possible.

Each step in this process took 10 times as much work as the previous step, so continuing in this way was impractical. Instead, Schaeffer turned to the beginning of a game, calculating all the positions that could result from one move, then two moves, then three moves, and so on. The program continued the game until there were only 10 pieces left, at which point it checked its database of endgames to find the outcome. Ultimately, the analysis included somewhere between 100 trillion and a quadrillion checkers positions. Schaeffer and his colleagues report their results in an upcoming Science.

“We’re pushing the frontiers of what computers can solve,” Schaeffer says. “If we had waited 10 or 20 years, the machines would be faster,” making the problem easy. As it was, he and his team had to invent clever ways of storing and searching the data.

For example, they stored the outcomes for the 39 trillion possible positions for endgames in a mere 237 gigabytes of com-puter-storage space, an average of 154 positions per byte. The mathematicians are now applying these techniques to bioinformat-ics, looking for ways to manage the massive quantity of data generated by the sequencing of genomes.

“It’s just a prodigious amount of work,” says Ken Thompson of Mountain View, Calif.–based Google, who in 1983 developed the first master-level chess computer program. Thompson says that solving checkers brings computers a step closer to being able to solve more-complicated games, such as chess or go. However, he estimates that those tasks will take another 100 years to complete. Chess has about 10²⁰times as many positions as checkers does, Schaeffer says. —J. REHMEYER

Den Mothers
Bears shift dens as ice
deteriorates

AMSTRUP

Pregnant polar bears in northern Alaska are now more likely to dig their birthing dens on land or landbound ice than on the

COLD CASE A female polar bear often has two cubs at a time in a den dug into the shore or floating ice. The cubs then stay with her for more than 2 years.

offshore ice they once used, according to 20 years of records.

This landward trend probably reflects the decline of the sea-ice habitat these bears have traditionally relied on, says Steven Amstrup of the U.S. Geological Survey in Anchorage, Alaska. He and his colleagues found the trend toward coastal denning in a long-term data set that records polar bear movements.

These bears don’t hunker down in dens to survive winter. They specialize in prowling ice to ambush seals. Only pregnant females dig dens, where they spend winters giving birth and nursing cubs.

Alaskan polar bears spend summers hunting on ice north of Alaska. As that ice shrinks, bears that find it unsuitable for denning face a long journey back to coastal denning sites. So the trend to landward denning may be only a stopgap adaptation to climate change, Amstrup says. “The biggest concern is that if the ice continues to retreat, there may come a time when bears can’t return to land.”

Amstrup startled biologists during the early 1990s when he reported, from radio-tracking data, that more than half of northern Alaskan polar bears’ maternity dens were on offshore, drifting pack ice. Polar bears in the rest of the Arctic den on land or on ice frozen fast to the shore.

The new study started as an attempt to see whether information beamed by radio collars to satellites could reliably indicate denning sites, says coauthor Anthony Fis-chbach, also of the USGS in Anchorage. It does, the researchers report online and in an upcoming issue of Polar Biology.

What surprised the researchers, however, was the distribution of their sample of 124 dens. From 1985 through 1994, 62 percent

of dens detectable by satellite were on floating ice. From 1998 to 2004, only 37 percent of dens were at sea.

Other research has documented that the amount of sea ice that stays frozen from year to year shrank 27 percent during the past 30 years, notes Amstrup. “If you’re a mother bear, you probably want to be on ice that’s pretty doggone stable,” he says.

The researchers reject the idea that female bears are lured to land to feed on scraps from the increasing number of bowhead whales killed by hunters. Tracking records show that pregnant bears rarely feed on the scraps.

The researchers also discount the impact of reduced bear hunting. Laws minimized hunting as of the early 1970s but didn’t change during the study period, says Fisch-bach. However, polar bear researcher Ian Stirling of the Canadian Wildlife Service, based in Edmonton, Alberta, says that it could have taken decades for changes in the law to show an effect.

Still, he agrees that deteriorating ice contributes to the denning shift. “As the climate is warming and we’re losing ice, you don’t have to be a rocket scientist to know that that’s going to have a significant negative effect on an animal that depends on ice for life,” he says. —S. MILIUS