1

私はテーブルとGenerate_moves（）などのいくつかの関数を持っていますが、minmaxアルゴリズムが機能するには、コンピューターに最適なテーブルを選択させるためにテーブルのスコアを設定する必要があります。

        public int Score()
        {
            if (Turn == "X")
            {
                if (gameWon("X")) return 100;
                if (gameWon("O")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("X");
            }

            if (Turn == "O")
            {
                if (gameWon("O")) return 100;
                if (gameWon("X")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("O");
            }

            return -1;
        }

直線canWin(string)または列にXまたはOがいくつあるかを示す数値を返しますが、テーブルのスコアを設定する理由が大きいとは思えません。

私がテーブルを持っている場合：

X - X
0 X 0
- - 0

スコアはと同じである必要があります

X - -
0 - X
0 0 X

とより大きくする必要があります

X - X
0 - -
- 0 -

また、スコア関数にさまざまなスコアを教えてもらう方法がわかりません。これを伝えるためにメソッドScoreを実装するにはどうすればよいですか？

編集：

コンピューターが最初にXで、私がOである場合

X - -      X - -      X - -     X - -
- - -   -> 0 - -   -> 0 X -  -> 0 X -
- - -      - - -      - - -     - - 0

次に、次善のオプションをコンピュータに選択させるにはどうすればよいですか。

X - X
0 X -
- - 0
4

5 に答える 5

1

Tic-Tac-Toeは、コンピューターにとって比較的簡単なゲームです。分岐係数と可能性の数が比較的少ないため、次のようになります。最も簡単な[計算]可能なヒューリスティック関数を作成し、minmaxを最も深いレベル、ゲームツリーの葉。これらはすべて特定の勝ち/負け/引き分けです。

それでもヒューリスティックを探している場合は、次を使用できますnumber of rows/cols/diagonals with exactly 2 "X"s and left square is empty

それでも、[この特定の問題について]損失の場合は-1、勝ちの場合は1、その他すべての可能性の場合は0を返すminmaxアルゴリズムの方がパフォーマンスが優れていると思います。これは、ゲームの葉に早く到達するため、より多くの情報が得られるためです。ヒューリスティック。

于 2012-02-08T14:09:07.533 に答える
1

あなたは物事を複雑にしすぎていると思います。考えられるTic-tac-toeゲームは40万未満です。実際、Tic-tac-toeは非常にシンプルなので、考えられるすべてのゲームの最良の動きを1枚の紙に書き留めることができます。

（完全なtic-tic-toeマップ）-XKCD

ミニマックスのような単純なアルゴリズムでさえやり過ぎです-力ずくですべての可能な動きをチェックするだけです。最近のPCでは数ミリ秒しかかかりません。

于 2012-02-08T18:01:46.547 に答える
0

1 つの可能性...スコア = x で勝つための残りの方法 (行、列、または対角線を埋めることができる) の数 - リーフ (最終状態) ではないすべての状態で 0 のために勝つための残りの方法の数) 葉の状態については、スコア = 1、0、または -1 しかありません

于 2012-02-08T14:14:02.000 に答える
0

私はあなたが話していることを知っています。必要なのは、優れたヒューリスティック関数です。here からヒューリスティック関数を見つけることができます（私はそれらのどれも試していません）：

MiniMax アルゴリズムで三目並べを解く

Visualgos: Tic-Tac-Toe

于 2013-01-28T08:02:44.663 に答える
0

2 番目の質問に答えるには:

次善の選択肢をコンピュータに選択させるにはどうすればよいでしょうか...

これは、ミニマックス アルゴリズムのタスクです。ゲームツリーから最良の動きをのぞきます。三目並べの場合、非常に洗練された評価関数は必要ありません。プレーヤーが勝った場合は正または負の値を返し、それ以外の場合は0 を返すだけで十分です。必要に応じて、1 人のプレーヤーが次の手で勝つことができるかどうかを評価することで拡張できます。分岐係数が大きく、ゲームツリーがさらに深くなる可能性があるゲームで必要な、より洗練された評価関数 (9 つの手だけでなく)。
私の経験*つまり、よりスマートな評価関数により、ゲーム ツリーの検索で 1 層深く進むと、この層に (同時に) 到達しないよりも良い結果が得られるということです。単純な評価によるより深い検索か、高度な評価によるそれほど深くない検索かを区別するのはそれほど簡単ではありません。ミニマックス アルゴリズムには他にも有望な重要な機能強化がたくさんあります。複雑な評価にとらわれないでください。

その後、評価関数を改善することができます。評価に関するその他の考え: functionmakeMoveで何らかの作業を行う方がよい場合があります。ここでは、(すべてではなく) 1 つの行、1 つの列、および 1 つまたは 2 つの対角線をチェックするだけで済みます。次に、現在のボードの横に、このチェックで取得した情報を保持します。この情報には、これが勝った手 (スコアを設定) であったかどうか、または他のプレイヤーからの次の手が強制されたかどうか (次のプレイヤーが行わなければならない手は、getMovesこの手のみを返すことに注意してください) が含まれます。最後になりましたが、1 つの列/行と 1 つの対角線に強制移動が含まれている場合、プレーヤーは 2 つの移動で勝ちます (スコアを維持します)。

評価関数で頑張ってください!

* 少し前に、Connect-Four-Game-Engine の評価関数に取り組みました。Connect-Four ボードを評価するための最良のアプローチは、James D. Allenの記事Expert Play in Connect-Fourの「Threat Analysis」の章で説明されているように、奇数と偶数の脅威を分析することでした。アルゴリズムは、メジャーおよびマイナーな脅威を分析しました。マイナーな脅威の分析部分を削除した後、アルファベータ検索のパフォーマンスが向上しました!

于 2012-02-08T21:18:43.667 に答える