問題タブ [minimax]

3x4 (行 x 列) グリッドでの 3 行ゲームの negamax-algorithm に苦労しています。これは、よく知られている 4-in-a-row のようにプレイされます。つまり、ピースがドロップされます (TicTacToe とは異なります)。プレイヤーを R と B としましょう。R が最初の移動を行い、B の移動はネガマックスによって制御されます。可能な手は 1、2、3、または 4 です。これは、R: 手 3 --> B: 手 1 --> R: 手 3 の後に到達した問題の位置です。

ここで、R によって手 3 を防御するために、B は手 3 自体をプレイする必要がありますが、B はそうすることを拒否します。代わりに手 1 をプレイし、R の次の手でゲームは終了します。

ちなみに、3x3グリッドで完全に機能するネガマックス実装のエラーを探すのに丸一日費やしましたが、何も見つかりませんでした。

それから私は考え始めました: ネガマックス アルゴリズムの動作の別の説明は、R が 3x4 グリッドで手番 3 でゲームを開始した後、B がすべてのバリエーションで失われるということです。

誰かがこの命題に反論したり、私に証明を指摘したりできますか?

ありがとう、RSel

Chomp というゲームのプログラムを書いています。ウィキペディアでゲームの説明を読むことができますが、とにかく簡単に説明します。

次元 nxm のチョコレート バーでプレイします。つまり、バーは nxm の正方形に分割されます。各ターンで、現在のプレーヤーは正方形を選択し、選択した正方形の下と右のすべてを食べます。したがって、たとえば、次は有効な最初の動きです。

目的は、対戦相手にチョコレートの最後の部分を強制的に食べさせることです (毒が入っています)。

AI 部分に関しては、深さ切り捨てを伴うミニマックス アルゴリズムを使用しました。しかし、適切な位置評価関数が思いつきません。その結果、私の評価関数では、人間のプレイヤーが私のプログラムに勝つのは非常に簡単です。

誰でもできます：

• 良い位置評価関数を提案するか、
• 参考になる情報を提供したり、
• 代替アルゴリズムを提案しますか?

五目並べの変種であるゲームを書いています。基本的に、巨大なボード上の三目並べ。

誰かがゲームの優れたAI戦略を知っているかどうか疑問に思います。私の現在の実装は非常に愚かで、長い時間がかかります（O（n ^ 3）、移動するのに約1〜2秒）：

tic tac toe のミニマックス実装に完全に失敗した後、何が問題なのかわかりません。今はAIがぐるぐる回ってるだけなのに…

なぜこうなった？

私はミニマックスを本当に理解せずに実装しようとして一日を過ごしました。さて、私はミニマックスがどのように機能するかを理解していると思いますが、アルファベータ法は理解していません。

これがミニマックスの私の理解です：

1. 深さの制限まで、可能なすべての動きのリストを生成します。

2. 下部のすべてのノードにとって、ゲームフィールドがどれほど有利かを評価します。

3. すべてのノードについて（下から開始）、レイヤーが最大の場合、そのノードのスコアはその子の最高スコアになります。レイヤーが最小の場合、そのノードのスコアはその子の最低スコアです。

4. スコアを最大にしようとしている場合はスコアが最も高く、最小スコアが必要な場合はスコアが最も低い移動を実行します。

アルファベータプルーニングについての私の理解は、親レイヤーが最小で、ノードのスコアが最小スコアよりも高い場合、結果に影響を与えないため、プルーニングできるということです。

しかし、私が理解していないのは、ノードのスコアを計算できる場合は、ノードより下のレイヤー上のすべてのノードのスコアを知る必要があるということです（ミニマックスの私の理解では）。つまり、同じ量のCPUパワーを引き続き使用することになります。

誰かが私が間違っていることを指摘してもらえますか？この答え（ミニマックスは馬鹿のために説明されました）は私がミニマックスを理解するのを助けました、しかし私はアルファベータ剪定がどのように役立つかわかりません。

ありがとうございました。

私はウィキペディアの記事のpseducodeをフォローしましたが、うまくいったと思います。ただし、スコアが返されるため、どのような動きをしたいのかを知りたい場合は、正確には役に立ちません。

最高の動きを得る方法だと思うものを試しましたが、実際にそれ（チェス）と対戦しようとすると、AIは深さレベル3でやや遅れた動きをするのでうまくいかないと思います。

これが私の関数です：

この質問は、Prolog の経験がない AI ウィザードでも答えられる可能性があると言っておきましょう。

優れた本Prolog Programming for Artificial Intelligenceには、非常に簡潔で巧妙なミニマックスの実装があります。

min_to_move/1しかし、著者はそれについてあまり詳しく説明していませんでしたmax_to_move/1。

誰かが私にこれらを説明できますか?

前もって感謝します！

三目並べ解決ロボットを作っています。練習用に、非常にうまく機能するミニマックス アルゴリズムを使用して Tic Tac Toe ゲームを作成しました。コードをコントローラーに移植したいと思ったとき、このコントローラー用の C/C++ コンパイラーのどれも再帰関数をサポートしていないことがわかりました。したがって、この再帰的なミニマックス関数を反復または内部スタックを使用する関数に変換する助けが必要です:

私はこれを行う方法について完全に迷っています。助けていただければ幸いです:)

アルファベータ法でミニマックスを使用する場合、再帰を介して送信する代わりに、クラス変数としてアルファとベータを使用することは可能ですか？

それ以外の：

私は書くことができます：

そうすることでコードを最適化しようとすると（各再帰にintを送信する必要がない場合は、少し時間がかかる可能性があると思いました）、チェスプレーヤーが突然馬鹿になり、ポーンを殺すために女王を犠牲にし、他の愚かな過ちを犯しました。

彼は常に「通常のアルファベータ」の対戦相手よりもパフォーマンスがかなり劣っています。これは、対戦相手と比較してツリーのごく一部しか検索しないためだと思います（どちらも同じ深さを使用していますが、変更されたプレーヤーは剪定しているようです）より積極的になり、それによって訪問されるノードの数が減ります）。念のため、これを2回行いました。ここで切り取ったもの以外は、何も変更しません。

アルファベータアルゴリズムが正しいことを理解していれば、これは何の違いもありませんが、私のチェスプレーヤーにとっては違いはあります。私は何か間違ったことをしていますか？

ですから、今の私の主な質問は、それが最適化の観点から、またはコードの実践の観点から良いことであるかどうかではなく、むしろそれが可能であるかどうかです。

私はJavaでツリーを作成してデータを入力し、ミニマックスアルゴリズムを使用してAIに最適なコースを見つけようとしています。

ツリーを生成する再帰関数：

ツリーに値を入力する関数：

内容を印刷して、すべてが機能したかどうかを確認する関数をテストします。

そして、ノードクラス自体：final class Node {
public String state = "BCXXXCXXX";

}

印刷機能を実行すると、最初のノードに期待していた1つのBxXXCXXXが印刷されます。空のノードと深さ1で呼び出しました。なぜ、深さ6までツリーの残りの部分を生成（または印刷）しないのですか？

これはおそらく無関係だと思いますが、このコードは最終的にAndroidゲームで使用されます。