問題タブ [alpha-beta-pruning]

私は時々ボードゲームの変種をプレイするプログラムを書いています。基本的な戦略は、標準的なアルファベータ法または同様の検索であり、エンドゲームやオープニングへの通常のアプローチによって強化されることもあります。私は主に変則チェスをいじっていたので、評価関数を選ぶときは、基本的なチェス評価関数を使用します。

しかし、今はまったく新しいボードゲームをプレイするプログラムを書いています。良いまたはまともな評価関数を選択するにはどうすればよいですか？

主な課題は、常に同じピースがボード上にあるため、通常のマテリアル機能が位置によって変化せず、ゲームのプレイ回数が1,000回未満であるため、人間が必ずしも十分にプレイできるとは限らないことです。まだ洞察を与えるには。（PS。私はMoGoアプローチを検討しましたが、ランダムゲームが終了する可能性は低いです。）

ゲームの詳細：ゲームは、片面に6個固定された10x10のボードでプレイされます。ピースには特定の移動ルールがあり、特定の方法で相互作用しますが、ピースがキャプチャされることはありません。ゲームの目標は、ボード上の特定の特別な正方形に十分な数のピースを置くことです。コンピュータプログラムの目標は、現在の人間のプレーヤーと競争力のある、またはそれよりも優れたプレーヤーを提供することです。

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

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

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

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

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

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

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

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

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

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

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

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

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

アルゴリズムは、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か？

私は現在チェスエンジンを書いていて、かなり進んでいますが、問題に遭遇したので、方法についていくつか意見をお願いします. わかりました、私の問題は、私のチェス AI が「最善の」動きをしないという事実です。その駒が取り戻される可能性があるという事実などの単純なことを認識できていないようです。私のアルファベータ剪定は次のようになります。

私のアルファ ベータ プルーニングは妥当な動きを返すので十分に機能すると思います。問題は rootMove を取得しようとするときだと思います。私は（によってルート移動を取得しようとしています

どんなアイデアでも役に立ちます、ありがとう。

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

Tic Tac Toe を解決するために利用できるアルゴリズムは何ですか? 特にボードのサイズが 3 * 3 ではなく 4 * 4 以上の場合は? Minimax & alpha-beta pruning で 4 * 4 を試しましたが、PC がハングしているようで、スタック オーバーフローで例外がスローされます。これらのソース コードが JavaScript で書かれているのを見ましたが、どのアルゴリズムを使用しているのかわかりません。 http://js-x.com/page/javascripts__example.html?view=153

ボードゲームをコーディングしています。アルファベータ法を使用してゲームツリーを生成しました。2つのオプションがあります。

1. 反復深化を使用してアルファベータを最適化し、時間が経過するまでもう1つの層を生成し続けるようにします。
2. 試行錯誤の結果、事前に下層を検査しなくても、制限時間内にすべてのボード構成で到達可能な最大深度がわかりました。

どちらのアプローチが優れており、検索がより深く到達するようになりますか？たとえば、最初は、利用可能なすべての時間を消費する深さXのツリーを生成できることを知っています...反復深化はさらに深さを追加できますか？

もっと明確にできるかどうか教えてください...

私は現在、ミニマックス法とアルファベータ法を使用してオセロ用のシンプルなAIを開発しています。

私の質問は、ボードの状態の評価関数に関連しています。

私は現在、以下を見て評価しようとしています。

1. ディスク数（パリティ）

2. 法的な動きの数

3. 特定のポジションの重要性

つまり、ルートノードがゲームの初期状態であるとしましょう。最初のアクションはAIのアクションであり、2番目のアクションは対戦相手のアクションです。

ノードレベル1で、AIのチップのディスク数と、アクションが完了した後の時点でAIが実行できる合法的な移動の数を評価しますか？

ノードレベル2で、対戦相手のチップのディスク数と、対戦相手がアクションを完了した後の時点で実行できる合法的な移動の数を評価しますか？

意味AI移動->対戦相手の移動==>この時点で、対戦相手のディスク数と対戦相手が作成できる合法的な数を評価します。

9MenのモリスゲームにゲームAIを実装しようとしています。

これまでのところ、ボードは次のように表されています。

さて、すべてのノードは次のように表されます。

トークンは次のよう になります。

そして、これが私が立ち往生している私のアルファベータ剪定アルゴリズムの実装です:

OK、これがこれまでの私の機能です。正しい道を進んでいてもわからない??!

私の機能で何が問題になっていますか？
上記の質問に答えてください (getBestMove() 関数の 1 から 5)。

事前に感謝し、私の言語の間違いを避けてください（私の英語はあまり上手ではありません）

saeednさん、お返事ありがとうございます!!

私は誰も私に答えないだろうと思っていました:)。何が起こっているのかを理解するのに本当に役立ちます。

そのため、 CheckWinner( bool )は、現在のプレイヤーがこの深さで非常に優れたアドバンテージ (勝ったり、対戦相手をブロックするなどの非常に優れた動きなど) を持っているかどうかを確認し、そうであれば、現在のプレイヤーにBIGスコアを返します。これはすべて、プレーヤーも対戦相手も毎ターン勝利（大きなスコア）​​を試みないためですよね？

それ以外の場合、depth =0 の場合は、現在選択されているボードの評価 (スコア) を返します ( int evaluateBoard() )。

この後、1 つのボードを生成する必要があります (1 つのトークンの可能な移動を使用)。

OK、新しく生成されたボードがあるので、再帰して、より良いボード (より良いSCOREを持つボード) が見つかった場合は、現在のボードを selectedBoard に保存します。そうでない場合は、カットオフして戻ります (ツリーをさらに下にチェックしないでください)。

ありがとうございます！