2

我目前正在为一个名为Skat的基于技巧的纸牌游戏开发一个求解器，它在完美的信息情况下。虽然大多数人可能不知道这个游戏，但请多多包涵；我的问题是一般性的。

Skat简介：
基本上，每个玩家交替打一张牌，每三张牌形成一个花样。每张卡都有特定的价值。玩家获得的分数是相应玩家赢得的技巧中包含的每张牌的值相加的结果。我遗漏了一些对我的问题不重要的事情，例如谁和谁比赛或者我什么时候赢得一墩。
我们应该记住的是，有一个运行分数，并且在调查某个位置（->它的历史）时谁玩过什么与该分数相关。

我用 Java 编写了一个 alpha beta 算法，它似乎工作正常，但它太慢了。似乎最有希望的第一个增强是使用转置表。我读到，在搜索 Skat 游戏的树时，您会遇到很多已经调查过的位置。
这就是我的问题发挥作用的地方：如果我找到一个之前已经调查过的位置，那么导致这个位置的动作会有所不同。因此，一般来说，分数（以及 alpha 或 beta）也会有所不同。
这引出了我的问题：如果我知道相同头寸的价值，但历史不同，我如何确定头寸的价值？
换句话说：我怎样才能解耦从其路径到根的子树，以便可以将其应用于新路径？
我的第一个冲动是这是不可能的，因为 alpha 或 beta 可能受到其他路径的影响，这可能不适用于当前位置，但是......

似乎已经有一个解决方案
......我似乎不明白。在 Sebastion Kupferschmid 关于 Skat 求解器的硕士论文中，我发现了这段代码（可能是 C-ish / 伪代码？）：

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)是我认为是各个位置的跑分（庄家到目前为止所获得的分数）。因为我不喜欢在不理解的情况下复制东西，所以这应该只是对任何想帮助我的人的帮助。当然，我已经对这段代码进行了一些思考，但我无法理解一件事：通过在再次调用函数之前从 alpha/beta 中减去当前分数 [例如] ab_tt(q, res - t(q), beta - t(q))，似乎存在某种解耦上。但是，如果我们将位置的值存储在转置表中而不在这里也进行相同的减法，那么究竟有什么好处呢？如果我们找到了一个之前调查过的位置，为什么我们可以只返回它的值（如果它是VALID）或者使用 alpha 或 beta 的绑定值？在我看来，从转置表存储和检索值都不会考虑这些位置的特定历史。还是会？

文献：
几乎没有英文资料涉及 skat 游戏中的 AI，但我发现了这个：A Skat Player Based on Monte Carlo Simulation by Kupferschmid, Helmert。不幸的是，整篇论文，尤其是对转置表的阐述相当紧凑。

编辑：

为了让每个人都能更好地想象在所有牌都打完之前，在 Skat 游戏中比分是如何发展的，这里有一个例子。游戏进程显示在下表中，每行一招。每墩牌后的实际分数在左侧，其中+X是庄家的分数（-Y是防守方的分数，与alpha beta 无关）。正如我所说，一招的获胜者（宣布者或防守队）将这一招中每张牌的价值添加到他们的分数中。

卡值如下：

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

1 回答 1

0

我解决了这个问题。正如我的问题中的参考所建议的那样，我不会对每个递归调用进行奇怪的减法运算，而是仅在将位置存储在转置表中时才从结果的 alpha beta 值中减去运行分数：

对于精确值（该位置尚未被修剪）：

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

如果节点导致 beta 截止：

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

如果节点导致 alpha 截止：

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

在哪里：

  • transpo是一个HashMap<Long, int[]>
  • hash是long表示该位置的值
  • bestVal是确切值或导致截止的值
  • TT_VALID,TT_LBOUND并且TT_UBOUND是简单的常量，描述转置表条目的类型

然而，这本身并没有奏效。在gamedev.net上发布了同样的问题后，一个名叫Álvaro的用户给了我一个决定性的提示：
当存储准确的分数 ( TT_VALID) 时，我应该只存储位置，提高 alpha。

于 2014-03-11T19:34:57.217 回答