ここ数日、Tic tac toe AI の miniMax アルゴリズムの実装に苦労しています。現在、私が抱えている問題は、minimax() 関数を呼び出したときに「returnBoard」入力で空のボードを取得することです。私は自分のアルゴリズムが一連のボードを通過していることを知っています。なぜなら、私は子供を手に入れたときにプリントアウトし、コンピューターが手を動かしてボードにスコアを与えているのを見ているからです。助言がありますか？

これが実行可能なコンテンツ全体です。

私は現在、完全な情報状況でSkatと呼ばれるトリックベースのカード ゲームのソルバーを開発しています。ほとんどの人はゲームを知らないかもしれませんが、ご容赦ください。私の問題は一般的な性質のものです。

Skat の簡単な紹介:
基本的に、各プレイヤーは 1 枚のカードを交互にプレイし、3 枚のカードごとにトリックを形成します。すべてのカードには特定の値があります。プレーヤーが達成したスコアは、それぞれのプレーヤーが獲得したトリックに含まれるすべてのカードの値を合計した結果です。誰が誰と対戦するか、またはいつトリックに勝つかなど、私の問題にとって重要ではない特定の事柄を省略しました。 私たちが心に留めておくべきことは、ランニングスコアがあり、特定のポジション（->その履歴）を調査するときに誰が以前に何をプレーしたかがそのスコアに関連しているということです。

Java でアルファ ベータ アルゴリズムを作成しましたが、これは正常に動作しているように見えますが、遅すぎます。最も有望と思われる最初の拡張機能は、転置テーブルの使用です。Skat ゲームのツリーを検索すると、既に調査済みの多くのポジションに遭遇することを読みました。
ここで問題が発生します。以前に調査済みのポジションを見つけた場合、そのポジションに至る動きは異なっていました。それに伴い、一般的に、スコア (およびアルファまたはベータ) も異なります。
これは私の質問につながります: 同じポジションの値を知っていても、履歴が異なる場合、どのようにしてポジションの値を決定できますか?
言い換えれば、どうすればデカップリングできますか新しいパスに適用できるように、そのパスからルートまでのサブツリー?
私の最初の衝動は、アルファまたはベータが現在の位置に適用できない可能性がある他のパスの影響を受けている可能性があるため、それは不可能であるということでしたが...

すでに解決策がある
ようです...私には理解できないようです。Sebastion Kupferschmid の Skat ソルバーに関する修士論文で、次のコードを見つけました (おそらく C っぽい / 疑似コード?):

それはかなり自明であるはずです。succ(p)現在の位置で可能なすべての動きを返す関数です。t(q)は、それぞれのポジションの実行中のスコア (ディクレアラーがこれまでに達成したポイント) であると私が信じているものです。理解せずにコピーするのは好きではないので、これは私を助けたい人の助けになるはずです. もちろん、私はこのコードについて少し考えましたが、1 つのことに頭を悩ませることはできません: 関数を再度呼び出す前にアルファ/ベータから現在のスコアを差し引くことによって [例ab_tt(q, res - t(q), beta - t(q))]、何らかのデカップリングが行われているようです。の上。しかし、ここでも同じ減算を行わずに位置の値を転置テーブルに格納すると、正確にはどのような利点があるのでしょうか?以前に調査した位置が見つかった場合、なぜその値を返すだけでよいのでしょうか (それが の場合VALID)、またはアルファまたはベータにバインドされた値を使用できますか? 私の見方では、転置テーブルからの値の保存と取得の両方が、これらの位置の特定の履歴を考慮していません。それともそうなるでしょうか？

文献:スケート ゲームでAI
を扱っている英語の情報源はほとんどありませんが、私はこれを見つけました。残念ながら、論文全体、特に転置表の詳細はかなりコンパクトです。

編集：

すべてのカードがプレイされるまで、Skat ゲーム全体でスコアがどのように発展するかを誰もがよりよく想像できるように、ここに例を示します。ゲームのコースは、下の表に 1 行に 1 トリックで表示されます。各トリックの後の実際のスコアは左側にあり、+Xはディクレアラーのスコアです ( -Yは防御チームのスコアであり、アルファ ベータには関係ありません)。前述したように、トリックの勝者 (ディクレアラーまたはディフェンディング チーム) は、このトリックの各カードの値をスコアに追加します。

カードの値は次のとおりです。

私は、コンピューター チェス プログラムのアルファ ベータ検索の主要なバリエーションを使用した反復的な深化の実装に取り​​組んでおり、検索の時間制限を含めることを望んでいました。たとえば、深さ 5 の検索の途中で制限時間に達した場合の結果について疑問に思っていました。この不完全な検索で新しい主要なバリエーションが見つかった場合、少なくとも深さ 4 での完全な検索によって見つかった主な変化は? そうでなければ、深さ 5 の不完全な検索で見つかったものをすべて破棄する必要があるようです。

チャンスノードを使用してゲームツリーでアルファベータの剪定を学習しようとしているので、例を見つけて、ツリーを解決した後にそれに取り組みました。次のようになります。

