問題タブ [negamax]

私が作成したゲームでは、Negamax は深度の低い検索ではうまく機能しますが、深度を大きくするとフリーズします。深さを「整数」ではなく「ロング」型に変更することを考えましたが、他に何ができるかわかりません。計算に時間がかかることはわかっているので、裏で計算していて、フリーズしていると解釈している可能性があります。アドバイスをいただければ幸いです。ゲームでは、プレーヤーはポジションで 3 つの可能な動きのうちの 1 つしか行うことができず、チェスのように、どのポジションでも可能な動きが多数あり、最終的な位置に到達するのは困難です。

ありがとう

ダズ

私は C++ でチェス エンジンを作成していますが、このアルゴリズムを使用すると、最大深度を 1 に設定して予想されるプレイが得られます。

これが私のコードです：

私はオセロ プレーヤーを作成しており、アルファ ベータ プルーニングを使用してミニマックス アルゴリズムを実装しています。それから、私はオンラインで最高のものについてたくさんの調査を行い、それらがすべて使用している「ネガマックス」アルゴリズムについて聞き続けました. ほとんどの人は、ネガマックスはミニマックスよりも速いと考えているようです (最小プレーヤーと最大プレーヤーが切り替わらないからだと思いますか?)。

ネガマックスを使用するとどれだけ高速になるかについての洞察と、ミニマックスコードをネガマックスアルゴリズムに変換する方法に関するヒントやコードを知っているかどうか疑問に思っていました。

これが私のミニマックスアルゴリズムです：

アルファ ベータの剪定について質問する回答があったので、以下に示します。

チェスのようなゲーム用に negamax アルゴリズムを作成しましたが、最終的なボード値の結果を使用する方法を知りたいです。ネガマックス アルゴリズムの最終リターンは、プレイヤーが最善の手を打った後のボードの値を表していることは理解していますが、それは正確には有用な情報ではありません。私はその動きが何であるかを知る必要があります。

コードは次のとおりです。

bestValue が決定された後、現在の一致状態の子を再評価することを考えました。次に、それらを反復処理して、stateScore が bestValue に等しい子を見つけます。しかし、それらの多くはとにかく同じstateScoreを持つため、それは機能しません。それは、それらがどのカウントにつながるかです...

Connect 4 に NegaMax AI を実装しようとしています。アルゴリズムがうまく機能する場合があり、AI が勝つことができます。ただし、相手の 3 連続を完全にブロックできなかったり、3 連続でウィニング ショットを打てなかったりする場合があります。

評価関数は、グリッド (水平、垂直、斜め上、斜め下) を反復処理し、4 つの正方形のすべてのセットを取得します。次に、これらの各セット内をチェックし、これに基づいて評価します。

ここで提供される評価コードに基づいて関数を作成しました: http://blogs.skicelab.com/maurizio/connect-four.html

私の機能は次のとおりです。

私の negamax 関数は次のようになります。

接続 4 が解決されたことは承知していますが、これには間違いなくより良い方法がありますが、これを修正/改善するためのヘルプや提案は大歓迎です. ありがとう！

三目並べアプリケーションにネガマックス検索機能を実装しようとしていますが、最適な値が返されず、半ランダムに推測しているように見えます。私のコードの関連部分は次のとおりです。

ボードをパラメーターとして渡すのではなく、WIN、DRAW、VALID、または OCCUPIED (最後の 2 つは現在の議論には関係ありません) のいずれかである移動の結果を渡すことに注意することが重要です。自明です。Coordinate クラスは、移動の行と列の値を保持するだけです。

どうもありがとうございました ：）

私は現在、チェッカー ゲームを実装していますが、AI の状態が悪いことが唯一の障害です。Groovyで書かれています。

私はアルファ、ベータ剪定を伴う次の（試みられた）negaMaxアルゴリズムを持っています。私はいくつかの疑似ガイドに従いましたが、結果がかなり無意味であるため、明らかにどこかで失敗しています。

メソッドは次のように呼び出されます。negaMax(3, Integer.MIN_VALUE, Integer.MAX_VALUE, 1)

私は 1 人がコンピュータ プレーヤーになると決めました。それ以外はすべてユーザーです。

動きのハッシュ マップ、チェッカー (Piece オブジェクト) としてのキー、および実際の動きとしての値を持つことを選択しました。実際に何ができるかを追跡する必要があるため、動きだけを保存しても意味がありません。

