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
|
from GameState import GameState
class GameController(object):
def get_next_move(self, state):
# when you get a new move, it is assumed that the game is not ended yet
assert state.get_moves()
def alpha_beta(node, alpha, beta):
# Based on https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning#Pseudocode
# node needs to support three operations: isTerminal(), value(), getChildren(), maximizingPlayer()
if node.isTerminal():
return node.value()
if node.maximizingPlayer():
v = float("-inf")
for child in node.getChildren():
v = max(v, alpha_beta(child, alpha, beta))
alpha = max(alpha, v)
if beta <= alpha:
break
else:
v = float("inf")
for child in node.getChildren():
v = min(v, alpha_beta(child, alpha, beta))
beta = min(beta, v)
if beta <= alpha:
break
return v
# A class for defining algorithms used (minimax and alpha-beta pruning)
class AlphaBeta:
def miniMax(State, Ply_num): # Function for the minimax algorithm
for i in range(State.Current.dimY):
for j in range(State.Current.dimX):
if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
State.Make(j, i, True)
if Ply_num < 2:
return (i, j)
Minimum_Score = 1000
i = 0
j = 0
for k, z in State.children.items():
Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
if Minimum_Score > Result:
Minimum_Score = Result
i = k[0]
j = k[1]
return (i, j)
# Alpha-beta pruning function for taking care of Alpha values
def Maximum(State, Ply_num, Alpha):
if Ply_num == 0:
return State.CurrentScore
for i in range(State.Current.dimY):
for j in range(State.Current.dimX):
if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
State.Make(j, i, False)
Maximum_Score = -1000
i = 0
j = 0
for k, z in State.children.items():
Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score)
if Maximum_Score < Result:
Maximum_Score = Result
if Result > Alpha:
return Result
return Maximum_Score
def Minimum(State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values
if Ply_num == 0:
return State.CurrentScore
for i in range(State.Current.dimY):
for j in range(State.Current.dimX):
if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
State.Make(j, i, True)
Minimum_Score = 1000
i = 0
j = 0
for k, z in State.children.items():
Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
if Minimum_Score > Result:
Minimum_Score = Result
if Result < Beta:
return Result
return Minimum_Score
|
