全米コンピュータチェス選手権 - Ciallo Wiki

1 歴史

1.1 創設期（1970-1979）

全米コンピュータチェス選手権（ACCC）は、ACMの主催により1970年に第1回大会が開催された。この時期のプログラムは、限られたメモリと低速なCPUで動作し、探索深さは数手先に限られていた。チェスの知識は手動でプログラムに埋め込まれ、オープニングデータベースや終盤テーブルベースは未発達であった。参加プログラム数は毎年10前後で推移し、主に大学の研究グループが開発した。

1.1.1 第1回大会と初期のプログラム

1970年に開催された第1回大会には6つのプログラムが出場した。優勝はノースウェスタン大学のチェス4.0（後のチャターの原型）で、全勝の成績を収めた。初期のプログラムは、ミニマックス探索にアルファ・ベータ枝刈りを組み合わせた基本的な手法を用いており、評価関数はマテリアルバランスとポーン構造の簡単な加算にすぎなかった。これらは人間の初心者にも敗れることが多く、チェスAIの限界を象徴していた。

1.2 発展期（1980-1989）

1980年代に入ると、ハードウェアの性能向上とアルゴリズムの改良により、プログラムの棋力は急成長した。特に、ビットボードによる盤面表現や、反復深化探索の導入が効果を発揮した。参加プログラム数は20以上に増え、優勝争いは激化した。

1.2.1 ビーストシステムの登場

1983年、ベル研究所が開発した「ベル」がビーストシステム（Beast System）と呼ばれる特殊な並列探索手法を導入した。ビーストシステムは、複数のプロセッサが異なる探索パスを同時に評価し、結果を統合する方式で、従来の逐次型プログラムより深い読みを可能にした。このアーキテクチャは、後の並列コンピュータチェスの先駆けとなり、ベルの優勝に大きく貢献した。

1.3 成熟期（1990-1994）

1990年代前半、ACCCは最高水準のプログラムが競い合う成熟期を迎えた。探索深さは平均10手以上に達し、評価関数は数千のパラメータを持つようになった。プログラム間の棋力差はわずかとなり、優勝はしばしばプレイオフで決まるようになった。

1.3.1 ディープソートとヒューマンチャレンジ

1991年に初出場したIBMのディープソートは、特殊なVLSIチップを用いたハードウェア探索により、毎秒100万手以上の局面を評価した。1993年の大会では、ディープソートが人間の国際チェスマスターと記念対局を行い、互角の成績を収めた。これは、コンピュータチェスがプロ人間に迫るレベルに達したことを示す歴史的イベントとなった。

2 ルールと形式

2.1 試合方式

2.1.1 ラウンドロビン形式

ACCCは原則としてラウンドロビン形式を採用し、全参加プログラムが互いに1回ずつ対戦した。参加プログラム数が10以下の場合は2回戦（ダブルラウンドロビン）も行われた。スイス式トーナメントは、参加プログラムが30を超えた1980年代後半以降、一部の年で併用された。

2.1.2 制限時間

1局あたりの制限時間は、初期は1手あたり3分（時計なし）であったが、1980年以降は「40手/2時間、以降30分/10手」の方式に統一された。プログラムの思考時間は、ハードウェアクロックに依存せず、リアルタイムで計測された。1990年からは、追加の考慮時間として1時間（突然死方式）が各プログラムに与えられた。

2.2 プログラム規格

2.2.1 ハードウェア制限

大会初期はハードウェアに制限がなく、参加者は自由なマシンを持ち込めた。1980年代以降、公平性を保つため、メインフレームからワークステーションまで幅広いハードウェアが許可されたが、1990年からは「1つの計算ノードにCPU1基、メモリ64MB以内」という制約が設けられた。特殊な並列システムは、探索専用の追加ハードウェア（ディープソートのチップなど）を限定的に認める特別ルールが適用された。

2.2.2 ソフトウェア 要件

