問題タブ [minimax]

ミニマックスアルゴリズムに関して簡単な質問があります。たとえば、三目並べゲームの場合、各プレーヤーがプレイする効用関数をどのように決定しますか？それは自動的には行われませんよね？ゲーム内の値をハードコーディングする必要がありますが、それ自体では値を学習できませんね。

空間と時間の複雑さを判断するのに問題があります。たとえば、分岐係数bを持ち、最大で深さdを持つツリーがある場合、時間と空間の複雑さをどのように計算できますか？それらがO（b ^ d）とO（bd）であることは知っていますが、私の問題はこれらの値を取得する方法です。

ミニマックス/ネガマックス アルゴリズムの使用を試み始めたばかりで、自分にとっては良さそうなアイデアを思いつきましたが、誰も使用していないため、ロジックに欠陥がある可能性があります。

なぜ私たちはこれをしないのですか:

depth=x で 3 を作成し、どの手を打つかを考えて、対戦相手を待ちます。彼がムーブを行った後、すでに評価したムーブのサブツリーを取得し、古いノードを使用しながらさらに深く構築し続けることができます。ノードのすでに評価された値を使用し、新しいより深いノードからの新しい値でそれらを重み付けできます。

新しい値は通常の方法ほど正確ではないかもしれませんが、より深く取得して利益を得ることができます。

文章が下手で構造化されていない質問で申し訳ありませんが、私の考えを理解していただければ幸いです。

ナイン・メンズ・モリスのゲーム用のゲームツリーを作りたいです。ノード評価を行うために、ツリーにミニマックスアルゴリズムを適用したいと思います。MinimaxはDFSを使用してノードを評価します。では、最初に特定の深さまでツリーを構築してからミニマックスを適用する必要がありますか、それともツリーの構築と評価のプロセスを再帰的なミニマックスDFSで一緒に実行できますか？

ありがとうArvind

