問題タブ [minimax]

三目並べゲームのMini-maxを探していましたが、再帰がどのように機能するのか理解できませんでしたか？さて、基本的にここに私の質問があります：

1. ミニマックスはどのようにして誰の番かを知るのですか？自分のターンを生成しているプレーヤーを示す最良の方法は何ですか？
2. 可能な動きをどのように生成しますか？
3. ターミナルノードにいることをどのように知っていますか？また、ターミナルノードをどのように生成しますか？

たとえば、この擬似コードでは

Anodeボードは正しいですか？そして、コードが再帰的に下がらなければならない層の深さはどれくらいですか？また、max関数とは何ですか？ノードはどこから生成されていますか？

これまでのところ、ボードを作成するための次のコードがあります。

しかし、誰の番かをどうやって知ることができますか？また、ボードの子ノードを生成するにはどうすればよいですか？

私は、両方のプレーヤーが人間であり、コンピューターがミニマックスアルゴリズムを使用して最適な動きを提案するたびに、三目並べゲームにミニマックスアルゴリズムを実装しようとしています。しかし、それは毎回正しい提案をしているわけではありません。例：次のシナリオに対して正しい提案はありません：プレーヤーX：1プレーヤーO：2プレーヤーX：5。これが私のコードです。

私はクラスを作る練習のためにtictactoeボードに取り組んでいますが、アルゴリズムに問題が発生しました。攻めのベストムーブを返しているように見えますが、守備はしていません。私はどこを台無しにしたのかわからず、それを見つけることができないようです。私はそれについてここで多くのことを調べ、それをsimularプロジェクトと比較しましたが、まだそれを理解できないようです. これが私のコードです。

すべてのクラスが一番下にあります。ヘルプと修正をお寄せいただきありがとうございます。:)

次のコードで再帰的にしましたが、スコアリングはまだわかりません..値が1、0、または-1の場合、同じ値の複数の移動がある場合、最初の移動が行われる可能性があります最善の手ではない「ブロッキング。

テストの結果は次のとおりです

テスト1

テスト 2

アルファ/ベータ法を含むウィキペディアにあるように、私はNegamaxを実装しました。

しかし、それは負けた動きを支持しているようであり、それは私の知る限り無効な結果です。

ゲームはTic-Tac-Toeです。ゲームプレイのほとんどを抽象化したので、アルゴリズム内のエラーを見つけるのはかなり簡単です。

この入力を与える：

アルゴリズムは、ピースを0、1に配置することを選択し、保証された損失を引き起こし、このトラップを実行します（勝つか引き分けで終了することはできません）。

ゲームの実装は正しいと確信していますが、アルゴリズムも正しいはずです。

編集：更新されevaluate、nextMove。

EDIT2：最初の問題を修正しましたが、まだバグがあるようです

コンピュータープログラムにカードゲームをプレイさせるために、ミニマックス検索（アルファベータプルーニングを使用）、またはむしろネガマックス検索を使用したいと思います。

カードゲームは実際には4人のプレイヤーで構成されています。そこで、ミニマックス法などを使えるようにするために、ゲームを「他人」に対して「私」に単純化しています。それぞれの「移動」の後、ゲーム自体から現在の状態の評価を客観的に読み取ることができます。4人のプレイヤー全員がカードを置いたとき、最も高いプレイヤーがすべてのプレイヤーに勝ちます-そしてカードの値がカウントされます。

他の3人のプレイヤー間のカードの分配が正確にどのようになっているのかわからないので、自分のものではないカードですべての可能な分配（「世界」）をシミュレートする必要があると思いました。あなたは12枚のカードを持っています、他の3人のプレーヤーは合計で36枚のカードを持っています。

したがって、私のアプローチはこのアルゴリズムです。ここで、playerはプログラムが動きを見つける必要があるかもしれない3人のコンピュータープレーヤーを象徴する1から3の間の数字です。そして-player、対戦相手、つまり他の3人のプレイヤー全員を表します。

これはうまくいくようですが、深さが1（depthLeft=1）の場合、プログラムはすでに平均50,000ムーブ（配置されたカード）を計算する必要があります。もちろん、これは多すぎます！

だから私の質問は：

1. 実装はまったく正しいですか？このようなゲームをシミュレートできますか？特に不完全情報については？
2. 速度と作業負荷のアルゴリズムをどのように改善できますか？
3. たとえば、良い結果を維持しながら、可能な移動のセットを50％のランダムなセットに減らして、速度を向上させることはできますか？
4. 私はUCTアルゴリズムが良い解決策であることに気づきました（多分）。このアルゴリズムを知っていますか？実装を手伝ってもらえますか？

情報が不完全な 2 人用ゲーム「Stratego」を開発したいと考えています。

