Why does my tic tac toe minimax algorithm utilizing a 1d representation of a tic tac toe board and allowing for play of both sides not work?

huangapple
go评论96阅读模式
英文:

Why does my tic tac toe minimax algorithm utilizing a 1d representation of a tic tac toe board and allowing for play of both sides not work?

问题

我编写了一个使用极小化极大算法来玩井字游戏的Python程序。棋盘用一个一维数组表示。玩家可以选择扮演任意一方。程序会递归生成所有合法的棋盘，并在每一轮交替最小化和最大化来检查是否有赢家。但出于某种原因，该算法从未生成过获胜的棋盘。

起初我以为与算法没有正确地最小化和最大化右侧有关，但我检查了后发现代码无明显问题。

  1. import random
  3. # 其他代码...
  5. # 以下代码不要翻译
  6. # Main Code
  7. test()
  8. letter = 'X'
  9. board = [""] * 9
  10. player = random.choice([0, 1])
  11. print("You are playing as", player)
  12. while True:
  13.     printBoard(board)
  14.     winner = getWinner(board)
  15.     if winner is not None:
  16.         if winner == "Tie":
  17.             print("Tie")
  18.         else:
  19.             print("Winner:", winner)
  20.         break
  21.     if player == 0:
  22.         if letter == "O":
  23.             move = findBestMove(board, letter, player)
  24.             print("Computer played move", move)
  25.             board[move] = letter
  26.         else:
  27.             move = int(input("Enter move (0-8): "))
  28.             while board[move] != "":
  29.                 move = int(input("Invalid move. Enter move (0-8): "))
  30.             board[move] = letter
  31.     elif player == 1:
  32.         if letter == "X":
  33.             move = findBestMove(board, letter, player)
  34.             print("Computer played move", move)
  35.             board[move] = letter
  36.         else:
  37.             move = int(input("Enter move (0-8): "))
  38.             while board[move] != "":
  39.                 move = int(input("Invalid move. Enter move (0-8): "))
  40.             board[move] = letter
  41.     letter = getOtherPlayer(letter)
英文:

I wrote a python program utilizing the minimax algorithm to play tic tac toe. The board is represented by a 1d array. The player is able to play as either side. The program recursively generates all of the legal boards and checks for a winner alternating between minimizing and maximizing every turn. For some reason the algorithm never generates a winning board.

At first I assumed it was related to the algorithm not minimizing and maximizing for the right side but I checked and I don't see any reason the code wouldn't work

  1. import random
  3. def getOtherPlayer(letter):
  4.     if letter == "X":
  5.         return "O"
  6.     else:
  7.         return "X"
  10. def getWinner(board):
  11.     for i in range(3):
  12.         # Check rows
  13.         if board[i*3] == board[i*3+1] == board[i*3+2] != "":
  14.             return board[i*3]
  15.         # Check columns
  16.         if board[i] == board[i+3] == board[i+6] != "":
  17.             return board[i]
  18.     # Check diagonals
  19.     if board[0] == board[4] == board[8] != "":
  20.         return board[0]
  21.     if board[2] == board[4] == board[6] != "":
  22.         return board[2]
  23.     # Check for tie
  24.     if "" not in board:
  25.         return "Tie"
  26.     # No winner yet
  27.     return None
  29. def test():
  30.     board = ['X', '', 'O', 'X', 'O', 'X', 'O', 'X', 'O']
  31.     print(getScore(board, 'X', False))
  33. def getAvailableMoves(board):
  34.     return [i for i in range(len(board)) if board[i] == ""]
  37. def getScore(board, letter, isMaximizing):
  38.     winner = getWinner(board)
  39.     if winner == letter and isMaximizing:
  40.         print('win')
  41.         return 1  # current player wins
  42.     elif winner == letter and isMaximizing is False:
  43.         print('lose')
  44.         return -1
  45.     else:
  46.         print(board)
  47.         print(letter)
  48.         print(isMaximizing)
  49.         print('tie')
  50.         return 0  # tie (no winner)
  53. def minimax(board, letter, player):
  54.     if player == 0:
  55.         if letter == "X":
  56.             bestScore = float('inf')
  57.             isMaximizing = False
  58.         else:
  59.             bestScore = float('-inf')
  60.             isMaximizing = True
  61.     if player == 1:
  62.         if letter == "O":
  63.             bestScore = float('inf')
  64.             isMaximizing = False
  65.         else:
  66.             bestScore = float('-inf')
  67.             isMaximizing = True
  68.     winner = getWinner(board)
  69.     if winner is not None:
  70.         print("terminal")
  71.         return getScore(board, letter, isMaximizing)
  72.     availableMoves = getAvailableMoves(board)
  73.     if isMaximizing:
  74.         for move in availableMoves:
  75.             board[move] = letter
  76.             score = minimax(board, getOtherPlayer(letter), player)
  77.             board[move] = ""
  78.             bestScore = max(score, bestScore)
  79.     else:
  80.         for move in availableMoves:
  81.             board[move] = letter
  82.             print(board)
  83.             score = minimax(board, getOtherPlayer(letter), player)
  84.             board[move] = ""
  85.             bestScore = min(score, bestScore)
  86.     return bestScore
  91. def findBestMove(board, startingLetter, player):
  92.     availableMoves = getAvailableMoves(board)
  93.     bestMove = None
  94.     bestScore = -9999
  95.     for move in availableMoves:
  96.         board[move] = startingLetter
  97.         score = minimax(board, getOtherPlayer(startingLetter), player)
  98.         board[move] = ""
  99.         if score > bestScore:
  100.             bestScore = score
  101.             bestMove = move
  102.     return bestMove
  105. def printBoard(board):
  106.     print()
  107.     for i in range(3):
  108.         print(board[i * 3:i * 3 + 3])
  110. # Main Code
  111. test()
  112. letter = 'X'
  113. board = [""] * 9
  114. player = random.choice([0, 1])
  115. print("You are playing as", player)
  116. while True:
  117.     printBoard(board)
  118.     winner = getWinner(board)
  119.     if winner is not None:
  120.         if winner == "Tie":
  121.             print("Tie")
  122.         else:
  123.             print("Winner:", winner)
  124.         break
  125.     if player == 0:
  126.         if letter == "O":
  127.             move = findBestMove(board, letter, player)
  128.             print("Computer played move", move)
  129.             board[move] = letter
  130.         else:
  131.             move = int(input("Enter move (0-8): "))
  132.             while board[move] != "":
  133.                 move = int(input("Invalid move. Enter move (0-8): "))
  134.             board[move] = letter
  135.     elif player == 1:
  136.         if letter == "X":
  137.             move = findBestMove(board, letter, player)
  138.             print("Computer played move", move)
  139.             board[move] = letter
  140.         else:
  141.             move = int(input("Enter move (0-8): "))
  142.             while board[move] != "":
  143.                 move = int(input("Invalid move. Enter move (0-8): "))
  144.             board[move] = letter
  145.     letter = getOtherPlayer(letter)

