I'm making an Othello player, and implemented a minimax algorithm with alpha-beta pruning. Then I did a bunch of research on the best ones online and keep hearing about a "negamax" algorithm that they all use. It seems like most people think negamax is faster than minimax (i think because it doesn't switch between min and max player?), so I'd like to turn my minimax algorithm into negamax if that's not too difficult.
I was wondering if people had any insight on how much faster using negamax is, and any tips or code on how to turn my minimax code into a negamax algorithm that'd be appreciated!
Here's my minimax algorithm:
def minimax(Board, maximizingPlayer, depth, count):
# maximizing player has 'B' and minimizing 'W'
if maximizingPlayer: player, opp = Board.player, Board.opp
else: player, opp = Board.opp, Board.player
moves_list = Board.get_moves_list(player, opp)
best_move = (-1,-1)
# base case
if ( depth==0 or moves_list == [] ):
best_score, parity, mobility, stability = Board.evaluate()
best_move = (-1, -1)
return best_score, best_move, count
# maximizing player
if maximizingPlayer:
best_score = float("-inf")
for move in moves_list:
new_board = deepcopy(Board)
new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
the_score, the_move, count = minimax(new_board, False, depth-1, count+1)
best_score = max(best_score, the_score)
if (the_score == best_score):
best_move = move
return best_score, best_move, count
# minimzing player
else:
best_score = float("inf")
for move in moves_list:
new_board = deepcopy(Board)
new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
the_score, the_move, count = minimax(new_board, True, depth-1, count+1)
best_score = min(best_score, the_score)
if (the_score == best_score):
best_move = move
return best_score, best_move, count
Since I got a response asking about my Alpha-beta pruning, here is that:
def alphabeta(Board, maximizingPlayer, depth, count, alpha, beta):
# maximizing player has 'B' and minimizing 'W'
if maximizingPlayer: player, opp = Board.player, Board.opp
else: player, opp = Board.opp, Board.player
moves_list = Board.get_moves_list(player, opp)
best_move = (-1,-1)
# base case
if ( depth==0 or moves_list == [] ):
best_score, parity, mobility, stability = Board.evaluate()
best_move = (-1, -1)
return best_score, best_move, count
# maximizing player
if maximizingPlayer:
best_score = float("-inf")
for move in moves_list:
new_board = deepcopy(Board)
new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
the_score, the_move, count = alphabeta(new_board, False, depth-1, count+1, alpha, beta)
if (the_score > alpha):
alpha = the_score
best_move = move
if beta <= alpha: break
return alpha, best_move, count
# minimzing player
else:
best_score = float("inf")
for move in moves_list:
new_board = deepcopy(Board)
new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
the_score, the_move, count = alphabeta(new_board, True, depth-1, count+1, alpha, beta)
if (the_score < beta):
beta = the_score
best_move = move
if beta <= alpha: break
return beta, best_move, count
I think now that you have implemented minimax it is good enough but you need to implement the most important optimization in minimax that is alpha-beta pruning which would be a simple change to your code with very significant improvement in speed.
EDIT:-
Noticed that you have used alpha-beta so you can implement negamax but your notion that it doesnt switch is not correct but it reduces the code for minimax ( i doubt significant improvement in speed) . The idea here is that the points for a move for one player is always -ve of the other player but same magnitude that allows you to calculate max(a,b) = -min(-a,-b).
Simple translation here is :-
score = -negamax(depth-1,-player)
best = max(score,best)
These are only lines to evaluate minimax using negamax
Here you dont need to evaluate min and max alternatively but the fact that the scores given to minplayer are always negative of positive player is sufficient so that you can always evaluate max to get correct score.
Note:-
This is not significant optimization in terms of speed but makes code simple and readable so its worth it but unfortunately you need erase alot of code to convert your code to negamax so i advice not to.