問題タブ [minimax]

アルファベータ法のアルゴリズムは次のとおりです。

アルゴリズムは、ACTIONS関数が特定ので使用可能なすべてのアクションのリストを提供することを示していますstate。

たとえば、チェッカーのゲームを見てみましょう。あるチェッカー、たとえばA、が別のチェッカー、たとえば、と対角線上にあるとしますB。Aを実行できる場合B、それは（可能であれば、他のチェッカーを実行する必要があるため、避けられない）アクションです。または、複数のテイクがある場合、これらはすべてアクションです。この状況は、実際には鉛筆と紙を使用して描くことができます。より具体的には、状況はツリーを使用して表すことができます。各ノードは状態を表し、その子ノードへのエッジはその状態からの可能なアクションを表します。

ツリーデータ構造を明示的に格納する必要はないと思います。ただし、上記のアルゴリズムには次のステートメントが含まれていますreturn the action in ACTIONS(state) with value v。これで、ACTIONS(state)は特定の状態から可能なアクションを返します（たとえば、どこでAプレイする必要があるか）。

すべてのアルゴリズムを実行すると、値が取得され、ターミナルノードから渡されvた値でノードを追跡します。v

ここで、すべての状態からのすべての可能な移動またはアクションの完全なツリーを保存しないと仮定します。がreturn the action ACTIONS(state) with the value v実行されると、次の状態につながるアクションのみが取得され、アクションの1つが可能な限り最良のパスにつながることがわかります。しかし、ツリー全体など、追加の簿記がない場合、アクションを値と一致させることができますvか？

ミニマックス アルゴリズムを使用してチェスの動きを検索する独自のチェス エンジンに問題があります。5 層の深さ検索を使用し、マテリアル/ボーナス/モビリティ評価のみを使用しますが、無限に与えても愚かな動きをし、貴重なピースを犠牲にします。 （これは確かに検索の問題です）、私はどのタイプの剪定も使用しておらず、数秒で 5 深度の検索結果が得られます。

私はこの問題で1週間立ち往生しています。問題はチェスロジックではなくバックトラッキングにあると確信しています（したがって、チェスのバックグラウンドのない人なら誰でもこれを解決できます:)）そして私はたくさん検索しましたこれはスタックオーバーフローの私の最初の質問です皆さんが私を失望させないことを願っています:)

簡易検索コードはこちら

最近、私はミニマックスアルゴリズムに苦労しており、ようやく理解できたと言えます（stackoverflowの別の投稿に感謝します）。したがって、私はエディターを開き、試してみるために、非常に単純な (コードで私を責めないでください:P) tic tac toe に実装しようとしました。すべてが機能していますが、コンピュータ移動機能は常に私を -1 と返します。私はあなたにコードを提供するように求めているのではなく、それが「なぜ」それを行うのかを教えてください。コードを何度も検索しましたが、何も見つかりませんでした。コードはおそらく、Web で見つけた別のコードと非常によく似ています。ここに私のコードがあります:

Minimax アルゴリズムのみを適用して、Java で 3 * 3 Tic Tac Toe ゲームを実装しました。しかし、ボードのサイズを 4 * 4 に変更すると、プログラムがハングするようです。この問題を解決するために、アルファ ベータ プルーニングを使用して Minimax を適用する必要があるのか​​、それとも Minimax 自体で問題ないのかを尋ねたいと思います。

私は無敵の Tic Tac Toe の Minimax アルゴリズムに取り組んでいます。コンピューターが最初に実行されるときと、プレーヤーが最初に実行されるときの両方で機能する必要があります。現在のバージョンでは、コンピューターが先に行っても負けることはありません。ただし、プレイヤーが最初に行った場合、Minimax は最善の手を見つけられないようです (スコアとして常に -1 を返します)。

プレイヤーが最初の動きをした場合、コンピュータのミニマックス スコアが -1 に戻る原因は何ですか?

例：

「Minimax」クラスは次のとおりです。

「ボード」クラスは次のとおりです。

混乱があった場合の「Mark2」クラスは次のとおりです。

私は小さなゲームにミニマックスを実装していて、私が「先延ばし」と呼んでいるものに気づいています。非常に単純な例に要約します。

キャプチャーザフラッグゲームでは、旗はプレーヤーAから1マス上にあり、プレーヤーBは50スペース離れています。Aの番で、6手先を検索できます。私が見ているのは、Aは、すぐに旗をつかまなくても、Bの前に旗に到達できることを知っているので、すべての可能な動きの値が「Win」であるということです。したがって、UPが注文の最後の動きである場合、Bがすぐ近くに来るまでしばらく左と右に移動し、最後に旗を取得する必要があります。