学校のプロジェクトでは、C++ で日付ゲームを作成する必要があります ( http://www.cut-the-knot.org/Curriculum/Games/Date.shtmlの例)。コンピューター プレーヤーは、アルファ ベータ プルーニングを使用して Minimax アルゴリズムを実装する必要があります。 . これまでのところ、対戦相手がそれらを縮小すると仮定しながら、潜在的な利益を最大化するという観点から、アルゴリズムの背後にある目標が何であるかを理解しています.

しかし、私が読んだリソースのどれも、ミニマックスがすべての決定の基礎となる評価関数を設計する方法を理解するのに役立ちませんでした。すべての例では、リーフ ノードに任意の番号が割り当てられていますが、実際にはそれらのノードに意味のある値を割り当てる必要があります。

直感的には、葉のノードが勝った場合は +1、負けた場合は -1 のようになりますが、中間のノードはどのように評価されるのでしょうか。

どんな助けでも大歓迎です。

私は特定のトピックを尋ねるためにここにいます-私は実際にこれについての情報をウェブ上でほとんど見つけませんでした。MinimaxアルゴリズムのF＃バージョンを実装しています。私が今抱えている問題は、ツリーのリーフ（以下のデータ構造）を比較したいということです。VSが私にくれたエラーを検索して、私は次のようなものにたどり着きました。

私が持っていた木のタイプ：

そしてIComparableを実装するための誘惑

最後に、LeafPのリストの最大値（および最小値）を静的な値で取得したいだけです（他の関数で計算します）。

上記のコードはコンパイルされます。ただし、これでテストします。

GetHashCodeのオーバーライドの"|:? TreeOfPosition as y-> compare（x）（y）"行にSystem.StackOverflowExceptionが発生しました。

ミニマックスについて話し合っているので、hubfs.net（http://cs.hubfs.net/forums/thread/15891.aspx ）にスレッドがあります。ここに私の最新のコードがあります（http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm）

前もって感謝します、

ペドロ・デュッソ

ええと、私はその考えを非常にはっきりと理解しましたが、それを機能させることはできません。リーフのリスト（「List.max」：P）から最大の静的値を持つリーフを取得したいことを思い出して、CompareToまたはEqualsを実装すると、List.maxがそれらで機能するようになると思います。私はこのようなものを構成します：

私がこのように関数を配置している問題は次のとおりです。

1）パターン弁別器「LeafP」が定義されていません（LeafPに赤い下線が引かれています）

2）（77,39）：エラーFS0039：値またはコンストラクター'mycompare'が定義されていません。ALTENTERを実行しようとすると、このメッセージがF＃インタラクティブに表示されます。位置{77,39}は、（GetHashCode内の）mycompare呼び出しの開始に対応します。

私が間違っているのは何ですか？何を改善できますか？

どうもありがとう、

ペドロ・デュッソ

編集3-解決済み

はい！私はあなたの答えを最終的に機能させるために管理します！

最終的なコードは次のとおりです。

フィードバックをお寄せいただきありがとうございます！

ペドロ・デュッソ

この質問は、F＃の構文上の質問というよりも、意味論的アルゴリズムのデータ構造に関する質問です。私はミニマックスアルゴリズムを持っています。ミニマックスアルゴリズムは、開始位置から次の最良の動きを返す必要があります。これを行うために、それはすべての次の動きを計算し、次に次の次の動きを決定された深さまで、またはそれ以上の動きがなくなるまで動かします。次のようなツリーを構築します。

ツリーを処理するための休眠データ構造体があります。

上記の例のツリーではP、aはブランチと、bはリーフです。以下のコードは私のミニマックスアルゴリズムです：cd

このコードは、たとえば、私にリーフを返しますc。再帰呼び出しをに変更したとき

そして、この変更により、良い葉の静的な値が上がります。最高の第2レベルノードを返す必要があります。誰かが助けてくれることを願っています！ペドロ・デュッソ

編集1

すべての回答者に感謝します、彼らは私を大いに助けてくれます。申し訳ありませんが、あまり指定していませんでした。部分的に行きましょう：

LeafP(position, 0)1）ツリーを作成するときに、静的な値としてデフォルト値0を使用してリーフを設定したため、LeafPと一致しています。静的な値を上げて、リーフを削除し、（ブランチの前の）リーフを（最小または最大）静的な値で作成するときに、この方法で元のブランチリーフを評価できないようにすると思いました（ 0の値）。

2）私の最大の問題は、2番目のレベル（プレイしなければならない次の動き）を最高の位置に戻すことでした。私はそれをこのように解決しました：

ツリー全体を渡す代わりに、開始ノードの子だけを渡し、結果のリスト（現在のレベルに最適であるために上がった静的な値を持つ元のブランチのリスト）を再度フィルタリングします。このようにして、必要なノードを取得します。

kvbの答えは非常に興味深いと思いましたが、少し複雑でした。私が理解した他のものは、静的な値を私に返すだけです–そして私はそれらを私のために働かせることができませんでした:(

すべての答えに感謝します、それらのすべては私にたくさんのインスピレーションを与えました。

これが私の完全なコードです：（http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm）

ペドロ・デュッソ

この質問についてGoogleとStackoverflowを検索しましたが、ミニマックス関数がどのように機能するかまだわかりません。

ウィキペディアのエントリに関数の疑似コード バージョンがあることがわかりました。

Google で見つけた他のいくつかのミニマックス関数は、基本的に同じものです。これを C++ で実装しようとしていますが、これがこれまでに思いついたものです。

ご覧のとおり、私はこのミニマックス関数についてかなり混乱しています。少なくとも、これを助けるためのヒントを教えてください。

ありがとう！:)

チェッカーのゲーム用です。古いバージョンのコードについては、改訂履歴を参照してください。

私は深さ0でそれを試しています、そしてスコアはゲームの約半分で正しいです、そしてそれから突然それは台無しになり始めます。プレーヤーの1人は、自分のスコアが実際よりも高いと宣言し始めます。なぜそれは半分のゲームでしか機能しないのでしょうか？！

私がプログラマーである限り、私はまだアルゴリズムの非常に初等レベルの教育を受けています（私は独学であるため）。おそらく、あなたがあなたの答えで提案することができるそれらに関する良い初心者の本があります。