ClassicComputerScienceProblemsInPython/Chapter8/minimax.py at master · vnikov/ClassicComputerScienceProblemsInPython · GitHub

History

73 lines (65 loc) · 3.09 KB

Raw

# minimax.py

# From Classic Computer Science Problems in Python Chapter 8

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

# http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from __future__ import annotations

from board import Piece, Board, Move

# Find the best possible outcome for original player

def minimax(board: Board, maximizing: bool, original_player: Piece, max_depth: int = 8) -> float:

# Base case – terminal position or maximum depth reached

if board.is_win or board.is_draw or max_depth == 0:

return board.evaluate(original_player)

# Recursive case - maximize your gains or minimize the opponent's gains

if maximizing:

best_eval: float = float("-inf") # arbitrarily low starting point

for move in board.legal_moves:

result: float = minimax(board.move(move), False, original_player, max_depth - 1)

best_eval = max(result, best_eval) # we want the move with the highest evaluation

return best_eval

else: # minimizing

worst_eval: float = float("inf")

for move in board.legal_moves:

result = minimax(board.move(move), True, original_player, max_depth - 1)

worst_eval = min(result, worst_eval) # we want the move with the lowest evaluation

return worst_eval

def alphabeta(board: Board, maximizing: bool, original_player: Piece, max_depth: int = 8, alpha: float = float("-inf"), beta: float = float("inf")) -> float:

# Base case – terminal position or maximum depth reached

if board.is_win or board.is_draw or max_depth == 0:

return board.evaluate(original_player)

# Recursive case - maximize your gains or minimize the opponent's gains

if maximizing:

for move in board.legal_moves:

result: float = alphabeta(board.move(move), False, original_player, max_depth - 1, alpha, beta)

alpha = max(result, alpha)

if beta <= alpha:

break

return alpha

else: # minimizing

for move in board.legal_moves:

result = alphabeta(board.move(move), True, original_player, max_depth - 1, alpha, beta)

beta = min(result, beta)

if beta <= alpha:

break

return beta

# Find the best possible move in the current position

# looking up to max_depth ahead

def find_best_move(board: Board, max_depth: int = 8) -> Move:

best_eval: float = float("-inf")

best_move: Move = Move(-1)

for move in board.legal_moves:

result: float = alphabeta(board.move(move), False, board.turn, max_depth)

if result > best_eval:

best_eval = result

best_move = move

return best_move

ClassicComputerScienceProblemsInPython/Chapter8/minimax.py at master · vnikov/ClassicComputerScienceProblemsInPython · GitHub

Expand file tree

Breadcrumbs

minimax.py

Latest commit

History

Breadcrumbs

minimax.py

File metadata and controls