-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimax.py
121 lines (91 loc) · 4.85 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
class IA:
def __init__(self, type):
self.algortimo = None
self.visitado = dict()
self.nos_expandidos = 0
self.profundidade_expandida = 0
if type == 0:
self.algortimo = self.minimax
else:
self.algortimo = self.alpha_beta
def minimax(self, jogo, profundidade_max, profundidade = 0):
melhores_jogadas = [None]
def minimax_auxiliar(IA, jogo, profundidade_max, profundidade, melhores_jogadas):
IA.profundidade_expandida = max(IA.profundidade_expandida, profundidade)
if(profundidade >= profundidade_max):
return jogo.utilidades()
elif(jogo.utilidade() == jogo.utilidade_max):
return jogo.utilidade_max
elif(jogo.utilidade() == jogo.utilidade_min):
return jogo.utilidade_min
else:
jogadas_possiveis = jogo.jogadas_possiveis()
melhor_jogada = None
melhor_utilidade = None
for jogada in jogadas_possiveis:
proximo = jogo.copy()
proximo.jogar(jogada)
if(str(proximo.blocos) in IA.visitado):
proximo_utilidade = IA.visitado[str(proximo.blocos)]
else:
proximo_utilidade = minimax_auxiliar(IA, proximo, profundidade_max, profundidade+1, melhores_jogadas)
IA.visitado[str(proximo.blocos)] = proximo_utilidade
IA.nos_expandidos += 1
if(melhor_jogada == None):
melhor_jogada = jogada
melhor_utilidade = proximo_utilidade
if(melhor_utilidade < proximo_utilidade if jogo.primeira_jogada_turno else melhor_utilidade > proximo_utilidade):
melhor_jogada = jogada
melhor_utilidade = proximo_utilidade
melhores_jogadas[0] = melhor_jogada
return melhor_utilidade
minimax_auxiliar(self, jogo, profundidade_max, profundidade, melhores_jogadas)
return melhores_jogadas[0]
def alpha_beta(self, jogo, profundidade_max, profundidade=0):
melhores_jogadas = [None]
def alpha_beta_auxiliar(IA, jogo, profundidade_max, profundidade, alpha, beta, melhores_jogadas):
IA.profundidade_expandida = max(IA.profundidade_expandida, profundidade)
if(profundidade >= profundidade_max):
return jogo.utilidades()
elif(jogo.utilidade() == jogo.utilidade_max):
return jogo.utilidade_max
elif(jogo.utilidade() == jogo.utilidade_min):
return jogo.utilidade_min
else:
jogadas_possiveis = jogo.jogadas_possiveis()
melhor_jogada = None
melhor_utilidade = None
for jogada in jogadas_possiveis:
proximo = jogo.copy()
proximo.jogar(jogada)
if(str(proximo.blocos) in IA.visitado):
proximo_utilidade = IA.visitado[str(proximo.blocos)]
else:
proximo_utilidade = alpha_beta_auxiliar(IA, proximo, profundidade_max, profundidade+1, alpha, beta, melhores_jogadas)
IA.visitado[str(proximo.blocos)] = proximo_utilidade
IA.nos_expandidos += 1
if(melhor_jogada == None):
melhor_jogada = jogada
melhor_utilidade = proximo_utilidade
if(melhor_utilidade < proximo_utilidade if jogo.primeira_jogada_turno else melhor_utilidade > proximo_utilidade):
melhor_jogada = jogada
melhor_utilidade = proximo_utilidade
if(jogo.primeira_jogada_turno):
alpha = max(alpha, int(proximo_utilidade))
else:
beta = min(beta, int(proximo_utilidade))
if(beta <= alpha):
break
melhores_jogadas[0] = melhor_jogada
return melhor_utilidade
alpha_beta_auxiliar(self, jogo, profundidade_max, profundidade, float("-inf"), float("inf"), melhores_jogadas)
return melhores_jogadas[0]
def jogar(self, jogo, profundidade_max = 2):
self.nos_expandidos = 0
self.profundidade_expandida = 0
jogada = self.algortimo(jogo, profundidade_max)
jogo.jogar(jogada)
print("Nós expandidos:", self.nos_expandidos)
print("Profundidade expandida:", self.profundidade_expandida, "\n")
self.visitado.clear()
return jogada