私は三目並べAIを作成しました。各ボードの状態を考えると、私のAIは移動する正確な場所を1つ返します。また、AIで可能なすべてのプレイをループする関数を作成しました
つまり、これはAIが特定のボードに対して移動できるようにする再帰関数であり、次に他のプレイがすべての可能な移動を実行できるようにし、可能な移動ごとに新しいボードを使用して再帰関数を呼び出します。
これは、AIが最初に行われるときと、もう一方が最初に行われるときに行います...そしてこれらを足し合わせます。最終的には、勝ちは418回、引き分けは115回、負けは0回になります。
しかし今、私の問題は、どうすれば勝利の量を最大化できるかということです。この統計を何かと比較する必要がありますが、何と比較すればよいかわかりません。
私の感じでは、あなたが引用している統計はすでにかなり良いものです. 熟練した三目並べのプレイヤー 2 人は常に引き分けで終わり、対戦相手がゲームのプレイ方法を知っている場合、強制的に勝つ方法はありません。
アップデート
AI の正しさを証明するもっと洗練された方法があるかもしれませんが、最も簡単な方法は力ずくの方法です。ゲーム ツリーとしてすべての可能なボード ポジションを列挙し、損失に直接つながる枝を剪定するだけです。次に、ツリーの各ブランチについて、そのブランチをたどることで得られる勝利の確率を計算できます。次に、ボードの各位置で AI をテストし、勝利の可能性が最も高いブランチを選択していることを確認するだけです。
まず、移動9が常に強制されていることを確認する必要があります。ボードには空のマス目が1つだけあります。7回の移動後、正確に3つの状況が発生する可能性があるため、移動も8回の強制と見なすことができます。
O次の動きで勝つことができます、その場合それは勝ちますX残りの2つの正方形のいずれかにを置くと、のゲームに勝ちますX。この場合O、次の動きに関係なく負けます。X勝利への道は0または1つあり、その場合Oはブロックして引き分けを強制しますこれは、最大7回の移動でゲームが終了することを意味します。
また、中央、コーナー、または側面の3つの開口部の動きしかないことにも注意してください。ボードは「標準的な」開口部（左上隅または上面の中央）に一致するように回転できるため、4つのコーナーまたは側面のどちらを使用するかは関係ありません。
これで、状態分析コードを作成できます。3つの可能な開口部のそれぞれから始めて、移動するまでに開いているすべての正方形を使用して、最大6つの追加の移動をバックトラックして検索します。各移動後、位置を分析して、勝ったかどうXかを確認します。OマークXはWxとして勝ち、OWoとして勝ちます。残りのポジションは未定です。
WxまたはWoの後に位置を探索しないでください。前のステップに戻って、対応する側の勝利を報告してください。
7番目の動きに到達したら、位置を静的に分析して、それが上記の3つの状況のいずれかに該当するかどうかを判断し、位置にWx、Wo、またはDrawのマークを付けます。
ここで最も重要なステップに移ります。N-1プレーヤーによる移動に戻るときp、
これを正しく行うと、3つのオープニングポジションすべてがドローとして分類されます。あなたは3つの動きの後にいくつかの強制的な勝利を見るはずです。
この手順を実行すると、各位置がWx、Wo、またはDrawとして分類されます。AIが、Wpとして分類された位置でプレーヤーpに勝利をもたらした場合、または引き分けとして分類された位置で引き分けを獲得した場合、AIは完璧です。一方、AIがp引き分けのみを取得するWpとして静的に分類される位置がある場合は、AIエンジンを改善する必要があります。
あなたがしているのは、AI よりも線形の最適化です。ここでは、Tic-Tac-Toe のすべての線形代数については説明しません。ネット上にはたくさんの例があります。
したがって、線形代数を使用すると、結果について何も証明する必要はありません (魔法の統計の検索など)。これは、元の方程式に単純な解を挿入するだけで結果を検証できるためです。
結論として、次の 2 つのケースがあります。
単純な「演繹」ロジック (実際には非形式線形代数定式化) を使用しています。コードを見ずに結果をチェックするためのすぐに使用できる方法が見つかりません。EDIT : Andrew Cooper が示唆するように、ブルート フォースは、コードを見なくてもすぐに使用できるメソッドになる可能性があります。
正式な線形代数の定式化を使用しています。結果は、元の方程式に単純な解を挿入することで検証できます。
私たちが知っていることを考えると
あなたのAIは、次の場合に最適であることがすでに証明されています
それは負けませんでした、あなたはそれが勝つことを要求することはできません。フルツリー検索には悪い動きも含まれていたため、勝利はカウントされませんでした。以上で完了です。
ただ楽しみのために：
ゲームに勝つ/引く/負けるチャンスについての先験的な知識がなかった場合、一般的な戦略は失われたポジションを永続的に保存することです。次のゲームでは、それらを避けようとします。失われた位置への移動を避けられない場合は、別の位置を見つけました。このようにして、（可能であれば）特定の戦略に負けないようにすること、または戦略のエラーを回避することを学ぶことができます。
または、次のリンクでいつでも三目並べアルゴリズムを試すことができます。
三目並べ AI が正しいことが証明されるためには、次の 2 つの条件を満たす必要があります。
どちらの条件も、両方のプレーヤーが最適にプレーした場合、三目並べは常に引き分けに終わるという事実に由来します。
プログラムがこれら 2 つの条件を満たしているかどうかを自動的に判断する方法の 1 つは、考えられるすべての三目並べゲームの「ミニマックス ツリー」と呼ばれるものを作成することです。ミニマックス ツリーは、各プレイヤーの最適な動きを完全に特徴付けているため、これを使用して、プログラムが常に最適な動きを選択するかどうかを確認できます。つまり、私の答えは基本的に、「完璧な AI を作成し、それが自分の AI と同じように動作するかどうかを確認する」ということになります。ただし、ミニマックス アルゴリズムは知っておくと役立ちます。私の知る限り、これは AI が実際に最適に動作するかどうかをテストする唯一の方法です。
ミニマックス アルゴリズムの仕組みは次のとおりです(GIF の説明については、ウィキペディアを参照してください。ミニマックスに関するウィキペディアの記事にも疑似コードがいくつかあります)。
検討中の三目並べのセットアップから始めて、可能なすべての後続の動きのツリーを構築します。ルート ノードの初期位置。ツリーの最下位レベルには、考えられるすべての最終的な位置があります。
最初のプレーヤーが勝つすべての最終的な位置に +1 の値を割り当て、2 番目のプレーヤーが勝つすべての動きに -1 の値を割り当て、すべての引き分けに 0 の値を割り当てます。
次に、これらの値をツリーのルート ノードまで伝播します。各プレーヤーが最適にプレーすると仮定します。最後の手で、プレイヤー 1 は +1 の値を持つ手、つまりゲームに勝つ手を選択します。+1 の値を持つ手がない場合、プレーヤー 1 は値 0 の手を選択し、ゲームを引き分けます。したがって、プレイヤー プレイヤー 1 の移動であるノードには、その子ノードの最大値が割り当てられます。逆に、プレイヤー 2 の手の場合、彼らはゲームに勝つ -1 の値を持つ手を選択することを好みます。勝ちの手が利用できない場合、彼らはゲームを引き分けることを好みます。したがって、プレーヤー 2 の番になったノードには、子ノードの最小値に等しい値が割り当てられます。このルールを使用すると、ツリーの最も深いレベルからルート ノードまで値を伝達できます。
ルート ノードの値が +1 の場合、最初のプレイヤーが最適なプレイで勝つはずです。値が -1 の場合、2 番目のプレイヤーが勝つはずです。値が 0 の場合、最適なプレーは引き分けにつながります。
それぞれの状況で、アルゴリズムが最適な動きを選択するかどうかを判断できるようになりました。三目並べで考えられるすべての動きのツリーを構築し、ミニマックス アルゴリズムを使用して各動きに +1、0、または -1 を割り当てます。あなたのプログラムがPlayer Oneの場合、常に最大値の動きを選択するのが最適です. プレイヤー 2 としてプレイする場合は、常に最小値の移動を選択するのが最適です。
次に、ツリー内のすべての動きをループして、AI に動きを選択するように依頼できます。上記は、選択した移動が最適かどうかを判断する方法を示しています。
比較できる唯一のことは、ある潜在的な動きを別の動きと比較することです。コンピューターが手を出す番になったら、その時点からすべての可能なゲームをプレイさせ、可能な限り多くの勝利につながる動きを選択します。常に勝つことはできませんが、相手に悪い動きをするチャンスを与えることはできます。
簡単に言えば、決定木は、最終結果の期待値 (および可能性) を再帰的に計算する方法です。ツリーの各「ブランチ」は、sum of (value * chance)この決定の可能性から誰の期待値が計算されるかの決定です。
限られたオプションのシナリオ(三目並べなど) では、ツリー全体を事前に計算することができるため、人間のプレイヤーが移動するたびに (チャンス)、選択 (決定) することができます。勝つ。
チェスのゲームでも解決策は似ていますが、木は事前に構築されていません。各手が動くたびに、コンピュータはボード上で可能なすべての手の値を計算してn前方への深さを求めます。プレーヤーが選択したゲームの難易度に応じて、最高、2 番目、または n 番目に良い期待値を選択します。
