Chinookは、ボードゲームであるチェッカー（ドラフツとも呼ばれる）をプレイするコンピュータプログラムである。コンピュータ科学者のジョナサン・シェーファーが率いるアルバータ大学のチームによって開発されたChinookは、人間のチェッカーの最高水準で競争するように設計された。1994年には、人間の世界チャンピオンであるマリオン・ティンズリーを破り、戦略ゲームの世界選手権で優勝した最初のコンピュータプログラムとなるという歴史的なマイルストーンを達成した。2007年には、Chinookチームがこのプログラムがチェッカーを実質的に解明したと発表した。つまり、両者が完璧にプレイすれば、ゲームは常に引き分けになることを意味する。
Chinookの開発は、人工知能とゲーム理論の研究プロジェクトとして1989年に始まった。このプログラムは、探索アルゴリズム、評価関数、および広範なオープニングブックの組み合わせを使用する。その成功は、ミニマックス探索とアルファベータ枝刈りという、プログラムが毎秒数百万の局面を探索することを可能にする技術の原理に基づいていた。このプログラムは数年にわたって改良され、評価関数と探索効率に大幅な改善が加えられた。
世界選手権での功績
Chinookの最も有名な功績は、1990年に米国全国チェッカー選手権で2位に入り、世界選手権への挑戦権を獲得したことであり、人間の世界タイトルに資格を得た最初のコンピュータとなった。1992年には、Chinookは現役世界チャンピオンであり、広く史上最高のチェッカー選手と見なされていたマリオン・ティンズリーと対戦した。この試合は40ゲームで引き分けに終わり、ティンズリーがタイトルを保持した。1994年には再戦が行われたが、ティンズリーは健康上の理由で6ゲーム後に棄権し、Chinookが勝利者と宣言され、ボードゲームで世界選手権を保持した最初のコンピュータプログラムとなった。
ティンズリーの引退後、Chinookは1995年にドン・ラファティに対してタイトルを防衛し、試合に勝利した。このプログラムは人間のトーナメントに出場し続けたが、1996年シーズン後に競技から引退した。
チェッカーの解明
2007年、Chinookチームはジャーナル『Science』に論文を発表し、チェッカーを解明したと発表した。この解明には、遡及解析と探索アルゴリズムの組み合わせを使用して、完璧なプレイでゲームが引き分けになることを証明する大規模な計算作業が含まれていた。チームは、ボード上に最大10個の駒があるすべての局面のデータベースを計算した。これには約10^14回の計算が必要であり、分散コンピューティングを使用して18年以上の継続的な計算時間を要した。結果は、標準的な開始位置から、チェッカーは理論上の引き分けであり、両者が最適にプレイすればどちらのプレイヤーも勝利を強制できないことを示した。
チェッカーの解明は、機械学習とゲームAIにおける画期的な成果であり、当時解明された最大のゲームであり、探索空間は約5×10^20の可能な局面であった。これは、探索アルゴリズムと大規模計算を組み合わせる力を示し、ゲームにおける人間の専門知識の限界についての洞察を提供した。
技術的アプローチ
Chinookのアーキテクチャは、古典的なゲームプレイAI設計に基づいていた。これは、アルファベータ枝刈りを用いた深さ優先探索を使用して局面を評価し、駒の数、機動性、位置的な利点を考慮した洗練された評価関数を採用していた。このプログラムには、専門家のプレイからの数百万の局面を含む大規模なオープニングブックと、遡及解析を使用して構築されたエンドゲームデータベースもあった。エンドゲームデータベースは解明プロセスにとって重要であり、プログラムがゲームの後半で完璧にプレイすることを可能にした。
解明の取り組みでは、チームは「証明数探索」と呼ばれる技術を使用して、勝利または敗北の可能性が最も高い局面に向けて探索を導いた。また、エンドゲームデータベースの数十億の局面を処理するために分散コンピューティングネットワークを使用した。最終的な解明はチェッカーが引き分けであるという証明であったが、チームはどちらかのプレイヤーがミスを犯した場合、もう一方が勝利を強制できることも示した。
遺産と影響
Chinookの成功は、人工知能とゲーム研究の分野に大きな影響を与えた。これは、コネクトフォー（1988年に解明）や、後にAlphaGoなどのプログラムによって取り組まれた囲碁など、他のゲームを解明するその後の取り組みに影響を与えた。Chinookはまた、大きな状態空間を持つゲームを解明するための技術の開発に貢献し、そのアプローチは他の組み合わせ問題にも適用されている。
技術的な貢献に加えて、Chinookは人間と機械の知能の性質に関する哲学的な疑問を提起した。このプログラムの人間の世界チャンピオンに対する勝利は、チェス（1997年のディープ・ブルー）や囲碁（2016年のAlphaGo）におけるその後の成果の先駆けとなった。今日、Chinookは、コンピュータが複雑な戦略ゲームを習得する可能性を示した先駆的な取り組みとして記憶されている。
Chinookプロジェクトはまた、探索アルゴリズムの性能を測定するためのテストであるFhourstonesベンチマークの開発にもつながった。このプログラムのコードとデータベースは研究目的で利用可能になっており、その遺産はゲームプレイAIシステムの設計に影響を与え続けている。