6

私は、C 用の Tic Tac Toe コードの単純なゲームに取り組んでいます。ほとんどのコードが完成しましたが、AI が決して負けないようにしたいと考えています。

ミニマックス アルゴリズムについて読みましたが、理解できません。このアルゴリズムを使用して、コンピューターが勝つか引き分けても負けないようにするにはどうすればよいですか?

4

4 に答える 4

8

この種の問題にアプローチする方法は、可能性のある未来を探ることです。通常 (チェスやドラフト AI の場合)、先物は特定の手数先と見なしますが、三目並べゲームは非常に短いため、ゲームの最後まで探索できます。

概念的な実装

したがって、分岐構造を作成します。

  • AI は自分自身があらゆる法的措置を講じていると想像します。
  • 彼らの AI は、ユーザーが合法的な動きのそれぞれの後に、ユーザーが行うことができるそれぞれの合法的な動きを想像します。
  • 次に、AI は次の正当な動きをそれぞれ想像します。
  • 等

次に、最も分岐した端 (時間的に最も前方) から順に、現在のターンのプレイヤー (AI またはユーザー) が、各分岐点で自分に最適な未来 (勝ち、負け、または引き分け) を選択します。次に、ツリーの上位 (現在に近い) のプレーヤーに引き渡します。仮想ターンのプレイヤーにとって最良の未来を選択するたびに、最終的に最初の分岐点に到達し、AI が敗北、引き分け、勝利に向かって展開する未来を確認できます。勝つ未来を選択します（または、利用できない場合は引き分けます）。

実際の実装

概念的にはこれが起こっていることに注意してください。ただし、ツリー全体を作成する必要はなく、このように判断してください。ツリーをたどって最も遠い時点に到達し、その時点で選択することも同様に簡単です。

ここで、このアプローチは再帰関数でうまく機能します。関数の各レベルは、そのすべてのブランチをポーリングします。可能な未来をそれらに渡し、-1,0,+1 を返します。各ポイントで現在のプレーヤーの最高のスコアを選択します。トップレベルは、それぞれの未来がどのように展開するか、どれだけうまく展開するかを実際には知らずに、動きを選択します。

疑似コード

この疑似コードでは、+1 は AI の勝利、0 は引き分け、-1 はユーザーの敗北であると想定しています。

determineNextMove(currentStateOfBoard)
    currentBestMove= null
    currentBestScore= - veryLargeNumber

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI’sMove)
        if score>currentBestScore
            currentBestMove=legalMove
            currentBestScore=score
        end
    end

    make currentBestMove

end

getFutureScoreOfMove(stateOfBoard, playersTurn)

    if no LegalMoves
       return 1 if AI wins, 0 if draw, -1 if user wins
    end


    if playersTurn=AI’sTurn
        currentBestScore= - veryLargeNumber //this is the worst case for AI
    else
        currentBestScore= + veryLargeNumber //this is the worst case for Player
    end

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn)
        if playersTurn ==AI’sTurn AND score>currentBestScore //AI wants positive score
           currentBestScore=score
        end
        if playersTurn ==Users’sTurn AND score<currentBestScore //user wants negative score
           currentBestScore=score
        end

     end

     return currentBestScore
end

この疑似コードは、開始ボードが何であるかを気にせず (現在のボードで AI が移動するたびにこの関数を呼び出します)、将来のパスがどのようになるかを返しません (ユーザーが最適にプレイするかどうかはわかりません。情報は役に立たない）が、AIにとって最適な未来に向かう動きを常に選択します。

より大きな問題に関する考慮事項

この場合、ゲームの最後まで探索する場合、可能な限り最良の未来 (勝ち、負け、または引き分け) は明らかですが、(たとえば) 未来に 5 つの動きしかない場合は、次のようになります。それを決定する何らかの方法を見つけなければなりません。チェスやドラフトでは、ピース スコアがこれを行う最も簡単な方法であり、ピースの位置が有用な強化になります。

于 2013-07-28T10:59:46.347 に答える
4

そんなことを5年ほど前からやっています。私は調査を行いました。時間はtic tac toeかからず、最初の 2 つか 3 つの動きのパターンを準備するだけです。

遊び方を確認する必要があります。

  1. コンピューターが最初に起動します。
  2. プレーヤーが最初に開始します。

9 つの異なる開始位置があります。

開始位置

しかし、実際にはそれらのうちの 3 つだけが異なります (他はローテーションされます)。tic tac toeその後、いくつかの特定の動きの後に何をすべきかがわかります。この場合、エンディングは最初の手によって決定されるため、アルゴリズムは必要ないと思います。したがって、この場合、いくつかのif-elseorswitchステートメントとrandomジェネレーターが必要になります。

于 2013-07-28T10:40:52.247 に答える
1

ユーザーが勝てるケースを予測する補助プログラムを作成します。次に、ユーザーが勝つためにしなければならないことをするためにあなたのAIを言うことができます.

于 2013-07-28T10:32:07.687 に答える