以下は、知的ゲームで使用されるコンピューターアルゴリズムに関する短いストーリーです。
最も単純なゲームの1つであるtic-tac-toeを使用して、アルゴリズムの検討を開始します。 ほぼ全員が、決して負けないような方法でプレイする方法を知っていると思いますが、コンピューターがどのように成功するかを見てみましょう。
ほとんどすべてのゲームは、いわゆる 各ノードが問題を解決する1ステップ（ゲーム内で移動）になる決定木、ツリー内の分岐はソリューションに対応し、より完全なソリューションにつながります。シートは最終的なソリューション（最終位置）を表します。 私たちの目標は、ツリーのルートからリーフへの最適なパスを見つけることです。
通常、決定木は非常に大きくなります。 検討している三目並べゲームの場合、ツリーには50万以上のノードが含まれています。 チェッカー、チェス、および特にshogovとgoでは、木が1桁大きいことは明らかです。
しかし、それにもかかわらず、子供のゲームの例では、非常に大きなツリーで最適なソリューションを見つけることができる方法を検討できます。
プレーヤーにn個の可能な移動がある場合、対応するノードにはn個のブランチ（子孫）があります。 たとえば、tic-tac-toeでは、ルートノードは空のフィールドに対応します。 最初のプレイヤーは、9つの正方形のいずれかにクロスを置くことができます。 可能な各移動は、ルートノードからのブランチに対応します。 プレイヤーが短剣を置くと、2番目のプレイヤーは残りの8マスのいずれかにゼロを置くことができます。 これらの動きはそれぞれ、ボード上のクロスの現在の位置を表すノードからの分岐に対応しています。 この図は、調査中のツリーの小さな断片を示しています。
図からわかるように、ゲームツリーは非常に速く成長します。 ツリーがこのように成長し続けると、ツリー全体に9！= 362880の葉が含まれます。
実際、ゲームツリー内の多くのノードはルールによって禁止されています。 たとえば、プレーヤーの1人がすでに勝っている場合、この段階でツリーの構築を完了できます。 不可能なノードをすべて削除すると、ツリーが25万シートに削減されます。 しかし、これはまだ非常に非常に大きなツリーであり、その周りを完全に歩くには許容できないほど長い時間がかかります。 より複雑なゲームでは、ツリーは単純に想像できません。 プレイヤーが各ステップでチェスで16の可能な動きを持っている場合、5つの動きの後、ツリーには1兆ノット以上があります。
ゲームツリーで検索を実行するには、競技場の位置の値を決定できる必要があります。 三目並べでは、最初のプレイヤーが勝つため、3つの十字が並んでいる位置は最初のプレイヤーにとって非常に重要です。 つま先を設定するプレーヤーの価値は、フィールドのこれらの位置では非常に小さいです。同時に負けるからです。
各プレーヤーには、フィールド上の特定の位置に4つの値を割り当てることができます。
•4-勝利。
•3-明確な状況ではありません。
•2-描画。
•1-損失。
ゲームツリーの包括的な研究には、ミニマックス戦略を使用できます。 この場合、次の移動後に敵の位置が持つ可能性がある最大値を最小化しようとします。 まず、可能な動きのそれぞれの後に対戦相手が獲得できる最大値が決定されます。 次に、相手が最小値を受け取る動きが選択されます。
最適なストロークを検索するプロシージャは、フィールド位置の値を計算します。 この手順では、考えられるすべての動きを調べます。 移動するたびに、自分自身を再帰的に呼び出して、敵の位置が持つ価値を判断します。 次に、相手に最小値を与える動きを選択します。 3つの可能なイベントのいずれかが発生するまで、プロシージャ自体の再帰的な処理が継続されます。 まず、プレイヤーが勝つ位置を見つけることができます。 この場合、プロシージャはフィールドの位置の値を4に設定します。プレーヤーが負けた場合、フィールドの値は1に設定されます。次に、プレーヤーが移動できない位置を見つけることができます。 ゲームは引き分けで終了するため、プロシージャは位置の値を2に設定します。そして最後に、プロシージャは再帰の所定の深さを達成できます。 許容深度を超える場合、フィールド値は3に設定され、結果が不確実であることを示します。 最大の再帰の深さは、プログラムが時間を浪費するのを防ぎます。 これは、検索がほぼ無期限に続くチェスなどの複雑なゲームでは特に重要です。 再帰の最大の深さでも、スキルのレベルを設定できます。 プログラムがツリーを深く探索できるほど、その動きは良くなります。
この図は、ゲーム終了時のゲームツリーを示しています。 最初と3番目の動きはゼロをプレイするプレーヤーの勝利につながるため、これらの動きの値は4です。彼にとって、2番目の可能な動きは引き分けになり、値は2です。
ミニマックスアルゴリズムがゲームツリーを探索する唯一のツールである場合、大きなツリーの列挙はかなり複雑になります。 幸いなことに、大きなツリーを検索するために使用できるいくつかのトリックがあります。
まず、ゲームの専門家が選択した最初のいくつかの動きを思い出すことができます。 プログラムの最初の移動を選択すると、検索ツリーは9倍に削減されます。 実際、プログラムは、相手が移動するまでツリーを反復処理するべきではありません。 この場合、コンピューターとその敵の両方が既にブランチを選択しているため、ツリーには7！= 5040のブランチのみが含まれます。
追加のメモリを使用して複数の動きを保存すると、ツリーの検索に必要な時間が大幅に短縮されます。
検索を改善する別の方法は、重要なパターンを示すことです。 チェスでは、そのようなパターンは、キングまたはクイーンのように、一度に複数のピースを脅かすような位置になります。 チェスプログラムが交換パターンに気付くと、再帰の深さを一時的に変更して、一連の交換を最後まで表示し、交換が有益かどうかを判断できます。 交換が行われると、残りの数字の数が少なくなり、ツリー内の検索が簡素化されます。
最後に、より複雑なケースでは、ヒューリスティックを使用する必要があります。 たとえば、チェスでは、通常のヒューリスティックは利点を強化することです。 敵の強力なピースが少なく、同数の弱いピースがある場合は、可能な限り交換する必要があります。
現実はどうですか（チェッカーとチェス）
小学生でも三目並べのツリーを完全に整理できます。 チェッカーでは、可能な位置の数は数10 20によって推定されます。 これは非常に多くのことですが、2007年にスーパーコンピューターはすべての可能な動きを計算することができました。 つまり、2007年以降、人は（理論的にも）コンピューターに勝つことができません。
チェスを使用すると、近い将来、完全なバストを実現することはほとんど不可能です。 すべての可能なチェスの位置の数は10 46と推定されます。 この数は非常に大きいため、スーパーコンピューターでさえ、これらの位置をソートするには天文学的な時間が必要になります。 それにもかかわらず、チェスのいくつかの進歩があります。 すべてのポジションをソートすることは不可能ですが、ヒューリスティックとポジションベースは非常に効果的であることが判明しました。 あなたがチェスをすることを学んだことがあるなら、おそらく王室、女王のギャンビット、フィリドールの防衛、またはオールドインディアンの防衛について話しました。 これらの開口部はすべて、ゲームの開始時に適用されます。 問題は、それらが長い間、非常に深く計算されていることです（20移動まで）。 チェスのエンドゲームも非常によく計算されています。 これを確認するには、インターネットで「ライトピースに対するルークのエンドゲーム」、「クイーンに対する2つのルークのエンドゲーム」などを検索するだけです。 ゲームの中間部分のみを計算する必要があり、前述のように、ヒューリスティックは非常に効果的です。
1990年代半ばに、世界チャンピオンを打ち負かす可能性のあるプログラムが作成されました。 顕著な例は、ディープブルー-カスパロフの試合です。 1996年にKasparovが1試合しか負けなかったが試合に勝った場合、1997年にDeep Blueは個別の試合ではなく試合全体でKasparovを破りました。
現実はどうですか（将realityと囲and）
将giとチェスの主な違いは、取った駒はゲームを離れず、いつでもフィールドの任意のマスに戻ることができるということです。 この機能は、大きなフィールドサイズと大きな数字のセットとともに、将giを非常に難しいゲームにします。 パーティーの数は10 226に急激に増加し、エクスチェンジヒューリスティック（最も一般的な）は完全に無効になります。エクスチェンジはゲームを複雑にするだけであるため、その数を考えると将buildのパーティーのベースを構築することはほとんど不可能です。
プログラムの大部分は上記のミニマックス戦略を使用しており、プログラムの主な違いは位置推定とヒューリスティックアルゴリズムです。 プロ選手の尊厳を損なわないように、プログラムとプロの試合は現在禁止されていますが、将association協会は時々試合の許可を与えます。 このゲームでのAIの最大の成果は、最強の女性に対する勝利です。 清水一葉は、あからプログラムと対戦しました。 厳密に言えば、Akaraは1つのプログラムではなく、4つの独立したエンジンです。 最善の動きに関する決定は、単純な投票によって行われます。 AIの分野での著しい進歩にもかかわらず、プログラムの将giはまだ最強のプレーヤーを倒すことができません。
囲gameのゲームではさらに興味深いことがあります。 10 171の最終位置の数。これにより、すべてのオプションを直接列挙する必要がなくなります。
残念ながら、ミニマックス検索ツリーも非常にうまく機能しません。 実際のところ、移動中のポジションの数は非常に急速に増加しており、スーパーコンピューターでさえ十分な速度で動きを整理することはできません。 最高のプログラムは、12の動きに対して「未来を見る」ことができます。 受け取ったポジションが評価され、最適なオプションが選択されます。 これらのオプションの場合、プログラムはゲームの内陸部の分析を再開し、最適なオプションを選択しようとします。 そして何度も。 goの機能の1つは、このゲームでは戦略的思考が戦術的よりもはるかに重要であることです。 また、プログラムがローカルの戦術的優位性を達成したとしても、実際のマスターが勝ちます。
それにもかかわらず、プログラマは、プロレベルでプログラムをプレイできる非常に独創的なアルゴリズムを発見しました（最強のプレイヤーや勝利を勝ち取るという話はありません）。
主なアイデアは、モンテカルロツリーで検索アルゴリズムを使用することです。 名前から、これがランダム化アルゴリズムであることは明らかです。 goではどのように使用されますか？ プログラムは、現在の位置からプレイできる数百万のゲームをランダムにソートしました。 さらに、各ゲームは最後までプレイされ、プログラムは移動の収益性を計算します。唯一の制限はルールに従うことです。
数百万のゲームを最後まで失ったため、プログラムは最初の動きの後に勝つ可能性に関する統計を受け取ります。 これらの統計によると、プログラムは、そのような動きが5％の確率で勝つことを決定します。3％などです。 次に、プログラムは単に勝率が最も高い動きを選択し、アルゴリズムを繰り返します。 その結果、プログラムは勝利につながる可能性が最も高い動きをします。
この方法を使用すると、プログラムは最強のプレーヤーを倒すことができましたが、ハンディキャップは7石でした。
遅かれ早かれ、プログラムがゲームの100％で人々を打ち負かし始める時が来るでしょうか？ もちろんそうではありませんが、私たちは常にボトルを持っています！