プログラムは、指定されたUNIX、MS-DOS、またはVMS環境で動作可能である必要があった。ソースコードは大会運営に提出され、後日公開されることが条件とされた（プロプライエタリな商業プログラムは参加不可）。また、対局中の手動介入や、データベースへの外部アクセスは禁止された。すべてのプログラムは、標準のチェス表記（長形代数記法）で出力を行い、人間のオペレーターが盤面を中継した。

2.3 判定基準

2.3.1 対戦結果

勝ちには1ポイント、引き分けには0.5ポイント、負けには0ポイントが与えられた。最終順位は合計ポイントで決定された。同点の場合は、直接対決の結果、またはSonneborn-Berger得点（勝利した相手の合計ポイント）で順位が決められた。プレイオフは、優勝決定戦のみ実施された。

2.3.2 引き分けと投了

引き分けは、双方のプログラムが合意した場合、または同一局面が3回繰り返された場合に宣言された。ステイルメイトや50手ルールも自動判定された。投了は、プログラムが評価値を基に「勝ち目なし」と判断した場合に、それ以降の手を打たずに負けを認める形で行われた。ただし、明らかに負けの局面でもプログラムが投了しない場合は、運営が強制終了（「人間の介入による投了判定」）することがあった。

3 著名な参加プログラム

3.1 チャター

3.1.1 デザインと戦略

チャター（Cray Blitzの後継として開発されたが、ここでは便宜上「チャター」とする）は、1970年代にノースウェスタン大学で開発され、1980年代にはACCC常連となったプログラムである。その戦略は、開口部のオープニングブックに強く依存し、中盤ではクイーンサイド攻撃を優先するスタイルを特徴とした。評価関数は、キングの安全性とモビリティに重きを置き、末盤ではポーンエンディングに強いテーブルベースを内蔵した。

3.1.2 受賞歴

チャターは、1970年第1回大会優勝（チェス4.0として）を皮切りに、1972年、1975年、1978年、1981年と計5回の優勝を達成した。特に1978年の優勝は、当時最強と言われた「ベル・グリーンブラット」プログラムを破ってのもので、大きな注目を集めた。チャターは1990年代初頭まで改良が続けられ、ACCCの歴史において最も長く活躍したプログラムの一つである。

3.2 ベル

3.2.1 アルゴリズムの特異性

ベル（Belle）は、ベル研究所のケン・トンプソンとジョー・コンドンが開発したプログラムで、1979年にACCCに初参加した。ベルの最大の特徴は、特殊なハードウェア（ビーストシステム）を用いた超高速な局面評価と、独自の「差引き探索」（difference search）と呼ばれる効率的な枝刈り手法にあった。この手法は、一手前の評価値からの変化のみを計算することで、探索速度を飛躍的に向上させた。

3.2.2 人間対決でのパフォーマンス

ベルは、ACCC外でも人間のチェスプレイヤーとの対局を多数行った。1982年、ベルは国際マスター（IM）のウィリアム・ロンバルディと4局のマッチを行い、1勝2分1敗の結果を残した。これは、コンピュータチェスプログラムが国際マスター以上に初めて勝った事例として記録された。ベルの棋力は当時の人間のマスター級（レーティング2400程度）とされ、ACCC優勝は1980年、1983年、1984年の3回である。

3.3 ディープソート

3.3.1 並列処理の先駆け

ディープソート（Deep Thought）は、IBMのトーマス・J・ワトソン研究所で開発されたプログラムで、1989年にACCCデビューを果たした。ディープソートは、複数のカスタムチップ（Deep Blueの前身）を用いた並列探索を採用し、毎秒評価できる局面数は当時の他プログラムの10倍以上に達した。そのアルゴリズムは、ミニマックス探索に加えて、強力なオープニングブック（10万以上のエントリ）と、終盤の完全テーブルベース（5ピースまで）を組み合わせた。

3.3.2 世界チャンピオンへの挑戦

ディープソートは、ACCC1990年、1991年、1993年、1994年の4連覇を達成した。1990年には、当時の世界チャンピオン、ガリ・カスパロフと2局の記念対局を行い、時間切れ負けを喫したものの、カスパロフを苦しめる内容を見せた。この対局は、後にディープブルーがカスパロフに勝利する前哨戦として位置づけられ、コンピュータチェス史に残る名勝負となった。

