ChessEngine/MiniMax.py at master · ShaneKilloran/ChessEngine · 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
81
##########################
######   MINI-MAX   ######
##########################

class MiniMax:
    # print utility value of root node (assuming it is max)
    # print names of all nodes visited during search
    def __init__(self, root):
        #self.game_tree = game_tree  # GameTree
        self.root = root  # GameNode
        #self.currentNode = None     # GameNode
        self.successors = root.children        # List of GameNodes
        return

    def minimax(self, node):
        # first, find the max value
        #best_val = self.max_value(node) # should be root node of tree

        # second, find the node which HAS that max value
        #  --> means we need to propagate the values back up the
        #      tree as part of our minimax algorithm
        successors = node.children
        #print ("MiniMax:  Utility Value of Root Node: = " + str(best_val))
        # find the node with our best move
        best_move = None
        best_val = -1
        for elem in successors:   # ---> Need to propagate values up tree for this to work
            print("Looking at ",elem.move, "with value: ", elem.value)
            if elem.value >= best_val:
                best_move = elem.move
                best_val = elem.value

        # return that best value that we've found
        print("Best move is: ",best_move)
        return best_move


    def max_value(self, node):
        #print ("MiniMax-->MAX: Visited Node :: " + str(node.move))
        if self.isTerminal(node):
            return self.getUtility(node)

        infinity = float('inf')
        max_value = -infinity

        successors_states = self.getSuccessors(node)
        for state in successors_states:
            max_value = max(max_value, self.min_value(state))
        return max_value

    def min_value(self, node):
        #print ("MiniMax-->MIN: Visited Node :: " + str(node.move))
        if self.isTerminal(node):
            return self.getUtility(node)

        infinity = float('inf')
        min_value = infinity

        successor_states = self.getSuccessors(node)
        for state in successor_states:
            min_value = min(min_value, self.max_value(state))
        return min_value

    #                     #
    #   UTILITY METHODS   #
    #                     #

    # successor states in a game tree are the child nodes...
    def getSuccessors(self, node):
        assert node is not None
        return node.children

    # return true if the node has NO children (successor states)
    # return false if the node has children (successor states)
    def isTerminal(self, node):
        assert node is not None
        return len(node.children) == 0

    def getUtility(self, node):
        assert node is not None
        return node.value