java 21点极小极大算法

Question

我正在用极大极小树实现一个21点游戏，它计算概率并根据概率自动进行游戏

假设我们玩一副牌，第一个游戏庄家拿：“5”，玩家拿“57”，所以玩家的总分是12分

在这种情况下，首先，我试图检查所有可能的可能性，为球员的立场的决定

如果球员站起来：

我在牌组中的剩余牌如下： 牌组结构（K，V）K：卡号，V：卡号

{1: 4, 2: 4, 3: 4, 4: 4, 5: 2, 6: 4, 7: 3, 8: 4, 9: 4, 10: 16}

现在，经销商应该超过17号。一些示例如下所示：

5(base card) + 1(11) + 1 = 17  (possibility of this hand : 4/49 * 3/48)
5(base card) + 1(11) + 2 = 18  (possibility of this hand : 4/49 * 4/48)
......
5 (base card) + 10 + 1 + 1 = 17 (possibility of this hand : 16/49 * 4/48 * 3/48)

我的问题是，我如何计算所有这些可能性，以及球员决定是否有效的最终可能性。我想不出如何对这些数字组合进行编码

编辑：

我找到了计算可能组合的代码。它和我长得很像。我需要改变我的问题，我希望我能做到这一点

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Answer 1

这个游戏不是真的minimax的情况

在minimax中，两个玩家根据已知的位置进行移动，并在确定他们的最佳移动时考虑另一个玩家的移动

由于本例中有两名玩家，一名玩家（除了决定是否站立外，他实际上不会改变棋盘的状态）和一名庄家（他只是随机移动），处于未知棋盘状态，有随机选项，因此不能使用minimax

在这种情况下，一个相当有效的算法是从5开始，再加上7：

base = 5
cards = [7]

使用以下公式：

if sum(cards) + base < 16:
  hit()
else:
  if evalStand() > minStandChance:
    hit()

如果为true，则无需计算牌树，因为玩家无论如何都需要获得另一张牌

在那之后，得到站在那之后的概率：

def evalStand():
  hand = base + sum(cards)
  sums = []
  for cardValue, count in cards.items():
    for i in range(count):
      sums.append(cardValue + hand)
  return len([i for i in sums if i <= 21])/float(len(sums))

只需过滤出仍将获得玩家的手牌的比例<；=21.在这个游戏中一个常用的策略是爬到21号。这是模仿它的。如果在下一轮后站立的概率小于，比如说，0.5，玩家可以停止获得牌

同样，这种情况对minimax不利，但这应该是一个很好的替代解决方案

编辑：

正如@NickLarsen所指出的，minStandChance代表了一种启发式。没有一个变量是100%准确的，但可以根据您希望人工智能发挥的风险大小进行调整。（接近0是有风险的，接近1是保守的）