最初は動作がバグのように見えましたが、それをステップスルーすることで、それぞれの動きが本当に「勝利」であると確信しましたが、動作は良くありません。今から4ムーブキャプチャした旗を、現在キャプチャした旗よりも価値を低くすることで評価に影響を与えることができましたが、ミニマックス検索に欠けているよりも側面があるのではないかと思いました。後でしか得られない同じように高いスコアよりも早い段階で高いスコアが最も望ましいという概念はありますか？

紛らわしいタイトル。詳しく説明します。ミニマックス検索を使用してコンピューターの次の動きを生成する AI チェス ゲームがあります。ミニマックス ツリーを選択された深さ (たとえば 5) まで下った後、最終的に次の最善の手を見つけます。私自身のテスト目的で、この次善の手 (チェス盤の構成として表される) だけでなく、次の手のスコアを決定するために使用された次の 4 つの手も印刷できるようにしたいと考えています。つまり、ミニマックス ツリーの各下位レベルでの最良の選択のパスであり、最終的に最良の次の動きとして選択された最上位ノードから始まります。何か案は？

私は現在、ミニマックスアルゴリズムを自分自身に教えようとしており、それをJavaの三目並べで実装しようとしています。ただし、私のアルゴリズムにはバグがあり、その原因を特定できません。

以下は完全なソースコードです（テキストの壁でごめんなさい！）：

プログラムを実行したときの出力は次のとおりです（コンピューターは円です）。

あなたが最初の動きの後に見ることができるように、コンピュータはそれがどんな動きをしてもそれが引き分けを得ることができると考えます（スコア= 0）。

2番目の動きで、列0、行1にクロスを置きます。何らかの理由で、コンピューターは、引き分けに到達するための2つの可能な動き（スコア= 0）と負けるための4つの動き（スコア= -1）があると考えます。 。その後、引き分けになると考えて間違った動きをします。

hasWonメソッドに何か問題があると最初に思いましたが、3つ続けて取得する8つの方法すべてをテストし、すべてtrueを返しました。

findBestMove、max、またはminメソッドのどこかに問題が存在するのではないかと思いますが、何が原因であるかを正確に把握することはできませんでした。

誰かがバグの原因を教えてくれたり、再帰的アルゴリズムをより適切にデバッグする方法について提案してくれたら、本当にありがたいです。

私はイタリア人なので、英語が下手で申し訳ありません。

私は C# でチェス ゲームの完全な実装、Player vs Player、Player vs Computer を書いていますが、今は NegaMax アルゴリズムの実装に苦労しています。興味のある方は、こちらが私の github リポジトリです: https://github.com/crybot/ChessEngine_NOGUI/tree/master/Chess%20Engine%20-%20NOGUI

私はこのプロジェクトを可能な限り OO にしようと試みたので、私の設計が間違っていると思われる場合は教えてください :)

ここに私の問題があります:

すべてのプレイヤーに対して対称的に機能する非常に単純な評価関数を実装しました。

そして、ここに私の NegaMax 関数があります。この関数は、Game パラメーター (ボード、プレーヤー、ecc.ecc を含む)、enum によって提供される playerColor、および深度検索を受け入れます。

まず、EnginePlayer のすべての可能な動きをスキャンしてから、NegaMax 関数からスコアを取得しますが、何かが機能していません...

これですべてだと思います...私が間違っていることを見つけていただければ幸いです:)ありがとう。

編集: ムーブ ジェネレーターの不正解を示す Perft を実装しました。比較的見つけやすいバグを見つけるのに大いに役立ちましたが、最終的にいくつかの結果はまだ間違っています。結果は次のとおりです。

正しい結果は次のとおりです: https://chessprogramming.wikispaces.com/Perft+Results

ご覧のように、深さ 4 では正しいノードが分析されますが、キャプチャとチェックの値は正しくありません (メイトは正しいのに)。

これらの結果のおかげで、深さ 4 で移動ごとに分析されたノードを分割することでバグを分離しようとしました。これらの結果が得られました。

そして、Sharper から取得したこれらの結果と比較します。

しかし、ここでも値は正しいです...だから私はそれらの結果を得るための深さ5のperftを試しました:

次に、Sharper の結果と比較します。

それで、ポーンのダブルプッシュによって生成された動きが問題の原因であることに気付きました...しかし、実際にはバグを見つけることができません... 誰か同じ問題がありましたか? または同様のもの、またはそのバグを見つけるための単なるヒント...

ありがとうございます ：）

そこで最近、ゼロサムゲームで使われているミニマックス関数を見ていました。私はそれを完全に理解しましたが、実際の機能のためにボードがどのように実装されているかを除いて：

たとえば、私が見つけたこのサンプル実装には、次の宣言があります。

私の唯一の質問は、正確にはBoard何ですか？それは構造体、クラス、配列、またはその他の構造体ですか？また、三目並べのようなミニマックス用のサンプルボードをどのように実装しますか（例として）？ウィキペディアまたはグーグルで何も見つかりませんでした。