-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathMinimax.py
164 lines (142 loc) · 4.21 KB
/
Minimax.py
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
# Minimax Algorithm
#
# Author: Luke Munro
from Clone import *
from Player import *
import copy
import random
from utils import orderMoves
from utils import formatMoves
from utils import makeCommands
class Minimax(Player):
""" Mnimax algorithm as a player. """
def __init__(self, dim, base, random=True):
Player.__init__(self, "Minimax " + str(base))
self.dim = dim
self.base = base
self.random = random
self.ENDING_SEQUENCE = False
def getMove(self, game_state, depth, DEBUG=False):
initial_node = Clone(game_state)
moves = initial_node.find_moves()
branches = [0] * len(moves)
best_score = -9e99
best_move = moves[0]
# FIRST MOVE IS EVALUATED HERE FOR RANDOMNESS
if depth > 0:
for i, move in enumerate(moves):
clone = copy.deepcopy(initial_node)
old_usedBoxes = clone.usedBoxes
clone.move(move)
clone.depth += 1
if old_usedBoxes < clone.usedBoxes:
branches[i] += (clone.usedBoxes - old_usedBoxes)
score = self.max_play(clone, depth)
else:
score = self.min_play(clone, depth)
branches[i] += score
if DEBUG:
initial_node.display_game()
print (branches)
print (moves)
if self.random: # RANDOM BAD AI
rand_move = random.randint(0, num_best_moves(branches)-1)
else: # TRAIN AI MAKE FIRST GOOD MOVE
rand_move = 0
return formatMoves(orderMoves(branches), moves)[rand_move]
def rankMoves(self, game_state, depth, DEBUG=False):
initial_node = Clone(game_state)
all_moves = makeCommands(self.dim)
legal_moves = initial_node.find_moves()
ranks = [0] * len(all_moves)
if depth>0:
for move in legal_moves:
i = all_moves.index(move)
clone = copy.deepcopy(initial_node)
old_usedBoxes = clone.usedBoxes
clone.move(move)
clone.depth += 1
if old_usedBoxes < clone.usedBoxes:
ranks[i] += (clone.usedBoxes - old_usedBoxes)
score = self.max_play(clone, depth)
else:
score = self.min_play(clone, depth)
ranks[i] += score
if DEBUG:
initial_node.display_game()
print (ranks)
print (all_moves)
return ranks
def min_play(self, node, depth):
if node.is_game_over() or node.depth == depth:
# if node.is_game_over(): # check over this later
# return -9e99
return node.score
node.depth += 1
moves = node.find_moves()
best_score = 9e99
for move in moves:
clone = copy.deepcopy(node)
old_usedBoxes = clone.usedBoxes
clone.move(move)
if old_usedBoxes < clone.usedBoxes:
clone.plus(old_usedBoxes - clone.usedBoxes)
score = self.min_play(clone, depth)
else:
score = self.max_play(clone, depth)
if score < best_score:
best_move = move
best_score = score
return best_score
def max_play(self, node, depth):
if node.is_game_over() or node.depth == depth:
return node.score
node.depth += 1
moves = node.find_moves()
best_score = -9e99
for move in moves:
clone = copy.deepcopy(node)
old_usedBoxes = clone.usedBoxes
clone.move(move)
if old_usedBoxes < clone.usedBoxes:
clone.plus(clone.usedBoxes - old_usedBoxes)
score = self.max_play(clone, depth)
else:
score = self.min_play(clone, depth)
if score > best_score:
best_move = move
best_score = score
return best_score
# -------------- ENDING SEQUENCE FOR SHALLOWBLUE -----------------
def check_ending_chain(self, game_state, current_score, DEBUG=False):
initial_state = Clone(game_state)
initial_state.plus(current_score)
self.ENDING_SEQUENCE = self.continue_chain(initial_state)
if DEBUG:
G.display_game()
def continue_chain(self, node, DEBUG=False):
if node.is_game_over() or node.score >= 5:
return True
moves = node.find_moves()
can_end = False
for move in moves:
if DEBUG:
print (move)
print (can_end)
if can_end == True:
break
clone = copy.deepcopy(node)
old_usedBoxes = clone.usedBoxes
clone.move(move)
if old_usedBoxes < clone.usedBoxes:
clone.plus(clone.usedBoxes - old_usedBoxes)
can_end = self.continue_chain(clone)
return can_end
def main(): # FOR SCENARIO DEPTH TESTING
m_state = [[1, 1, 1], [0, 0, 0, 0], [1, 1, 0], [0, 0, 0, 0], [1, 1, 1], [0, 0, 0, 0],\
[1, 1, 1]]
AI = Minimax(3, 0)
# AI.check_ending_chain(m_state, True)
print (AI.rankMoves(m_state, 5, True))
if __name__=="__main__":
main()