Loading article…
コンピュータチェスには、チェスをプレイできるハードウェア（専用コンピュータ）とソフトウェアの両方が含まれます。コンピュータチェスは、対戦相手がいなくても練習できる機会を提供するだけでなく、分析、娯楽、トレーニングの機会も提供します。チェスのグランドマスター以上のレベルでプレイできるコンピュータチェスアプリケーションは、スーパーコンピュータからスマートフォンまで、さまざまなハードウェアで利用可能です。スタンドアロンのチェスプレイマシンも利用できます。Stockfish 、Leela Chess Zero、GNU Chess、Fruitなどの無料のオープンソースアプリケーションが、さまざまなプラットフォームで利用可能です。
コンピュータチェスアプリケーションは、ハードウェアで実装されているかソフトウェアで実装されているかにかかわらず、人間とは異なる戦略を用いて手を選択します。現在の局面から一連の手を表すツリーを構築、探索、評価するためにヒューリスティックな手法を用い、プレイ中に最良の手順を実行しようとします。このようなツリーは通常、数千から数百万のノードを持つ非常に大きなものです。毎秒数万から数十万、あるいはそれ以上のノードを処理できる現代のコンピュータの計算速度と、ツリーを関連性の高いノードに絞り込む拡張および縮小ヒューリスティックによって、このようなアプローチは効果的になります。
チェスやチェスに似たゲームをプレイできる最初のチェスマシンは、真空管コンピュータ時代の初期（1950年代）にデジタルコンピュータ上で動作するソフトウェアプログラムでした。初期のプログラムは非常にプレイが下手で、初心者でも勝つことができました。40年後の1997年には、スーパーコンピュータや専用ハードウェア上で動作するチェスエンジンが、最高の人間プレイヤーさえも打ち負かすことができるようになりました。2006年までに、デスクトップPC上で動作するプログラムも同じ能力を達成しました。2006年、マギル大学のコンピュータサイエンス教授であるモンティ・ニューボーンは、「科学は完了した」と宣言しました。しかし、チェスには極めて多くのバリエーションが存在するため、現代のコンピュータでチェスを解くことは現在不可能です。[ 1 ]
コンピュータチェスはかつて「AIのショウジョウバエ」、知識工学の最先端と考えられていた。現在ではこの分野は科学的に完成したパラダイムとみなされており、チェスをプレイすることはありふれたコンピューティング活動となっている。[ 2 ]
かつては、スタンドアロンのチェスマシン（通常はソフトウェアチェスプログラムを実行するマイクロプロセッサ、まれに専用ハードウェア）が販売されていました。今日では、チェスエンジンは、スマートフォンやPCなどの一般的なデバイスにソフトウェアとしてインストールできます[ 3 ] 。単独でインストールすることも、ChessbaseやChess.comおよびLichess（どちらも主にWebサイト）のモバイルアプリなどのGUIプログラムと併用することもできます[ 4 ] 。無料のオープンソースエンジンの例としては、 Stockfish [ 5 ]やLeela Chess Zero [ 6 ]（Lc0）などがあります。Chess.comは、Torchという独自のエンジンを維持しています[ 7 ] 。Stockfishを含む一部のチェスエンジンには、WebAssemblyやJavaScriptなどの言語で作成されたWeb版があります[ 8 ]。ほとんどのチェスプログラムやサイトは、チェスエンジンを使用して局面やゲームを分析する機能を提供しており、一部のプログラムやサイトは、通常の対戦相手のようにエンジンと対戦する機能を提供しています（カスタムレベルの強さでプレイするように設定できます）。
チェスエンジンのハードウェア要件は最小限ですが、パフォーマンスはプロセッサ速度と、大きな転置テーブルを保持するために必要なメモリによって異なります。Stockfish などの最新のチェスエンジンのほとんどは、CPU上でのみ実行されるように調整された、効率的に更新可能なニューラルネットワークに依存していますが、[ 9 ] [ 10 ] Lc0 はGPUパフォーマンスに依存するネットワークを使用しています。[ 11 ] [ 12 ] Stockfish などのトップエンジンは、コンシューマーグレードのハードウェアで実行されている場合でも、世界最高のプレイヤーに確実に勝つことが期待できます。[ 13 ]
おそらく最も一般的なチェスソフトウェアは、単にチェスをプレイするプログラムでしょう。人間プレイヤーが盤上で駒を動かすと、AIが次の手を計算してプレイし、ゲームが終了するまで人間とAIが交互にターンを行います。駒の動きを計算するチェスエンジンとグラフィカルユーザーインターフェース（GUI）は、別々のプログラムである場合もあります。GUIには異なるエンジンを接続することで、さまざまなスタイルの対戦相手とプレイできます。エンジンは多くの場合、シンプルなテキストコマンドラインインターフェースを備えていますが、GUIはさまざまな駒セット、盤面スタイル、さらには3Dやアニメーションの駒を提供する場合があります。最近のエンジンは非常に高性能であるため、エンジンまたはGUIは、人間プレイヤーの勝率を高めるために、エンジンの能力を制限する方法を提供する場合があります。FritzやRybkaなどのUniversal Chess Interface （UCI）エンジンには、エンジンのEloレーティングを下げるための組み込みメカニズム（UCIのuci_limitstrengthおよびuci_eloパラメータ経由）が備わっている場合があります。 Fritzのバージョンによっては、現在のエンジンの性能を制限したり、ミス率を変更したり、プレイスタイルを変更したりできるハンディキャップモードやファンモードが搭載されています。また、 Fritzにはフレンドモードもあり、ゲーム中にプレイヤーのレベルに合わせてプレイしようとします。
チェスデータベースを使用すると、ユーザーは膨大な数の過去のゲームを検索し、分析し、統計を確認し、オープニングレパートリーを策定できます。Chessbase (PC 用)はプロのプレイヤーの間でこれらの目的でよく使用されるプログラムですが、Windows、Mac、Linux 用のShane の Chess Information Database (Scid) [ 14 ] 、 PC 用のChess Assistant [ 15 ] [ 16 ] 、 Android 用の Gerhard Kalab の Chess PGN Master [ 17 ]、iOS 用の Giordano Vicoli の Chess-Studio [ 18 ]などの代替プログラムもあります。
Playchessのようなプログラムを使えば、プレイヤーはインターネット経由で互いに対戦することができる。
チェストレーニングプログラムはチェスを教えます。Chessmasterには、IMジョシュ・ウェイツキンとGMラリー・クリスチャンセンによるプレイスルーチュートリアルがあります。ステファン・マイヤー＝カーレンは、ロブ・ブルニアとコー・ヴァン・ウィガーデンのStepコースブックに基づいたShredder Chess Tutorを提供しています。元世界チャンピオンのマグナス・カールセンのPlay Magnus社は、 AndroidとiOS向けのMagnus Trainerアプリをリリースしました。Chessbaseには、子供向けのFritzとChessterがあります。Convektaは、GMアレクサンダー・カリニンとマキシム・ブロフのチュートリアルに基づいたCT-ARTやChess Kingシリーズなど、多数のトレーニングアプリを提供しています。
1957年に反駁スクリーニング（アルファベータ枝刈りを応用して指し手の評価を最適化する手法）を発見した後、カーネギーメロン大学の研究チームは、1967年までにコンピュータが人間の世界チャンピオンを打ち負かすだろうと予測した。[ 19 ]しかし、指し手を評価する正しい順序を決定することの難しさは予測していなかった。研究者たちは、他の分岐を評価する際に再検討すべき異常に高得点の指し手であるキラーヒューリスティックを特定するプログラムの能力を向上させるために努力したが、1970年代に入っても、ほとんどのトップチェスプレイヤーは、コンピュータがすぐにマスターレベルでプレイできるようになることはないだろうと考えていた。[ 20 ] 1968年、国際マスターのデイビッド・レヴィは、 10年以内にチェス・コンピューターが自分に勝つことはできないだろうという有名な賭けをした。 [ 21 ]また、1976年には、シニア・マスターでありインディアナ大学の心理学教授であるエリオット・ハーストが、「現在のコンピューター・プログラムがマスター・プレイヤーに1ゲームでも勝つ唯一の方法は、マスターが、おそらく50ゲームを同時にプレイしながら泥酔状態で、1年に1度あるかないかのミスを犯すことだろう」と書いた。[ 20 ]
1970年代後半、チェスプログラムは高度なスキルを持つ人間のプレイヤーを打ち負かし始めた。[ 20 ]ハーストの声明が出された年、ノースウェスタン大学のチェス4.5は、ポール・マッソン・アメリカ・チェス選手権のクラスBレベルで、人間が出場するトーナメントで初めて優勝した。レヴィは1978年にチェス4.7を破って賭けに勝ったが、チェス4.7は6局のうち1局に勝利し、トーナメントレベルでマスタークラスのプレイヤーに対する最初のコンピュータ勝利を達成した。[ 21 ] 1980年、ベルはマスターを頻繁に破り始めた。1982年までに、2つのプログラムがマスターレベルでプレイし、3つはそれよりやや劣っていた。[ 20 ]
理論的なブレークスルーなしに突然改善が見られたのは予想外だった。ベルが毎秒 10 万の局面（約 8 プライ）を調べる能力で十分だとは、多くの人が予想していなかったからだ。成功したマイクロコンピュータ プログラムSargonの開発者であるスプラックレン兄弟は、改善の 90% は評価速度の向上によるもので、評価の改善によるものは 10% だけだと推定した。ニュー サイエンティストは1982 年に、コンピュータは「ひどいチェスをプレイする…不器用で、非効率的で、散漫で、ただただ醜い」と述べたが、人間は「恐ろしいミス、驚くべき過ち、理解不能な見落とし、重大な誤算など」を、自分たちが思っているよりもはるかに頻繁に犯してコンピュータに負けている。「要するに、コンピュータは主に人間のイニシアチブにおける誤算を見つけて利用する能力によって勝つ」のだ。[ 20 ]
1982年までに、マイクロコンピュータのチェスプログラムは1秒間に最大1,500手まで評価できるようになり、5年前のメインフレームのチェスプログラムと同等の強さになり、アマチュアプレイヤーの大多数を打ち負かすことができた。1970年代半ばのデビュー時よりも1、2手先までしか先読みできなかったが、それによって専門家の予想以上にプレイが向上した。一見些細な改善が「心理的な閾値を超えることを可能にしたようで、その後は人間のミスの豊富な収穫にアクセスできるようになる」とニューサイエンティストは書いている。[ 20 ] 1984年にSPOCをレビューしたBYTEは、「コンピュータ（メインフレーム、ミニ、マイクロ）は醜く、洗練されていないチェスをプレイする傾向がある」と書いたが、ロバート・バーンの「戦術的には平均的な人間のプレイヤーよりもミスが少ない」という発言に言及した。同誌はSPOCをIBM PC向けの「最先端のチェスプログラム」であり、「驚くほど高い」レベルのプレイが可能だと評し、USCFレーティングを1700（クラスB）と推定した。[ 22 ]
1982年の北米コンピュータチェス選手権で、モンロー・ニューボーンはチェスプログラムが5年以内に世界チャンピオンになる可能性があると予測し、トーナメントディレクターで国際マスターのマイケル・ヴァルヴォは10年、スプラックレン兄弟は15年、ケン・トンプソンは20年以上と予測し、その他は絶対に起こらないと予測した。しかし、最も広く受け入れられている意見は、2000年頃に起こるというものだった。 [ 23 ] 1989年、レヴィはエキシビションマッチでディープソートに敗れた。しかし、ディープソートは、当時の世界チャンピオンであるガルリ・カスパロフが1989年に2回の力強い勝利で示したように、世界選手権レベルにはまだかなり及ばなかった。カスパロフがトーナメント時間コントロールでコンピュータに初めて負けたのは、 1996年のディープブルー対カスパロフ、第1ゲームでIBMのディープブルーとの対戦までなかった。実際、この対局は、現役世界チャンピオンが通常の持ち時間制の対局でコンピューターに敗れた初めてのケースだった。しかし、カスパロフは態勢を立て直し、残りの5局のうち3局に勝利し、 2局を引き分け、見事な勝利を収めた。
1997年5月、改良版のディープ・ブルーが再戦でカスパロフを3勝2敗で破った。この対決を主に扱ったドキュメンタリー映画『ゲームオーバー：カスパロフと機械』が2003年に制作された。
処理能力の向上と評価機能の改善により、市販のワークステーションで動作するチェスプログラムは、トップレベルのプレイヤーに匹敵するようになった。1998年、Rebel 10は、当時世界ランキング2位だったヴィスワナサン・アナンドを5対3で破った。しかし、これらのゲームのほとんどは通常の持ち時間で行われたものではなかった。8つのゲームのうち、4つはブリッツゲーム（各手に5分＋フィッシャーディレイ5秒）で、Rebelが3対1で勝利した。2つはラピッドゲーム（各サイドに15分）で、Rebelが1.5対1.5で勝利した。最後に、2つのゲームは、通常のトーナメントゲームとして、クラシックな持ち時間（2時間で40手、1時間のサドンデス）で行われた。ここでは、アナンドが1.5対1.5で勝利した。[ 24 ]高速ゲームではコンピュータが人間より優れたプレイをしたが、プレイヤーのレーティングが決定されるクラシックな持ち時間では、その優位性はそれほど明確ではなかった。
2000年代初頭には、JuniorやFritzといった市販のプログラムが、元世界チャンピオンのガルリ・カスパロフやクラシック世界チャンピオンのウラジーミル・クラムニクとの対局で引き分けに持ち込むことができた。
2002年10月、ウラジーミル・クラムニクとディープ・フリッツは、8局制の「ブレインズ・イン・バーレーン」対局で対戦し、引き分けに終わった。クラムニクは第2局と第3局を「従来型の」対コンピュータ戦術、つまりコンピュータがゲームツリー探索で見つけられない長期的な優位性を得るために保守的にプレイすることで勝利した。しかし、第5局はクラムニクの重大なミスによりフリッツが勝利した。第6局は、大会解説者によって「壮観」と評された。序盤から中盤にかけて優勢だったクラムニクは、強力な戦術的攻撃を仕掛けるために駒の犠牲を試みた。これは、そのような攻撃に対する防御に最も強いコンピュータに対しては非常にリスクの高い戦略として知られている。予想通り、フリッツは完璧な防御を見つけ、クラムニクの攻撃は失速し、彼は不利な局面となった。クラムニクは局面が負けだと判断して投了した。しかし、試合後の人間とコンピューターによる分析では、フリッツ・プログラムが勝利を収めることはまず不可能であり、クラムニクは事実上引き分けを犠牲にしたことが明らかになった。最後の2局は引き分けだった。こうした状況を踏まえると、ほとんどの解説者は依然としてクラムニクの方がこの対局で優勢だったと評価している。
2003年1月、カスパロフはニューヨーク市で、別のチェス・コンピューター・プログラムであるジュニアと対戦した。試合は3対3の引き分けに終わった。
2003年11月、カスパロフはX3Dフリッツと対戦した。試合は2対2の引き分けに終わった。
2005年、カスタムハードウェアと64個のプロセッサを備えた専用チェスコンピュータであり、2005年の第14回IPCCCの優勝者でもあるHydraは、6局マッチで7位のマイケル・アダムスを5½対½で破った（ただし、アダムスの準備は2002年のシリーズでのクラムニクの準備よりもはるかに不十分だった）。[ 25 ]
2006年11月から12月にかけて、世界チャンピオンのウラジーミル・クラムニクはディープ・フリッツと対戦した。今回はコンピューターが勝利し、試合は2勝4敗で終了した。クラムニクはコンピューターのオープニングブックを見ることができた。最初の5局で、クラムニクは典型的な「コンピューター対策」の局面勝負に持ち込んだ。彼は1局を落とし（そのうち1局でチェックメイトを見落とした）、次の4局は引き分けた。最終局では、試合を引き分けに持ち込もうと、クラムニクはより攻撃的なシシリアン・ディフェンスを採用したが、惨敗した。
2006年のクラムニク対ディープ・フリッツ戦の結果、人間とコンピュータのチェス競技への関心が急落するのではないかという憶測があった。[ 26 ]例えばニューボーンによれば、「科学は終わった」とのことである。[ 27 ]
人間とコンピュータのチェス対局では、1990年代後半に最高のコンピュータシステムが人間のチェスチャンピオンを追い抜いたことが示されました。それ以前の40年間は、最高の機械がEloレーティングで年間約40ポイント上昇するのに対し、最高の人間は年間約2ポイントしか上昇しないという傾向がありました。[ 28 ]人間との競争でコンピュータが獲得した最高レーティングは、1988年のDeep ThoughtのUSCFレーティング2551で、FIDEはもはやレーティングリストに人間とコンピュータの結果を載せていません。機械専用のEloプールがレーティングマシン用に作成されていますが、これらの数値は見た目は似ていますが、直接比較されることはありません。[ 29 ] 2016年、スウェーデンチェスコンピュータ協会はコンピュータプログラムKomodoを3361と評価しました。
チェスエンジンは改良を続けている。2009年には、低速なハードウェアで動作するチェスエンジンがグランドマスターレベルに達した。携帯電話がパフォーマンスレーティング2898でカテゴリー6のトーナメントで優勝した。携帯電話HTC Touch HDのPocket Fritz 4内で動作するチェスエンジンHiarcs 13は、2009年8月4日から14日にかけてアルゼンチンのブエノスアイレスで開催されたコパ・メルコスールトーナメントで9勝1引き分けで優勝した。 [ 30 ] Pocket Fritz 4は1秒あたり2万未満の局面を探索する。[ 31 ]これは、パフォーマンスレーティング2880で1秒あたり2億の局面を探索するDeep Blueなどのスーパーコンピュータとは対照的である。
アドバンストチェスは、1998年にカスパロフによって開発されたチェスの一種で、人間同士が対戦し、両者ともコンピュータを利用して自身の能力を強化する。カスパロフは、この「アドバンスト」プレイヤーは、人間単独、あるいはコンピュータ単独よりも強いと主張した。これは、フリースタイルチェスの大会など、数多くの場面で証明されている。
今日のプレイヤーは、チェスエンジンを対戦相手ではなく分析ツールとして扱う傾向がある。[ 32 ]チェスのグランドマスター、アンドリュー・ソルティスは2016年に「コンピューターはあまりにも優秀すぎる」と述べ、世界チャンピオンのマMagnus Carlsen はコンピューターチェスをしない理由として「彼はいつも負けてしまうし、ゲームに参加すらせずに負けることほど落ち込むことはない」と述べている。[ 33 ]
20世紀初頭、ルークとキングのエンドゲームをプレイする機械式チェスや、ヘックスなどの他のゲームをプレイする電気式チェスが登場して以来、科学者や理論家は、人間がどのように知識を学び、記憶し、考え、応用するかを手続き的に表現しようと試みてきました。そして、チェスというゲームは、その圧倒的な複雑さゆえに、「人工知能（AI）のショウジョウバエ」となりました。 [注1 ]複雑さの手続き的解決は思考と同義となり、チェス自動人形の時代以前の初期のコンピュータは、一般的に「電子頭脳」と呼ばれていました。20世紀後半から、チェス（およびチェッカーなどの他のゲーム）をプレイする際に適用される知識と思考を表現するために、いくつかの異なるスキーマが考案されました。
人間のチェスプレイヤーは、「目的と手段」のヒューリスティックを用いることで、必要な手数に関係なく、最適な結果とそれを達成する方法を直感的に判断できますが、コンピュータは体系的に分析する必要があります。ほとんどのプレイヤーは、必要に応じて少なくとも5手先（10プライ）まで先を読むことが、うまくプレイするために必要であることに同意しています。通常のトーナメントルールでは、各プレイヤーは1手あたり平均3分が与えられます。平均して、1つのチェスの局面には30以上の合法的な手があるため、コンピュータが10プライ（5手）先を読むには、1000兆通りの可能性を検討する必要があります。1秒間に100万の局面を検討できるコンピュータでも、30年以上かかるでしょう。[ 20 ]
チェスのプレイを手続き的に表現しようとする初期の試みはデジタル電子時代以前に行われたが、そのような複雑さを計算する余地を与えたのは、プログラム内蔵型のデジタルコンピュータであった。クロード・シャノンは1949年に、チェスのアルゴリズム的解法の原理を概説した。その論文では、ゲームは「木」、つまり手に対応する選択（枝）のデジタルデータ構造で表現される。木のノードは、手の選択によって生じる盤上の局面である。最初の手から最後の手まで木を構築してチェスのゲーム全体を表現することは不可能であることはすぐに明らかになった。チェスでは局面ごとに平均36手あり、平均的なゲームは投了まで約35手（チェックメイト、ステイルメイト、または引き分けの場合は60～80手）続く。各プレイヤーの最初の手の後には400通りの局面があり、それぞれ2手後には約20万通り、 わずか3手後には1億2000万近くの局面がある。
そこで、ある程度の深さまで限定的に先読み（探索）を行い、その後、ドメイン固有の知識を用いて結果として得られる最終局面を評価するという方法が提案された。両者が適切な手を指した場合、一種の中間的な局面が得られ、その評価によってプレイヤーは選択した手が良し悪しを判断できる。ツリー上での探索や比較操作はコンピュータ計算に適していたが、評価関数における微妙なチェスの知識の表現は適していなかった。初期のチェスプログラムは、この両方の点で問題を抱えていた。広大なツリーを探索するには、利用可能な計算リソースをはるかに超える計算リソースが必要であり、どのようなチェスの知識が有用で、どのように符号化すべきかが判明するまでには数十年を要した。
チェスをプレイするコンピュータシステムの開発者は、いくつかの基本的な実装上の問題について決定を下さなければなりません。これには以下が含まれます。
アドリアーン・デ・グロートは、様々なレベルのチェスプレイヤーにインタビューを行い、熟練者も初心者も、指す手を決める前に40～50局面ほど検討しているという結論に至った。熟練者がはるかに優れているのは、経験から培われたパターン認識能力を駆使しているからである。これにより、劣っていると思われる手は考慮しないことで、他の局面よりもはるかに深く特定の局面を分析することができる。このことを裏付ける証拠として、優れたプレイヤーは実際のチェスゲームの局面を、同じ駒の完全なランダムな配置ではなく、少数の認識可能なサブ局面に分解して記憶する方がはるかに容易であることが挙げられる。対照的に、下手なプレイヤーはどちらの局面についても記憶力は同じレベルである。
コンピュータチェスにおけるこれに相当するのは、人間のプレイヤーのパターン認識能力に対応する葉評価の評価関数と、人間のプレイヤーの経験構築に対応するテクセルチューニング、確率的勾配降下法、強化学習などの機械学習技術を用いたそれらの訓練です。これにより、現代のプログラムは、人間のプレイヤーと同様に、前方剪定やその他の選択的ヒューリスティックを用いて、評価関数によって不適切と判断された手を単純に考慮しないことで、他の手よりもはるかに深く特定の手順を分析することができます。この点において、コンピュータプログラムと人間の唯一の根本的な違いは、コンピュータプログラムは人間のプレイヤーよりもはるかに深く探索できるため、人間のプレイヤーでは不可能なほど多くのノードを探索し、視野の限界効果をはるかに回避できるという点です。
コンピュータチェスプログラムは、通常、いくつかの一般的な事実上の標準規格をサポートしています。今日のプログラムのほぼすべては、ゲームの手順をポータブルゲーム記譜法（PGN）で読み書きでき、個々の局面をフォーサイス・エドワーズ記譜法（FEN）で読み書きできます。古いチェスプログラムは長い代数記譜法しか理解できないことが多かったのですが、今日ではユーザーはチェスプログラムが標準的な代数式チェス記譜法を理解することを期待しています。
1990年代後半から、プログラマーは、局面における最善の手を計算するコマンドラインインターフェースを備えたエンジンと、プレイヤーが見ることができるチェス盤と動かせる駒を提供するグラフィカルユーザーインターフェース（GUI）を別々に開発し始めました。エンジンは、チェスエンジン通信プロトコル（CECP）やユニバーサルチェスインターフェース（UCI）などのプロトコルを使用して、GUIに指し手を伝達します。チェスプログラムをこれら2つの部分に分割することで、開発者はプログラムの両方の部分を書く必要なく、ユーザーインターフェースのみ、またはエンジンのみを書くことができます。（チェスエンジンも参照。）
開発者は、エンジンをオープニングブックやエンドゲームテーブルベースに接続するか、あるいはそれをGUIに任せるかを決定する必要がある。
各チェスの局面を表すために使用されるデータ構造は、指し手の生成と局面評価のパフォーマンスに大きく影響します。方法としては、配列に格納された駒（「メールボックス」と「0x88」）、リストに格納された駒の位置（「駒リスト」）、駒の位置を表すビットセットの集合（「ビットボード」）、およびコンパクトな長期保存のためのハフマン符号化された局面などがあります。
コンピュータチェスプログラムは、チェスの動きをゲームツリーとして捉えます。理論的には、すべての動き、それらの動きに対するすべての反撃、さらにそれらに対するすべての反撃、といった具合に、プレイヤーが行う個々の動きを「プライ」と呼びながら、順に調べていきます。この評価は、一定の最大探索深度に達するか、プログラムが最終的な「葉」の位置（例えばチェックメイト）に到達したと判断するまで続きます。
コンピュータチェスで使用される探索アルゴリズムの一種にミニマックス探索アルゴリズムがあります。これは、各手番でプレイヤーの「最善」の手を選択するアルゴリズムで、一方のプレイヤーはスコアを最大化しようとし、もう一方のプレイヤーはスコアを最小化しようとします。この交互のプロセスにより、局面の探索値を表す評価値を持つ特定の終端ノードに到達します。その値はルートまで遡って計算され、その評価値が盤面上の局面の評価値となります。この探索プロセスはミニマックスと呼ばれます。
ミニマックスアルゴリズムを単純に実装した場合、実用的な時間内に探索できる深さは限られるため、最適な手を探す速度を大幅に向上させるための様々な手法が考案されてきた。アルファベータ枝刈りは、考えられる探索結果の上限と下限を定義し、その境界が一致するまで探索を続けるシステムであり、プログラムの探索空間を削減するために一般的に用いられる。
さらに、静止探索、前方剪定、探索拡張、探索縮小といった様々な選択的探索ヒューリスティックも使用されます。これらのヒューリスティックは、明らかに悪い手（過去の手）を除外したり、興味深いノード（チェック拡張、7段目のパスドポーンなど）を調査したりするために、特定の条件に基づいて実行されます。ただし、これらの選択的探索ヒューリスティックは非常に慎重に使用する必要があります。プログラムが過度に拡張すると、興味のない局面を調べるのに多くの時間を浪費してしまいます。剪定や縮小が多すぎると、興味深いノードが切り捨てられるリスクがあります。
モンテカルロ木探索（MCTS）は、探索空間のランダムサンプリングに基づいて探索木を拡張するヒューリスティック探索アルゴリズムです。コンピュータチェスでよく使用されるモンテカルロ木探索の一種に、木に適用される予測値と信頼上限境界（PUCT）があります。
DeepMindのAlphaZeroとLeela Chess Zeroは、ミニマックス法ではなくMCTSを使用しています。これらのエンジンは、評価関数とポリシー（指し手の選択）を計算するためにグラフィックス処理ユニット（GPU）上でバッチ処理を使用するため、GPU上での計算は本質的に並列処理であることから、並列探索アルゴリズムが必要となります。コンピュータチェスで使用されるミニマックス法とアルファベータ法は本質的に逐次処理アルゴリズムであるため、GPU上でのバッチ処理には適していません。一方、MCTSは優れた代替手段となります。モンテカルロ木探索で使用されるランダムサンプリングは並列計算に適しており、GPU上での計算をサポートするほぼすべてのエンジンがアルファベータ法ではなくMCTSを使用しているのはそのためです。
チェスプログラムを強化するために、他にも多くの最適化手法が利用できます。例えば、転置テーブルは、以前に評価された局面を記録し、再計算の手間を省くために使用されます。反駁テーブルは、良い手と思われる手を「反駁」する重要な手を記録します。これらの手は、通常、様々な局面で最初に試されます（ある局面を反駁する手は、別の局面も反駁する可能性が高いからです）。欠点は、転置テーブルが深いプライ深度では、数千万から数億のエントリを持つ非常に大きなものになる可能性があることです。例えば、1996年のIBMのディープブルーの転置テーブルは5 億エントリでした。転置テーブルが小さすぎると、見つかったエントリによって節約される時間よりも、スレッシングによって存在しないエントリを探すのに多くの時間を費やすことになります。多くのチェスエンジンは、人間のように相手の時間を使ってより深いレベルまで探索する「熟考」を利用して、プレイの強さを高めています。
もちろん、ハードウェアの高速化とメモリの増設は、チェスプログラムの性能向上につながります。プログラムがシングルコアまたは少数のコアで動作している場合、ハイパースレッディングアーキテクチャによってパフォーマンスがわずかに向上する可能性があります。最新のプログラムの多くは、マルチコアを活用して並列探索を行うように設計されています。また、汎用コンピュータ上で動作し、指し手の生成、並列探索、または評価を専用プロセッサまたは専用コプロセッサに割り当てるように設計されたプログラムもあります。
チェスの探索に関する最初の論文は、1950年にクロード・シャノンによって発表されました。[ 34 ]彼は、コンピュータにチェスをプレイさせるプログラムが作られる前に、使用されるであろう2つの主要な探索戦略を予測し、それらを「タイプA」と「タイプB」と名付けました。 [ 35 ]
タイプAのプログラムは「総当たり」アプローチを採用し、純粋なナイーブミニマックスアルゴリズムを使用して、固定された手数で考えられるすべての局面を調べます。シャノンは、このアプローチは2つの理由から非現実的だと考えました。
まず、実際の局面ではおよそ30手が可能なため、チェスコンピュータが毎秒100万局面を評価するという「非常に楽観的な」場合でも、両者が3手先（6プライ）を探索する際に必要となる約10⁹局面を探索するには約16分かかると予想した。（この速度を達成するのに約40年かかった。）後にアルファベータ剪定と呼ばれる探索アルゴリズムが登場し、可能な探索結果の上限と下限を定義し、その境界が一致するまで探索を続けるシステムによって、ゲームツリーの分岐係数は対数的に減少したが、それでも当時のチェスプログラムではツリーの指数関数的な爆発を利用することは不可能だった。
第二に、静止状態の問題を無視し、駒の交換やその他の重要な一連の動き（「ライン」）の終わりにある局面のみを評価しようとした。彼は、これに対処するためにミニマックス法を適応させると、調べる必要のある局面の数が大幅に増加し、プログラムがさらに遅くなると予想した。彼は、これに対処するためにタイプAを適応させると、調べる必要のある局面の数が大幅に増加し、プログラムがさらに遅くなると予想した。
これは自然と「選択的探索」または「タイプB探索」と呼ばれるものにつながった。これはチェスの知識（ヒューリスティクス）を用いて、各局面からおそらく良いと思われる手をいくつか選択して探索し、それ以外の手は探索せずに除外するものである。シャノンは、悪い手や取るに足らない手を調べるために処理能力を浪費する代わりに、タイプBプログラムでは次の2つの改善点を用いると提案した。
これにより、妥当な時間内に最も重要な局面をより深く（より遠くまで）見通すことができるようになるはずだった。しかし、初期の選択的探索の試みでは、最良の手がしばしば除外されてしまった。その結果、この最初の選択的探索パラダイムが支配的だった次の25年間は、ほとんど進歩が見られなかった。この初期に作成された最高のプログラムは、1967年のMac Hack VIで、平均的なアマチュアとほぼ同じレベル（米国チェス連盟のレーティングスケールでCクラス）でプレイした。
一方、ハードウェアの性能は向上し続け、1974年にはノースウェスタン大学のチェス4.0プログラムで初めて総当たり探索が実装されました。この手法では、ノードにおけるすべての代替手が探索され、どれも除外されません。彼らは、すべての手を単純に探索するのに必要な時間が、知識集約型のヒューリスティックを適用してその中から少数の手を選択するのに必要な時間よりもはるかに短いことを発見しました。また、良い手を時期尚早に、あるいは意図せず除外してしまうことがないため、パフォーマンスが大幅に向上するという利点もありました。
1980年代と1990年代には、静止探索、ヌル移動剪定、その他の現代的な選択的探索ヒューリスティックの開発により、選択的探索パラダイムにおいてついに進歩が見られました。これらのヒューリスティックは、以前のヒューリスティックよりもはるかに誤りが少なく、より深く探索できるため、節約できる追加時間に見合う価値があると判断され、多くのエンジンで広く採用されました。多くの現代のプログラムは、探索アルゴリズムの基盤としてアルファベータ探索を使用していますが、現代のプログラムで使用されるこれらの追加の選択的探索ヒューリスティックは、プログラムがもはや「総当たり」探索を行わないことを意味します。代わりに、プログラムは、これらの選択的探索ヒューリスティックに大きく依存して、プログラムが良いと考える行を拡張し、プログラムが悪いと考える行を剪定および削減し、探索ツリーのほとんどのノードが剪定されるまで、探索ツリーのほとんどのノードが剪定され、現代のプログラムが非常に深く探索できるようになります。
2006年、レミ・クーロンは、タイプBの選択的探索の一種であるモンテカルロ木探索を開発しました。2007年、レヴェンテ・コチスとチャバ・セペシュヴァーリは、モンテカルロ木探索の改良版である「木に適用された上限信頼区間」（略してUCT）を開発しました。2011年、クリス・ロジンは、UCTのバリエーションである「予測器＋木に適用された上限信頼区間」（略してPUCT）を開発しました。PUCTはその後、 2017年にAlphaZeroで、そして2018年にはLeela Chess Zeroで使用されました。
1970年代、ほとんどのチェスプログラムはControl Data Cyber 176やCray-1といったスーパーコンピュータ上で動作しており、コンピュータチェスの開発期においては処理能力が性能の制約要因であったことを示している。当時のチェスプログラムは、3手以上の深さまで探索することに苦労していた。プロセッサの速度と評価関数に組み込まれた知識との関係が明らかになったのは、1980年代にハードウェアチェスマシンが登場してからである。
コンピュータの処理速度を2倍にすると、対局の強さが約50～70Eloポイント向上すると推定されている（Levy & Newborn 1991 :192）。
ほとんどのチェスの局面において、コンピュータは考えられるすべての最終局面を事前に予測することはできません。そのため、数手先まで予測し、考えられる局面（リーフと呼ばれる）を比較する必要があります。リーフを評価するアルゴリズムは「評価関数」と呼ばれ、チェスプログラムによって大きく異なる場合がよくあります。評価関数は通常、局面をポーンの100分の1（センチポーンと呼ばれる）単位で評価し、慣例として、プラスの評価は白に有利、マイナスの評価は黒に有利となります。ただし、評価関数によっては、センチポーンの代わりに勝率、引き分け率、敗率を出力するものもあります。
歴史的に、手作業で作成された評価関数は、駒の価値と、各側の強さに影響を与える他の要素を考慮します。各側の駒の価値を計算する際、駒の典型的な値は、ポーンが1ポイント、ナイトまたはビショップが3ポイント、ルークが5ポイント、クイーンが9ポイントです。（チェスの駒の相対的価値を参照）。キングには、チェックメイトが他のすべての要素を上回ることを確実にするために、200ポイントなどの恣意的に高い値が与えられることがあります（シャノンの論文）。 （Levy & Newborn 1991 :45）。駒のポイントに加えて、ほとんどの手作業で作成された評価関数は、ポーン構造、ビショップのペアが通常より高い価値を持つこと、中央に配置された駒が高い価値を持つことなど、多くの要素を考慮に入れています。キングの保護と、ゲームのフェーズ（オープニング、ミドル、エンドゲーム）も通常考慮されます。テクセル回転法、確率的勾配降下法、強化学習などの機械学習技術は、通常、手作業で作成された評価関数を最適化するために使用されます。
現代の評価関数のほとんどはニューラルネットワークを利用しています。現在最も一般的に使用されている評価関数は、効率的に更新可能なニューラルネットワークです。これは、入力が駒とマス目のテーブルである浅いニューラルネットワークです。駒とマス目のテーブルは、チェス盤のマス目に対応する 64 個の値のセットであり、通常、すべての駒と色に対して駒とマス目のテーブルが存在するため、12 個の駒とマス目のテーブル、つまりニューラルネットワークへの 768 個の入力が存在します。さらに、一部のエンジンは、評価関数に深層ニューラルネットワークを使用しています。ニューラルネットワークは通常、強化学習アルゴリズムを使用して、教師あり学習または教師なし学習と組み合わせてトレーニングされます。
評価関数の出力は、センチポーンなどの単位で量子化された単一のスカラー値であり、手作業で作成された評価関数の場合は、前述のさまざまな要素の加重和、ニューラルネットワークベースの評価関数の場合は、ニューラルネットワークのヘッドの出力となります。この評価は、評価対象のノードの下にあるサブツリーの値を、探索が終了（つまりゲーム終了）するまで行われたかのように表現または近似します。探索中、評価は他のリーフの評価と比較され、どちらかの側にとって悪い手や不適切な手を表すノードが除外され、収束によって、両者にとって最良の手となった局面の値を表すノードが得られます。
終盤戦は、必要な探索の深さゆえに、長らくチェスプログラムの大きな弱点の一つであった。他の点ではマスターレベルのプログラムであっても、中級レベルの人間プレイヤーでさえ勝利を収められるような局面で、勝利を手にすることができなかったのだ。
この問題を解決するために、コンピュータを用いて、キングとポーン対キングの局面から始まるチェスの終盤局面を完全に分析する手法が用いられてきた。このような終盤局面の表は、逆算分析の一種を用いて事前に作成される。これは、最終結果が分かっている局面（例えば、片方の側がチェックメイトされている局面）から始め、そこから一手離れた局面、さらにそこから一手離れた局面、といった具合に分析を進めていくものである。ケン・トンプソンはこの分野の先駆者であった。
コンピュータ解析の結果は、時に人々を驚かせた。1977年、トンプソンのチェスマシン「ベル」は、キングとルーク対キングとクイーンのエンドゲーム表ベースを使用し、理論上は負けとなるはずの局面で、複数のマスター相手に引き分けに持ち込むことに成功した（フィリドール局面#クイーン対ルークを参照）。これは、防御側のキングとルークをできるだけ長く近くに保って敗北を遅らせるという通常の戦略に従っていなかったにもかかわらず達成された。プログラムのいくつかの指し手の理由を尋ねられたトンプソンは、プログラムのデータベースが単に最良の手を返しただけだと述べる以外に、明確な説明はできなかった。
ほとんどのグランドマスターは、クイーン対ルークのエンドゲームでコンピュータと対戦することを拒否したが、ウォルター・ブラウンは挑戦を受け入れた。クイーン対ルークの局面が設定され、完璧なプレイをすればクイーンが30手で勝利できる。ブラウンには50手を指すのに2時間半が与えられ、そうでなければ50手ルールに基づいて引き分けとなる。45手後、ブラウンは次の5手以内にチェックメイトを強制することもルークを獲得することもできなかったため、引き分けに同意した。最終局面では、ブラウンはまだチェックメイトまで17手離れていたが、ルークを獲得するまではそれほど遠くなかった。ブラウンはエンドゲームを研究し、1週間後にクイーンが30手で勝利できる別の局面で再びコンピュータと対戦した。今度は、50手でルークを獲得し、勝利の局面を得た。[ 36 ] [ 37 ]
これまで勝利が確実視されていた局面の中には、完璧なプレイを相手にしても、チェスの50手ルールで定められた手数よりも多くの手数を要することが判明したものもあった。そのため、数年間、国際チェス連盟（FIDE）の公式ルールは、こうした終盤戦で許容される手数を増やすように変更された。しばらくすると、ルールはすべての局面で50手に戻された。というのも、こうした局面がさらに発見され、ルールはますます複雑化し、人間が完璧にプレイすることは不可能だったため、人間のプレイには何ら影響がなかったからである。
長年にわたり、エドワード表ベース、デ・コーニング表ベース、ナリモフ表ベースなど、他のエンドゲームデータベース形式がリリースされており、ナリモフ表ベースはRybka、Shredder、Fritzなどの多くのチェスプログラムで使用されています。 6 個の駒のすべての局面の表ベースが利用可能です。[ 38 ] 7 個の駒のエンドゲームのいくつかは、Marc Bourzutschky と Yakov Konoval によって分析されています。[ 39 ]モスクワのロモノーソフ スーパーコンピュータを使用するプログラマーは、7 個以下の駒のすべてのエンドゲームのチェス表ベースを完成させました (6 つの白の駒と 1 つの黒のキングなど、自明なエンドゲームの局面は除外されています)。[ 40 ] [ 41 ]これらのエンドゲームデータベースのすべてにおいて、キャスリングはもはや不可能であると想定されています。
多くのテーブルベースは、50手ルールを考慮していません。このルールでは、駒の取り合いやポーンの動きがないまま50手経過した場合、どちらのプレイヤーも引き分けを主張できます。そのため、テーブルベースは、50手ルールによって実際には引き分けとなる局面で、「66手で強制チェックメイト」といった結果を返すことがあります。その理由の一つは、チェスのルールが再び変更され、そのような局面で勝利するための時間がさらに長くなった場合でも、すべてのテーブルベースを再生成する必要がないからです。また、テーブルベースを使用するプログラムにとって、この「特徴」に気づいて考慮に入れるのは非常に簡単で、いずれにせよ、エンドゲームテーブルベースを使用する場合は、最短で勝利につながる手を選択します（たとえ完璧なプレイで50手ルールに抵触するとしても）。テーブルベースを使用しない相手と対戦する場合、このような選択は50手以内に勝利する可能性を高めます。
最先端の圧縮技術を使用するナリモフのテーブルベースでは、 5ピースのエンディングすべてをカバーするには7.05 GBのハードディスク容量が必要です。6ピースのエンディングすべてをカバーするには、約1.2 TBが必要です。7ピースのテーブルベースには、50～200 TBのストレージ容量が必要になると推定されています。[ 42 ]
1999年、カスパロフがインターネット上で世界各国の代表とエキシビションマッチを行った際、エンドゲームデータベースが重要な役割を果たした。7ピースのクイーンとポーンのエンドゲームに突入し、世界チームは引き分けを目指して奮闘した。ユージン・ナリモフは、両者ともクイーンを2つずつ持つ6ピースのエンドゲーム表を作成し、両者の分析に大いに役立てた。
最も人気のあるエンドゲームテーブルベースはシジジーで、Stockfish、Leela Chess Zero、Komodoなどのトップクラスのコンピュータプログラムのほとんどで使用されています。また、他の形式よりもサイズがかなり小さく、7ピースのテーブルベースはわずか18.4 TBしか必要としません。[ 43 ]
Stockfishのような最新のチェスエンジンでは、テーブルベースはプレイの強さをほんのわずかに向上させるだけです（Stockfish 15の時点では、6人制のシジジーチェスで約3 Eloポイント）。[ 44 ]
チェスエンジンは、人間と同様に、データベースに保存されているオープニングブックを参照することで、処理時間を節約したり、強いと知られている変化を選択したりすることができます。オープニングブックは、オープニングや変化に応じて深さは異なりますが、通常は最初の10～12手（20～24手）までを網羅しています。コンピュータチェスの初期の時代には、人間のグランドマスターが何十年にもわたって深く研究してきた変化を信頼する方が、20世紀半ばのエンジンの性能の低さよりも優れていました。そして現代においても、コンピュータエンジンが事前に様々なオープニングをじっくりと分析し、対局中にその結果を参照するだけで済むようにすることで、プレイ速度が向上します。
1990年代、当時のチェスエンジンの強みは暗記したオープニングブックと既知の局面に関する知識にあると考える理論家もいたため、チェスプログラムに自力で考えさせるために、意図的に定跡外の手を指すことが有効な対抗策になると考える者もいた。しかし、当時ですら疑わしい仮説だったようで、ガルリ・カスパロフは1997年のディープ・ブルー対ガルリ・カスパロフの第1局で非標準的なミーゼス・オープニングを用いて試みたが、敗北した。この戦術は時が経つにつれてさらに弱体化していった。コンピュータのデータベースに保存されているオープニングブックは、最も準備の整った人間よりもはるかに膨大になり得るため、コンピュータは稀な変化にも十分対応でき、正しい指し方を知っているからである。より一般的に言えば、チェスエンジンは、全く未知の状況（Chess960のようなバリエーションで見られるような状況）においても非常に強力なので、オープニングブックがないことは、戦術的に優れたチェスエンジンにとっては大きな不利にはならず、馴染みのない盤面変化においても正確な強力な手を発見することができる。
現代のエンジントーナメントでは、引き分け率を減らしゲームに多様性を加えるために、エンジンはアンバランスなものを含むさまざまなオープニングから局面をプレイするように指示されることが多い。[ 45 ]
CEGT、[ 46 ] CSS、[ 47 ] SSDF、[ 48 ] WBEC、[ 49 ] REBEL、[ 50 ] FGRL、[ 51 ]および IPON [ 52 ]は、ファンがエンジンの強さを比較できるレーティングリストを維持しています。2020年代初頭のレーティングリストでは、Stockfish、Komodo、Leela Chess Zero、Fat Fritzのさまざまなバージョンが上位を占めています。
CCRL（Computer Chess Rating Lists）は、コンピュータチェスエンジン同士を対戦させることでその強さをテストする組織です。CCRLは、コンピュータ同士の競争を促進し、結果をレーティングリストに集計するために2006年に設立されました。[ 53 ]
この組織は、40/40 (40手ごとに40分)、40/4 (40手ごとに4分)、および40/4 FRC (同じ時間制限だがChess960) の3つの異なるリストを運用しています。[注2 ]熟考 (または常時脳) はオフにされ、Crafty 19.17 BHをベンチマークとして使用して、タイミングは AMD64 X2 4600+ (2.4 GHz) CPUに合わせて調整されます。汎用的で中立的なオープニング ブック(エンジンのブックとは対照的に) が、4 人または 5 人のテーブルベースとともに、ゲーム開始から 12 手までの制限で使用されます。[ 53 ] [ 54 ] [ 55 ]
チェスをプレイする機械を作るというアイデアは18世紀に遡ります。1769年頃、ハンガリーの発明家ファルカス・ケンペレンが作った「トルコ人」と呼ばれるチェスをプレイする自動人形が有名になりましたが、後に偽物であることが暴露されました。デジタルコンピューティングが開発される前は、自律的にチェスをプレイする装置の唯一の成功例は、スペインのエンジニア、レオナルド・トーレス・ケベドが作った「エル・アヘドレシスタ」（1912年）でした。キングとルーク対キングのエンドゲームに限定されていましたが、最初の意思決定自動人形と考えられています。[ 56 ]
それ以来、チェス愛好家やコンピュータエンジニアは、ますます真剣に、そして成功裏に、チェスをプレイする機械やコンピュータプログラムを開発してきた。コンピュータチェスに真剣に取り組んだ数少ないチェスのグランドマスターの一人が、元世界チェスチャンピオンのミハイル・ボトヴィニクで、彼はこのテーマに関する著作をいくつか執筆した。ボトヴィニクのコンピュータチェスへの関心は50年代に始まり、1958年にマックス・ユーウェと共にオランダのテレビで議論したように、シャノンの選択的タイプB戦略に基づくチェスアルゴリズムを好んだ。 1960年代初頭のソビエト連邦で入手可能な比較的原始的なハードウェアを使用していたボトヴィニクは、ソフトウェアによる指し手の選択技術を研究する以外に選択肢がなかった。当時、最も強力なコンピュータだけが3プライの全幅探索を超えることを達成できたが、ボトヴィニクはそのようなマシンを持っていなかった。 1965年、ボトヴィニクは、1967年にジョン・マッカーシー率いるコトク・マッカーシー・プログラムとの通信チェス対決で勝利した米ソコンピュータチェス対決においてITEPチームのコンサルタントを務めた（コトク・マッカーシーを参照）。その後、モスクワの制御科学研究所でチェスプログラムKaissaを作成したチームに助言を与えた。ボトヴィニクは、チェスの達人の思考をモデル化する独自のアイデアを持っていた。1966年にモスクワ中央チェスクラブで攻撃マップと軌道に関する初期のアイデアを発表し議論した後、ウラジーミル・ブテンコを支持者および協力者として見つけた。ブテンコは、軌道を決定する15x15ベクトル攻撃盤表現をM-20コンピュータに初めて実装した。1970年にボトヴィニクがゾーンの概念を導入した後、ブテンコはそれ以上の協力を拒否し、Eurekaと呼ばれる独自のプログラムを書き始めた。 1970年代から80年代にかけて、ボトヴィニクはボリス・スティルマン、アレクサンダー・ユーディン、アレクサンダー・レズニツキー、ミハイル・ツファスマン、ミハイル・チュダコフらを中心とするチームを率いて、人工知能をベースとしたチェスプロジェクト「パイオニア」に取り組んだ。1990年代には、すでに80代になっていたボトヴィニクは、新たなプロジェクト「CCサピエンス」に着手した。
開発上の重要な節目の一つは、チェス・プログラムシリーズを担当し、最初の3回のACMコンピュータ・チェス選手権（1970～72年）で優勝したノースウェスタン大学のチームが、1973年にタイプB探索を放棄したことでした。その結果生まれたプログラム、Chess 4.0は、その年の選手権で優勝し、その後継プログラムは1974年のACM選手権と、同年開催された第1回世界コンピュータ・チェス選手権で2位となり、1975年、1976年、1977年には再びACM選手権で優勝しました。タイプAの実装は、同じくらい高速であることが判明しました。以前はどの手を探索する価値があるかを判断するのにかかっていた時間で、すべての手を探索することが可能になったのです。実際、Chess 4.0は、現在もすべての現代チェス・プログラムが基本的に踏襲しているパラダイムを確立し、それは1965年にロシアのITEPによって成功裏に開始されたものでした。
1978年、ケン・トンプソンのハードウェアチェスマシン「ベル」の初期バージョンが、当時圧倒的な強さを誇っていたノースウェスタン大学チェス4.7を破り、北米コンピュータチェス選手権で優勝した。
処理能力の向上により、総当たり探索はコンピュータチェスの初期開発段階に比べて格段に効率的になった。コンピュータの能力が向上するにつれ、限定的な局面評価と枝刈り技術に支えられた戦術計算を重視したプログラムが、トップレベルの人間プレイヤーと競い合うようになった。チェスにおいては、このアプローチは、コンピュータが人間の思考プロセスを模倣しようとするのではなく、大規模な計算に集中できるようになったことで効果的であることが証明された。1997年、推定5億の局面を毎秒評価できるIBMのディープ・ブルーは、標準時間制の対局で当時の世界チャンピオン、ガルリ・カスパロフを破り、コンピュータがそのような条件下で現世界チャンピオンを破った最初の事例となった。
2016年、NPRは専門家にコンピュータチェスエンジンのプレイスタイルについて説明を求めた。IBMのマーレイ・キャンベルは、「コンピュータには美的感覚がない…どんな局面でも、たとえそれが不条理に見えても、客観的に見て最善だと思う手を指し、どんなに醜い手でも指すことができる」と述べた。グランドマスターのアンドリュー・ソルティスとスーザン・ポルガーは、コンピュータは人間よりも撤退する可能性が高いと述べた。[ 33 ]
ニューラルネットワークは、NeuroChess、Morph、Blondie25、Giraffe、 AlphaZero、MuZeroなどのプログラムによって1980年代後半からチェスエンジンの評価機能に使用されてきましたが、[ 57 ] [ 58 ] [ 59 ] [ 60][61 ]効率的に更新可能なニューラルネットワークが2020年夏に登場するまで、チェスエンジンに広く採用されることはありませんでした。効率的に更新可能なニューラルネットワークは、もともと2018年にYu Nasu氏によってコンピュータ将棋で開発され、 [ 62 ] [ 63 ] 2020年5月31日にStockfishの派生版であるStockfish NNUEに移植され、[ 64 ] 2020年8月6日に公式のStockfishエンジンに統合されました。[ 65 ] [ 66 ]その後、他のチェスプログラマーが開発を開始しました。自社のエンジンにニューラルネットワークを採用する。
王立協会のベンキ・ラマクリシュナン氏など一部の人々は、AlphaZeroがチェスエンジンにおけるニューラルネットワークの普及につながったと考えている。 [ 67 ]しかし、AlphaZeroがニューラルネットワークの使用を開始させたエンジンはごくわずかで、それらはAlphaZero論文を再現するために特別に開発されたLeela Chess Zeroのような新しい実験的なエンジンであった。AlphaZeroの評価関数で使用された深層ニューラルネットワークは高価なグラフィックス処理ユニットを必要としたが、これは既存のチェスエンジンとは互換性がなかった。チェスエンジンの大部分は中央処理装置のみを使用しており、GPU上で情報を計算および処理するには、 NvidiaのCUDAなどのバックエンドの特別なライブラリが必要であったが、どのエンジンもそれにアクセスできなかった。そのため、 KomodoやStockfishといったチェスエンジンの大部分は、2020年にコンピュータ将棋からコンピュータチェスに効率的に更新可能なニューラルネットワークが移植されるまで、手作業で作成された評価関数を使用し続けていました。このニューラルネットワークは、GPUやCUDAのようなライブラリを一切必要としませんでした。しかし、コンピュータチェスで使用されるニューラルネットワークは比較的浅く、 AlphaZeroが先駆的に開発した深層強化学習手法は、コンピュータチェスでは依然として極めて稀です。
これらのチェス対戦システムには、導入時期がおおよそ以下のカスタムハードウェアが含まれています（専用マイクロコンピュータは除く）。
1970年代後半から1990年代初頭にかけて、チェス専用コンピュータの市場は競争が激しかった。しかし、1990年代半ばになると、専用プロセッサを搭載したコンピュータは、パーソナルコンピュータの高速プロセッサに太刀打ちできなくなり、市場は変化した。
最近では、一部の愛好家がマルチエミュレータースーパーシステムを使用して、Fidelity や Hegener & Glaser の Mephisto コンピュータ用に作成されたチェスプログラムを、Windows 10などの最新の 64 ビットオペレーティングシステム上で実行しています。[ 90 ] Rebel の作者であるEd Schröder も、自身が作成した Hegener & Glaser Mephisto の 3 つのプログラムを UCI エンジンとして動作するように改造しました。[ 91 ]
これらのプログラムはMS-DOS上で実行でき、 DOSBoxやQEMUなどのエミュレータを介して64ビットWindows 10上で実行できます。[ 92 ]
著名なコンピュータチェス理論家には以下のような人物がいる。
チェスを完全に解くことは、一般的にかなり難しいと考えられている。初期局面の価値を確実に決定するという弱い意味においても、計算コストの低いチェスを解く方法は存在しないと広く推測されており、したがって、どちらの側にとっても完璧なプレイのための戦略を実際に使用できる形で記述するという強い意味でのチェスを解くという考えは、今日では非現実的であるように思われる。しかし、チェスの局面における最善の手を決定する計算コストの低い方法が存在しないことが証明されているわけではなく、また、現代のコンピュータハードウェア上で動作する従来のアルファベータ探索器が許容できる時間内に初期局面を解くことができないということも証明されていない。後者を証明する難しさは、チェスゲームの過程で起こりうる盤面の数は膨大である（少なくとも 10 43 [ 94 ]から 10 47のオーダー）一方で、初期局面が比較的少ない手数でどちらかの側がチェックメイトまたは3 回繰り返しを強制できる可能性を数学的に確実に排除することが難しいという事実にある。この場合、探索木は可能な局面の集合のごく小さな部分集合しか包含しない可能性がある。一般化チェス（任意の数の駒と任意の大きさのチェス盤でプレイされるチェス）はEXPTIME 完全であることが数学的に証明されている[ 95 ] 。これは、一般化チェスの任意の局面で勝者を決定するには最悪の場合指数時間かかることが証明できることを意味する。しかし、 この理論的な結果は、通常の 8x8 チェスを解くのに必要な作業量の下限を与えない。
マーティン・ガードナーのミニチェスは、約10¹⁸通りの盤面配置が可能な5×5の盤面で行われるゲームで、その解法が確立されました。ゲーム理論上の値は1/2（つまり、どちらの側も引き分けを強制できる）であり、その結果を達成するための強制戦略が記述されています。
反対側でも進展が見られ、2012年時点で、7個以下の駒（キング2個とその他の駒5個以下）によるエンドゲームはすべて解決されている。
「チェスエンジン」とは、与えられた局面において最も強い手を計算し、順序付けるソフトウェアのことです。エンジン開発者は、エンジンの性能向上に注力し、多くの場合、他者が開発したグラフィカルユーザーインターフェース（GUI）にエンジンをインポートするだけです。エンジンは、ステファン・マイヤー＝カーレンとフランツ・フーバーによって開発された、現在では広く普及しているユニバーサルチェスインターフェースなどの標準化されたプロトコルを使用してGUIと通信します。他にも、ティム・マンがGNU ChessとWinboard用に開発したチェスエンジン通信プロトコルなどがあります。Chessbaseは独自のプロトコルを使用しており、かつてはMillennium 2000がChessGenius用に別のプロトコルを使用していました。あるオペレーティングシステムとプロトコル用に設計されたエンジンは、他のOSやプロトコルに移植することができます。チェスエンジンは、専用のチェスエンジントーナメントで定期的に対戦します。
1997年、インターネットチェスクラブは、ウェブブラウザ内で他のユーザーとオンラインでチェスをプレイするための最初のJavaクライアントをリリースしました。[ 96 ] これは恐らく最初のチェスウェブアプリの1つでした。Free Internet Chess Serverは、同様のクライアントをすぐに提供しました。[ 97 ] 2004年、国際通信チェス連盟は、電子メールベースのシステムに代わるウェブサーバーを開設しました。[ 98 ] Chess.comは2007年にライブチェスの提供を開始しました。 [ 99 ] Chessbase / Playchessは以前からダウンロード可能なクライアントを提供しており、2013年にウェブベースのクライアントを追加しました。[ 100 ]
もう1つの人気のあるウェブアプリは戦術トレーニングです。現在は閉鎖されているChess Tactics Serverは2006年にサイトを開設し[ 101 ] 、翌年にはChesstempoが続き[ 102 ]、Chess.comは2008年にTactics Trainerを追加しました[ 103 ] 。Chessbaseは2015年に戦術トレーナーのウェブアプリを追加しました[ 104 ]。
Chessbaseは1998年にチェスゲームデータベースをオンライン化しました。[ 105 ] もう一つの初期のチェスゲームデータベースは、1999年に始まったChess Labです。[ 106 ] New In Chessは当初、 Windows 3.x用のNICBaseプログラムをリリースしてChessbaseと競合しようとしましたが、最終的にはソフトウェアを諦め、2002年からオンラインデータベースに注力することにしました。[ 107 ]
2006年からはオンラインでエンジンShredderと対戦することができた。 [ 108 ] 2015年には、Chessbase はプレイ Fritz ウェブ アプリを追加し、[ 109 ]対局を保存するための My Games も追加した。[ 110 ]
2007年から、Chess.comはトレーニングプログラム「Chess Mentor」のコンテンツをオンラインで顧客に提供し始めた。[ 111 ]サム・シャンクランドやウォルター・ブラウン などのトップGMがレッスンを提供している。
人工知能の導入は、特にエリートレベルにおいて、チェスのゲームを大きく変革した。AIは防御戦略に大きな影響を与えた。ストレスや疲労といった要因による感情的・心理的な影響を受けやすい人間とは異なり、AIはあらゆる可能性のある手を無条件に計算できる能力を持っている。その結果、かつては防御不可能と考えられていた多くの局面が、今では防御可能と認識されるようになった。
何百万ものゲームを研究した後、チェスエンジンは新しい分析を行い、既存のオープニング理論を改良しました。これらの改良は新しいアイデアを生み出し、ゲームのあらゆる部分でプレイヤーの考え方を変えました。[ 112 ]クラシックチェスでは、エリートプレイヤーは一般的に、確立された分析や主要なエンジンの推奨に沿った10～15のオープニングムーブを行うことでゲームを開始します。[ 113 ]
従来の対面式トーナメントでは、プレイヤーが電子機器を使用しようとする試みを阻止するために携帯型金属探知機が使用されるが、オンラインチェスにおけるフェアプレーの監視ははるかに困難である。
2020年のヨーロッパオンラインチェス選手権では、過去最多となる約4000人のプレイヤーが参加したが、80人以上の参加者が不正行為で失格となった。そのほとんどは初心者とユースのカテゴリーのプレイヤーだった。[ 114 ]このイベントは、オンライン競技における高度な検出方法の必要性が高まっていることを浮き彫りにした。
これらの問題に対応するため、 Chess.comなどのチェスプラットフォームは、プレイヤーのあり得ない動きを追跡し、エンジンが行う可能性のある動きと比較するAIベースの統計モデルを開発しました。疑わしいケースはすべて専門家による調査が行われ、その結果は定期的に公開されます。FIDEは、オンラインイベントでの不正行為防止対策を強化するために、AI行動追跡技術を導入しました。[ 115 ]
AI ベースの検出システムは、機械学習を組み合わせてさまざまなゲームで不審なプレイヤーの行動を追跡します。これは、実際の動きと利用可能な統計から導き出された予測された動きとの間の差異を測定することによって行われます。異常に高いスキルレベルのプレイヤーや、自動チェスシステムの特徴的な動きを模倣できる異常な戦略。公平性と正確性を保証するために、何らかのアクションを実行する前に、各ケースは人間の専門家によって調査され、決定が正しいことを確認します。[ 115 ]
娯楽目的というよりは真剣なプレイと考えられてきたが、2018年以降に作成されたGPT-3のような大規模言語モデル（LLM）は、適切な言語プロンプトを与えることでチェスの指し手を生成できることが発見された。ネイティブのチェスエンジンに比べると非効率的ではあるが、LLMが単に夢のような状態でチェスのようなフレーズを唱えるのではなく、オープニング以降の盤面の状態を追跡できるという事実は、非常に驚くべきことと考えられた。LLMのプレイはエンジンのプレイと比べていくつかの癖がある。例えば、エンジンは一般的に盤面の状態がどのように到達したかを「気にしない」。しかし、LLMは、強力なプレイによって到達したチェスの局面と、一連の奇妙な先行する指し手によって生成された同じ盤面の状態（一般的に弱くランダムな指し手を生成する）に対して、異なる質の指し手を生成するようだ。[ 116 ]
{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク){{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)
この記事には、CC BY-SA 3.0ライセンスの下で利用可能なChess Programming Wikiのテキストが含まれています。