chess/search.py at main · s0tt/chess · GitHub

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
74
75
76
77
78
79
80
import numpy as np

class TreeSearch:
    def __init__(self, model, depth = 4):
        self.GameModel = model
        self.depth = depth
        pass

    def search(self, search_type="alphabeta"):
        if search_type == "minimax":
            best_score, best_move = self.maxi(self.depth)
        elif search_type == "alphabeta":
            best_score, best_move = self.alphaMax(-float("inf"), float("inf"), self.depth)
        return best_move

    def alphaMax(self, alpha, beta, depth):
        max_move = (-1, -1)
        if depth == 0:
            return self.GameModel.eval_board_shannon(), max_move
        legal_moves = self.GameModel.generate_legal_moves(self.GameModel.player_turn, silent=True)
        for orig, all_dest in legal_moves.items():
            for dest in all_dest:
                self.GameModel.move_piece(orig, dest, silent=True)
                score, _ = self.alphaMin(alpha, beta, depth - 1)
                self.GameModel.unmove_piece()
                if score >= beta: # score too good -> enemy will never allow this move, return
                    return beta, max_move
                if score > alpha: # new best score that is not "too" good
                    alpha = score # alpha is max
                    max_move = (orig, dest)
        return alpha, max_move

    def alphaMin(self, alpha, beta, depth):
        min_move = (-1, -1)
        if depth == 0:
            return -self.GameModel.eval_board_shannon(), min_move
        legal_moves = self.GameModel.generate_legal_moves(self.GameModel.player_turn, silent=True)
        for orig, all_dest in legal_moves.items():
            for dest in all_dest:
                self.GameModel.move_piece(orig, dest, silent=True)
                score, _ = self.alphaMax(alpha, beta, depth - 1)
                self.GameModel.unmove_piece()
                if score <= alpha: # score too bad -> do not consider rest as I will not blunder
                    return alpha, min_move
                if score < beta: # new bad score that is not "too" bad but still bad
                    beta = score # beta is min
                    min_move = (orig, dest)
        return beta, min_move

    def maxi(self, depth):
        if depth == 0:
            return self.GameModel.eval_board_shannon(), (-1, -1)
        max_score = -float("inf")
        max_move = (-1, -1)
        legal_moves = self.GameModel.generate_legal_moves(self.GameModel.player_turn, silent=True)
        for orig, all_dest in legal_moves.items():
            for dest in all_dest:
                self.GameModel.move_piece(orig, dest, silent=True)
                score, _ = self.mini(depth - 1)
                self.GameModel.unmove_piece()
                if score > max_score:
                    max_score = score
                    max_move = (orig, dest)
        return max_score, max_move

    def mini(self, depth):
        if depth == 0:
            return -self.GameModel.eval_board_shannon(), (-1, -1)
        min_score = float("inf")
        min_move = (-1, -1)
        legal_moves = self.GameModel.generate_legal_moves(self.GameModel.player_turn)
        for orig, all_dest in legal_moves.items():
            for dest in all_dest:
                self.GameModel.move_piece(orig, dest, silent=True)
                score, _ = self.maxi(depth - 1)
                self.GameModel.unmove_piece()
                if score < min_score:
                    min_score = score
                    min_move = (orig, dest)
        return min_score, min_move