答案1

得分: 3

问题出在你的 getScore 函数中。

只有在赢家是 letter 时才返回非零值，但是当赢家是另一名玩家时却不返回。然而这将是你会遇到的情况：如果有一方获胜，那将是由最后移动的玩家来完成的，而在你调用 getScore 时，letter 实际上是下一个要出手的玩家。因此，即使游戏已经获胜，getScore 也会返回0。

以下是对该函数的建议修正：

  1. def getScore(board, letter, isMaximizing):
  2.     winner = getWinner(board)
  3.     # 当游戏尚未结束，或者是平局时，返回0
  4.     if not winner or winner == '平局':
  5.         return 0
  6.     # 当我们到达这里时，我们知道游戏已经结束。
  7.     # 当 `letter` 赢家并且正在最大化时，或者
  8.     # 当 `letter` 输家并且正在最小化时，返回1
  9.     # 当 `letter` 输家并且正在最大化时，或者
  10.     # 当 `letter` 赢家并且正在最小化时，返回-1
  11.     # 简而言之：如果表达式 `winner == letter` 的布尔值与
  12.     # `isMaximizing` 的布尔值相同，则返回1，否则返回-1
  13.     return 1 if (winner == letter) == isMaximizing else -1

一个小提醒：在分析你的代码时，我发现你使用了一个变量 player，确定了人类玩家是否使用 "X" 和 "O"，但该变量是一个数字 (0 或 1)。你可以通过将 "X" 和 "O" 也用于 player 值来避免一些代码重复。

另外，为什么不始终将 "X" 设定为最大化的玩家，无论是人类还是非人类玩家呢？当然，在 findBestMove 函数中需要更加小心一些，但其他的都会变得更简单。

英文:

The problem is in your getScore function.

It only returns a non-zero value when the winner is letter, but not when the winner is the other player. Yet that is the situation you will have: if there is a win, it will have been played by the player that moved last, while in your calls to getScore, letter is actually the player who is next to play. As a consequence, getScore will return 0 even when the game has been won.

Here is a suggested correction of that function:

  1. def getScore(board, letter, isMaximizing):
  2.     winner = getWinner(board)
  3.     # When the game is not over yet, or it is a tie, then return 0
  4.     if not winner or winner == 'Tie':
  5.         return 0
  6.     # When we get here, we know the game has been won.
  7.     # Return 1  when `letter` is the winner and is maximizing, or
  8.     #           when `letter` is the loser  and is minimizing
  9.     # Return -1 when `letter` is the loser  and is maximizing, or
  10.     #           when `letter` is the winner and is minimizing
  11.     # In short: if the expression `winner == letter` has the same boolean value as
  12.     #           `isMaximizing` return 1, else return -1
  13.     return 1 if (winner == letter) == isMaximizing else -1

A small remark: When analysing your code I found it quite confusing that you used a variable player which determines whether the human player plays with "X" and "O", but the variable is a number (0 or 1). You can avoid some code repetition by using "X" and "O" also for the player value.

Also, why not make "X" always the maximizing player, no matter if it is the human or non-human player? Sure, you'd need a bit more care in the findBestMove function, but all the rest would become simpler.

huangapple
  • 本文由 发表于 2023年2月27日 09:15:25
  • 转载请务必保留本文链接：https://go.coder-hub.com/75576062.html
  • algorithm
  • minimax
  • python
  • recursion
  • tic-tac-toe
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定