問題タブ [minimax]

Android 用のリバーシ ゲームを実装する必要があります。私はすべてのゲームを実装することに成功し、機能していますが、問題は私が AI を持っていないことです。実際、すべての動きで、コンピューターは彼に最高のピース数を達成する位置に移動します。

alpha-beta pruning アルゴリズムを実装することにしました。インターネットでいろいろ調べたのですが、どうすればよいのか、最終的な結論には至りませんでした。いくつかの機能を実装しようとしましたが、目的の動作を実現できませんでした。

私のボードはクラス Board に保存されます (このクラス内では、各プレイヤーが占有するピースは 2 次元の int 配列に保存されます)。小さな図を添付しました（見栄えが悪くてすみません）。

図: https://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

私の実装で minimax アルゴリズムを使用する方法を理解するのに助けが必要です。

ここまででわかったことは、ボードの価値に関する評価関数を作成する必要があるということです。

ボードの価値を計算するには、次の要素を考慮する必要があります: -フリー コーナー (私の質問は、フリー コーナー、または現在の動きで取ることができるコーナーだけに注意する必要があるということです!ここでジレンマ) . - ボードの可動性: 現在の移動後に、移動できるピースの数を確認します。・ボードの安定性…ボード上で裏返せないピースの数を意味することは知っています。-移動が私に提供するピースの数

Boardオブジェクトと部門を引数として取る新しいクラスBoardAIを実装する予定です。

この AI をどのように実装する必要があるかについて、アイデアの論理的な流れを教えてください。dept で計算しているときに再帰について助けが必要ですが、最良の選択をどのように計算するのかわかりません。

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

私はチェスプログラムに着実に取り組んでおり、ミニマックス検索、反復的な深化、および転置テーブルが間もなく登場します。ただし、現時点では、静止検索で特定したバグがあります。疑似コードの実装を直接コピーしたのに、うまくいかないようで、イライラしています。オンラインで見つけた他の実装でも同様の結果が得られました。

このバグは、複数の奪還が可能な場合に対戦相手の「最良の」捕獲を誤って計算するようであり、その結果、通常は検索を呼び出す側に有利な値が返されます。

エンジンはC#で書かれています

私の評価関数は、それぞれ白または黒を支持する +/- 値を返します。

この Python コードでは、同期の問題にすぎないと思います。このコードは、ミニマックス アルゴリズムを Tic Tac Toe ゲームに適用することを目的としており、可能なすべての動きを 1 つずつ調べる単一のプロセスではなく、並列プロセスで実装されています。それを本当に悪い考えだとレッテルを貼る前に、私はそうすることを要求されました.

未知のメソッドは、その名前で示唆されていることを正確に実行すると仮定し、適切に機能すると仮定します (手動でテストされています)。私が100％確信していない唯一の方法はこれです。コードは次のとおりです。

ゲームボードは、単純なBoardクラス (拡張listクラス) で表されます。 クラスはPython モジュール SimpleQueueからインポートされます。function は、私が実装したヒューリスティック関数です。この関数は、プレイヤー MAX に適したボードには正の値を返し、MIN には負の値を返し、引き分けの場合には 0 を返します。アルゴリズムコードは次のとおりです。ProcessmultiprocessingH

主な方法は単純です：

私はしばしばこの種のエラーに遭遇します：

しかしいつもではない。再帰的な方法に間違いはありますか？私は本当にそれを理解することはできません。

私のアイデアは、ターンごとにローカルキューを構築し、そのキューから最大/最小値を抽出して、前のターンのキューである「上部」キューに移動することでした。

私は学校でボードゲームの AI コンテストに参加する予定で、優位に立つために同時実行のアイデアを考え出そうとしています。Javaで実装する予定で、cまたはc ++の方がはるかに高速であることを理解しているため、おそらく不利になるでしょう。

ゲーム ツリーを単純に半分に分割することはできないようです。これは、最良の手を最初に残すべき移動順序のためであり、特定の深さで現在のアルファ/ベータを伝達することは困難であるか、不可能でさえあるようです。 . 同期が必要な転置テーブルも使用します。

検索以外に、2 番目のスレッドが実行できることで、検索を支援したり、ある種の速度向上を提供したりできるものはありますか。各 AI は 5 秒で動き、相手が考えている間にプログラムを実行できます。

どんなにあいまいなものであっても、ご意見をいただければ幸いです。

ミニマックス アルゴリズムは、三目並べのようなゲームの 2 人のプレーヤーについてよく説明されています。タンク ゲームの AI を作成する必要があります。このゲームでは、戦車は壁の形をした障害物がある迷路を移動する必要があります。目標は、コインの山を集めることです。プレイヤーが 2 人だけの場合は、ミニマックス アルゴリズムを実装できます。しかし、それを2つ以上に実装する方法は? 各ターンで、各プレイヤーは自分の勝率を最大化しようとします。元のミニマックス アルゴリズムのように 2 人のプレイヤー レベルを作成することで、すべてのプレイヤーを 1 人の敵として考えることはできません。質問の形式が適切でない場合はご容赦ください。このフォーラムはまだ新しい

(注: これは CS の宿題ではありません)

