問題タブ [alpha-beta-pruning]

この与えられたツリーにアルファベータプルーニングアルゴリズムを適用しようとしています。

ノードCに到達すると、Bのすべての子を展開した後、A> = -4を指定し、次にCを展開してI = -3を取得するため、スタックします。これは-4より大きい（-3> = -4） 。したがって、Aを-3に更新しますか？もしそうなら、その後、-3> = -3なので、JとKを削除しますか？例を実行したとき、J、K、M、およびNを剪定しました。これについては本当にわかりません=（

編集：

別の質問：Bを探索し、Bの値をAに渡した後、この値をCに渡し、したがってIに渡しますか？私はこれが事実であるという例を見ました。ここにあります：http ：//web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf

ただし、この例（http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf）では、値を渡していないように見えます。代わりに、値を上向きに伝搬しているだけのようです。どちらが正しいのか、それがまったく違いを生むのかはわかりません。

個人的なプロジェクトとして Connect 4 の Python で minimax を使用して AI を実装しようとしています。現在、私はこれを持っています。

しかし、コンピューターは何らかの理由で勝ちの動きをしません。たとえば、このボードが与えられた場合、コンピューターは 4 列目でプレイして勝利を収める必要があります。ただし、実際には 3 列目で再生されました。

OK、私の問題はボードゲームプログラミングで遊んだことがある人なら誰でもよく知っているはずなので、ここにあります：

• MiniMaxアルゴリズムのバリエーションを実装しました（最小/最大値の代わりに移動を返します）。
• 完全に失敗しましたが、アルファベータとして設定しようとしました。

だから、これが私のMiniMaxコードです：

アルファベータ検索になるように上記のことをどのように調整できるかについてのアイデアはありますか？

そして、これがアルファ-ベータ変換の私の試みです（これは惨めに失敗します）：

ヒント（誤解を避けるため）：

• このthis->eval()関数は、プレーヤーAの観点からスコアを返します。たとえば、+ 100スコアは、ポジションがプレーヤーAに有利であることを意味し、-100スコアは、ポジションがプレーヤーBに有利であることを意味します。

• MINUS_INFとPLUS_INFは、それぞれ任意の小さい値と大きい値として定義されています。

• これは宿題のようなものではありません（もしそれが私がそのようなもので遊ぶことに興味を持っていなかったとしたら...笑）

• Moveは、移動に関する詳細と、それぞれの値（関数によって割り当てられた値）を含む単純なクラスevalです。

• HASHMAKE移動- UNHASHMAKE（非）作成と移動-（非）ハッシュの2つのマクロであり、大きな違いはありません。

• MAXMOVEこのように定義されます：#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

• MINMOVEこのように定義されます：#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

PLINQ を使用すると、説明できないような奇妙な結果が得られます。検索プロセスを高速化するために Alpha Beta ツリー検索を並列化しようとしてきましたが、実際には速度が低下しています。並列度を上げると、1 秒あたりのノード数が直線的に増加すると予想されます...そして、プルーニングが後で延期されるため、処理される追加のノードでヒットします。ノード数は予想と一致しますが、私の時間は一致しません:

非 plinq、訪問したノード: 61418、ランタイム: 0:00.67

並列度: 1、アクセスしたノード: 61418、ランタイム: 0:01.48

並列度: 2、訪問したノード: 75504、ランタイム: 0:10.08

並列度: 4、訪問したノード: 95664、実行時間: 1:51.98

並列度: 8、訪問したノード: 108148、実行時間: 1:48.94

可能性のある犯人を特定するのを手伝ってくれる人はいますか?

関連コード:

そして、ツリーのレベル間でアルファ ベータ パラメータを共有するためのデータ構造...

人工知能とそれをプログラムに実装する方法について学ぼうとしています。最も簡単に開始できるのは、単純なゲーム (この場合は Tic-Tac-Toe) とゲーム検索ツリー (再帰呼び出しであり、実際のデータ構造ではありません) です。このトピックに関する講義で、この非常に役立つビデオを見つけました。

私が抱えている問題は、アルゴリズムへの最初の呼び出しの実行に非常に長い時間 (約 15 秒) がかかっていることです。コード全体にデバッグ ログ出力を配置しましたが、アルゴリズムの一部を過度に呼び出しているようです。

コンピューターに最適な動きを選択する方法は次のとおりです。

スポットが空の場合にmakeMoveメソッドが移動し、値を返す場所 (-1 - 人間の勝利、0 - 引き分け、1 - コンピュータの勝利、-2 または 2 - それ以外)。エラーはgetAllLegalMovesメソッドにある可能性があると思いますが：

すべてを要約すると:最適な動きを選択するのに時間がかかる原因は何ですか? 私は何が欠けていますか？このアルゴリズムを実装する簡単な方法はありますか? どんな助けや提案も大歓迎です、ありがとう!

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

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

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

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

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

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