コンピュータチェス

コンピュータチェスは、コンピュータが指すチェスのことである。

1. 歴史
-----

1.1. 人間に勝つまで
------------

トルコ人やアジーブなど、18世紀から19世紀にかけて様々な「チェスを指す機械」が公開されてきたが、それらはどれも中に人が隠れて操作するイリュージョンであった。

チャールズ・バベッジは、1840年代に機械にゲームを行わせることに興味を持ち、思考ルーチンを考えた。ただし、チェスの場合は組合せが膨大になり現実的でないことに気づいている。

スペインの技術者レオナルド・トーレス・ケベードは、1912年に歴史上最初のコンピュータゲームと呼ばれるチェス機械、エル・アヘドレシスタを作成した。この機械はチェスの終盤のみを扱い白のキングとルークで人間側の黒のキングを詰ませようとするもので、内部の電気機械的な装置により盤面の状況を判断し駒の動きを決めることができ、人間側のキングの最初の位置がどこであってもチェックメイトすることができた。

コンピュータでチェスプログラムを作ることの可能性に初めて言及したのは、ドイツのコンラート・ツーゼであるといわれている。

ベル研究所のクロード・シャノンは、1949年に「チェスをするコンピュータのプログラミング」という論文を発表し、評価関数の特徴・探索木の作り方の戦略について考察している。

アラン・チューリングは、1951年に解析のアルゴリズムを考案し、実際にシミュレーションによる試合を試みている。

記録に残っている最初の動作するプログラムは、1956年のロスアラモス研究所のプログラムである。ただし、これは6×6のミニチュアボードによるものであった。

コンピュータ同士の最初のチェス対戦は、人工知能の父ジョン・マッカーシーらと、ソビエト連邦のモスクワ理論実験物理研究所の間で1966年から9ヵ月に渡って行われ、結果はソ連側の2勝2分だった。

最初にコンピュータが人間のチェスの選手権に参加したのは1967年のボストンの競技会の Mac Hack VI である。この時のコンピュータのレーティングは1670といわれ、やや強いアマチュアのレベルに達している。

1978年、'78東京オープン大会にコロンビア大学ニューボーン博士が開発したコンピューターチェス「オーストリッチ」が持ち込まれる。日本チェス協会の男性が対戦して男性側が三戦三勝。

コンピュータ同士の最初のチェス選手権は1970年にニューヨークで開催され、その時は当時の コントロール・データ・コーポレーション のスーパーコンピュータ上で動作する CHESS 3.0 というプログラムが優勝している。その後、北アメリカでのコンピュータチェス選手権は毎年開催され、1984年には当時最速のコンピュータであった Cray で動作する CRAY BLITZ が優勝、1988年にはディープ・ブルーの前身であるディープ・ソートが優勝するなどの記録が残っている。

1988年、ディープ・ソートはLong Beachでのトーナメントでグランドマスターのベント・ラーセンに勝利。グランドマスターに勝った史上初のプログラムとなった。

1989年にディープ・ソートは世界チャンピオンガルリ・カスパロフと対戦し、接戦の末に敗れた。1990年には、アナトリー・カルポフにも敗北。しかし、これらの試合は、人間がやがてコンピュータに敗れることを予感させるものであった。

1996年にIBMのコンピュータであるディープ・ブルーがガルリ・カスパロフと対戦し、1つのゲームとしては、初めて世界チャンピオンに勝利を収めた。ただし、これは6戦中の1勝に過ぎず、全体ではカスパロフの3勝1敗2引き分けであった。しかし、翌1997年に、ディープ・ブルーは、2勝1敗3引き分けとカスパロフ相手に雪辱を果たした。現実的にはこれだけの試合数で実力は評価できないが、世界チャンピオンと互角に戦えるだけの能力になったとIBMは宣伝した。しかし、これらの対戦では、試合中にプログラマーが自由にプログラムや次の一手に介入できるルールになっており、IBMチームにはグランドマスターも加わっていた一方で、カスパロフ側もトレーニングや解析にデータベースソフトを利用していたなど、純粋な「人間対機械」というわけではなかった。

1.2. ハードの低性能化
-------------

その後も人間対コンピュータの対戦は行なわれ、2002年の10月に行われたウラジーミル・クラムニクとコンピュータソフトディープ・フリッツとのマッチでは、両者引き分け。2003年1月26日から2月7日までニューヨークで行なわれた、カスパロフと「ディープ・ジュニア」とのマッチも、1勝1敗4引き分けで両者引き分けに終わっている。2003年11月11日から11月18日に行なわれたカスパロフとX3D Fritz のマッチは1勝1敗2引き分けで両者引き分けに終わった。

