問題タブ [minmax]

三目並べのゲームで最小最大アルゴリズム (コンピューター AI) を機能させようとしています。私は何日もこれにこだわっています。"O"基本的に、コンピューター AI が単純にマーカー ( ) をボード ピースから順番に配置する理由がわかりません0-8。

たとえば、人間のプレイヤーとして、私が を選択する1と、コンピューターは を選択します0。

次に、私が を選択する4と、コンピューターは を選択します2。

等々：

できる限り minmax アルゴリズムをデバッグしましたが、何が起こっているのかを追跡するのが非常に難しくなっています。

これは、アルゴリズムを使用したComputerPlayerクラスです (すべての print ステートメントはありません)。方法は、minmax私が多くの問題を抱えているところです。(私は、worst_scoreまたは関連するロジックを使用することに 100% 確信があるわけではありません。)

最近、次の問題に遭遇しました。

ランダムに分散された 0 と 1 のランダムな長さ (L) のベクトル (たとえば、[0,1,1,1,0,0,1,0]) があるとします。ベクトルを 2 つのサブに分割する必要があります。インデックス K のベクトルなので、次の条件が有効です。

• 左のサブベクトルには、K からの要素の最大数が逆順に含まれている必要があります。たとえば、0 の数は 1 の数以上である必要があります。
• 右サブベクトルには、1 の数がゼロの数以上であるなど、K+1 から始まる最大数の要素が含まれている必要があります。

たとえば、[1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0] 分割はインデックス 9、左ベクトルは [1,0]、右ベクトルは [0,1]

次のソリューションを書きましたが、複雑さは O(L^2) です。最悪の場合の O(L) の複雑さを伴う解決策があると思いますが、私を助けることができるものは何も見つかりません。何か案が？ありがとう

転置テーブルで強化されたアルファベータ最小最大プルーニングを実装しようとしています。この疑似コードを参照として使用します。

http://people.csail.mit.edu/plaat/mtdf.html#abmem

このアルゴリズムに対する 3 つの質問:

1. 保存された各転置テーブル エントリに深さ (= リーフ レベルまでの距離) を格納し、entry.depth>=currentDepth (= エントリがリーフ レベルからほぼ等しい) の場合にのみエントリを使用する必要があると思います。それは上記の疑似コードには示されておらず、そこでは議論されていません。それを正しく理解していることを確認したかったのです。

2. 各ポジションのベストムーブを保存して、ムーブオーダーに使用し、検索が停止した後にベストムーブを抽出したいと考えています。純粋な最小値と最大値では、どちらの動きが最適かは明らかですが、アルファ ベータ カットオフで反復する場合、どの動きが最適でしょうか? 特定の位置での最良の動きは、ループが終了したときに見つかった最良の動きであると仮定できますか (カットオフの有無にかかわらず)?

3. このアルゴリズムを反復深化スキームで実行する場合、各深さが増加する前に転置テーブルをクリアする必要がありますか? 前回の反復から保存された位置を使用したいと思いますが、情報がより深い検索に適しているかどうかはわかりません (テーブル エントリの深さを確認するときである必要があります)。

置換テーブルを追加してから MTD(f) をチェスの純粋なアルファ ベータ プルーニングに追加すると、期待されるパフォーマンスの向上はどのくらいですか?

私のピュア アルファ ベータ プルーニングでは、次の移動順序を使用します。

• 主変動 (以前の反復深化反復から)
• 転置表からの最良の移動 (存在する場合)
• キャプチャ: 最高のキャプチャ、次に最低のキャプチャ
• キラームーブ
• 履歴ヒューリスティック

上記の設定で、深さ 9 の平均結果は次のようになります。

• ピュア アルファ ベータ: X ノードを訪問
• alpha beta+TT: 0.5*X ノードを訪問
• MTDF(f): 0.25*X ノードを訪問

私はより良い結果を期待していましたが、それが得られるのと同じくらい良いかどうか、または実装に問題があるかどうかを確認したかったのですか?

0.1 ポーンの精度で検索します。

リストタグ内の最小日付と最大日付を見つける必要があります 1つの列でこのように Min Date:01/01/2015 / Max Date:01/05/2015

Min dt と Max dt を「PoRequiredDate」として 1 つの列に追加する必要があります

MiniMax ツリーとアルファ ベータ プルーニングの概念は理解していますが、アルファ ベータ プルーニングに関する多くのリソース (ウィキペディアなど) で α​​ >= β のような条件が存在する理由がわかりません。具体的には、等号は紛らわしいです。私が理解しているように、アルファ ベータは minmax が返す動きを返しますが、ほとんどの場合は高速です。しかし、この例はそれと矛盾しています:

上は元の最小最大ツリーです。ご覧のとおり、スコア 3 の 1 つの手が選択されます。では、アルファ ベータを実行してみましょう。

3 >= 3 であるため、最も右の手を切り捨てます。しかし、アルゴリズムは同じスコアを持つ 2 つの手のどちらかを選択できますが、min-max で見たように、正しい選択はわずかに悪いです。アルゴリズムが単純に α > β を指定した場合、これは発生しないため、2 も検索する必要があります。

それはウィキペディアの疑似コード (および他の多くのリソース) のタイプミスでしたか? または、ここで本当に大きなことを誤解していました。

次のコードでは、コンソールからの入力リストの値を受け入れることができません。

IndexError : リスト引数のインデックスが範囲外です。

インデックスが範囲外になった場所が見つかりません。助けてください。事前に感謝します。

最小値が最大値よりも低いインデックス位置にある配列の最小/最大値のみを返す方法はありますか?

たとえば、次のようなものがあるとします。

この配列で .minmax を実行すると、次のようになります。

ただし、この場合、最大値よりも低いインデックスを持つ最小値を取得することにのみ関心があります。

これを行うためのさまざまな方法を考えてみましたが、あまり運がありませんでした。2つの差が負の値を返す最小/最大値を取得する方法を見つけようとしましたが、それを行う方法を見つけることができませんでした.

編集：明確にするために、これは基本的にストックピッカーであることを意図しています。配列要素は、毎日の株価です。配列の最小値と最大値の差を最大化することに関心があります (在庫 = 3 の日に購入し、在庫 = 15 の日に販売します)。値は、絶対的な最小値または最大値ではない場合があります。

#max、#min、#minmax を理解しています。了解です<=>。しかし、これらの関数の 1 つのブロック内でどのように機能するのでしょうか?

つまり、下の 3 行目で何が起こっているのでしょうか。<=> は #min で何をしていますか?

http://ruby-doc.org/core-2.2.3/Enumerable.html#method-i-minの例

数値の配列に対してどのような動作をしますか?