10

少し背景：C ++でマルチノードツリーを学習する方法として、可能なすべてのTicTacToeボードを生成し、ノードで始まるブランチがそのノードから続くことができるすべてのボードになるようにツリーに格納することにしました。ノードは、1つの動きで続くボードです。その後、そのツリーを決定木として使用してTicTacToeを再生するAIを作成するのは楽しいだろうと思いました。

TTTは、完璧なプレーヤーが負けることのない解決可能な問題であるため、AIを初めて試すのは簡単なAIのようでした。

AIを最初に実装したとき、生成時に各ノードに2つのフィールドを追加しました。Xが勝つ回数とOがそのノードの下のすべての子で勝つ回数です。最善の解決策は、各移動でAIを選択し、最も多く勝つサブツリーを下に移動することであると考えました。それから私はそれがほとんどの場合完璧に機能する一方で、私がそれを打ち負かすことができる方法を見つけたことを発見しました。これは私のコードの問題ではなく、AIにパスを選択させる方法の問題でした。

それから私は、コンピューターの最大の勝利または人間の最大の損失のどちらか多い方のツリーを選択することにしました。これにより、パフォーマンスは向上しましたが、それでも完璧ではありません。私はまだそれを打ち負かすことができました。

ですから、私には2つのアイデアがあり、どちらが優れているかについての意見を期待しています。

1）勝ち負けを最大化する代わりに、勝ちに1、引き分けに0、負けに-1の値を割り当てることができます。次に、その次のノードが損失をもたらす移動になることはできないため、最も高い値を持つツリーを選択することが最良の移動になります。ボード生成の変更は簡単ですが、同じ検索スペースとメモリ使用量を維持します。または...

2）ボードの生成中に、XまたはOのいずれかが次の手で勝つようなボードがある場合、その勝ちを妨げる子だけが生成されます。他の子ノードは考慮されず、その後、生成は通常どおり続行されます。ツリーのサイズを縮小しますが、1ムーブの勝利があるかどうかを判断するアルゴリズムを実装する必要があり、それは線形時間でしか実行できないと思います（ボードの生成が大幅に遅くなると思いますか？）

どちらが良いですか、それともさらに良い解決策がありますか？

4

4 に答える 4

14

決定木に基づいて AI を実装する (通常) 正しい方法は、「Minimax」アルゴリズムを使用することです。

  1. 各リーフ ノードにスコアを割り当てます (+1=プレイヤーの勝利、-1=プレイヤーの敗北、0=引き分け)。

  2. 次のルールを各ノードに適用して、ツリーを上に向かって作業します。

    • 均等な深さ (プレーヤーが移動するとき) の場合、スコアが最も高い子を選択し、そのスコアをノードにコピーします。
    • 奇数の深さの場合 (コンピューターが移動する場合)、スコアが最も低い子を選択し、そのスコアをノードにコピーします。

もちろん、誰が最初に行くかによって、偶数と奇数を逆にする必要があるかもしれません。

詳細については、次を参照してください。

于 2009-12-08T19:19:39.433 に答える
8

あなたが一つのことを忘れていることを除いて、あなたの既存のアルゴリズムは良いです。他のプレイヤーの動きによって少なくともタイができなくなるようなパスは絶対に選択しないでください。

したがって、基本的に、プレーヤーが次に移動する可能性のあるブランチを破棄して、結び付けられない状況を引き起こし、既存のアルゴリズムを実行します。これにより、負ける可能性を排除しながら、不完全な対戦相手に勝つ可能性が最も高くなります。

于 2009-12-08T19:04:14.580 に答える
4

Tic-Tac-Toeは、欲張りアルゴリズムを使用して解決でき、決定木を実際に必要としません。

現在のアルゴリズムを引き続き使用する場合は、パトロスが提案するように実行し、各決定で失う可能性を最小限に抑えます。

より簡単なアプローチが必要な場合は、AIに毎ターン次のことを行わせます。

  1. 可能であれば、勝利のTic-Tac-Toeを完了します。
  2. 可能であれば、反対側のTic-Tac-Toeをブロックします。

  3. 各正方形の望ましさを評価し、線上で（AIによって）互いに取られた正方形について、その正方形の望ましさの1ポイントを追加します。対戦相手が取ったマスごとに、望ましさのポイントを1つ取り除きます。

    たとえば、ボードが現在次の場合：

    _|O|X
_|X|_
O| |

    左上隅の望ましさは0です（同じ行のXに1、対角線のXに1、ただし各Oに-1）。

  4. 最も望ましい広場でプレイします。恣意的に結びつきを断ち切る。

    上記の例では、AIは右中央の正方形を選択します。これは、望ましさが2であるため、次のターンに勝利につながるためです。

  5. ゲームが始まったばかりの場合は中央のマス目をプレイし、中央のマス目が取られている場合はランダムにコーナーを選びます。

  6. 勝つ（または同点）。

これは私の10年生のVisualBasic用語プロジェクトでした。打ち負かすことは不可能であり、決定木を保存するよりもはるかに少ないメモリで済みます。

于 2009-12-08T19:04:57.147 に答える
0

これを行う「単純な」方法 (2 人のプレイヤーが順番に手番を行う任意のゲームの場合) は、どちらかが勝者となるボードになるまで、考えられる手ごとを再帰的に試行し、その後、ツリーを上方向に戻ることです。ノードを「O勝」、「X勝」、または「引き分け」としてマークします。

あなたがステップアップするたびに (そのようなステップの 1 つは通常プライと呼ばれます)、それが誰の手であるかに応じて、プレーヤーが自分に最適な動きを選択すると想定します。葉から上に移動しているため、各子ノードの最適な結果が常にわかります。

サブツリーで勝ち負けの可能性のあるボードの数を数えるときは、基本的に、各プレイヤーが常にランダムな動きをすることを前提としています。ご指摘のとおり、賢いプレイヤーと対戦する場合、これはあまり効果的ではありません。上で概説したスキームは、代わりに、対戦相手が常に完璧な動きをし、勝とうとすることを前提としています。

于 2009-12-08T19:10:40.603 に答える