今、いくつか質問があります：

• まず、葉の範囲が -infinity と +infinity であると想像すると、剪定されたノードだけが一番右のノードであると言えますか?

• もう 1 つの質問は、葉の範囲が -2 から 2 であると想像した場合、次の図の丸で囲まれた領域だけが剪定されると言えるでしょうか (または、私が間違っているので、剪定すべきではありません)。

アルファベータ枝刈りが非効率的であると言える場合はありますか。言い換えれば、勝つために 27 に到達する必要があるゲームがあり、あなたと対戦相手は合計するために毎回 1、2、5 しか使用できないとします。では、ここでアルファベータ剪定は効率的ですか? そのように評価するのは少し混乱しませんか? 特に、私たちがあまり気にしない多くの可能性があるケースの最初の段階では?

これを説明できる気がしますが、できません！ヘルプ。

アップデート

更新1

これを試しました（2行目）：alphabeta関数の最初の命令としてノードの色の変更を追加しました。私はこの結果を得ています：

緑色のノードは訪問済みノードです。アルゴリズムがノードを正しくスローするように見えますよね？しかし、ノードで正しい値を出力する方法 — 私もこれを行う必要がありますか? 子の値の最小値、子の値の最大値 (剪定された枝を除く)。

Update 2

アルファとベータをツリー ノードに出力しようとしましたが、正しい結果が得られませんでした。これがコードです (18 行目と 31 行目が追加されました)。これはコードの結果です:

この画像では、奇妙な場所を示しています。

最初の矢印: なぜ 7 と 6 の最小値が 5 なのか? 2 番目の矢印: 4、3、2 の最大数が 5 になるのはなぜですか? 変。そのため、現在は正しく機能していると思います。

古い質問

むかしむかし、ここで同様の質問を作成しました。「なぜこのエラーが発生するのですか？」のようなものでした。ロールバックして新しいものを作成しましょう。この質問は次のとおりです。「Alpha Beta Pruning アルゴリズムの結果を表示するにはどうすればよいですか?」

ウィキでこのアルゴリズムの疑似コードを見つけました。ここで見つけることができます。

私の認識は以下のとおりです (JavaScript に関するものですが、この質問に答えるために JS、Java、C++ などの知識が必要だとは思いません)。問題は、このアルゴリズムの結果をグラフ (ツリー構造) に出力する方法です。開始時には、次のツリー構造があります。

注:アルファ ベータ プルーニング アルゴリズムを使用するツリー構造 (いくつかのリンクされnodeた s) があり、別のツリー構造 (結果を表示するため、「グラフ」と呼びましょう) があります。グラフを表示するために使用するツリーのノードは、アルゴリズムの結果を見つけるために使用するノードに接続されています。

そのため、アルファ ベータ プルーニング アルゴリズムのコードは以下のとおりです。アルゴリズムのプロセス/結果を正しく表示するには、何をどこに出力する必要があるかを明確にしていただけますか?

アルファとベータを出力すると仮定していますが、それは間違っていると思います。試してみましたが、うまくいきません。

剪定を表示し、ツリー内のすべてのノードに正しい値を入力したいと考えています。

これは、アルファ ベータ プルーニングを使用したミニマックスの私の実現です。

グラフ上でアルファ ベータ アルゴリズムを実行するプログラムを作成しました。

(画像をクリックすると拡大版が表示されます)

私はこのグラフを持っています：

アルゴリズムの結果:

この画像は、問題のある領域を示しています。

これら 2 つのノードがプルーニングされたのはなぜですか? グループの最初のノードは 5、前の頂点の親ノードは 2 であるため、5 と 2 を比較します。5は 2 未満ではありませんが、プログラムはカットオフを行いました。なんで？ノード値が 2 より小さい場合にのみ実行する必要がありますが、この場合はそうではありません。

α-β プルーニング理論で何か誤解しているので、間違った値を比較していますか? それとも私の認識の問題ですか？以前は他のすべてのブランチが完全に機能していたのに、なぜここでのみ問題が発生するのでしょうか? 一方、こちらの画像をご覧ください。

プログラムは整理する必要があり、整理が完了します。最初の子頂点が 5 または 1 の場合、なぜ剪定が行われるのですか?

私のアルファベータ機能（GitHub上）：

この関数は、Wikipedia の疑似コードを JavaScript に翻訳したものです。

注: 完全なソースを開くと、alpha_beta_blankここで関数を示したことに気付くでしょう。この関数は、Wikipedia の疑似コードを翻訳したものです。実際、プログラムで別の関数を使用していますが、上記のようにどちらも正しく機能していません。

デバッグについて。この関数(すべてのデバッグ ステートメントを含む元の関数) を見ると、デバッグ メッセージを出力していることがわかります。デバッグ トレースのこの部分は、問題の頂点に属しています。

名前付きのグラフの一部 (ログを理解できるように):

GitHub の完全なリポジトリ。