爪哇最小/最大Tic Tac Toe

Question

我正在用min/max创建一个tic-tac-toe，以便将其扩展到alpha-beta修剪。因此，在我的最小/最大值过程中，我发现对于这样的电路板配置，如果一条路径的导联为+1（X-win）-1（O-win）或0（Draw）：

在0回合中，它选择左下角，因为这一步将导致它获胜。如果我检查每个表是否有一个块，那么它就不会运行得那么快，我不认为应该这样实现min/max

0|x|0
-|x|-
-|-|- 

有人能解释为什么最小值/最大值不够聪明，无法检测到这一点吗。我认为它查看了左侧节点并返回+1/-1/0

Answer 1

我不太确定你的问题。如前所述，当多条路径导致胜利或所有路径导致失败时，min/max会出现问题。在这种情况下，从数学上正确地选择任何一条或任何一条获胜的道路，或任何一条失败的道路。然而，如果与一个不完美的对手比赛，选择最短的获胜路径和最长的失败路径往往更明智（希望对手不是完美的，而是选择了错误的选择）

这种行为很容易在min/max中实现，使用每个递归的衰减。也就是说，每当你从一个递归调用返回一些东西时，将结果乘以0.9或类似的值。这将导致更长负面路径的得分更高，更长正面路径的得分更小

然而，一旦你开始使用启发式方法，这确实会导致问题

Answer 2

编辑：我把“纯”极小极大与极小极大+启发式混为一谈。我编辑了我的答案来解决这个问题

也许这有助于定义minmax。从An article by a UC Berkeley student

minimax(player,board)
    if(game over in current board position)
        return winner
    children = all legal moves for player from this board
    if(max's turn)
        return maximal score of calling minimax on all the children
    else (min's turn)
        return minimal score of calling minimax on all the children

使用minimax，你是在尽量减少损失，而不是最大化收益。所以，“你的”回合是min's回合。根据这个定义，如果你可以通过选择一个正方形而失败，那么它将被标记为-1。如果你能打成平局，但永远不会输，它将被标记为^{。只有当这是一场有保证的胜利时，它才会被标记为^{

Should I check each table for a block

如果你正确地定义了你的分数和算法（将正确的球员与正确的逻辑相匹配），你就不需要“检查封盖”。任何玩家没有阻止的游戏子树都应该隐式地被评估^{，因为在某个点（可能很快）它会评估为一个损失，而这个损失会冒出来

这种算法的真正问题（以及你可能会得到你意想不到的结果）是所有的子树都可能导致损失。在这一点上，你将需要使用启发式来获得关于你应该采取哪一步的更好信息。你需要比简单的{-1, 0, 1}更好的东西，因为有些动作可以让你赢，但你会阻止它们，因为你也可能输