63

三目並べの実装で難しい部分は、マシンが実行する最善の動きを決定することだと思います。

追求できるアルゴリズムは何ですか？単純なものから複雑なものまで、実装を検討しています。問題のこの部分にどのように取り組みますか?

4

10 に答える 10

55

完全なゲーム (毎回勝つか引き分け) をプレイするためのウィキペディアの戦略は、単純な疑似コードのように見えます。

ウィキペディアより引用(Tic Tac Toe#Strategy)

Newell と Simon の 1972 年の tic-tac-toe で使用されているように、次のリストから利用可能な最初の手を選択すると、プレイヤーは完全な Tic-tac-toe (勝つか、少なくとも引き分け) をプレイできます。プログラム。 [6]

  1. 勝つ: 2 つ連続している場合は、3 つ目をプレイして 3 つ連続します。

  2. ブロック: 対戦相手が 2 つ続けて持っている場合は、3 つ目をプレイしてブロックします。

  3. フォーク: 2 つの方法で勝つことができる機会を作成します。

  4. 対戦相手のフォークをブロック:

    オプション 1: 対戦相手がフォークを作成したり勝利したりしない限り、対戦相手を防御に追い込むために 2 つ続けて作成します。たとえば、「X」にコーナーがあり、「O」にセンターがあり、「X」にも反対側のコーナーがある場合、「O」は勝つためにコーナーをプレーしてはなりません。(このシナリオでコーナーをプレーすると、「X」が勝つためのフォークが作成されます。)

    オプション 2: 対戦相手がフォークできる構成がある場合は、そのフォークをブロックします。

  5. Center: センターを演奏します。

  6. 反対側のコーナー: 相手がコーナーにいる場合は、反対側のコーナーをプレーします。

  7. エンプティ コーナー: エンプティ コーナーをプレイします。

  8. エンプティ サイド: エンプティ サイドをプレイします。

「フォーク」状況がどのように見えるかを認識することは、提案されているように力ずくで行うことができます。

注: 「完璧な」対戦相手は良い練習になりますが、最終的に「対戦」する価値はありません。ただし、上記の優先順位を変更して、対戦相手の性格に特徴的な弱点を与えることができます.

于 2008-09-24T05:43:13.753 に答える
39

(三目並べまたはチェスのようなはるかに難しいゲームの場合) 必要なのは、ミニマックス アルゴリズム、またはその少し複雑なバリアントであるalpha-beta pruningです。ただし、通常の素朴なミニマックスは、三目並べのような小さな検索スペースのゲームでは問題ありません。

一言で言えば、あなたがしたいことは、あなたにとって最良の結果をもたらす動きを探すことではなく、最悪の結果が可能な限り良い動きを探すことです. 対戦相手が最適なプレイをしていると想定する場合、相手は自分にとって最悪の動きをするだろうと想定する必要があるため、相手の最大ゲインを最小限に抑える動きを取らなければなりません。

于 2008-09-24T07:40:27.153 に答える
14

可能性のあるすべてのボードを生成し、後でツリーのさらに下に生成されるボードに基づいてスコアリングする力ずくの方法は、多くのメモリを必要としません。特に、ボードを 90 度回転させたり、垂直方向に反転させたりするのは冗長であることがわかっている場合はなおさらです。横軸と斜め軸。

そのポイントに到達すると、結果を説明するツリー グラフに 1k 未満のデータが表示され、コンピューターにとって最適な動きになります。

-アダム

于 2008-09-24T05:31:26.980 に答える
7

三目並べの典型的なアルゴリズムは次のようになります。

Board : ボードを表す 9 要素のベクトル。2 (空白を示す)、3 (X を示す)、または 5 (O を示す) を格納します。ターン: ゲームのどの手をプレイしようとしているのかを示す整数。最初の動きは 1 で示され、最後の動きは 9 で示されます。

アルゴリズム

メイン アルゴリズムは 3 つの関数を使用します。

Make2: ボードの中央の正方形が空白の場合、つまり の場合は 5 を返しますboard[5]=2。それ以外の場合、この関数は角以外の正方形を返します(2, 4, 6 or 8)。

Posswin(p)p: プレーヤーが次の手で勝てない場合は 0 を返します。それ以外の場合は、勝利の動きを構成するマスの数を返します。この関数は、プログラムが勝つことと対戦相手の勝利をブロックすることの両方を可能にします。この関数は、行、列、および対角線のそれぞれをチェックすることによって動作します。行全体（または列または対角線）の各正方形の値を掛け合わせることで、勝利の可能性を確認できます。商品が18( 3 x 3 x 2)の場合、X当選可能です。積が50( 5 x 5 x 2) の場合、O が勝つことができます。勝利行 (縦列または対角線) が見つかった場合、その中の空白の正方形を決定でき、その正方形の数がこの関数によって返されます。

Go (n): 正方形 n で動きます。このプロシージャは[n]、ターンが奇数の場合はボードを 3 に設定し、ターンが偶数の場合はボードを 5 に設定します。また、ターンが 1 つ増えます。

アルゴリズムには、各動きの戦略が組み込まれています。を出したら奇数手X、○を出したら偶数手。

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

私はそれを使用しました。皆さんの気持ちを教えてください。

于 2012-07-13T18:16:58.987 に答える
6

可能性のある場所の 3x3 マトリックスのみを扱っているため、計算能力に負担をかけることなく、すべての可能性の検索を作成するのは非常に簡単です。空きスペースごとに、そのスペースをマークした後に考えられるすべての結果を計算し (再帰的に言います)、勝つ可能性が最も高い動きを使用します。

これを最適化することは、本当に労力の無駄です。いくつかの簡単なものは次のとおりです。

  • 最初に他のチームの勝利の可能性を確認し、最初に見つけたチームをブロックします (とにかく 2 つのゲームオーバーがある場合)。
  • 開いている場合は常に中央に移動します (前のルールには候補がありません)。
  • 両サイドの前で角を曲がる (これも前のルールが空の場合)
于 2008-09-24T05:33:20.830 に答える
3

いくつかのサンプル ゲームで AI をプレイさせて学習させることができます。教師あり学習アルゴリズムを使用して、それを支援します。

于 2008-09-24T05:37:42.020 に答える
3

遊び場を使わない試み。

  1. 勝つために（あなたのダブル）
  2. 無ければ負けない(相手のダブル)
  3. そうでない場合は、すでにフォークを持っていますか（ダブルダブルを持っていますか）
  4. そうでない場合、対戦相手がフォークを持っている場合
    1. 可能なダブルとフォークのブロッキング ポイントを検索します (究極の勝利)
    2. ブロッキングポイントでフォークを検索しない場合（対戦相手に最も負ける可能性を与えます）
    3. ポイントをブロックするだけでなく（負けないように）
  5. ダブルとフォークを検索しない場合（究極の勝利）
  6. そうでない場合は、対戦相手に最も負ける可能性を与えるフォークのみを検索します
  7. そうでない場合は、double のみを検索します
  8. 行き止まりでなければ引き分け、ランダム。
  9. そうでない場合（最初の動きを意味します）
    1. それがゲームの最初の動きである場合。
      1. 対戦相手に最大の負けの可能性を与える (アルゴリズムは、相手に 7 負けの可能性を与えるコーナーのみをもたらす)
      2. または退屈を壊すためにランダムに。
    2. それがゲームの 2 番目の動きである場合。
      1. 負けていないポイントだけを見つけます（もう少しオプションを提供します）
      2. または、このリストで最高の勝率を持つポイントを見つけます (すべてのコーナーまたは隣接するコーナーまたは中央のみになるため、退屈な場合があります)。

注: ダブルとフォークがある場合、ダブルが対戦相手にダブルを与えるかどうかを確認します。与える場合は、新しい必須ポイントがフォーク リストに含まれているかどうかを確認します。

于 2012-06-19T14:41:52.553 に答える
1

各正方形を数値スコアでランク付けします。マスを取った場合は、次の選択肢に進みます (ランクの降順でソート)。戦略を選択する必要があります (最初に行くには 2 つの主な戦略があり、2 番目に行くには 3 つ (と思います) あります)。技術的には、すべての戦略をプログラムしてから、ランダムに 1 つを選択することができます。そうなると対戦相手の予測が難しくなります。

于 2008-09-24T05:28:33.073 に答える
0

この回答は、あなたが P1 の完璧なアルゴリズムの実装を理解していることを前提としており、他の人よりもいくつかの間違いを犯す可能性が高い普通の人間のプレーヤーに対して条件で勝利を収める方法について説明しています。

もちろん、両方のプレイヤーが最適なプレイをした場合、ゲームは引き分けで終了する必要があります。人間のレベルでは、コーナーでプレーする P1 ははるかに頻繁に勝利をもたらします。心理的な理由が何であれ、P2 はセンターでプレーすることはそれほど重要ではないと考えるように仕向けられています。これは彼らにとって不幸なことです。

P2が中央で正しくブロックした場合、P1 は反対側のコーナーをプレーする必要があります。これは、心理的な理由で、P2 がコーナーをプレーする対称性を好むためです。

P1 が最初の動きで行う可能性のある動きに対して、その後両方のプレーヤーが最適にプレーした場合に P1 に勝利をもたらす P2 が行う可能性のある動きがあります。その意味で、P1 はどこでもプレイできます。エッジ ム​​ーブは、このムーブに対する可能な応答の最大部分が引き分けになるという意味で最も弱いですが、P1 の勝利を生み出す応答はまだあります。

経験的に (より正確には、逸話的に) ベストな P1 のスターティング ムーブは、最初のコーナー、2 番目のセンター、最後のエッジのようです。

直接または GUI を介して追加できる次の課題は、ボードを表示しないことです。人間は間違いなくすべての状態を覚えることができますが、追加された課題により、覚えるのに手間がかからない対称ボードが好まれるようになり、最初のブランチで概説した間違いにつながります。

私はパーティーでとても楽しいです、私は知っています。

于 2016-04-12T17:20:34.050 に答える