チェッカープログラムは、ボードゲームであるチェッカー（ドラフツとも呼ばれる）をプレイするために設計されたコンピューターソフトウェアです。これらのプログラムは、アルゴリズム技術を用いて局面を評価し、最適な手を探索し、人間のプレイヤーや他のコンピューターと対戦します。最も著名なチェッカープログラムは、アルバータ大学（プロジェクトはトロントではなくそこに拠点を置いていた）でジョナサン・シェーファー率いるチームによって開発されたChinookであり、これは競技プレイとゲーム解決の両方で歴史的な節目を達成しました。
Chinookは1989年から2007年にかけて、アルバータ大学のチーム（ジョナサン・シェーファー、ロブ・レイク、ポール・ルー、マーティン・ブライアント、ノーマン・トレロア）によって開発されました。機械学習に依存する現代のアプローチとは異なり、Chinookの知識はその作成者によって完全に手書きでコード化され、探索アルゴリズムや評価関数などの伝統的な人工知能技術を使用していました。この違いは、AIがルールベースのシステムからデータ駆動型の手法へと進化したことを浮き彫りにしています。
人間対機械の世界チャンピオン
1990年、Chinookは米国全国選手権でマリオン・ティンズリーに次ぐ2位となり、人間の世界選手権に出場する権利を獲得しました。当初、米国チェッカー連盟と英国ドラフツ協会は、人間の選手権へのコンピューター参加に反対していました。ティンズリーが抗議のためタイトルを辞任したとき、これらの組織は新しいタイトル「人間対機械の世界選手権」を創設し、競技の進行を許可しました。ティンズリーは最初の対局で4勝2敗33引き分けで勝利しました。
1994年の再戦では、6局が引き分けとなった後、ティンズリーが膵臓癌のため棄権したため、Chinookが人間対機械の世界チャンピオンと宣言されました。これにより、Chinookは人間に対して世界選手権タイトルを獲得した最初のコンピュータープログラムとなりましたが、最も近い競争相手よりもはるかに優れていたティンズリーを破ることはありませんでした。1995年、Chinookはドン・ラファティとの32局の対局でタイトルを防衛し、31引き分けで1-0の勝利を収めました。この後、シェーファーは競技プレイをやめ、チェッカーの完全解決に専念することを決定しました。
アルゴリズム
Chinookのアルゴリズムは、4つの主要な構成要素で構成されていました：グランドマスターの対局からの手を含むオープニングブック、可能な手を探索するための深い探索アルゴリズム、手の評価関数、そして8個以下の駒を持つすべての局面をカバーする終盤データベースです。評価関数は、駒数、キング数、閉じ込められたキング、手番、そして駒数（キングになるための妨げられない経路を持つ駒）などの特徴を考慮した線形の手書き関数でした。すべての知識は学習ではなく作成者によってプログラムされ、これは後のDeepMindのアプローチなどのAIシステムとは対照的でした。
タイムラインとチェッカーの解決
Chinookの開発における主要な節目には以下が含まれます：1997年、シェーファーが著書「One Jump Ahead: Challenging Human Supremacy in Checkers」（2008年11月に更新）を出版；2003年5月24日、10駒データベース（各サイド5駒）が完成；2004年8月2日、オープニング「ホワイト・ドクター」（10-14 22-18 12-16）が引き分けであることが証明されました。さらに、2006年1月18日（09-13 21-17 05-09）と2006年4月18日（09-13 22-17 13-22）に、他のオープニングが引き分けであることが証明されました。
2007年3月10日、シェーファーはACM SIGCSE会議で、最終的な解決が3〜5ヶ月以内に期待されると発表しました。2007年7月19日、ジャーナル『Science』は「Checkers Is Solved」を発表し、完璧なプレイでは最良の結果が引き分けであることを証明しました。これにより、チェッカーはより単純なゲームに関する初期の研究に続き、完全に解決された最初の主要なボードゲームとなりました。競技の最盛期には、Chinookのレーティングは2814 Eloでした。
遺産
Chinookの成功は、深層学習の台頭以前における、深い探索や手書き評価などの古典的なAI技術の力を実証しました。そのチェッカーの解決は、チェスコンピューターであるディープ・ブルーに匹敵する、ゲームAIにおける画期的な成果であり続けています。現代のチェッカープログラムはニューラルネットワークを使用するかもしれませんが、Chinookのアプローチはゲーム理論と組合せゲーム解決におけるその後の研究に影響を与え、その手法はカーネギーメロン大学やMIT CSAILなどの機関のAIコースで今も研究されています。