Negamax Alpha-Beta pruning

negamax_alpha_beta_pruning.py

def negamax(
	board: chess.Board, 
	depth: int, 
	player: int, 
	alpha: float = float("-inf"), 
	beta: float = float("inf")) -> Tuple[Union[int, chess.Move]]:
	"""
	This functions receives a board, depth and a player; and it returns
	the best move for the current board based on how many depths we're looking ahead
	and which player is playing. Alpha and beta are used to prune the search tree.
	Alpha represents the best score for the maximizing player (best choice (highest value)  we've found 
	along the path for max) and beta represents the best score for the minimizing player
	(best choice (lowest value) we've found along the path for min). When Alpha is higher 
	than or equal to Beta, we can prune the search  tree; because it means that the 
	maximizing player won't find a better move in this branch.

	OBS:
		- We only need to evaluate the value for leaf nodes because they are our final states
		of the board and therefore we need to use their values to base our decision of what is 
		the best move.

	Arguments: 
		- board: chess board state
		- depth: how many depths we want to calculate for this board
		- player: player that is currently moving pieces. 1 for AI (max), -1 for human (min).

	Returns:
		- best_score, best_move: returns best move that it found and its value.
	"""

	# recursion base case
	if depth == 0:
		# evaluate current board
		score = player * board_value(board)
		return score, None

	best_move = None

	# initializing best_score
	best_score = float("-inf")
	
	for move in board.legal_moves:
		# Make the move
		board.push(move)

		# if threefold repetition we do not analyze this position
		if board.can_claim_threefold_repetition():
			board.pop()  
			continue

		score = -negamax(board, depth-1, -player, -beta, -alpha)[0]

		# take move back
		board.pop()

		if score >= beta:
			return score, move

		# update best move
		if score > best_score:
			best_score = score
			best_move = move
		
		# setting alpha variable to do prunning
		alpha = max(alpha, score)

		# alpha beta prunning when we already found a solution that is at least as good as the current one
		# those branches won't be able to influence the final decision so we don't need to waste time analyzing them
		if alpha >= beta:
			break

	# if it returned no best move, we make a random one
	if not best_move:
		if board.legal_moves:
			best_move = random.choice([move for move in board.legal_moves])
		else:
			best_move = (None, None)
	
	return best_score, best_move