問題タブ [minimax]

レッスン例の特定のノードがアルファ ベータ プルーニングの結果として出力される理由を理解するのに頭を悩ませていたので、Peter Norvig のバージョンのアルファ ベータ プルーニングを Java で実装しました。

教科書によると、拡張する必要がある唯一のターミナル ノードは次のとおりです。

その順序で。

私のアルゴリズムは次のように出力します：

ルートは、ミニマックス ルートの正しい値です。数時間デバッグしましたが、障害が見つからないようです。何か見落としがありますか、それとも教科書が間違っていますか?

I am writing program with POSIX threads to find minimax in integer array. My question is how can I determine how many threads do I need to and is it correct to output minimum and maximum inside the thread function? And why do would I need dynamic threads?

Here is my code:

私は現在、オセロ用の優れた AI を作ろうとしており、Minimax アルゴリズムを使用してそれを実現しました。しかし、α-β プルーニングを使用してさらに深く検索しようとすると、アルゴリズムがひどく機能しているように見えました。Wiki や Berkely.edu などの他のソースで確認しましたが、正しく実装されていると思いますが、まだ問題が見つかりません。

したがって、上記が私のnegamaxコード(ウィキペディアからコピー)であり、次のように呼び出される場合:

次に、関数を呼び出す深さに関係なく、この関数は常に正の値を返しますか。これは、ヒューリスティック値自体が常に正であると想定しています。

私は (例えばhttp://radagast.se/othello/Help/order.html ) を読みましたが、最初に各レベルで最良の動きを検索すると (反復的な深化を使用して見つけることができます)、検索がはるかに高速になります。

追加のメモリと CPU 時間をあまり使用せずに、可能な限り最良の動きを検索するにはどうすればよいでしょうか?

Floyd-Warshall-Algorithm を実装して、全ペア最短経路問題を解決しました。これで、簡単な変更でミニマックスまたはマキシミン パスも計算できることがわかりました。しかし、結果の意味がわかりません (ミニマックス パスとは)。ウェブでいくつかの説明を見つけましたが、混乱しています。

ミニマックス - グラフ問題のミニマックスには、パスに沿って最大コストを最小化する 2 つのノード間のパスを見つけることが含まれます。

Maximin - Minimax とは逆に、パスに沿って最小コストを最大化するパスを見つける必要があるという問題があります。

誰か他の説明や例を教えてください。

私は3日間、ミニマックスアルゴリズムと一般的な再帰呼び出し（プログラミングに比較的慣れていない）の両方で最初に試みた小さなコードで何がうまくいかなかったかを理解しようと努力してきました。基本的に、実際に学習して作業したいもの、つまりミニマックスアルゴリズムを除いて、すべてがアプリケーションで機能しています。

基本的に、プレーヤーが移動するたびに、コンピューターは次の2つのいずれかを実行します。

• そのすぐ隣に勝利の動きがある場合、それはその動きを使用します。やさしい。
• ただし、この動きが直接見えない場合は、プレーヤーが勝つことができる動きを選択します。それがすべきことの正反対。

私はそれがから来ていないことを知っています：

• リーガルムーブゲッター
• ボードエバリュエーター自体は、それがポインターを持った奇妙なものから来ているのかどうかわかりませんが、エバリュエーターは正しいスコアを返しています。

コードは次のとおりです（プログラムを開始する関数の一部を切り取りました）：

あなたが助けることができることを願っています！

アルファ ベータ カットのミニマックスを使用して、オセロをプレイする単純なエンジンを作成しています。うまくプレイしていますが、奇妙なインデックス範囲外の例外が発生することがあります（常にエンドゲームの近くで）。

これが私のアルゴリズムです

makeMove と undoMove 内で、ゲームの状態 (黒の勝利、白の勝利、引き分け) を更新します。また、これらのメソッド内でプレーヤーを切り替えます。プレーヤーが手札を持っていない場合、ボードを変更せずにダミーの動きを行い、プレーヤーを切り替えます。

コードはもっとたくさんありますが、問題はアルゴリズムがゲーム オーバーの位置に達したときに発生すると思います。この問題は、エンジンがランダムな動きをするように設定した場合には発生しないため、問題はアルファ ベータ アルゴリズムにあるはずです。

ここに getAllMoves があり、この呼び出し getFlips:

これが getFlips です。

updateState は次のとおりです。

ありがとう！

アルファ ベータ プルーニングでミニマックスを使用してオセロ エンジンを作成しています。正常に動作していますが、次の問題が見つかりました。

アルゴリズムが位置が失われたことを検出すると、予想どおり -INFINITY を返しますが、この場合、「最良の」動きを追跡できません...位置はすでに失われていますが、とにかく有効な動きを返す必要があります（優れたチェスエンジンのように、より長く生き残る動きが望ましいです）。

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

私はそれを使用して呼び出します：

失われた位置 (たとえば、10 移動後に失われたと想像してください) が検索されると、上記の最良の変数は、引数として渡された空の無効な移動に等しくなります...なぜ??

助けてくれてありがとう！

アルファベータ法の基本的な実装はありますが、移動順序を改善する方法がわかりません。浅い検索、反復深化、またはbestMovesから遷移表への格納で実行できることを読みました。

このアルゴリズムでこれらの改善の1つを実装する方法について何か提案はありますか？