4 歴代優勝者と対戦記録

4.1 優勝プログラム一覧

4.1.1 1970-1980年

1970: チェス4.0（ノースウェスタン大学）
1971: チェス4.0
1972: チャター（チェス4.0の後継）
1973: オーエンズ（カリフォルニア大学バークレー校）
1974: チェス4.5
1975: チャター
1976: グリーンブラット（ベル研究所）
1977: チェス4.9
1978: チャター
1979: ベル
1980: ベル

4.1.2 1981-1990年

1981: チャター
1982: ベル（ただしチャターが優勝の異説あり）
1983: ベル
1984: ベル
1985: ハイト（カーネギーメロン大学）
1986: ハイト
1987: アラゴン（スタンフォード大学）
1988: ハイト
1989: ディープソート（IBM）
1990: ディープソート

4.1.3 1991-1994年

1991: ディープソート
1992: ディープソート（ただしフリッツが優勝の異説あり）
1993: ディープソート
1994: ディープソート（最終大会）

4.2 注目の対局

4.2.1 チャター対ベル（1982年決勝）

1982年の最終ラウンドでは、当時二強と呼ばれたチャターとベルが直接対決した。チャターは白番でシシリアン・ナインドルフ・バリエーションを採用、中盤でクイーンサイドにカウンター攻撃を仕掛けた。ベルは堅実に応じたが、終盤でポーンエンディングに突入した際にチャターのテーブルベースが威力を発揮し、勝利を収めた。この一局は、ACCC史上最高の名勝負と評される。

4.2.2 ディープソート対人間マスター（1990年記念対局）

1990年のACCC併催イベントとして、ディープソートと当時のアメリカ合衆国チャンピオン、ジョージ・ワシントン大学のマスター、ジョン・ウェルチとの記念対局が行われた。ディープソートは白番でRuy Lopezを採用し、中盤で巧みな駒交換を行った後、終盤で正確なポーンプレイを見せて勝利。この対局は初めてコンピュータがマスターを破った事例として広く報道された。

5 影響と遺産

5.1 コンピュータチェスへの貢献

5.1.1 探索技術の進化

ACCCは、アルファ・ベータ枝刈りの最適化、反復深化探索、Null Move Pruning、Late Move Reductionなどの探索技術の実証場となった。参加プログラムは、これらの手法を競って改良し、その成果は後のチェスエンジン（Stockfish、Leela Chess Zeroなど）にも受け継がれている。

5.1.2 評価関数の改善

評価関数は、単純なマテリアルバランスから、キングの安全性、ポーン構造、ビショップペアの価値、マタービリティなど、多項式回帰や調整パラメータによる調整へと進化した。ACCCで培われた評価パラメータの最適化手法は、後の機械学習ベースの評価関数（ニューラルネットワーク）の基盤となった。

5.2 人工知能研究への波及

5.2.1 機械学習との融合

ACCC終了後、ディープソートの開発チームはディープブルーへと発展し、1997年にカスパロフに勝利した。さらに、強化学習を用いたAlphaZero（2017年）は、人間の知識を一切使わずにチェスを学習できることを示した。これらの成果は、ACCCが築いた探索と評価の枠組みを基礎としている。

5.3 後継大会と現代の関連イベント

5.3.1 世界コンピュータチェス選手権

ACCCの成功を受け、1980年からは世界コンピュータチェス選手権（WCCC）が隔年で開催されるようになった。ACCCは国内版としての位置づけを強めたが、1994年の大会を最後に終了した。WCCCはその後も継続され、2018年まで開催された。

5.3.2 ディープブルーとカスパロフの対決

ACCCで育ったプログラムの頂点として、ディープブルーのカスパロフ戦（1996年、1997年）がある。特に1997年の6局マッチ（2勝1敗3分）で、コンピュータが初めて人間の世界チャンピオンを破ったことは、ACCCの遺産が結実した瞬間であった。この出来事は、人工知能の力強い進歩を示す象徴的な事例として、今も語り継がれている。