2

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

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

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

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

def ab_tt(p, alpha, beta):
    if p isa Leaf:
        return 0

    if hash.lookup(p, val, flag):
        if flag == VALID:
            return val
        elif flag == LBOUND:
            alpha = max(alpha, val)
        elif flag == UBOUND:
            beta = min(beta, val)
        if alpha >= beta:
            return val

    if p isa MAX_Node:
        res = alpha
    else:
        res = beta

    for q in succ(p):
        if p isa MAX_Node:
            succVal = t(q) + ab_tt(q, res - t(q), beta - t(q))
            res = max(res, succVal)
            if res >= beta:
                hash.add(p, res, LBOUND)
                return res
        elif p isa MIN_Node:
            succVal = t(q) + ab_tt(q, alpha - t(q), res - t(q))
            res = min(res, succVal)
            if res <= alpha:
                hash.add(p, res, UBOUND)
                return res
    hash.add(p, res, VALID)
    return res

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

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

編集：

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

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

Rank    J   A   10  K   Q   9   8   7
Value   2   11  10  4   3   0   0   0
4

1 に答える 1

0

問題を解決しました。私の質問の参照で示唆されているように、再帰呼び出しごとに奇妙な減算を行う代わりに、転置テーブルに位置を格納する場合にのみ、結果のアルファベータ値から実行中のスコアを減算します。

正確な値の場合 (位置は剪定されていません):

transpo.put(hash, new int[] { TT_VALID, bestVal - node.getScore()});

ノードがベータカットオフを引き起こした場合:

transpo.put(hash, new int[] { TT_LBOUND, bestVal - node.getScore()});

ノードがアルファ カットオフを引き起こした場合:

transpo.put(hash, new int[] { TT_UBOUND, bestVal - node.getScore()});

どこ：

  • transpoですHashMap<Long, int[]>
  • hashlongその位置を表す値です
  • bestVal正確な値またはカットオフの原因となった値のいずれかです
  • TT_VALID、TT_LBOUNDおよびTT_UBOUNDは単純な定数で、転置テーブル エントリのタイプを記述します。

ただし、これ自体は機能しませんでした。gamedev.netに同じ質問を投稿した後、Álvaroという名前のユーザーが決定的
なヒントを与えてくれました。TT_VALID

于 2014-03-11T19:34:57.217 に答える