Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • News from the world of maths: Game over for checkers

      3 August, 2007
      Friday, August 03, 2007

      Game over for checkers

      Computer scientists at the University of Alberta have solved checkers, the popular board game with a history dating back to 3,000 BC.

      After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten. Completed in late April this year, the program, Chinook, may be played to a draw but will never be defeated. The results of this research were published recently in the journal Science.

      "This is a tremendous achievement — a truly significant advance in artificial intelligence," said Dr. Jaap van den Herik, editor of the International Computer Games Journal. "I think we've raised the bar — and raised it quite a bit — in terms of what can be achieved in computer technology and artificial intelligence," said Schaeffer, chair of the University of Alberta Department of Computing Science. "With Chinook, we've pushed the envelope about one million times more than anything that's been done before."

      A self-described "awful" checkers player, Schaeffer created Chinook to exploit the superior processing and memory capabilities of computers and determine the best way to incorporate artificial intelligence principals in order to play checkers.

      With the help of some top-level checkers players, Schaeffer programmed heuristics — rules of thumb — into a computer software program that captured knowledge of successful and unsuccessful checkers moves. Then he and his team let the program run, while they painstakingly monitored, fixed, tweaked, and updated it as it went.

      An average of 50 computers, with more than 200 running at peak times, were used everyday to compute the knowledge necessary to complete Chinook. Now that it is complete, the program no longer needs heuristics — it has become a database of information that knows the best move to play in every situation of a game. If Chinook's opponent also plays perfectly the game would end in a draw.

      "We've taken the knowledge used in artificial intelligence applications to the extreme by replacing human-understandable heuristics with perfect knowledge," Schaffer said. "It's an exciting demonstration of the possibilities that software and hardware are now capable of achieving."

      Schaeffer started the Chinook project in 1989, with the initial goal of winning the human world checkers championship. In 1990 it earned the right to play for the championship. The program went on to lose in the championship match in 1992, but won it in 1994, becoming the first computer program to win a human world championship in any game — a feat recognized by the Guinness Book of World Records.

      Chinook remained undefeated until the program was retired in 1997. With his sights set on developing Chinook into the perfect checkers program, Schaeffer restarted the project in 2001. "I'm thrilled with this achievement," he said. "Solving checkers has been something of an obsession of mine for nearly two decades, and it's really satisfying to see it through to its conclusion."

      "I'm also really proud of the artificial intelligence program that we've built at the University of Alberta," he added. "We've built up the premier games group in the world, definitely second-to-none. And we've built up a strong, international, truly world-class reputation, and I'm very proud of that."

      posted by Plus @ 4:23 PM

      0 Comments:

      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms