Chomp游戏的算法

Question

我正在为Chomp游戏写一个程序。您可以在维基百科上阅读游戏的描述，但是无论如何，我会简要地描述它。

我们在维为n的巧克力棒上玩，也就是说，该条被划分为n正方形。在每一个回合中，当前玩家选择一个正方形，并吃掉所选方块的下方和右边的所有东西。因此，例如，以下是有效的第一步：

​

​

目的是迫使你的对手吃最后一块巧克力(它是有毒的)。

关于人工智能部分，我使用了一个带有深度截断的极小极大算法.然而，我无法提出一个合适的职位评估功能。结果是，用我的评估功能，人类玩家很容易战胜我的程序。

有谁能：

• 建议良好的职位评估功能或
• 提供一些有用的参考或
• 建议另一种算法？

Answer 1

你的板子有多大？

如果你的棋盘相当小，那么你就可以用动态规划精确地解决游戏问题。在Python中：

n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))

def moves(board):
    return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]

@memoize
def wins(board):
    if not board: return True
    return any(not wins(move) for move in moves(board))

函数胜诉(董事会)计算董事会是否是一个获胜的位置。板表示是一组元组(x，y)，指示是否仍在板上(x，y)。该函数移动计算可在一次移动中到达的板的列表。

wins函数背后的逻辑是这样工作的。如果棋盘在我们移动时是空的，那么另一个玩家肯定吃了最后一块，所以我们赢了。如果董事会不是空的，那么我们可以赢，如果有any移动，我们可以这样做，结果的位置是一个失败的位置(即不赢，即not wins(move))，因为我们让另一个玩家进入一个失败的位置。

您还需要memoize函数来缓存结果：

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

通过缓存，我们只计算出谁是给定位置的赢家一次，即使这个位置可以以多种方式到达。例如，如果第一位玩家在第一步中吃掉了剩下的所有行，那么可以获得单排巧克力的位置，但也可以通过其他一系列的移动来获得。一次又一次地计算谁在单行板上获胜是浪费的，所以我们缓存结果。这提高了渐进性能，从O((n*m)^(n+m))到O((n+m)!/(n!m!))，这是一个巨大的改进，尽管对大型板来说仍然缓慢。

为了方便起见，这里有一个调试打印功能：

def show(board):
    for x in range(n):
        print '|' + ''.join('x ' if (x,y) in board else '  ' for y in range(m))

这段代码仍然相当慢，因为代码没有以任何方式进行优化(这是Python.)。如果您用C或Java有效地编写它，您可能会提高100倍以上的性能。您应该能够轻松地处理10x10板，并且您可能可以处理多达15x15板。您还应该使用不同的板表示形式，例如位板。如果您使用多个处理器，甚至可以将其速度提高1000倍。

这里是从minimax派生出来的

我们将从minimax开始：

def minimax(board, depth):
  if depth > maxdepth: return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move, depth-1))
    return alpha

我们可以删除深度检查来进行全面搜索：

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move))
    return alpha

因为游戏结束了，启发式将返回-1或1，这取决于哪个玩家赢了。如果我们将-1表示为false，1表示为true，则max(a,b)变为a or b，-a表示为not a。

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not minimax(move)
    return alpha

您可以看到这相当于：

def minimax(board):
  if not board: return True
  return any([not minimax(move) for move in moves(board)])

如果我们用alpha-beta剪枝开始使用minimax：

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -beta, -alpha))
      if alpha >= beta: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

搜索从alpha = -1和beta = 1开始，一旦alpha变成1，循环就会中断。因此，我们可以假设alpha停留在-1和β停留在递归调用中。因此，代码相当于：

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -1, 1))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

因此，我们可以简单地删除参数，因为它们总是以相同的值传入：

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board)

我们可以再次从-1和1切换到布尔人：

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not alphabeta(move))
      if alpha: break
    return alpha

因此，您可以看到，这等同于在生成器中使用any，一旦它找到了一个True值，就立即停止迭代，而不是总是计算整个子列表：

def alphabeta(board):
  if not board: return True
  return any(not alphabeta(move) for move in moves(board))

注意，这里我们使用的是any(not alphabeta(move) for move in moves(board))而不是any([not minimax(move) for move in moves(board)])。这将搜索速度提高了大约10倍，以达到合理大小的董事会。这并不是因为第一种形式更快，而是因为它允许我们在找到一个值为True时跳过整个循环的其余部分，包括递归调用。

所以你可以看到，wins功能只是伪装下的alphabeta搜索。我们赢的下一个窍门是回忆录。在游戏编程中，这将被称为“转位表”。所以wins函数是用转位表进行alphabeta搜索。当然，直接写下这个算法要比通过这个推导更简单;)

Answer 2

我不认为一个好的位置评估功能在这里是可能的，因为不像国际象棋这样的游戏，没有‘进步’只有赢或输。维基百科的文章指出，对于现代计算机来说，一种详尽的解决方案是可行的，我认为，如果给出合适的回忆录和优化，你会发现情况就是这样。

你可能会发现一个相关的游戏是尼姆。