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
|
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
if state.player == 1:
self.CurrentScore = self.Current.score[2]-self.Current.score[1]
elif state.player ==2:
self.CurrentScore = self.Current.score[1]-self.Current.score[2]
self.children = {}
def update_score(self):
if self.Current.player == 2:
self.CurrentScore = self.Current.score[1]-self.Current.score[2]
elif self.Current.player == 1:
self.CurrentScore = self.Current.score[2]-self.Current.score[1]
def Make(self, r,c,o): # Function for generating a child node
self.children[(r,c,o)] = ABNode(self.Current)
move=(r,c,o)
self.children[(r,c,o)].Current.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(self, State, Ply_num): # Function for the minimax algorithm
start=ABNode(State)
possiblemoves=State.get_moves()
for x in possiblemoves:
if (x[0],x[1],x[2]) not in start.children:
start.Make(x[0],x[1],x[2])
if Ply_num < 2:
return (i, j)
Minimum_Score = 1000
r = 0
c = 0
o = ""
for k, z in start.children.items():
Result = self.Maximum(z, Ply_num - 1, Minimum_Score)
if Minimum_Score > Result:
Minimum_Score = Result
r = k[0]
c = k[1]
o = k[2]
return (r,c,o)
# Alpha-beta pruning function for taking care of Alpha values
def Maximum(self, State, Ply_num, Alpha):
if Ply_num == 0:
return State.CurrentScore
possiblemoves=State.Current.get_moves()
for x in possiblemoves:
if (x[0],x[1],x[2]) not in State.children:
State.Make(x[0],x[1],x[2])
Maximum_Score = -1000
r = 0
c = 0
o=""
for k, z in State.children.items():
Result = AlphaBeta.Minimum(z, Ply_num - 1, Maximum_Score)
if Maximum_Score < Result:
Maximum_Score = Result
if Result > Alpha:
return Result
return Maximum_Score
def Minimum(self, State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values
if Ply_num == 0:
return State.CurrentScore
possiblemoves=State.get_moves()
for x in possiblemoves:
if (x[0],x[1],x[2]) not in State.children:
State.Make(x[0],x[1],x[2])
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
|