Coffeescript でミニマックス ゲーム ツリー検索アルゴリズムを実装しようとしましたが、アルゴリズムで引き続きエラーが発生します。2 つの主な問題があるようです: 1) アルゴリズム自体が、アルファ ベータ プルーニング中に適切な値を返していないようです (明らかに、より大きな問題です)。2) 9 つの整数の配列で表される私のゲームボード オブジェクトが、 DOM にアタッチされると、ボードが複製され、それをパラメーターとしてミニマックス検索関数の再帰呼び出しに渡すことが問題になります。

ボード、ボット (ミニマックス アルゴリズムが存在する場所)、およびゲームの 3 つのクラスがあります。読み込み時に新しいゲームが開始され (それに応じてデバッグ アラートがポップアップします)、ボードはデバッグを容易にするために事前に構成されたプレイでモックされることに注意してください。

私はミニマックス ソリューションで 3 つの別々の試みを試みたことに注意してください (空き時間に何週間もこれに頭を悩ませていました)、後者の 2 つは現在コメント アウトされています。私の最終的な解決策では、この疑似コードに従っています。

index.html

ボードコーヒー

bot.coffee

ルールズコーヒー

ゲームコーヒー

助けてくれてとても感謝しています。

このような質問は以前にも聞いたことがあると思いますが、疑問を解決することができませんでした。私は単純なOthelloエンジンを持っています（実際には非常にうまく機能します）。これは、以下のクラスを使用して最良の動きを実現します。

私はbestFoundインスタンス変数を持っていますが、疑問は、なぜ呼び出す必要があるのか​​ということです

そしてそれを渡しますか？コードは機能しますが、私には非常に奇妙に思えます！

最高の動きやプリンシパルバリエーションを得るための「より良い」方法はありますか？私は実際には再帰の専門家ではありません。これをデバッグして視覚化するのは非常に困難です。ありがとう！

** PS：https://github.com/fernandotenorio/でクローンを作成できます

Javaでチェッカーゲームのアルファベータプルーニングを使用してミニマックスを実装しようとしています。私のミニマックスアルゴリズムは完璧に機能します。私のコードは、アルファベータコードを使用して実行されます。残念ながら、標準のミニマックスアルゴリズムに対して1000ゲームをプレイすると、アルファベータアルゴリズムは常に50ゲーム程度遅れます。

アルファベータ法は動きの質を低下させるべきではないので、それらを達成するのにかかる時間だけで、何かが間違っている必要があります。ただし、ペンと紙を取り出し、仮想の葉ノード値を描画し、アルゴリズムを使用して、正しい最良の動きを計算するかどうかを予測しました。論理エラーはないようです。このビデオのツリーを使用しました：Alpha-BetaPruningを使用してアルゴリズムをトレースしました。論理的にはすべて同じ選択を行う必要があるため、機能する実装である必要があります。

また、コードにprintステートメントを追加しました（混乱を減らすために削除されています）。値は正しく返され、表示され、プルーニングが行われます。私の最善の努力にもかかわらず、私は論理エラーがどこにあるかを見つけることができませんでした。これは、これを実装するための私の3番目の異なる試みであり、それらすべてに同じ問題がありました。

ここに完全なコードを投稿することはできません。長すぎるため、エラーに関連するメソッドを含めました。確かではありませんが、問題は非再帰的なmove（）メソッドにある可能性が高いと思いますが、論理的なエラーを見つけることができないので、もっとスラッシングして、おそらく何かを作っているでしょう韻や理由がなくても、良くなるよりも悪くなる。

forループの再帰呼び出しから複数の整数値を回復するためのトリックはありますか？それは私のミニマックスとネガマックスの両方の実装でうまく機能しますが、アルファベータ法はいくつかの奇妙な結果を生み出すようです。

私は Nine Men's Morris ゲームを書いていますが、これまでのところ Negascout 検索は問題なく動作しています。ただし、反復的な深化を追加したいので、次のコードを思い付きました。

私も吸引窓を使っています。しかし、検索すると最悪の動きが返されます!! 問題は検索ウィンドウの再設定にあると思います。検索ウィンドウを外側のループに移動する必要がありますか?

他の AI と競合する AI を作成する必要があります。

どちらの AI も同じハードウェアで実行され、処理時間とメモリ量は同じです。対戦相手の AI が、アルファ ベータ プルーニングを伴うミニマックス アルゴリズムを使用することはわかっています。

私の質問は、そのような相手を打ち負かすためのいくつかのアプローチは何ですか? 自分でミニマックスを使用すると、両方の AI が互いの動きを完全に予測し、ゲーム固有のプロパティ (最初の動きが勝つなど) に基づいてゲームが解決されます。

明らかな解決策は、より良い評価を可能にする可能性のある動きをどうにかして先に見ることです。プロセッサ時間は同じであるため、より深く評価することはできませんでした (反対の AI コードが等しく最適化されていると仮定して)。事前に計算されたツリーを使用してさらに利点を得ることができましたが、スーパー コンピューターがなければ、重要なゲームを「解く」ことはできませんでした。

アルファベータが剪定したような最適でないノードを意図的に選択することには、何らかの価値がありますか? これにより、対戦相手が戻ってツリーを再評価する必要があるため、CPU 時間のペナルティが発生する可能性があります。ペナルティが発生するだけでなく、ミニマックス ツリー + アルファ ベータを評価して、アルファ ベータが直接的な利益を得ることなくどのノードを削除するかを確認する必要があります。

そのような対戦相手に対して最適化するための他の戦略は何ですか?