FilesExpand file tree

 master

/

minimax.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (65 loc) · 3.09 KB

 master

/

minimax.py

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (65 loc) · 3.09 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

# minimax.py

# From Classic Computer Science Problems in Python Chapter 8

# Copyright 2018 David Kopec

#

# 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