カスパロフの棋力に大きな変化がないので、2003年には汎用PCと一般人が購入できるソフトが、ディープ・ブルーの様な専用機に匹敵する性能を持った事が窺える。

ディープ・ブルーの後は、PCで動くコンピュータソフトが主力であるが、ハードウェアを含めて最強のチェス・コンピュータを作る試みがヒドラプロジェクトで行われている。これは、64ノードの Xeon プロセッサからなる。

2005年11月には、人間とコンピュータのチームによる対戦がスペインのビルバオで行われた。人間のチームはいずれも公式世界チャンピオンの経験者であるルスラン・ポノマリョフ、ルスタム・カシムジャノフ、アレクサンドル・カリフマンの3人、コンピュータのチームは、ヒドラ、フリッツ、Junior の3種。結果は8-4でコンピュータの勝利となり、この頃から人間がコンピュータに勝つことが次第に難しくなってきた。

2006年11月25日から12月5日にかけてディープ・フリッツはクラムニクと再戦し、2勝4引き分けの勝利を収めている。

2009年8月には、スマートフォンのHTC Touch HDに搭載された「Pocket Fritz 4」がアルゼンチンで開催されたカテゴリー6の大会に出場し10戦中9勝1分の戦績を収め、グランドマスター級の評価が与えられた。Pocket Fritz 4は1秒間に2万局面を読むが、ディープ・ブルーが1秒間に2億局面を読むのに比べると演算能力は1万分の1に過ぎず、ソフトの進化を印象づけるものとなった。

1.3. アンチコンピュータ戦略
----------------

コンピュータチェスの実力が人間のトップクラスに追いつき、さらにそれを追い越したと評価されるようになっても、コンピュータチェスに独特の弱点、落し穴はいくつか知られており、こうした穴を突く「アンチコンピュータ戦略」も人間対コンピュータの勝負では試みられてきた。

1997年のカスパロフ対ディープブルーでは、序盤の定跡を外して未知の局面に持ち込めば、定跡通りに指させるよりもディープブルーの力を落とすことができると考えたカスパロフが、第3局でイレギュラーなゲームの入り方をしたが、有利な先手を持ったにもかかわらず引き分けに終わった。

2008年3月15日に行われたヒカル・ナカムラとRybkaの対局では、ナカムラが一切の攻撃の意思を見せずひたすら手待ちを続けることで、Rybkaに「自らが優勢である」と錯覚させて無理な動きを誘発させ、途中で一気の反撃に転じて勝利した。この弱点をついたために、この対局は271ムーブの長期戦となった。

2. 人間側下手のハンデキャップマッチ
-------------------

2007年3月には、グランドマスターのJaan Ehlvestが「Rybka」と対戦。Rybka側は常にポーンを1つ落とすというハンデキャップマッチだったが、Rybkaが4勝1敗3分で勝利している。

2008年9月には、同じくグランドマスターのVadim MilovとRybkaが8局のハンデキャップマッチを含む対局を行った。最初の2局はMilovが有利な先手白番を持った通常の対局で、Rybkaの1勝1分。次の2局はMilovが先手白番、Rybkaが後手黒番でポーンを1つ落とす「pawn-and-move」でMilovの1勝1分。最後の4局はRybkaが先手白番でルークを落とし、Milovが後手黒番でナイトを落とすハンデで行われ、Milovの1勝3分となった。トータルスコアはMilovの2勝1敗5分となったが、この対局は、このレベルのグランドマスターがコンピュータ側にハンデを課した状態でようやく互角に争えるという結果を示すものとなった。

2014年8月23日には、ヒカル・ナカムラとStockfishのハンデキャップマッチ4局が行われた。Stockfishのハードウェアは、3.0GHz、8コアのIntel Xeon E5を搭載したMac Proであった。4局を通じて、Stockfishには序盤定跡とエンドゲームのデータベースにアクセスできない、というハンデが課された。最初の2局は、ナカムラが2008年版のMacBook Pro上で動くコンピュータチェスソフト「Rybka 3」を使用できるアドバンテージを得た上で、先後を変えて行われ、ナカムラは先手番でドローとしたが後手番では敗れた。なお、StockfishとRybka 3の実力差はStockfishがRybka 3に対して勝率75%である。次の2局はナカムラが先手でコンピュータのアシストなし、Stockfishが後手でポーンを一つ落とすハンデで行われ、こちらもナカムラの1分1敗となり、4局通算ではナカムラの2分け2敗であった。

2018年6月17日には、ヒカル・ナカムラとKomodoのハンデキャップマッチ3局が行われた。1局目はナカムラが先手番でポーンを1手先に動かしたところから始め後手のKomodoはポーンを1つ落とすハンデでドロー、2局目はKomodoが先手番で後手のナカムラがポーン1つをナイトに交換するハンデでドロー、3局目はKomodoが先手番でキングとポーン以外の駒をすべてナイトと交換し後手のナカムラがナイト2つを落とすハンデでドローに終わった。対局の持ち時間は双方10分で1手につき5秒加算、KomodoはCPUにIntel Core i9-7960Xを用いてオーバークロックさせ、5駒までのエンドゲームデータベースにアクセス可能とした。

