标签: minimax

我在确定空间和时间的复杂性方面遇到了一些麻烦.例如,如果我的树具有分支因子b并且最多具有深度d,那么如何计算时间和空间复杂度？我知道它们是O(b ^ d)和O(bd),但我的问题是如何获得这些值.

谢谢!

我正在创建一个C程序来玩Gomoku.它使用Minimax搜索来决定最佳移动.但是,它只能搜索最佳移动10秒.如何确定我的搜索功能何时花了10秒钟搜索.如果您可以向我提供一个示例或文档的链接,将非常感激.

具有alpha-beta修剪的minimax算法能否产生与minimax不同的答案而不进行修剪？

我有点理解minimax算法如何适用于Tic Tac Toe python,但我不知道如何在Python中实际编码...这是我到目前为止所做的:

from copy import deepcopy

class TicTacToeBrain :

    def __init__(self, player = "x") :
        self._squares = {}
        self._copySquares = {}
        self._winningCombos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8],
        [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6])

    def createBoard(self) :
        for i in range(9) :
            self._squares[i] = None
        print(self._squares)

    def showBoard(self) :
        print(self._squares[0], self._squares[1], self._squares[2])
        print(self._squares[3], self._squares[4], self._squares[5])
        print(self._squares[6], self._squares[7], self._squares[8])

    def getAvailableMoves(self) :
        self._availableMoves = [] …

我使用 Minimax 和 Alpha Beta Pruning 制作了一个 Tic Tac Toe 游戏。我想为 Tic Tac Toe (10x10) 游戏制作计算机 AI，但它的游戏树大小大得离谱。

我的代码是这样的，我只需要更改两个变量即可更改连续所需的棋盘大小 + 单元格数。例子：

boardSize = 3 // This is for 3x3 tic tac toe

boardSize = 4 // This is for 4x4 tic tac toe

boardSize = 10 // This is for 10x10 tic tac toe

和

winStreak = 3 // Need to make 3 cells in a row to win

winStreak = 4 // Need to make 4 cells in a row …

我正在尝试使用 alpha-beta 剪枝和转置表来实现极小极大算法。这是针对可能循环的 pacman 代理，因此必须特别注意这一点。如果一个状态（游戏和回合的状态（pacman 或 Ghost））在换位表中，并且之前看到的状态是该节点的父节点（祖父节点，...），则可以将其丢弃。这适用于没有 ab 剪枝的极小极大。从之前的搜索来看，tt（转置表）与ab的实现似乎要困难得多。我试图使代码尽可能清晰，它基于伪代码Artificial Intelligence: A Modern Approach。我希望使用第一种方法使最终结果尽可能接近。

我发现的每个伪代码都以非常不同的方式定义：

第一个伪代码； 第二个伪代码；第三个伪代码

大多数差异看起来只是表面上的。但这些代码都没有完全符合我正在寻找的结构：用 ab 剪枝除以 minValue 和 maxValue 的 minimax

提前致谢，

请询问任何进一步的解释

我正在为游戏的标准8 * 8草稿版本编写跳棋AI。该状态被表示为一个镜头，带有代表列表板上零件的坐标列表。我想做的是遵循此伪代码进行Min-Max搜索。

function minimax(position, depth, maximizingPlayer)
   if depth == 0 or game over in position
        return static evaluation of position

   if maximizingPlayer
         maxEval = -infinity
         for each child of position
              eval = minimax(child, depth-1, False)
              maxEval = max(maxEval, eval)
         return maxEval
   else 
          minEval = +infinity
          for each child of position
              eval = minimax(child, depth-1, true)
              minEval = min(minEval, eval)
         return minEval

按照我的理解，在我的情况，position将是GameState。因此，在我的程序中，我想minimax再次调用的所有子元素，每个子GameState元素都只是一个GameState，并对其应用了一个招式。最终，我将达到深度0，在该深度中，我将返回一个启发式函数，该函数已进行计算。我受困的地方是如何在移动后迭代每个可能的GameState。我有一个函数可以计算特定GameState可以进行的所有可能动作，但是我仍然坚持如何遍历所有这些动作，并使用每个动作的应用产生的新GameState调用minimax。

回到伪代码，我知道这child将是一个函数调用applyMove，该函数 接受Move和当前的GameState，并返回带有新棋子位置的GameState。每个“孩子”将因不同的举动而成为不同的GameState。我对Haskell来说还很陌生，我知道我可能需要为此使用折叠。但是我只是坚持如何编写它，我找不到很多可以轻松地与自己的情况相关的示例。任何建议/提示将不胜感激。

这些举措名单将是这个样子： …

我正在尝试使用 python 中的极小极大算法编写井字棋机器人。我的代码似乎应该对我有用，但错误地评估了位置，搜索太多或太少的节点，并且每场比赛都输给了我。

mainboard = ["-", "-", "-", "-", "-", "-", "-", "-", "-"]
nodes = 0

def detectwin(b):
    signs = ["O", "X"]
    for s in signs:
        for i in range(3):
            j = 3 * i
            if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
                (b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)):
                if s == "O": return 1
                if s == "X": return -1
        if ((b[0]==s and b[4]==s and b[8]==s) or
            (b[2]==s …

我正在制作一个Tic-Tac-Toe计划.我打算用它来使用minimax.我为所有可能的游戏序列制作了一个有空间的树,我正在寻找一种填充它的方法.我目前有这种类型:

typedef struct name
{
    char grid [3] [3];
    struct name * child [9];
} node;

我正在寻找一种填充网格的方法,就像它在这里显示的一样.我如何填充网格以确保所有可能的组合都存在？我的计划是让游戏识别玩家可以采取的每一个动作,然后决定采取什么步骤来获胜(我仍然需要弄清楚决定部分,但我一直坚持,直到我可以填充树中的网格) .

我正在制作一个黑白棋玩家，并通过 alpha-beta 剪枝实现了极小极大算法。然后我在网上对最好的算法做了很多研究，并不断听到他们都使用的“negamax”算法。似乎大多数人都认为 negamax 比 minimax 更快（我认为是因为它不会在最小和最大玩家之间切换？），所以如果不太困难的话，我想将我的 minimax 算法转换为 negamax。

我想知道人们是否对使用 negamax 的速度有多快有任何见解，以及有关如何将我的 minimax 代码转换为 negamax 算法的任何提示或代码，我们将不胜感激！

这是我的极小极大算法：

def minimax(Board, maximizingPlayer, depth, count):
     # maximizing player has 'B' and minimizing 'W'
     if maximizingPlayer: player, opp = Board.player, Board.opp
     else: player, opp = Board.opp, Board.player

     moves_list = Board.get_moves_list(player, opp)
     best_move = (-1,-1)

     # base case
     if ( depth==0 or moves_list == [] ):
         best_score, parity, mobility, stability = Board.evaluate()
         best_move = (-1, -1)
         return best_score, best_move, count

     # maximizing player
     if …