 |
|
New computer cluster solves 3500-year old game
August 29, 2002Dutch computer scientists from the Vrije Universiteit Amsterdam have solved the game of awari. With optimal play from both players, the game ends in a draw. Awari (a mancala variant, that is also known as wari, owari, awalé, awélé, and ayo) is an ancient board game that originates from Africa, and is played worldwide now.
Both players own six pits, in which stones are kept. The stones, 48 in total, are sown around over the pits, and can be captured according to the rules of the game. The objective of the game is to capture more than 24 stones. Although the rules are simple, the game requires profound strategic insight to be played well.
Dr. John W. Romein and Prof. dr. ir. Henri E. Bal solved the game by developing a program that computes the best move and eventual outcome for all 889,063,398,406 positions that can possibly occur in a game. The results are stored in a database that is 778 gigabyte large. The database was computed on a large computer cluster with 144 processors. A new and fast, parallel algorithm managed to compute the database in only 51 hours. Each processor accounted for part of the postitions, but the processors closely co-operated to determine the best moves. One complication was that the available main memory, 72 gigabyte, was by far not large enough to hold the entire database. Another problem was the heavy communication between the processors; a total of 1.0 petabit (= 10^{15} bits) was sent over the interconnection network.
The researchers are currently developing an invincible awari program, that uses the database to play perfectly. The game can be played online via http://awari.cs.vu.nl/. By default, the program plays at a weaker level, so that the human can actually win. The web interface can also be used to look up any position, to ask for the best move. The research is an important step forward in a research area within Artificial Intelligence, to solve games with increasing complexity. For example, Connect-4 was solved a decade ago, and some chess endgames are solved as well. Although solving checkers seems feasible, chess and go are not solvable in the foreseeable future.
Vrije Universiteit
Science Research Departments
Earth Science
Alternative Energy | Anthropology and Archaeology | Earthquakes and Volcanoes | Environment and Nature News | Global Warming | High-Energy and Particle Physics | Ozone Hole | Scientists Slow Light | Tsunami
Space Science
Astronomy and Space News | Black Holes | Chandra X-Ray Observatory | Extrasolar Planets | Hubble Telescope | International Space Station | Jupiter Galileo Mission | Jupiter Cassini Mission Flyby | Mars Exploration | Mars Odyssey 2001 | Mars Global Surveyor | Mars Polar Lander | Mars Climate Orbiter | Mars Pathfinder | Meteors and Asteroids | Mir Space Station | NEAR Asteroid Probe Mission | Pluto Planet Debate | Search for Extraterrestrial Life | Space Shuttle Program | Space Shuttle Mission: STS-102 | Space Weather
Life Science
Animal News | Biotechnology and Genetics | Brain Research | Human Cloning | Dinosaur and Fossil Discoveries | Endangered Species | Gene Therapy | Genetically Modified Food | Stem Cell Research | Whales and Whaling
 | Breaking Dawn (The Twilight Saga, Book 4) by Stephenie Meyer When you loved the one who was killing you, it left you no options. How could you run, how could you fight, when doing so would hurt that beloved one? If your life was all you had to give, how could you not give it? If it was someone you truly loved? To be irrevocably in love with a vampire is both fantasy and nightmare woven into a dangerously heightened reality for Bella Swan. Pulled in one... |
 | Twilight (The Twilight Saga, Book 1) by Stephenie Meyer "Softly he brushed my cheek, then held my face between his marble hands. 'Be very still,' he whispered, as if I wasn't already frozen. Slowly, never moving his eyes from mine, he leaned toward me. Then abruptly, but very gently, he rested his cold cheek against the hollow at the base of my throat." As Shakespeare knew, love burns high when thwarted by obstacles. In Twilight, an exquisite... |
 | Eclipse (The Twilight Saga, Book 3) by Stephenie Meyer Readers captivated by Twilight and New Moon will eagerly devour Eclipse, the much anticipated third book in Stephenie Meyer's riveting vampire love saga. As Seattle is ravaged by a string of mysterious killings and a malicious vampire continues her quest for revenge, Bella once again finds herself surrounded by danger. In the midst of it all, she is forced to choose between her love for Edward... |
 | Watchmen by Alan Moore Has any comic been as acclaimed as Alan Moore and Dave Gibbons' Watchmen? Possibly only Frank Miller's The Dark Knight Returns, but Watchmen remains the critics' favorite. Why? Because Moore is a better writer, and Watchmen a more complex and dark and literate creation than Miller's fantastic, subversive take on the Batman myth. Moore, renowned for many other of the genre's finest creations (Saga... |
 | The Obama Nation: Leftist Politics and the Cult of Personality by Jerome R. Corsi In this thoroughly researched and documented book, the #1 New York Times bestselling co-author of Unfit for Command: Swift Boat Veterans Speak Out Against John Kerry explains why the extreme leftism of an Obama presidency would leave the United States weakened, diminished and divided, why Obama must be defeated—and how he can be. THE OBAMA NATION Leftist Politics and the Cult of... |
 | Brisingr (Inheritance, Book 3) by Christopher Paolini OATHS SWORN . . . loyalties tested . . . forces collide.Following the colossal battle against the Empire’s warriors on the Burning Plains, Eragon and his dragon, Saphira, have narrowly escaped with their lives. Still there is more at hand for the Rider and his dragon, as Eragon finds himself bound by a tangle of promises he may not be able to keep.First is Eragon’s oath to his cousin... |
 | New Moon (The Twilight Saga, Book 2) by Stephenie Meyer Legions of readers entranced by Twilight are hungry for more and they won't be disappointed. In New Moon, Stephenie Meyer delivers another irresistible combination of romance and suspense with a supernatural twist. The "star-crossed" lovers theme continues as Bella and Edward find themselves facing new obstacles, including a devastating separation, the mysterious appearance of dangerous wolves... |
 | Publication Manual of the American Psychological Association by American Psychological Association ...offers updated information on reporting statistics, writing withour bias, preparing manuscripts with a word processor for electronic production, and publishing research in accordance with ethical... |
 | The Limits of Power: The End of American Exceptionalism by Andrew Bacevich From an acclaimed conservative historian and former military officer, a bracing call for a pragmatic confrontation with the nation's problemsThe Limits of Power identifies a profound triple crisis facing America: the economy, in remarkable disarray, can no longer be fixed by relying on expansion abroad; the government, transformed by an imperial presidency, is a democracy in form only; U.S.... |
 | Three Cups of Tea: One Man's Mission to Promote Peace . . . One School at a Time by Greg Mortenson, David Oliver Relin The astonishing, uplifting story of a real-life Indiana Jones and his humanitarian campaign to use education to combat terrorism in the Taliban’s backyard Anyone who despairs of the individual’s power to change lives has to read the story of Greg Mortenson, a homeless mountaineer who, following a 1993 climb of Pakistan’s treacherous K2, was inspired by a chance encounter with impoverished... |
| © 2008 BrightSurf.com |