我的井字游戏告诉我平局时我赢了
my tic tac toe game tells me I am winning when it is a tie
理论上，我的 minimax 算法应该可以正常工作。我找不到任何明显的问题。但是...每当我 运行 为 'O' 时，我的算法都会说该玩家将获胜。然而，井字棋是一种抽签游戏。
我很困惑！
import time
positionsChecked = 0
maxDepthChecked = 0
drawn = 0
wonForAI = 0
wonForPlayer = 0
def areMovesLeft(board):
for i in board:
for j in i:
if j == '-':
return True
return False
def evaluate(board, humanSprite, AISprite):
movesLeft = areMovesLeft(board)
if not movesLeft:
return 0
for i in range(3):
if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
if board[i][0] == humanSprite:
return -10
elif board[i][0] == AISprite:
return 10
if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
if board[0][i] == humanSprite:
return -10
elif board[0][i] == AISprite:
return 10
if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
if board[0][0] == humanSprite:
return -10
elif board[0][0] == AISprite:
return 10
if board[0][2] == board[1][1] and board[1][1] == board[2][0]:
if board[0][2] == humanSprite:
return -10
elif board[0][2] == AISprite:
return 10
return 0
def minimax(board, isMaxPlayer, depth, humanSprite, AISprite, alpha, beta):
global positionsChecked, maxDepthChecked, drawn, wonForAI, wonForPlayer
best = 0
if depth > maxDepthChecked:
maxDepthChecked = depth
movesLeft = areMovesLeft(board)
if not movesLeft:
positionsChecked += 1
return 0
score = evaluate(board, humanSprite, AISprite)
if score == 10:
return score - depth
positionsChecked += 1
if score == -10:
positionsChecked +=1
return score + depth
for i in range(3):
for j in range(3):
if board[i][j] == '-':
movesLeft = True
if isMaxPlayer:
best = -1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = AISprite
var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
best = max(best, var2)
board[i][j] = '-'
alpha = max(alpha, best)
if alpha <= beta:
break
break
return best
else:
best = 1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = humanSprite
var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
best = min(best, var2)
board[i][j] = '-'
beta = min(beta, best)
if beta <= alpha:
break
break
print(best)
if best > 0:
wonForAI += 1
elif best == 0:
drawn +=1
elif best < 0:
wonForPlayer += 1
return best
def calcBestMove(board, humanSprite, AISprite):
global positionsChecked
global maxDepthChecked
maxDepthChecked = 0
positionsChecked = 0
print("Best move being calculated...")
timeBeforeMove = time.time() # I am using this to calculate how long the program takes to find the best move
bestValue = -1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = AISprite
moveValue = minimax(board, False, 1, humanSprite, AISprite, -1000, 1000)
board[i][j] = '-'
if moveValue > bestValue:
bestValue = moveValue
bestRow = i
bestCol = j
print(f"\nThe value of the best move is {bestValue}. The best move is ({bestRow + 1}, {bestCol + 1})")
timeAfterMove = time.time()
timeTaken = timeAfterMove - timeBeforeMove
print(f"The time it took the AI to find the best move is {timeTaken} seconds.")
print(f"The AI searched {positionsChecked} positions.")
print(f"Deepest search is {maxDepthChecked}")
print(f"Drawn is {drawn} and won for player is {wonForPlayer} and wonfor ai is {wonForAI}")
board[bestRow][bestCol] = AISprite
def printBoard(board): # this prints the board
print(" | | ")
print(f" {board[0][0]} | {board[0][1]} | {board[0][2]} ")
print(" | | ")
print("---------|---------|---------")
print(" | | ")
print(f" {board[1][0]} | {board[1][1]} | {board[1][2]} ")
print(" | | ")
print("---------|---------|---------")
print(" | | ")
print(f" {board[2][0]} | {board[2][1]} | {board[2][2]} ")
print(" | | ")
def switchTurns(humanSprite, AISprite, isHumanTurn, board): # controls the flow of the game
printBoard(board)
if isHumanTurn:
while True:
row = input("Enter row: ")
column = input("Enter column: ")
if (row == '1' or row == '2' or row == '3') and (column == '1' or column == '2' or column == '3'):
row = int(row)-1
column = int(column)-1
if 0 <= row <= 2 and 0 <= column <= 2 and board[row][column] == '-':
board[row][column] = humanSprite
break
else:
if not (0 <= row <= 2 and 0 <= column <= 2):
print("Out of range!")
else:
print("Box already filled")
else:
print("Not valid values!")
else:
calcBestMove(board, humanSprite, AISprite)
gameStatus = evaluate(board, humanSprite, AISprite)
if gameStatus == 0:
movesLeft = False
for i in range(3):
for j in range(3):
if board[i][j] == '-':
movesLeft = True
if not movesLeft:
print("It's a tie!")
else:
switchTurns(humanSprite, AISprite, not isHumanTurn, board)
else:
printBoard(board)
if gameStatus == -10:
print("Human wins!")
elif gameStatus == 10:
print("AI wins!")
return
def chooseFirstOrSecond():
playerGoesFirst = input("DO you want to be first or second? (f/s) ")
if playerGoesFirst == 'f' or playerGoesFirst == 's':
if playerGoesFirst == 'f':
switchTurns('X', 'O', True, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
if playerGoesFirst == 's':
switchTurns('O', 'X', False, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
else:
print("Invalid!")
chooseFirstOrSecond()
chooseFirstOrSecond()
举个我玩过的游戏的例子：
DO you want to be first or second? (f/s) s
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Best move being calculated...
The value of the best move is -4. The best move is (1, 1)
The time it took the AI to find the best move is 1.8505730628967285 seconds.
The AI searched 59492 positions.
Deepest search is 9
Drawn is 17158 and won for player is 20451 and wonfor ai is 2820
| |
X | - | -
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Enter row: 1
Enter column: 3
| |
X | - | O
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Best move being calculated...
The value of the best move is -4. The best move is (2, 1)
The time it took the AI to find the best move is 0.04171943664550781 seconds.
The AI searched 1322 positions.
Deepest search is 7
Drawn is 17529 and won for player is 20903 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Enter row: 3
Enter column: 1
| |
X | - | O
| |
---------|---------|---------
| |
X | - | -
| |
---------|---------|---------
| |
O | - | -
| |
Best move being calculated...
The value of the best move is -6. The best move is (2, 2)
The time it took the AI to find the best move is 0.0019884109497070312 seconds.
The AI searched 66 positions.
Deepest search is 5
Drawn is 17531 and won for player is 20939 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | X | -
| |
---------|---------|---------
| |
O | - | -
| |
Enter row: 2
Enter column: 3
| |
X | - | O
| |
---------|---------|---------
| |
X | X | O
| |
---------|---------|---------
| |
O | - | -
| |
Best move being calculated...
The value of the best move is 9. The best move is (3, 3)
The time it took the AI to find the best move is 0.0 seconds.
The AI searched 4 positions.
Deepest search is 3
Drawn is 17531 and won for player is 20941 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | X | O
| |
---------|---------|---------
| |
O | - | X
| |
AI wins!
（0以上为AI胜利，0以下为玩家胜利。）
你可以清楚地看到，它说我一直赢到最后一个回合......
我不知道为什么...
我认为您在 alpha-beta 修剪中翻转了比较运算符。具体来说，在 if isMaxPlayer: 分支中，
if alpha <= beta:
break
应该是
if alpha >= beta:
break
理论上，我的 minimax 算法应该可以正常工作。我找不到任何明显的问题。但是...每当我 运行 为 'O' 时，我的算法都会说该玩家将获胜。然而，井字棋是一种抽签游戏。 我很困惑！
import time
positionsChecked = 0
maxDepthChecked = 0
drawn = 0
wonForAI = 0
wonForPlayer = 0
def areMovesLeft(board):
for i in board:
for j in i:
if j == '-':
return True
return False
def evaluate(board, humanSprite, AISprite):
movesLeft = areMovesLeft(board)
if not movesLeft:
return 0
for i in range(3):
if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
if board[i][0] == humanSprite:
return -10
elif board[i][0] == AISprite:
return 10
if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
if board[0][i] == humanSprite:
return -10
elif board[0][i] == AISprite:
return 10
if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
if board[0][0] == humanSprite:
return -10
elif board[0][0] == AISprite:
return 10
if board[0][2] == board[1][1] and board[1][1] == board[2][0]:
if board[0][2] == humanSprite:
return -10
elif board[0][2] == AISprite:
return 10
return 0
def minimax(board, isMaxPlayer, depth, humanSprite, AISprite, alpha, beta):
global positionsChecked, maxDepthChecked, drawn, wonForAI, wonForPlayer
best = 0
if depth > maxDepthChecked:
maxDepthChecked = depth
movesLeft = areMovesLeft(board)
if not movesLeft:
positionsChecked += 1
return 0
score = evaluate(board, humanSprite, AISprite)
if score == 10:
return score - depth
positionsChecked += 1
if score == -10:
positionsChecked +=1
return score + depth
for i in range(3):
for j in range(3):
if board[i][j] == '-':
movesLeft = True
if isMaxPlayer:
best = -1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = AISprite
var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
best = max(best, var2)
board[i][j] = '-'
alpha = max(alpha, best)
if alpha <= beta:
break
break
return best
else:
best = 1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = humanSprite
var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
best = min(best, var2)
board[i][j] = '-'
beta = min(beta, best)
if beta <= alpha:
break
break
print(best)
if best > 0:
wonForAI += 1
elif best == 0:
drawn +=1
elif best < 0:
wonForPlayer += 1
return best
def calcBestMove(board, humanSprite, AISprite):
global positionsChecked
global maxDepthChecked
maxDepthChecked = 0
positionsChecked = 0
print("Best move being calculated...")
timeBeforeMove = time.time() # I am using this to calculate how long the program takes to find the best move
bestValue = -1000
for i in range(3):
for j in range(3):
if board[i][j] == '-':
board[i][j] = AISprite
moveValue = minimax(board, False, 1, humanSprite, AISprite, -1000, 1000)
board[i][j] = '-'
if moveValue > bestValue:
bestValue = moveValue
bestRow = i
bestCol = j
print(f"\nThe value of the best move is {bestValue}. The best move is ({bestRow + 1}, {bestCol + 1})")
timeAfterMove = time.time()
timeTaken = timeAfterMove - timeBeforeMove
print(f"The time it took the AI to find the best move is {timeTaken} seconds.")
print(f"The AI searched {positionsChecked} positions.")
print(f"Deepest search is {maxDepthChecked}")
print(f"Drawn is {drawn} and won for player is {wonForPlayer} and wonfor ai is {wonForAI}")
board[bestRow][bestCol] = AISprite
def printBoard(board): # this prints the board
print(" | | ")
print(f" {board[0][0]} | {board[0][1]} | {board[0][2]} ")
print(" | | ")
print("---------|---------|---------")
print(" | | ")
print(f" {board[1][0]} | {board[1][1]} | {board[1][2]} ")
print(" | | ")
print("---------|---------|---------")
print(" | | ")
print(f" {board[2][0]} | {board[2][1]} | {board[2][2]} ")
print(" | | ")
def switchTurns(humanSprite, AISprite, isHumanTurn, board): # controls the flow of the game
printBoard(board)
if isHumanTurn:
while True:
row = input("Enter row: ")
column = input("Enter column: ")
if (row == '1' or row == '2' or row == '3') and (column == '1' or column == '2' or column == '3'):
row = int(row)-1
column = int(column)-1
if 0 <= row <= 2 and 0 <= column <= 2 and board[row][column] == '-':
board[row][column] = humanSprite
break
else:
if not (0 <= row <= 2 and 0 <= column <= 2):
print("Out of range!")
else:
print("Box already filled")
else:
print("Not valid values!")
else:
calcBestMove(board, humanSprite, AISprite)
gameStatus = evaluate(board, humanSprite, AISprite)
if gameStatus == 0:
movesLeft = False
for i in range(3):
for j in range(3):
if board[i][j] == '-':
movesLeft = True
if not movesLeft:
print("It's a tie!")
else:
switchTurns(humanSprite, AISprite, not isHumanTurn, board)
else:
printBoard(board)
if gameStatus == -10:
print("Human wins!")
elif gameStatus == 10:
print("AI wins!")
return
def chooseFirstOrSecond():
playerGoesFirst = input("DO you want to be first or second? (f/s) ")
if playerGoesFirst == 'f' or playerGoesFirst == 's':
if playerGoesFirst == 'f':
switchTurns('X', 'O', True, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
if playerGoesFirst == 's':
switchTurns('O', 'X', False, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
else:
print("Invalid!")
chooseFirstOrSecond()
chooseFirstOrSecond()
举个我玩过的游戏的例子：
DO you want to be first or second? (f/s) s
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Best move being calculated...
The value of the best move is -4. The best move is (1, 1)
The time it took the AI to find the best move is 1.8505730628967285 seconds.
The AI searched 59492 positions.
Deepest search is 9
Drawn is 17158 and won for player is 20451 and wonfor ai is 2820
| |
X | - | -
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Enter row: 1
Enter column: 3
| |
X | - | O
| |
---------|---------|---------
| |
- | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Best move being calculated...
The value of the best move is -4. The best move is (2, 1)
The time it took the AI to find the best move is 0.04171943664550781 seconds.
The AI searched 1322 positions.
Deepest search is 7
Drawn is 17529 and won for player is 20903 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | - | -
| |
---------|---------|---------
| |
- | - | -
| |
Enter row: 3
Enter column: 1
| |
X | - | O
| |
---------|---------|---------
| |
X | - | -
| |
---------|---------|---------
| |
O | - | -
| |
Best move being calculated...
The value of the best move is -6. The best move is (2, 2)
The time it took the AI to find the best move is 0.0019884109497070312 seconds.
The AI searched 66 positions.
Deepest search is 5
Drawn is 17531 and won for player is 20939 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | X | -
| |
---------|---------|---------
| |
O | - | -
| |
Enter row: 2
Enter column: 3
| |
X | - | O
| |
---------|---------|---------
| |
X | X | O
| |
---------|---------|---------
| |
O | - | -
| |
Best move being calculated...
The value of the best move is 9. The best move is (3, 3)
The time it took the AI to find the best move is 0.0 seconds.
The AI searched 4 positions.
Deepest search is 3
Drawn is 17531 and won for player is 20941 and wonfor ai is 2862
| |
X | - | O
| |
---------|---------|---------
| |
X | X | O
| |
---------|---------|---------
| |
O | - | X
| |
AI wins!
（0以上为AI胜利，0以下为玩家胜利。） 你可以清楚地看到，它说我一直赢到最后一个回合...... 我不知道为什么...
我认为您在 alpha-beta 修剪中翻转了比较运算符。具体来说，在 if isMaxPlayer: 分支中，
if alpha <= beta:
break
应该是
if alpha >= beta:
break