ゲームはチェスに「いくらか」似ていますが、最初は相手の駒のランクについて何も知りません。駒が敵の駒を攻撃したり攻撃されたりすると、ランクが明らかになり、ランクの高い駒がランクの低い駒を殺したり捕獲したりします。ゲームの詳細については、こちらをご覧ください。

少し調べてみました。JA Stankiewicz 著の「Opponent Modeling in Stratego」を読みました。しかし、ゲームの開発方法に関する完全なチュートリアルは見つかりませんでした。私は 2 人用ゲーム (「オセロ」、別名リバーシ) の開発に成功し、MINIMAX アルゴリズムとアルファ ベータ プルーニングに精通しています。

ゼロサム 2 プレーヤー ゲームの開発にもモンテカルロ木探索が使用されていることをどこかで見つけました。ストラテゴなどのゲームに使用できますか? 同じことの完全なチュートリアルを入手できますか?

モンテカルロ木探索を含まない他のチュートリアルも役に立ちます:)

私は tictactoe プログラムを書いていますが、それはあなたの伝統的な tictactoe ではありません

まず、ボードは 4x4 で、勝つ方法は、同じ種類のカードを 3 つと、対戦相手を 1 行、1 列、または斜めに並べることです。したがって、次の例では、最初の列で「O」が勝利します。

プログラムに打ち負かすことができない「ハード」モードを与えるために、ミニマックスアルゴリズムを実装しようとしています。

私の問題は、考えられるすべてのゲーム状態を含むツリーを作成することは期待できないため、生成できるゲーム状態を評価する何らかの関数を考え出す必要があることです。

私の質問だと思いますが、どうすればそのような機能を思い付くことができますか?

この質問と私の別の質問は、いくつかのことを理解した後、1 つに統合されたので、この質問を修正しました。

私が自分の機能で達成しようとしていることは、以下に概説されています。

1. すべてのスポットを繰り返します。開いている場合は、現在のプレーヤーのシンボルがあるスポットを選択します。
2. この動きによってゲームに勝利し、コンピューター プレイヤーの番になった場合、スポット (整数) とスポットのスコア (整数、この場合は 1) のキーと値のペアをscored-spotsハッシュ マップに追加します。
3. この同じ関数を再帰して呼び出し、新しい scored-spotsハッシュマップ、移動したばかりのボード、同じプレーヤー、および同じシンボルを渡します。
4. ただし、ゲームに勝てなかった場合は、次の条件ステートメントに進み、それを確認します。
5. 次の条件文も同じように、スコアが異なるだけです (コンピューターのターンでの勝利は 1、人間のターンでの勝利は -1、引き分けは 0)。
6. どの条件ステートメントも true と評価されない場合は、とにかく再帰します (scored-spotsこの場合、ハッシュ マップに違いはありません)。

これが私が試したコードですが、これは私が期待している値を返しません。

注:
boardは次のようなハッシュ マップです: {0 "0", 1 "1", 2 "2"}(スポット位置 - スポット値)
symは "X" や "O" などの記号、または次
current-playerのようなハッシュ マップです::computer:human
scored-spots{}

戻り値として期待しているのは、各オープン スポットがスコア付けされたハッシュ マップです。たとえば、{1 0, 4 1, 5 -1, 6 -1, 8 0}.

代わりに、この board: を渡す
{1 "X" 2 "X" 3 "O" 4 "4" 5 "5" 6 "6" 7 "7" 8 "X" 9 "O"}と
、多数listのハッシュ マップを含む戻り値が得られます。

ミニマックスのようなアルゴリズムを使用して完璧なゲームをプレイする方法を知っています（この場合、私はTic-Tac-Toeに似たゲームを探しています）

ただし、人間のプレイヤーが実際に敗北する可能性がある、不完全なアルゴリズム、またはさまざまな「スキルレベル」（Easy、Medium、Hardなど）のAIを作成するにはどうすればよいのでしょうか。

Minimax algorithm現在、 forを実装しようとしていTic Tac Toeます。現在のバージョンでは、コンピューターが失敗する場合がいくつかありますが、その理由はよくわかりません。たとえば、私が (人間のプレイヤーとして) 左上隅の x で開始すると、コンピューターは左下隅の ao で反応します (もちろん、これは彼が負けることと同じです)。プログラム全体はMVC-Design.

質問: Minimax アルゴリズムを正しく修正しましたか? または (そうでない場合) 「悪い」動きの原因は何ですか?

コードは次のとおりです: (正しいことをテストしたいくつかのメソッドのコードは省略しました)

ゲーム クラスは、Cell[][] 配列内のフィールドを表し (AIMinimax と同じ方法)、AIMinimax のインスタンスを作成し、これに対して nextMove を呼び出して、コンピューターが行う次の Move を生成します。デフォルトでは、Human Player が常に開始されます。

前もって感謝します！