使用 python 的 Tic、Tac、Toe 中的 Minimax 算法:递归不会结束
Minimax Algorithm in Tic, Tac, Toe using python: Recursion won't come to end
我是编程新手,想使用 minimax 算法编写 Tic、tac、toe 求解器。当我测试我的程序时,它 returns: maximum recursion depth exceeded in comparison.我不知道为什么我的递归不会停止。有人可以帮我解决这个问题吗?请随时给我一些关于如何改进我的代码的提示。
# in the scores list the scores of the moves are kept
scores = []
# in the empty_spots list all indices of the empty cells in the grid are kept
empty_spots = []
# function, which prints the grid
def show_grid(grid):
a = 0
for cell in grid:
a = a + 1
if cell == 1:
if a < 3:
print("X", end="")
else:
print("X")
a = 0
elif cell == -1:
if a < 3:
print("O", end="")
else:
print("O")
a = 0
else:
if a < 3:
print("_", end="")
else:
print("_")
a = 0
# function which checks if there is a victory or draw
def check_victory(grid, player):
Victory_Combos = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [6, 4, 2]]
for victorys in Victory_Combos:
if grid[victorys[0]] == player*-1 and grid[victorys[1]] == player*-1 and grid[victorys[2]] == player*-1:
return -10 * player
if 0 not in grid:
return 0
# function which finds all empty spots
def find_empty_spots(grid):
for cell in range(9):
if grid[cell] == 0:
empty_spots.append(cell)
return empty_spots
# minimax function
def minimax(grid, player, best_score, depth):
if check_victory(grid, player) != None:
return check_victory(grid, player)
list = find_empty_spots(grid)
for cell in list:
grid[cell] = player
scores.append(minimax(grid, player*-1, 1000*-player, depth + 1))
if player == 1:
best_score = -1000
for score in scores:
if best_score < score:
best_score = score
else:
best_score = 1000
for score in scores:
if best_score > score:
best_score = score
grid[cell] = 0
if depth == 0:
grid[scores.index(best_score)] = player
show_grid()
scores.clear()
return best_score
# example
print(minimax([-1,1,-1,1,1,0,1,-1,0],-1,1000,0))
问题出在你的empty_spots
,你永远不会清除它,因此你总是检查以前的(空)单元格。
def find_empty_spots(grid):
empty_spots = []
for cell in range(9):
if grid[cell] == 0:
empty_spots.append(cell)
return empty_spots
添加了 empty_spots = []
以在每次调用之前清除列表,否则您只是将单元格附加到现有列表中。
还有一件事 - list = find_empty_spots(grid)
是非常非常错误的,不要对变量名使用关键字,正确的方法是 lst = find_empty_spots(grid)
,或者更好,一些有意义的名称,empty_cells = find_empty_spots(grid)
.
我是编程新手,想使用 minimax 算法编写 Tic、tac、toe 求解器。当我测试我的程序时,它 returns: maximum recursion depth exceeded in comparison.我不知道为什么我的递归不会停止。有人可以帮我解决这个问题吗?请随时给我一些关于如何改进我的代码的提示。
# in the scores list the scores of the moves are kept
scores = []
# in the empty_spots list all indices of the empty cells in the grid are kept
empty_spots = []
# function, which prints the grid
def show_grid(grid):
a = 0
for cell in grid:
a = a + 1
if cell == 1:
if a < 3:
print("X", end="")
else:
print("X")
a = 0
elif cell == -1:
if a < 3:
print("O", end="")
else:
print("O")
a = 0
else:
if a < 3:
print("_", end="")
else:
print("_")
a = 0
# function which checks if there is a victory or draw
def check_victory(grid, player):
Victory_Combos = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [6, 4, 2]]
for victorys in Victory_Combos:
if grid[victorys[0]] == player*-1 and grid[victorys[1]] == player*-1 and grid[victorys[2]] == player*-1:
return -10 * player
if 0 not in grid:
return 0
# function which finds all empty spots
def find_empty_spots(grid):
for cell in range(9):
if grid[cell] == 0:
empty_spots.append(cell)
return empty_spots
# minimax function
def minimax(grid, player, best_score, depth):
if check_victory(grid, player) != None:
return check_victory(grid, player)
list = find_empty_spots(grid)
for cell in list:
grid[cell] = player
scores.append(minimax(grid, player*-1, 1000*-player, depth + 1))
if player == 1:
best_score = -1000
for score in scores:
if best_score < score:
best_score = score
else:
best_score = 1000
for score in scores:
if best_score > score:
best_score = score
grid[cell] = 0
if depth == 0:
grid[scores.index(best_score)] = player
show_grid()
scores.clear()
return best_score
# example
print(minimax([-1,1,-1,1,1,0,1,-1,0],-1,1000,0))
问题出在你的empty_spots
,你永远不会清除它,因此你总是检查以前的(空)单元格。
def find_empty_spots(grid):
empty_spots = []
for cell in range(9):
if grid[cell] == 0:
empty_spots.append(cell)
return empty_spots
添加了 empty_spots = []
以在每次调用之前清除列表,否则您只是将单元格附加到现有列表中。
还有一件事 - list = find_empty_spots(grid)
是非常非常错误的,不要对变量名使用关键字,正确的方法是 lst = find_empty_spots(grid)
,或者更好,一些有意义的名称,empty_cells = find_empty_spots(grid)
.