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
|
import math
from copy import deepcopy
from time import perf_counter
from random import choice
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()
class ABNode(object): # A class for Node related operations
def __init__(self, state):
self.Current = state
self.CurrentScore = self.Current.score[1]-self.Current.score[2]
self.children = {}
def update_score(self):
self.CurrentScore = self.Current.score[1]-self.Current.score[2]
def Make(self, r,c,o, player): # Function for generating a child node
self.children[(r,c,o)] = ABNode(self.Current)
move=(r,c,o)
self.children[(r,c,o)].play_move(move)
self.children[(r,c,o)].update_score()
def Populate(self, r,c,o, Child): # Function for adding a node
self.children[(r,c,o)] = Child
def Draw(self): # function for drawing the board
self.Current.Draw_mat()
# A class for defining algorithms used (minimax and alpha-beta pruning)
class AlphaBeta(object):
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
|
