我已经“成功地”开发了一个 minimax 算法,该算法可以建议跳棋游戏中的下一个最佳着法。 “SmartBot”使用这种算法。然而,当我测试 smartbot 对抗选择棋盘上随机可用动作的随机 bot 的功效时,我发现在 100 场比赛中,smartbot 有 38% 的胜率,而随机 bot 有 62% 的胜率。我不确定我正在运行的模拟是否产生了不正确的结果,或者我的 minimax 算法是否很糟糕。
我对整个SmartBot类的实现如下:
class SmartBot:
"""
Class representing the smartbot
"""
def __init__(self, game : Game, color : str):
"""
Constructor
Args:
game (Game): the current game
color (str): color of bot's pieces
"""
self._game = game
self._board = self._game.board
self._color = color
self.wins = 0
def suggest_move(self) -> tuple:
"""
Suggests a move!
Returns:
tuple(Piece, tuple): a tuple containing the piece that should be
moved and where it should be moved in coordinate form
"""
_, best_move = self._minimax(self._board, 2, True, self._game)
piece, move = best_move
return piece, move
def _minimax(self, board_state : Board, depth : int, max_player : bool, game : Game):
"""
Private method for finding the best move for the smartbot.
Args:
board_position (Board): current state of the board
depth (int): the depth of the game tree
max_player (bool): whether this is the max player or not
game (Game): current game
Returns:
_type_: _description_
"""
if depth == 0 or game.end_game:
return board_state._evaluate(), board_state
best_move = None
if max_player: #if AI
best = -math.inf
all_moves = self.get_all_moves(board_state, "B", game) #get all of the simulated moves
for piece,move,new_board in all_moves:
eval, _ = self._minimax(new_board, depth - 1, False, game)
if eval > best:
best = eval
best_move = (piece, move)
else: #if random or human
best = math.inf
all_moves = self.get_all_moves(board_state, "R", game)
for piece, move, new_board in all_moves:
eval, _ = self._minimax(new_board, depth - 1, True, game)
if eval < best:
best = eval
best_move = (piece, move)
return best, best_move
def simulate_move(self, piece, move, board, game):
original_loc = piece.location
start_row, start_col = piece.location
end_row, end_col = move
#are there jumps for the move we're considering?
jumps = game.piece_all_jumps(piece)
jumped_piece = None
#find the piece that the specified move will jump over
if jumps:
jumped_piece = board.get_piece_between(piece.location, move)
#if there is a jumped piece, remove it
if jumped_piece:
row, col = jumped_piece.location
board.grid[row][col] = None
game.jump_bool = False
#MOVE THE PIECE!
board.grid[start_row][start_col] = None
board.grid[end_row][end_col] = piece
board.pieces[piece.color].append(piece)
#handle kings
if not piece.is_king:
if (piece.color == 'R' and end_row == board.size - 1) or \
(piece.color == 'B' and end_row == 0):
piece.became_king = True
piece.is_king = True
new_board = deepcopy(board)
# REVERSE THE MOVE!
board._reverse_move(move, original_loc, game, jumped_piece)
return new_board
def get_all_moves(self, board, color, game):
#get all possible moves that we can make from a board
moves = []
all_moves = game.player_all_moves(board, color)
for _,move,piece in all_moves:
#simulate the movement of the piece on the board
new_board = self.simulate_move(piece, move, board, game)
moves.append((piece, move, new_board))
return moves
反转走棋方法如下:
def _reverse_move(self, move, original_loc, game, jumped_piece = None):
start_row, start_col = move
end_row, end_col = original_loc
#get the piece that moved
piece_moved = self.get_piece(move)
#if the piece became a king, unking it
if piece_moved.became_king:
piece_moved.is_king = False
piece_moved.became_king = False
最后,我的模拟如下:
class BotPlayer:
def __init__(self, name, color, game):
self.name = name
if self.name == "random":
self.bot = RandomBot(game, color)
elif self.name == "smart":
self.bot = SmartBot(game, color)
self.color = color
self.wins = 0
def simulate(player1, player2, num_games, board):
smart_wins = 0
dum_wins = 0
starting_players = []
for i in range(num_games):
board.reset_board()
game = Game(board) #current player starts as Black
if i != 0:
if starting_players[-1] == "B":
game.current_player = "R"
else:
game.current_player = "B"
starting_players.append(game.current_player)
#print(f"{game.current_player} starting this game")
#print_board(game.board)
bot1 = BotPlayer(player1, "B", game)
bot2 = BotPlayer(player2, "R", game)
bots = {"B": bot1, "R": bot2}
while not game.end_game:
piece, move = bots[game.current_player].bot.suggest_move()
if move != None:
game.move(piece, move)
if game.winner is not None:
if game.winner == bot1.color:
smart_wins += 1
else:
dum_wins += 1
#calculate wins
print(f"'B'({bots['B'].name}) is: {(smart_wins/num_games) * 100} %")
print(f"'R' bot ({bots['R'].name}) is: {(dum_wins/num_games) * 100} %")
模拟函数的示例调用是:
board = Board(6)
simulate("smart", 'random', 100, board)
任何帮助将不胜感激,因为我很困惑。谢谢!
我已经多次编辑算法,以及模拟功能。我不知道模拟是否被破坏或者我的算法本身是否运行良好。