別のハッシュマップを使用して、チェッカーをキーとして保存する後続の評価を保存しますが、代わりに今回は値の位置と位置スコアの両方を保存します (このためだけに Class PositionAndScore を作成しました)。

evaluateGameState 関数は、そのプレーヤーが動かせるピースの数としてスコアを初期化し、キ​​ングのポイントを追加し、タカブル ポジションにあるピースのポイントを撤回します。

ゲームをプレイするとき、コンピューターは最初の 2 つの動きを知的に見せますが、それ以降は下り坂になります。多くの場合、コンピューターは無効な動きを試みているため、実行されません。

私がこれまでに行ったことを調べて、何か間違っている点があればコメントするためだけに時間を割いてくれて、とても感謝しています。

どうもありがとう。

編集：わかりました、私はいくつかの進歩を遂げました。言及していないかもしれませんが、evaluationsハッシュマップはコンピューターの最善の動きを計算するために使用されます。それはそれから最高のスコアを取得します。

これが引き起こした問題は、プレーヤーが 1 であるループごとに評価ハッシュマップが追加されたため、正当ではない移動 (つまり、将来の移動であった) が追加されていたことでした。

これを解決するために、すべて同じ引数を使用するcallSearch()代わりに呼び出されるプリカーサ メソッドを追加することにしましたが、 も の引数に設定します。negaMaxrootDepthdepth

次に、アルゴリズムにこの小さな変更を加えました

私の考えでは、検索がルートに戻ったら、後続の評価を追加したいだけです。

いずれにせよ、これをすべて行った後、コンピューターはもはや不正な動きをしようとはしませんが、それでも適切な動きをすることはできません. 少し初歩的ですが、これは私の評価関数かもしれません。

チェス AI を構築しようとしていますが、奇妙なエラーが発生します。序文として、私はスタックオーバーフローを調べて同様の問題を見つけようとしましたが、タプルのアンパックを正しく実装していると思っていたので役に立ちませんでした。コードにバグが見つからないようです。

以下は私の negamax 関数のコードです。チェス盤、現在のプレイヤー、現在の深さを受け取ります。
ボード位置の値を表す数値を現在のプレイヤーに返す board.evalFunction() 関数を使用します。その機能は正常に動作しています。エラーが発生している行にマークを付けました: ValueError: need more than 0 values to unpack.
誰かが私を助けることができますか？

わかりましたので、これが少し長くなることを前もって認めます。私は C# 用のチェス エンジンを作成しており、最終的な目標は UCI の実装です。ボードを指定すると、エンジンがすべての有効な動きのリストを生成するところまで来ました。しかし、私の評価コードは苦労しているようです。それ自体に対してゲームをプレイするとき、エンジンはどちらかの側で 2 つのポーンを動かし、どちらかの側でピースを前後に動かすだけだからです。私の質問に答えるのに役立つことを願って、私のコードが呼び出されて使用される条件を最もよく理解できるように、以下のプログラムの重要な部分の概要を説明します。

これは、私のインターフェイスによって呼び出されるメイン メソッドに過ぎず、ここで興味深いものは何もありません。

この方法はうまく機能しています。x1、y1、x2、y2、重量の形式で移動のリストを返します。このメソッドが生成する重量は、殺されたピースの値です。ご不明な点がございましたら、お知らせください。

このメソッドはまだ完全ではありませんが (キャスリングやアンパッサンを処理しないため)、基本的には、特定の移動から新しいボード オブジェクトを生成するだけです。

このコードはおそらく必要ありませんが、ここのタイプミスがバグの原因である可能性を考慮して含めています。これは、エンジンに対してゲームをプレイしたり、エンジン自体を再生したりするための非常に基本的なユーザー インターフェイスです。

ここで、評価アルゴリズム自体を提示する前に、簡単に触れておきます。これは、コード全体で何度も参照されているボード オブジェクトです。これには、チェス盤の配列と、ゲームの現在の状態を定義するために必要なその他の変数が含まれています。

プログラムの残りの部分を概説したので、評価方法そのものを次に示します。コードは動きのリストを受け取り、それが検索されるはずの最も深い深さまである場合は、絶対値が最大のものを返すだけです。一番下にない場合は、受け取った先物リストの動きごとに単に先物リストを生成し、自分自身を再度呼び出します。次に、返された値が元の移動の重みに追加され、これまでに見つかった最良の移動と比較されます。しかし、私はこのアプローチで問題を抱えていました.negamaxがどのように機能するかを誤解したか、途中でタイプミスをしたためだと思います. 何が起こっているのか分かりますか？