反コンピューター戦術

対コンピュータ戦術は、人間が様々なゲーム、最も典型的にはチェスやArimaaなどのボードゲームでコンピュータの対戦相手に勝つために使用する方法です。これらは、単にプログラマーによって意図的に弱点や癖が与えられる興味深い挑戦となるようにプログラムされたAI（多くのビデオゲームAIのように）ではなく、勝つために全力を尽くしてプレイしているコンピュータAIとの競争に最も関連しています。このような戦術は、AIが有望な動きを探すために評価関数を使用してゲームツリーを検索し、多くの場合アルファベータ剪定やその他のミニマックスアルゴリズムを使用して検索を絞り込んでいた時代に最も関連しています。このようなアルゴリズムに対しては、長期的な優位性を目指して保守的にプレイするのが一般的な戦術です。この優位性はゆっくりと現れるため、コンピュータは検索中に気付かず、脅威を適切に回避できないというのが理論です。これにより、たとえば、微妙な優位性が最終的にパスしたポーンでチェスのエンドゲームに勝つことに変わる場合があります。 (逆に言えば、人間にとっては合理的に思えるが実際には破滅的な動きを誘い込む短期的な「罠」に AI を誘い込む試みは、完全情報のゲームではコンピューターに対しては基本的に決して通用しません。)

この分野は、コンピューターがチェスなどのゲームで非常に強かったものの、負ける可能性もあった 1990 年代から 2000 年代初頭に最も関連しています。当時でも、そのような戦術の有効性は疑問視されており、コンピューターを序盤から素早く追い出すために通常とは異なる動きや最適ではない動きをするなどのいくつかの戦術は、人間対コンピューターのトーナメントでは効果がないことが判明しました。機械学習の台頭により、対コンピューター戦術の適用性も低下しました。機械学習アルゴリズムは、長期戦では人間と同等かそれ以上に上手くプレイする傾向があるためです。

完全情報ゲーム用の古典的な AI を設計する際の 1 つの側面は、地平線効果です。コンピューター AI は、可能な動きと反撃の動きのゲーム ツリーを調べますが、ツリーに強制勝利が含まれていない限り、最終的には新しい可能性の探索を停止する必要があります。その場合、ボードの状態に対して評価関数が呼び出され、多くの場合、ボードがどちらの側に有利であるかを判断するために大まかなヒューリスティックが使用されます。チェスでは、これは物質的な利点 (追加の駒)、センターの制御、キングの安全性、ポーンの構造などです。地平線効果を利用するには、 AI が調べたプレイの先でのみ結果が明らかになる戦略を使用します。たとえば、AI が 10 プレイ先を調べていて、戦略が 12 ～ 20 プレイ (6 ～ 10 ターン) で「成果」を生む場合、AI は「見る」ことができない迫りくる脅威を回避しません。これは、地球の自然な曲率によって船が隠れている可能性がある「地平線の向こう」を見ることができない人と同じです。同様に、地平線を短く保つために、人間のプレイヤーは盤面の状態をできるだけ複雑にしておきたいと考えるかもしれません。駒を交換して盤面を単純化すると、考慮すべき選択肢が少なくなるため、AI は「より遠く」の未来を見ることができるため、地平線効果を利用しようとするときには回避されます。

非常に「決定論的」で、脅威に応じて特定の方法でプレイすることが知られている AI に対して最も効果的な戦術は、人間が AI がどのように対応するかを正確に知っている状況を強制することです。人間が AI がうまく処理できないと思われる状況を選択した場合、これは AI をそのような状況に確実に誘い込むことにつながります。AI がその特定のプレイ スタイルをうまく処理できる場合でも、人間が AI が常にそれを選択することを確信している場合、人間のプレーヤーの準備が簡単になります。つまり、AI が常にその種類のボードでプレイする招待を受け入れることを知って、この 1 つの状況を非常に詳しく学習するだけで済みます。

モンテカルロ木探索に基づくAIゲームは、アルファベータAIとは正反対の長所と短所を持っています。長期的な戦略には優れている傾向がありますが、罠に対処するのに問題があります。^[1]モンテカルロAIは一度罠に陥ると、その後かなりの期間、悪いプレイを続け、回復できない可能性があります。^[2]

戦略的にプレイするアルファベータAIに対しては、辛抱強く優位性を積み重ねることが有益な戦術となるかもしれないが、AlphaGoのようなMCTSベースのAI自身も、この辛抱強い戦略的なやり方でプレイする可能性がある。^[2]したがって、アルファベータに対しては悪いアプローチである意図的な戦術的プレイは、MCTSに対しては有効な対コンピュータ戦術となる。

ニューラルネットワークに基づくゲームAIは、無意味な動きをすることでAIの位置の評価を変え、負けてしまう敵対的摂動の影響を受けやすい。Lanらは、KataGoが劣った動きをするように導く盤面の状態の変更を見つけるアルゴリズムを開発した。^[3]しかし、画像認識における敵対的サンプルと同様に、これらの攻撃はコンピュータの支援なしには考案するのが難しい。

1997年のディープ・ブルー対ガルリ・カスパロフ戦では、カスパロフはゲーム開始時にディープ・ブルーをオープニングブックから追い出すために対コンピュータ戦術をとった。^[4]カスパロフは珍しいミーゼス・オープニングを選択し、コンピュータが自分でオープニングを打つ（つまり、オープニングブックを使用せずに自分のスキルに頼る）と、オープニングをうまく打てないだろうと考えた。 ^[5]カスパロフは、試合の他のゲームでも同様の対コンピュータオープニングを打ったが、この戦術は裏目に出た。^{[6] 2つの試合について、}ルイ・ロペスを選んだ2番目のゲームの後にカスパロフは次のように書いている。「黒で同じ受動的な対コンピュータ戦略を使うのは危険すぎると判断した。白ならゲームのペースをうまくコントロールしてチャンスを待つことができる。黒なら、ディープ・ブルーのオープニングブックに載っていたとしても、特に計画を見つけるのが難しいクローズドオープニングであれば、既知のオープニングを打つ方が安全だろう。他のゲームと同様、この戦略の欠点は、それが私のスタイルではなかったことです。私は対コンピューターチェスをプレイしながら、対カスパロフチェスもプレイしていました。」

バーレーンのブレインズは、 2002年10月に開催された、当時の世界チャンピオンであった人間のチェスのグランドマスター、ウラジミール・クラムニクとコンピュータプログラムDeep Fritz 7との間で行われた8ゲームのチェスの試合である。試合は4対4の引き分けに終わり、参加者それぞれが2勝、4引き分けで、それぞれ0.5ポイントの価値があった。^[7]

• ガルリ・カスパロフ vs. ディープ・ブルー（コンピュータ） IBM マンマシン、ニューヨーク、アメリカ 1997
• ガルリ・カスパロフ vs. X3D フリッツ（コンピュータ）マンマシン世界チェス選手権 2003
• Rybka (コンピュータ) vs.ヒカル・ナカムラICC ブリッツ 3 0 2008

Arimaa は、1997 年にカスパロフが Deep Blue に敗れたことにヒントを得て、アルファベータ プルーニング AI にとって難しいように特別に設計されたチェスの派生ゲームです。プレイヤーは 1 回の「移動」につき 4 つのアクションを実行できるため、探索空間のサイズが大幅に拡大し、盤面がほぼ満杯で駒がほとんど捕獲されていない状態で終了できるため、ユニット不足によるテーブルベースの終盤スタイルの「解決済み」ポジションを回避できます。人間の Arimaa プレイヤーはチェスよりも長く持ちこたえましたが、2015 年には優れたコンピューター AI に敗れました。^[8]