我无与伦比的井字游戏程序失败了
My unbeatable Tic Tac Toe program is failing
我试过用极小极大算法制作一个在井字游戏中不会输的程序。但是,在少数情况下,它会失败。例如,当井字棋盘上还剩下两个点时(在少数情况下),程序会停止播放并要求用户连续输入两次。此外,在某些情况下,当计算机明显获胜时,它没有做出正确的移动选择。
这是一项作业,如果今天能提供任何形式的帮助,我们将不胜感激。
非常感谢!
编辑:
请注意,该代码允许用户覆盖以前的动作。我会尽快解决这个问题。
但是,即使我不覆盖以前的机会,我也得不到结果。我已经测试了代码,问题似乎出在 minimax 函数中,但我保留了整个代码以防万一我错了,真正的问题出在其他地方。
编辑 2:抱歉 post 不完整!重现问题的测试用例如下。当我输入我的着法(位置 5)后,程序停止播放并让我玩所有的机会。
Would you like to go first (Y/N)?: n
. . .
. . .
. . .
x . .
. . .
. . .
Enter your choice (1-9): 5
x . .
. o .
. . .
x x .
. o .
. . .
Enter your choice (1-9): 7
x x .
. o .
o . .
x x .
. o .
o . .
Enter your choice (1-9):
另外,我知道我的代码很乱而且很业余 - 但是尽管使用了全局变量,我应该能够让它工作。如果你能帮我解决这个问题,我会把它全部清理干净。再次感谢!
编辑 3:另一个测试用例:
你想先走吗(Y/N)?: y
. . .
. . .
. . .
Enter your choice (1-9): 5
. . .
. o .
. . .
x . .
. o .
. . .
Enter your choice (1-9): 3
x . o
. o .
. . .
x . o
. o .
x . .
Enter your choice (1-9): 2
x o o
. o .
x . .
x o o
. o .
x . .
Enter your choice (1-9): 6
x o o
. o o
x . .
x o o
. o o
x . .
Enter your choice (1-9): 9
You win!
我的代码在 Python 3.6 和下面:
move = -1
n = 0
def evaluateBoard(board):
global n
#Checking for rows
cnt = 0
for i in range(n):
res = 0
for j in range(n):
res += board[cnt * n + j]
cnt += 1
if res == n:
return 1
elif res == -n:
return -1
#Checking for columns
for i in range(n):
res = 0
for j in range(n):
res += board[i + n * j]
if res == n:
return 1
elif res == -n:
return -1
#Checking for diagonals
res = res2 = 0
for i in range(n):
res += board[i * (n + 1)]
res2 += board[(i + 1) * (n - 1)]
if n in [res, res2]:
return 1
elif -n in [res, res2]:
return -1
return 0
def checkNonTerminal(board):
for pos in board:
if pos == 0:
return 1
return 0
def getScore(board, depth):
if evaluateBoard(board) == 1:
return 10 - depth
elif evaluateBoard(board) == -1:
return depth - 10
else:
return 0
def minimax(board, turn, depth):
if evaluateBoard(board) == 0 and checkNonTerminal(board) == 0:
return getScore(board, depth)
global move
moves = list()
scores = list()
for square, pos in enumerate(board):
if pos == 0:
#print(board)
new_board = board.copy()
new_board[square] = turn
moves.append(square)
#print("Moves:", moves, "depth:", depth, "turn:", turn, checkNonTerminal(new_board) == 0)
if evaluateBoard(new_board) in [1, -1] or checkNonTerminal(new_board) == 0:
return getScore(new_board, depth)
scores.append(minimax(new_board, turn * -1, depth + 1))
#print("scores", scores)
if turn == 1:
move = moves[scores.index(max(scores))]
return max(scores)
elif turn == -1:
move = moves[scores.index(min(scores))]
return min(scores)
def displayBoard(board):
global n
for i in range(n):
for j in range(n):
if board[n*i+j] == 1:
print("x", end = " ")
elif board[n*i+j] == -1:
print("o", end = " ")
else:
print(".", end = " ")
print()
def main():
global n
global move
n = 3
first_turn = input("Would you like to go first (Y/N)?: ")
if first_turn in ['Y', 'y']:
first_turn = -1
cnt = 1
else:
first_turn = 1
cnt = 2
board = [0] * 9
while evaluateBoard(board) == 0 and checkNonTerminal(board) == 1:
displayBoard(board)
if cnt % 2 == 0:
score = minimax(board, 1, 0)
print(score)
board[move] = 1
else:
choice = eval(input("Enter your choice (1-9): "))
board[choice - 1] = -1
cnt += 1
if evaluateBoard(board) == 1:
print("You lose!")
elif evaluateBoard(board) == -1:
print("You win!")
else:
print("It's a draw!")
main()
如果您检查的第一个动作是终结者,则您 return 没有设置动作。可能是您失败的获胜逻辑以及跳过回合的原因。
更编程化一点:
您的递归终止条件被过早触发,您也需要处理这种情况!
for square, pos in enumerate(board):
if pos == 0:
#print(board)
new_board = board.copy()
new_board[square] = turn
moves.append(square)
#print("Moves:", moves, "depth:", depth, "turn:", turn, checkNonTerminal(new_board) == 0)
if evaluateBoard(new_board) in [1, -1] or checkNonTerminal(new_board) == 0:
return getScore(new_board, depth) <----here
scores.append(minimax(new_board, turn * -1, depth + 1))
#print("scores", scores)
太忙了,无法检查,但我相信您也可以在那里设置您的移动变量——如果您只是弹出递归堆栈,它稍后会被覆盖。
PS,这是使用适当的 return 变量而不是仅仅设置全局变量的另一个原因 ;)
我试过用极小极大算法制作一个在井字游戏中不会输的程序。但是,在少数情况下,它会失败。例如,当井字棋盘上还剩下两个点时(在少数情况下),程序会停止播放并要求用户连续输入两次。此外,在某些情况下,当计算机明显获胜时,它没有做出正确的移动选择。
这是一项作业,如果今天能提供任何形式的帮助,我们将不胜感激。
非常感谢!
编辑: 请注意,该代码允许用户覆盖以前的动作。我会尽快解决这个问题。 但是,即使我不覆盖以前的机会,我也得不到结果。我已经测试了代码,问题似乎出在 minimax 函数中,但我保留了整个代码以防万一我错了,真正的问题出在其他地方。
编辑 2:抱歉 post 不完整!重现问题的测试用例如下。当我输入我的着法(位置 5)后,程序停止播放并让我玩所有的机会。
Would you like to go first (Y/N)?: n
. . .
. . .
. . .
x . .
. . .
. . .
Enter your choice (1-9): 5
x . .
. o .
. . .
x x .
. o .
. . .
Enter your choice (1-9): 7
x x .
. o .
o . .
x x .
. o .
o . .
Enter your choice (1-9):
另外,我知道我的代码很乱而且很业余 - 但是尽管使用了全局变量,我应该能够让它工作。如果你能帮我解决这个问题,我会把它全部清理干净。再次感谢!
编辑 3:另一个测试用例: 你想先走吗(Y/N)?: y
. . .
. . .
. . .
Enter your choice (1-9): 5
. . .
. o .
. . .
x . .
. o .
. . .
Enter your choice (1-9): 3
x . o
. o .
. . .
x . o
. o .
x . .
Enter your choice (1-9): 2
x o o
. o .
x . .
x o o
. o .
x . .
Enter your choice (1-9): 6
x o o
. o o
x . .
x o o
. o o
x . .
Enter your choice (1-9): 9
You win!
我的代码在 Python 3.6 和下面:
move = -1
n = 0
def evaluateBoard(board):
global n
#Checking for rows
cnt = 0
for i in range(n):
res = 0
for j in range(n):
res += board[cnt * n + j]
cnt += 1
if res == n:
return 1
elif res == -n:
return -1
#Checking for columns
for i in range(n):
res = 0
for j in range(n):
res += board[i + n * j]
if res == n:
return 1
elif res == -n:
return -1
#Checking for diagonals
res = res2 = 0
for i in range(n):
res += board[i * (n + 1)]
res2 += board[(i + 1) * (n - 1)]
if n in [res, res2]:
return 1
elif -n in [res, res2]:
return -1
return 0
def checkNonTerminal(board):
for pos in board:
if pos == 0:
return 1
return 0
def getScore(board, depth):
if evaluateBoard(board) == 1:
return 10 - depth
elif evaluateBoard(board) == -1:
return depth - 10
else:
return 0
def minimax(board, turn, depth):
if evaluateBoard(board) == 0 and checkNonTerminal(board) == 0:
return getScore(board, depth)
global move
moves = list()
scores = list()
for square, pos in enumerate(board):
if pos == 0:
#print(board)
new_board = board.copy()
new_board[square] = turn
moves.append(square)
#print("Moves:", moves, "depth:", depth, "turn:", turn, checkNonTerminal(new_board) == 0)
if evaluateBoard(new_board) in [1, -1] or checkNonTerminal(new_board) == 0:
return getScore(new_board, depth)
scores.append(minimax(new_board, turn * -1, depth + 1))
#print("scores", scores)
if turn == 1:
move = moves[scores.index(max(scores))]
return max(scores)
elif turn == -1:
move = moves[scores.index(min(scores))]
return min(scores)
def displayBoard(board):
global n
for i in range(n):
for j in range(n):
if board[n*i+j] == 1:
print("x", end = " ")
elif board[n*i+j] == -1:
print("o", end = " ")
else:
print(".", end = " ")
print()
def main():
global n
global move
n = 3
first_turn = input("Would you like to go first (Y/N)?: ")
if first_turn in ['Y', 'y']:
first_turn = -1
cnt = 1
else:
first_turn = 1
cnt = 2
board = [0] * 9
while evaluateBoard(board) == 0 and checkNonTerminal(board) == 1:
displayBoard(board)
if cnt % 2 == 0:
score = minimax(board, 1, 0)
print(score)
board[move] = 1
else:
choice = eval(input("Enter your choice (1-9): "))
board[choice - 1] = -1
cnt += 1
if evaluateBoard(board) == 1:
print("You lose!")
elif evaluateBoard(board) == -1:
print("You win!")
else:
print("It's a draw!")
main()
如果您检查的第一个动作是终结者,则您 return 没有设置动作。可能是您失败的获胜逻辑以及跳过回合的原因。
更编程化一点:
您的递归终止条件被过早触发,您也需要处理这种情况!
for square, pos in enumerate(board):
if pos == 0:
#print(board)
new_board = board.copy()
new_board[square] = turn
moves.append(square)
#print("Moves:", moves, "depth:", depth, "turn:", turn, checkNonTerminal(new_board) == 0)
if evaluateBoard(new_board) in [1, -1] or checkNonTerminal(new_board) == 0:
return getScore(new_board, depth) <----here
scores.append(minimax(new_board, turn * -1, depth + 1))
#print("scores", scores)
太忙了,无法检查,但我相信您也可以在那里设置您的移动变量——如果您只是弹出递归堆栈,它稍后会被覆盖。
PS,这是使用适当的 return 变量而不是仅仅设置全局变量的另一个原因 ;)