为什么我的 minimax 算法没有做出完美的移动 - 一维国际象棋？
Why my minimax algorithm doesn't make the perfect move - 1D Chess?
我正在尝试开发一种极小极大算法来下一维国际象棋，我正在考虑以下内容：8 个对齐的方格、1 个国王、1 个马和 1 个车。国王和车以通常的方式移动，而马一次移动 2 个方格。另外，如果相持或无法将死（只有2个国王或2个国王和一个额外的马）或8步没有减少棋子数量，则为平局。
这些是游戏本身的功能
from copy import deepcopy
# Board -> [list of pieces and non pieces, turn, plays without chagnge number of pieces]
# Piece -> 'K0', 'N1', 'R0', ...
def new_board():
return [['K0','N0','R0','--','--','R1','N1','K1'], 0, 0]
# Return True if there is any piece on the position index and False otherwise
def pieceQ(board, index):
return board[0][index][0] in ['K','N','R']
def available_piece(board, piece):
return piece in board[0]
# Return position of the piece
def piece_index(board, piece):
if piece in board[0]:
return board[0].index(piece)
else:
return -1
# Return the piece on position index
def index_piece(board, index):
if pieceQ(board, index):
return board[0][index]
else:
return '--'
def print_board(board, code = -1):
if code == -1:
print(board[0])
else:
second_board = deepcopy(board[0])
second_board[code] = '*'+second_board[code]+'*'
print(second_board)
def available_pieces(board):
a_pieces = []
for x in board[0]:
if x[1]==str(board[1]):
a_pieces += [x]
return a_pieces
# Returns the position of the pieces before and after the rook
def min_max_rook(board):
rook_index = board[0].index('R'+str(board[1]))
minim = 0
for i in range(len(board[0][:rook_index])):
if pieceQ(board, i):
minim = i
if index_piece(board, i)[1]==str(board[1]):
minim+=1
maxim = 7
for i in range(7, rook_index, -1):
if pieceQ(board, i):
maxim = i
if index_piece(board,i)[1]==str(board[1]):
maxim-=1
return (minim, maxim)
def available_moves(board):
pieces = available_pieces(board)
moves = []
for piece in pieces:
piece_ind = piece_index(board, piece)
# Move King
if piece[0]=='K':
# Move forward
if piece_ind<7:
second_board = deepcopy(board)
if index_piece(board, piece_ind+1)[1]!=str(board[1]) and index_piece(board, piece_ind+1)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind+1, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind+1)]
# Move backwards
if piece_ind>0:
second_board = deepcopy(board)
if index_piece(board, piece_ind-1)[1]!=str(board[1]) and index_piece(board, piece_ind-1)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind-1, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind-1)]
# Move Knight
elif piece[0]=='N':
# Move forward
if piece_ind<6:
second_board = deepcopy(board)
if index_piece(board, piece_ind+2)[1]!=str(board[1]) and index_piece(board, piece_ind+2)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind+2, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind+2)]
# Move backwards
if piece_ind>1:
second_board = deepcopy(board)
if index_piece(board, piece_ind-2)[1]!=str(board[1]) and index_piece(board, piece_ind-2)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind-2, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind-2)]
# Move Rook
elif piece[0]=='R':
minim, maxim = min_max_rook(board)
for i in range(minim, maxim+1):
second_board = deepcopy(board)
if i!=piece_ind and index_piece(board, i)[0]!='K':
second_board_2 = move(second_board, piece[0], i, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], i)]
return moves
def move(board, piece, position, free=False):
if not free and (piece, position) not in available_moves(board):
print('It is impossible to move '+piece+' to',position)
raise # IMPOSSIBLE MOVE
elif not available_piece(board, piece+str(board[1])):
raise #PIECE NOT AVAILABLE
else:
n_pieces_old = len([i for i in range(len(board[0])) if pieceQ(board,i)])
old_position = piece_index(board, piece+str(board[1]))
board[0][old_position] = '--'
board[0][position] = piece+str(board[1])
board[1] = (board[1]+1)%2
n_pieces_new = len([i for i in range(len(board[0])) if pieceQ(board,i)])
if n_pieces_old==n_pieces_new:
board[2] += 1
return [board[0],board[1],board[2]+1]
else:
board[2] = 0
return [board[0],board[1],0]
# Returns True if board is in a check position for player board[1]
def check(board):
king_index = piece_index(board, 'K'+str(board[1]))
if king_index+2 <= 7 and index_piece(board, king_index+2) == 'N'+str((board[1]+1)%2):
return True
elif king_index-2 >= 0 and index_piece(board, king_index-2) == 'N'+str((board[1]+1)%2):
return True
else:
# Check with Rook
rook_index = piece_index(board,'R'+str((board[1]+1)%2))
if rook_index != -1:
if abs(king_index-rook_index)==1:
return True
found = False
for i in range(min(king_index, rook_index)+1, max(king_index, rook_index)):
found = found or (pieceQ(board, i))
if not found:
return True
# Check with king
king_index_2 = piece_index(board, 'K'+str((board[1]+1)%2))
if abs(king_index-king_index_2)==1:
return True
else:
return False
def stalemate(board):
return (not check(board) and len(available_moves(board))==0) or len([board[0][i] for i in range(len(board[0])) if pieceQ(board, i)])==2 or (len([x for x in board[0] if x[0] in ['K', 'N']])==3 and len([i for i in range(len(board[0])) if pieceQ(board,i)])==3) or board[2]==8
def checkmate(board):
return check(board) and len(available_moves(board))==0
def game_over(board):
return checkmate(board) or stalemate(board)
def evaluate_board(board):
if not board[1]:
# Defeat
if checkmate(board):
return -1
# Victory
elif checkmate([board[0], (board[1]+1)%2]):
return 1
else:
return 0
else:
# Defeat
if checkmate(board):
return 1
# Victory
elif checkmate([board[0], (board[1]+1)%2]):
return -1
else:
return 0
这是我在 Codecademy tic tac toe 算法中启发的 minimax 算法。在这里，我保证将死棋总会发生。
def minimax(input_board, is_maximizing, max_depth=8):
depth = max_depth-1
# Base case - the game is over, so we return the value of the board
if game_over(input_board):
return [evaluate_board(input_board), ('','')]
# The maximizing player
elif is_maximizing:
# The best value starts at the lowest possible value
best_value = -float("Inf")
best_move = ('','')
av_moves = available_moves(input_board)
if len(av_moves)==1:
return [best_value, av_moves[0]]
else:
for m in av_moves:
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
if checkmate(new_board):
return [best_value, m]
# Loop through all the available moves
for m in av_moves:
# Make a copy of the board and apply the move to it
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
# Recursively find your opponent's best move
if depth >= 0:
hypothetical_value = minimax(new_board, False, depth)[0]
else:
return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]
# Update best value if you found a better hypothetical value
if hypothetical_value > best_value:
best_value = hypothetical_value
best_move = m
return [best_value, (best_move if best_move != ('','') else m)]
# The minimizing player
else:
# The best value starts at the highest possible value
best_value = float("Inf")
best_move = ('','')
av_moves = available_moves(input_board)
if len(av_moves)==1:
return [best_value, av_moves[0]]
else:
for m in av_moves:
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
if checkmate(new_board):
return [best_value, m]
# Testing all potential moves
for m in av_moves:
# Copying the board and making the move
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
# Passing the new board back to the maximizing player
if depth >= 0:
hypothetical_value = minimax(new_board, True, depth)[0]
else:
return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]
# Keeping track of the best value seen so far
if hypothetical_value < best_value:
best_value = hypothetical_value
best_move = m
return [best_value, (best_move if best_move != ('','') else m)]
（我考虑了从 0 到 7 的方块的棋盘）
玩家 0 是第一个上场的玩家。问题是我可以作为玩家 0 击败算法，我的移动是 - N3，N5，R3，K1，N7 - 但我可以作为玩家 1 移动 - N4，K6，N2，K5。这是我作为玩家 1 绘制的游戏。
['K0', 'N0', 'R0', '--', '--', 'R1', 'N1', 'K1']
['K0', '--', 'R0', 'N0', '--', 'R1', 'N1', 'K1']
件，位置：n4
['K0', '--', 'R0', 'N0', 'N1', 'R1', '--', 'K1']
['K0', '--', 'R0', '--', 'N1', 'N0', '- -', 'K1']
棋子，位置：k6
['K0', '--', 'R0', '--', 'N1', 'N0', 'K1', ' --']
['--', 'K0', 'R0', '--', 'N1', 'N0', 'K1', '--']
件，位置：n2
['--', 'K0', 'N1', '--', '--', 'N0', 'K1', '- -']
['--', '--', 'K0', '--', '--', 'N0', 'K1', '--']
我认为在我的 k6 之后它应该与车一起前进而不是与国王一起前进。
这样他最终可以平局而不是输球。
希望你能帮助我。
谢谢！
问题是我使用深度的方式不起作用。它应该在开头（在基本情况下）。我想问题已经解决了。
我正在尝试开发一种极小极大算法来下一维国际象棋，我正在考虑以下内容：8 个对齐的方格、1 个国王、1 个马和 1 个车。国王和车以通常的方式移动，而马一次移动 2 个方格。另外，如果相持或无法将死（只有2个国王或2个国王和一个额外的马）或8步没有减少棋子数量，则为平局。
这些是游戏本身的功能
from copy import deepcopy
# Board -> [list of pieces and non pieces, turn, plays without chagnge number of pieces]
# Piece -> 'K0', 'N1', 'R0', ...
def new_board():
return [['K0','N0','R0','--','--','R1','N1','K1'], 0, 0]
# Return True if there is any piece on the position index and False otherwise
def pieceQ(board, index):
return board[0][index][0] in ['K','N','R']
def available_piece(board, piece):
return piece in board[0]
# Return position of the piece
def piece_index(board, piece):
if piece in board[0]:
return board[0].index(piece)
else:
return -1
# Return the piece on position index
def index_piece(board, index):
if pieceQ(board, index):
return board[0][index]
else:
return '--'
def print_board(board, code = -1):
if code == -1:
print(board[0])
else:
second_board = deepcopy(board[0])
second_board[code] = '*'+second_board[code]+'*'
print(second_board)
def available_pieces(board):
a_pieces = []
for x in board[0]:
if x[1]==str(board[1]):
a_pieces += [x]
return a_pieces
# Returns the position of the pieces before and after the rook
def min_max_rook(board):
rook_index = board[0].index('R'+str(board[1]))
minim = 0
for i in range(len(board[0][:rook_index])):
if pieceQ(board, i):
minim = i
if index_piece(board, i)[1]==str(board[1]):
minim+=1
maxim = 7
for i in range(7, rook_index, -1):
if pieceQ(board, i):
maxim = i
if index_piece(board,i)[1]==str(board[1]):
maxim-=1
return (minim, maxim)
def available_moves(board):
pieces = available_pieces(board)
moves = []
for piece in pieces:
piece_ind = piece_index(board, piece)
# Move King
if piece[0]=='K':
# Move forward
if piece_ind<7:
second_board = deepcopy(board)
if index_piece(board, piece_ind+1)[1]!=str(board[1]) and index_piece(board, piece_ind+1)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind+1, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind+1)]
# Move backwards
if piece_ind>0:
second_board = deepcopy(board)
if index_piece(board, piece_ind-1)[1]!=str(board[1]) and index_piece(board, piece_ind-1)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind-1, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind-1)]
# Move Knight
elif piece[0]=='N':
# Move forward
if piece_ind<6:
second_board = deepcopy(board)
if index_piece(board, piece_ind+2)[1]!=str(board[1]) and index_piece(board, piece_ind+2)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind+2, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind+2)]
# Move backwards
if piece_ind>1:
second_board = deepcopy(board)
if index_piece(board, piece_ind-2)[1]!=str(board[1]) and index_piece(board, piece_ind-2)[0]!='K':
second_board_2 = move(second_board, piece[0], piece_ind-2, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], piece_ind-2)]
# Move Rook
elif piece[0]=='R':
minim, maxim = min_max_rook(board)
for i in range(minim, maxim+1):
second_board = deepcopy(board)
if i!=piece_ind and index_piece(board, i)[0]!='K':
second_board_2 = move(second_board, piece[0], i, free=True)
if not check((second_board_2[0],(second_board_2[1]+1)%2)):
moves += [(piece[0], i)]
return moves
def move(board, piece, position, free=False):
if not free and (piece, position) not in available_moves(board):
print('It is impossible to move '+piece+' to',position)
raise # IMPOSSIBLE MOVE
elif not available_piece(board, piece+str(board[1])):
raise #PIECE NOT AVAILABLE
else:
n_pieces_old = len([i for i in range(len(board[0])) if pieceQ(board,i)])
old_position = piece_index(board, piece+str(board[1]))
board[0][old_position] = '--'
board[0][position] = piece+str(board[1])
board[1] = (board[1]+1)%2
n_pieces_new = len([i for i in range(len(board[0])) if pieceQ(board,i)])
if n_pieces_old==n_pieces_new:
board[2] += 1
return [board[0],board[1],board[2]+1]
else:
board[2] = 0
return [board[0],board[1],0]
# Returns True if board is in a check position for player board[1]
def check(board):
king_index = piece_index(board, 'K'+str(board[1]))
if king_index+2 <= 7 and index_piece(board, king_index+2) == 'N'+str((board[1]+1)%2):
return True
elif king_index-2 >= 0 and index_piece(board, king_index-2) == 'N'+str((board[1]+1)%2):
return True
else:
# Check with Rook
rook_index = piece_index(board,'R'+str((board[1]+1)%2))
if rook_index != -1:
if abs(king_index-rook_index)==1:
return True
found = False
for i in range(min(king_index, rook_index)+1, max(king_index, rook_index)):
found = found or (pieceQ(board, i))
if not found:
return True
# Check with king
king_index_2 = piece_index(board, 'K'+str((board[1]+1)%2))
if abs(king_index-king_index_2)==1:
return True
else:
return False
def stalemate(board):
return (not check(board) and len(available_moves(board))==0) or len([board[0][i] for i in range(len(board[0])) if pieceQ(board, i)])==2 or (len([x for x in board[0] if x[0] in ['K', 'N']])==3 and len([i for i in range(len(board[0])) if pieceQ(board,i)])==3) or board[2]==8
def checkmate(board):
return check(board) and len(available_moves(board))==0
def game_over(board):
return checkmate(board) or stalemate(board)
def evaluate_board(board):
if not board[1]:
# Defeat
if checkmate(board):
return -1
# Victory
elif checkmate([board[0], (board[1]+1)%2]):
return 1
else:
return 0
else:
# Defeat
if checkmate(board):
return 1
# Victory
elif checkmate([board[0], (board[1]+1)%2]):
return -1
else:
return 0
这是我在 Codecademy tic tac toe 算法中启发的 minimax 算法。在这里，我保证将死棋总会发生。
def minimax(input_board, is_maximizing, max_depth=8):
depth = max_depth-1
# Base case - the game is over, so we return the value of the board
if game_over(input_board):
return [evaluate_board(input_board), ('','')]
# The maximizing player
elif is_maximizing:
# The best value starts at the lowest possible value
best_value = -float("Inf")
best_move = ('','')
av_moves = available_moves(input_board)
if len(av_moves)==1:
return [best_value, av_moves[0]]
else:
for m in av_moves:
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
if checkmate(new_board):
return [best_value, m]
# Loop through all the available moves
for m in av_moves:
# Make a copy of the board and apply the move to it
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
# Recursively find your opponent's best move
if depth >= 0:
hypothetical_value = minimax(new_board, False, depth)[0]
else:
return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]
# Update best value if you found a better hypothetical value
if hypothetical_value > best_value:
best_value = hypothetical_value
best_move = m
return [best_value, (best_move if best_move != ('','') else m)]
# The minimizing player
else:
# The best value starts at the highest possible value
best_value = float("Inf")
best_move = ('','')
av_moves = available_moves(input_board)
if len(av_moves)==1:
return [best_value, av_moves[0]]
else:
for m in av_moves:
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
if checkmate(new_board):
return [best_value, m]
# Testing all potential moves
for m in av_moves:
# Copying the board and making the move
new_board = deepcopy(input_board)
move(new_board, m[0], m[1])
# Passing the new board back to the maximizing player
if depth >= 0:
hypothetical_value = minimax(new_board, True, depth)[0]
else:
return [(best_value if best_move != ('','') else 0), (best_move if best_move != ('','') else m)]
# Keeping track of the best value seen so far
if hypothetical_value < best_value:
best_value = hypothetical_value
best_move = m
return [best_value, (best_move if best_move != ('','') else m)]
（我考虑了从 0 到 7 的方块的棋盘）
玩家 0 是第一个上场的玩家。问题是我可以作为玩家 0 击败算法，我的移动是 - N3，N5，R3，K1，N7 - 但我可以作为玩家 1 移动 - N4，K6，N2，K5。这是我作为玩家 1 绘制的游戏。
['K0', 'N0', 'R0', '--', '--', 'R1', 'N1', 'K1']
['K0', '--', 'R0', 'N0', '--', 'R1', 'N1', 'K1']
件，位置：n4 ['K0', '--', 'R0', 'N0', 'N1', 'R1', '--', 'K1']
['K0', '--', 'R0', '--', 'N1', 'N0', '- -', 'K1']
棋子，位置：k6 ['K0', '--', 'R0', '--', 'N1', 'N0', 'K1', ' --']
['--', 'K0', 'R0', '--', 'N1', 'N0', 'K1', '--']
件，位置：n2 ['--', 'K0', 'N1', '--', '--', 'N0', 'K1', '- -']
['--', '--', 'K0', '--', '--', 'N0', 'K1', '--']
我认为在我的 k6 之后它应该与车一起前进而不是与国王一起前进。
这样他最终可以平局而不是输球。 希望你能帮助我。
谢谢！
问题是我使用深度的方式不起作用。它应该在开头（在基本情况下）。我想问题已经解决了。