-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heuristic.py
164 lines (143 loc) · 5.73 KB
/
Heuristic.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
163
164
import copy
from rules import Rules
import math
from GrabSides import GrabSides
from PositionH import PositionH
from MobilityH import MobilityH
from StabilityH import StabilityH
from InteriorStability import InteriorStability
'''
Filename: Heuristic.py
Authors: Max Dulin,Jacob Krantz
Date: 4/26/17
Description:
calculates the value of a board state for a player of Othello.
Initialized with the token to be analyzed for and called by
function 'calculateValue'.
Heuristic factors:
- chip ratio
- mobility
- position
- stability
- particular cases
- corners
- Xsquares and Wedges
'''
class Heuristic:
# initializes necessary data structures
def __init__(self, myToken,oppToken):
self.rules = Rules()
self.__oppToken = oppToken
self.__myToken = myToken
self.__depth = 3
self.__positionScores = [[95,10,80,75,75,80,10,95],
[10,10,45,45,45,45,10,10],
[65,40,70,50,50,70,40,65],
[60,40,40,40,40,40,40,60],
[60,40,40,40,40,40,40,60],
[65,40,70,50,50,70,40,65],
[10,10,45,45,45,45,10,10],
[95,10,65,60,60,65,10,95]]
self.PositionH = PositionH(myToken,oppToken,self.__positionScores)
self.MobilityH = MobilityH(myToken,oppToken)
self.StabilityH = StabilityH(myToken,oppToken)
self.InteriorStability = InteriorStability(myToken,oppToken)
# calculates the value of a given board state.
# higher score return, the better the position.
# factors of success:
# - evaporation
# - chip ratio
# - mobility
# - position
# **option: add a multiplier in front of each to adjust their
# individual affect on the score. All are currently
# normalized to 0 < score < 1
def calculateValue(self, matrix,path):
#print path
movesPlayed = self.getMovesPlayed(copy.deepcopy(matrix))
score = 1
self.PositionH.setDepth(self.__depth)
if(movesPlayed < 17):
stabVal = 1 # don't think i need this here
posVal = 1
mobilityVal = 1
edge = 1
#edge = self.InteriorStability.getScore(matrix)
posVal = self.PositionH.getScore(copy.deepcopy(matrix),path)
mobilityVal = self.MobilityH.getScore(copy.deepcopy(matrix))
score = self.__getWeightStage1(stabVal,mobilityVal,posVal,edge)
elif(movesPlayed >= 17 and movesPlayed <=58):
#edge = self.InteriorStability.getScore(matrix)
edge = 1
stabVal = self.StabilityH.getScore(copy.deepcopy(matrix))
mobilityVal = self.MobilityH.getScore(copy.deepcopy(matrix))
posVal = self.PositionH.getScore(copy.deepcopy(matrix),path)
score = self.__getWeightStage2(stabVal,mobilityVal,posVal,edge)
else:
#edge = self.InteriorStability.getScore(matrix)
edge = 1
chipCount = self.__getChipRatio(movesPlayed, copy.deepcopy(matrix))
stabVal = self.StabilityH.getScore(copy.deepcopy(matrix))
mobilityVal = self.MobilityH.getScore(copy.deepcopy(matrix))
posVal = self.PositionH.getScore(copy.deepcopy(matrix),path)
score = self.__getWeightStage3(stabVal,mobilityVal,posVal,chipCount,edge)
#print '%.25f' % score
return score
#---------------------
# PRIVATE FUNCITONS
#---------------------
# counts all played turns on the board by looking for occupied spaces.
def getMovesPlayed(self, matrix):
movesPlayed = 0
for i in range(1,9):
for j in range(1,9):
if(matrix[i][j] != '-'):
movesPlayed += 1
return movesPlayed
#Would give the weights for each of the values put in for stage 1
def __getWeightStage1(self,stabVal,mobilityVal,posVal,edge):
#print posVal
stabVal = stabVal * .20
mobilityVal = mobilityVal *.40
posVal = posVal * .40
#edge = edge * .01
score = stabVal * mobilityVal * posVal
return score
#Would give the weights for each of the values for stage 2
def __getWeightStage2(self,stabVal,mobilityVal,posVal,edge):
stabVal = stabVal * .30
mobilityVal = mobilityVal *.75
posVal = posVal * .50
#edge = edge * .01
score = stabVal * mobilityVal * posVal
return score
#Gives the weights of the last stage of the game
def __getWeightStage3(self,stabVal,mobilityVal,posVal,chipCount,edge):
stabVal = stabVal * .30
mobilityVal = mobilityVal *.20
posVal = posVal * .1
chipCount = chipCount * .9
#edge = edge * .01
score = chipCount * mobilityVal * posVal
return score
#sets the depth of the heuristic
def setDepth(self,num):
self.__depth = num
###############################
#Rating the amount of chips on the board
###############################
# returns the ratio of chips on the board that are myToken.
def __getChipRatio(self, movesPlayed, matrix):
myCount = 0
oppCount = 3
for i in range(0,9):
for j in range(1,9):
if(matrix[i][j] == self.__myToken):
myCount += 1
elif(matrix[i][j] == self.__oppToken):
oppCount+=1
return (myCount/float(oppCount)) / float(movesPlayed)
# inverse of chip ratio: at beginning of game, give away
# more spaces to improve end game chances
def __evaporation(self,movesPlayed,matrix):
return 1 / float(self.__getChipRatio(movesPlayed,matrix))