Chinook
In plain wordsA checkers program from the University of Alberta that in 1994 became the first program crowned world champion in a contest against people, and in 2007 proved that perfect checkers always ends in a draw.
A program for checkers (draughts on an 8 × 8 board) developed from 1989 by a team led by Jonathan Schaeffer at the University of Alberta. Its play rested on deep alpha–beta searchminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best. guided by a hand-tuned evaluation function, an opening book, and endgame databases giving the exact outcome of every position with at most eight pieces on the board. It earned the right to challenge for the world title in 1990; the long-reigning champion Marion Tinsley beat it in 1992 in a newly created Man-Machine World Championship, and in the 1994 rematch Tinsley withdrew for health reasons, so Chinook took the title, the first time a program had become world champion in competition with humans. The project culminated in 2007, when Schaeffer's team announced that checkers is weakly solved: after nearly two decades of computation, they proved that perfect play by both sides leads to a draw, making checkers the most complex game solved to that date.
Chinook never needed to learn: by 2007 its creators had simply solved checkers.
Origin
Developed by Jonathan Schaeffer's team at the University of Alberta from 1989; the proof that perfect play leads to a draw was published as 'Checkers Is Solved' in Science in 2007.
Usage note
Contrast Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'. (1950s), which learned from experience and helped name machine learningmachine learning, n.: A way of building software that learns from examples instead of following rules written by a programmer. Shown thousands of labeled photos, for instance, a program can learn to recognize cats.; Chinook relied on search and exhaustive databases.
Related
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
- Deep BlueDeep Blue, prop. n.: IBM's chess computer that beat world champion Garry Kasparov in 1997, the first time a machine defeated a reigning world champion in a match under standard tournament conditions.
- Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'.
- AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs.
Sources
- Schaeffer, J. et al. (2007). Checkers Is Solved. Science 317(5844), 1518–1522.
Mentioned in
Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'.