3. コンピュータチェスがもたらした分枝
--------------------

チェスとほぼ同じ駒を使ってできるアリマアという新しいボードゲームが考案された。これは、1手あたりの可能な着手数がチェスに比べて遙かに多いため、当面の間は人間がコンピュータに負けることはないと考えられていたが、2015年にコンピュータプログラム「Sharp」が7勝2敗で人間を破っている。

ソフトの棋力向上を受けて、ネット対戦時にコンピュータの指し手を参照するプレイヤーが現れる。対して、カスパロフは人間同士が対局中にコンピュータで指し手を調べながら戦う「アドバンスト・チェス」という競技を提唱した。後者は両者了解の上で対局者双方がソフトを使用する点において前者とは大きく異なる。

4. コンピュータチェスのプログラミング技術・課題
-------------------------

コンピュータチェスのプログラミングは、以下の3つのフェーズに分割して考えることができる。

序盤 チェスの定跡は、昔から研究されているが、様々なバリエーションがある。通常のチェスソフトでは、序盤ではデータベースを参照しながら、現在の手順がデータベースにあるものかを検索する。データベースにあるもので、次の手が複数の候補を持てば、その最良の手を選択するか、ランダムに1つを選んで指すようにする。 データベースとしては、様々なものが作成されており、コンパクトなものから巨大なものまである。かならずしも巨大であれば良いというものでもない。 中盤 定跡のデータベースをはずれた時点から、評価関数をもとに探索を行いながら、最良の手順を探っていく。この時の、評価関数の与え方、探索時における無駄の排除がプログラミングの中心となる。探索の重複を避けるために、ハッシュテーブルを用いるのが普通である。 終盤 取った駒の再利用ができないチェスにおいては、双方のキングを除いた残りの駒がある程度少なくなった場合については、チェックメイト局面から逆行して局面を生成することにより、特定の局面において先後双方が最善を尽くした際に相手をチェックメイト可能かまたは引き分けに終わるかの完全解析を行うことが比較的容易である。このチェスの終盤戦＝エンドゲームのデータベース化の研究はかなり進んでいる。 1980年代初めには両キングを含めて残りが5駒以下の場合について完全解析が完了、2006年には残り6駒以下の場合のほとんどが完了し、2018年には残り7駒以下の場合が完了してデータベース化されている。これをテーブルベースと呼ぶ。後述のソフトウェアの中には、デフォルトでこれを含んでいるものや、オプションとして利用可能なものがある。 テーブルベースのデータ量の大きさは膨大であり、特に工夫をしない場合、残り6駒以下では1.2テラバイト、7駒以下では140テラバイトとなって、実用には不向きである。この問題を解決するために、データの持ち方を最適化したSyzygyテーブルベースが開発され、6駒以下では150ギガバイト、7駒以下では17テラバイトに圧縮することができ、多くのチェスエンジンに対応済みとなっている。8駒以下のテーブルベースについては現在研究が進んでいるが、そのデータ量は、最適化を行わなければ1ペタバイトに及ぶ。

5. 世界コンピュータチェス選手権
-----------------

1974年頃の参加プログラムは、専用の大規模なハードウェアを用いるものがほとんどであった。ディープ・ブルーは、1995年の香港での大会に出場し3位になっている。

1999年は、「世界コンピュータチェス選手権」と「世界マイクロコンピュータチェス選手権」は一体となって開催されている。近年は、ほとんどのプログラムがマイクロコンピュータ上で動作するプログラムになってしまったため、両者を区別する意味は失われた。

2010年には日本でコンピュータオリンピアードと同時開催され、Shredder、Rybka、Jonny、Fridolin、Pandix、Hector for Chess、Rondo、Junior、Darmenios、Thinkerの10種類が参加した。

5.1. 世界コンピュータチェス選手権の優勝ハードウェア
----------------------------

2005年に開催された第13回大会では、Shredder と Deep Junior の争いなるかと思われたが、優勝したのはアンソニー・コジィーによる Zappa、 2位には前評判の高かった Fruits、Shredder は Deep Sjeng と3位タイであった。

2007年から2010年まで Vasik Rajlich による Rybka が4年連続で優勝していたが、ソフトに問題があるとして優勝が取り消されている。

5.2. 世界マイクロコンピュータチェス選手権の優勝プログラム
-------------------------------



6. トップチェスエンジン選手権
----------------

トップチェスエンジン選手権