TicTacToe Minimax algorithm

Question

Я написал игру Tic Tac Toe, и я попытался реализовать алгоритм минимакса для AI, но у меня есть некоторые проблемы с кодом.

Проблема в том, что он не выбирает ход, который приведет к победе для ИИ, и он будет выбирать один и тот же ход снова и снова, если вы играете определенным образом. В принципе, алгоритм разбит.

Примечание: Алгоритм основан на псевдокоде Википедии.

Вот что мне удалось сделать:

def MiniMax(self, AI): 
    if self.evalWin(): 
     if AI: 
      return 10 

     return -10 

    if self.evalTie(): 
     if AI: 
      return 0 

     return 0 

    bestmove = None 
    bestMax = float("-inf") 
    bestMin = float("inf") 

    for move in self.getAvailableMoves(): 
     if AI: 
      self.makeMove(move, self.opponent) 

      score = self.MiniMax(False) 

      bst = max(bestMax, score[0]) if type(score) == tuple else max(bestMax, score) 

      if type(score) == tuple: 
       if score[0] >= bst: 
        bestmove = move 

      elif type(score) == int: 
       if score >= bst: 
        bestmove = move 

      self.makeMove(move, "_") 
      print(bst, bestmove) 

      return bst, bestmove 

     else: 
      self.makeMove(move, self.player) 

      score = self.MiniMax(True) 

      bstm = min(bestMin, score[0]) if type(score) == tuple else min(bestMin, score) 

      if type(score) == tuple: 
       if score[0] >= bstm: 
        bestmove = move 

      elif type(score) == int: 
       if score >= bstm: 
        bestmove = move 

      self.makeMove(move, "_") 

      return bstm, bestmove 

Answer 1

Tic-Tac-Toe имеет только 765 различных позиций. Легко сделать ИИ, который побеждает всегда, если это теоретически возможно.