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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
| import copy
from random import shuffle, randint
import numpy as np
class MyPlayer():
'''MiniMax AlphaBeta pruning'''
def __init__(self, my_color,opponent_color, board_size=8):
self.my_color = my_color
self.opponent_color = opponent_color
self.board_size = board_size
self.empty_color = -1
def move(self, board):
moves = self.get_all_valid_moves(board)
print(moves)
opponent_color = self.opponent_color
if not moves:
return None
move = self.find_best_move(board, 10, opponent_color)
return move
def __is_correct_move(self, move, board):
dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]
for i in range(len(dx)):
if self.__confirm_direction(move, dx[i], dy[i], board)[0]:
return True,
return False
def __confirm_direction(self, move, dx, dy, board):
posx = move[0]+dx
posy = move[1]+dy
opp_stones_inverted = 0
if (posx >= 0) and (posx < self.board_size) and (posy >= 0) and (posy < self.board_size):
if board[posx][posy] == self.opponent_color:
opp_stones_inverted += 1
while (posx >= 0) and (posx <= (self.board_size-1)) and (posy >= 0) and (posy <= (self.board_size-1)):
posx += dx
posy += dy
if (posx >= 0) and (posx < self.board_size) and (posy >= 0) and (posy < self.board_size):
if board[posx][posy] == -1:
return False, 0
if board[posx][posy] == self.my_color:
return True, opp_stones_inverted
opp_stones_inverted += 1
return False, 0
def get_all_valid_moves(self, board):
valid_moves = []
for x in range(self.board_size):
for y in range(self.board_size):
if (board[x][y] == -1) and self.__is_correct_move([x, y], board):
valid_moves.append( (x, y) )
if len(valid_moves) <= 0:
print('No possible move!')
return None
return valid_moves
def alphabeta(self, board, current_player, depth, alpha, beta):
"""
param board: current state
depth: how deep i want to predict
alpha: maximum score for me
beta: max opponent score
current_player: player color
"""
if Board().is_draw:
return 0
if Board().is_win or depth == 0:
return Board().evaluate(current_player)
if Board().turn == current_player:
for move in Board().legal_moves:
scores = self.alphabeta(Board().right_move(move), current_player, depth-1, alpha, beta)
alpha = max(scores, alpha)
if alpha >= beta:
break
return alpha
else:
for move in Board().legal_moves(board):
scores = alphabeta(Board().right_move(move), current_player, depth-1, alpha, beta)
beta = min(scores, beta)
if alpha >= beta:
break
return beta
def find_best_move(self, board, max_depth, opponent_color):
"""Finds the best valid move for player
board - current_state,
max-depth - the depth of searching
returns best move - (x, y)
"""
player = Board().turn
moves = Board().legal_moves
best_scores = float('-inf')
min_scores = -best_scores
best_move = moves[0]
for move in moves:
scores = self.alphabeta(Board().right_move(move), player, max_depth, alpha=best_scores, beta=min_scores)
print(move, scores)
if opponent_color:
scores = self.alphabeta(Board().right_move(move), player, max_depth, alpha=-best_scores, beta=-min_scores)
if scores > best_scores:
best_move = move
best_scores = scores
return best_move
def get_opposite_color(self, player_color):
"""looking for the color of the opponent"""
if player_color == self.my_color:
return self.opponent_color
elif player_color == self.opponent_color:
return self.my_color
else:
return self.empty_color
class Board():
"""Basic class for a board of game. Contains state of board for current turn."""
def __init__(self, turn = 0, size = 10, field = None):
if field is None:
pass
self._field = field
self._size = size
self._turn = turn
self._legal_moves = set()
def turn(self):
"""Returns number of current player."""
return self._turn
def field(self):
return self._field
def last_turn(self):
"""Returns number of previous player."""
return MyPlayer().get_opposite_color(self._turn)
def get_neighbours(self, location, area_size = 1):
"""Returns a list of adjacent locations."""
x, y = location
neighbours = ((x - i, y - j) for i in range(-area_size, area_size + 1)
for j in range(-area_size, area_size + 1))
possible_neighbours = [(x, y) for x, y in neighbours if 0 <= x < self._size and 0 <= y < self._size]
return possible_neighbours
def right_move(self, location):
"""
Returns board with next state after move.
:param location:
:return: copy of board with new state
"""
pass
def is_win(self):
"""Returns True if player wins."""
pass
def is_draw(self):
"""Returns True if there are no moves and no one wins."""
return not (self.is_win or self.legal_moves)
def legal_moves(self):
"""Returns list of possible and reasonable moves. It's necessary for ai."""
return list(self._legal_moves)
def evaluate(self, player):
"""Evaluate state of board for current player and returns estimation of scores. It's necessary for ai."""
pass
def get_value(self, x, y):
"""Returns value from field"""
return self._field[x][y].value
class Reversi(Board):
def __init__(self, size = 10, turn = 0, field: np.ndarray = None, boundary_moves: set = None,
last_move = None):
"""
A game board for reversi (otello).
:param size: 6, 8 or 10 for board size. If new board is empty
:param turn: 0 or 1 for player number.
:param field: Old field with new move. If a new board is obtained by making a move on the previous board.
:param boundary_moves: Set of positions for moves along the border of placed pieces.
:param last_move: Position of last move.
"""
if field is None:
# If creating new empty field
field = np.array([[-1 for _ in range(size)] for _ in range(size)])
field[size // 2 - 1][size // 2 - 1] = 0
field[size // 2][size // 2] = 0
field[size // 2 - 1][size // 2] = 1
field[size // 2][size // 2 - 1] = 1
boundary_moves = {(i, j) for i in range(size // 2 - 2, size // 2 + 2)
for j in range(size // 2 - 2, size // 2 + 2) if field[i][j] == 0}
self._field = field
self._size = size
self._turn = turn
self._boundary_moves = boundary_moves
self._legal_moves = []
self._gem_counters = [0, 0, 0]
self.last_move = last_move
# Recount gems
for i in range(3):
self._gem_counters[i] = (self._field == i).sum()
self.check_legal_moves()
# When player can't do any move return turn
if len(self._legal_moves) == 0:
self._turn = self.last_turn
self.check_legal_moves()
# When even opponent can't do any move set clear positions to zero to end game
def get_gem_count(self):
return self._gem_counters[0], self._gem_counters[1]
def check_legal_moves(self):
self._legal_moves = []
for x, y in self._boundary_moves:
# Flag that move is added to stop checking
move_added = False
# Check all directions
for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):
k = 1
next_x, next_y = x + k * dx, y + k * dy
# Flag to know when we reached reverse color
got_reverse_color = False
while 0 <= next_x < self._size and 0 <= next_y < self._size and self._field[next_x][next_y] != -1:
if self._field[next_x][next_y] == self.last_turn:
got_reverse_color = True
else:
if self._field[next_x][next_y] == self.turn and got_reverse_color:
# We can change color of at least one piece
self._legal_moves.append((x, y))
move_added = True
break
k += 1
next_x, next_y = x + k * dx, y + k * dy
if move_added:
break
def right_move(self, location):
"""
Returns board with next state after move.
:param location:
:return: copy of board with new state
"""
if location not in self._legal_moves:
return None
x, y = location
new_boundary_moves = self._boundary_moves.copy()
for i, j in self.get_neighbours((x, y)):
if 0 <= i < self._size and 0 <= j < self._size and self._field[i][j] == -1:
new_boundary_moves.add((i, j))
new_boundary_moves.remove((x, y))
new_field = self._field.copy()
new_field[x][y] = self.turn
for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):
k = 1
next_x, next_y = x + k * dx, y + k * dy
# Flag to know when we reached reverse color
got_reverse_color = False
while 0 <= next_x < self._size and 0 <= next_y < self._size and self._field[next_x][next_y] != -1:
if self._field[next_x][next_y] == self.last_turn:
got_reverse_color = True
else:
if self._field[next_x][next_y] == self.turn and got_reverse_color:
next_x -= dx
next_y -= dy
while next_x != x or next_y != y:
new_field[next_x][next_y] = self.turn
next_x -= dx
next_y -= dy
break
k += 1
next_x, next_y = x + k * dx, y + k * dy
new_turn = self.last_turn
return Reversi(self._size, new_turn, new_field, new_boundary_moves, location)
def is_win(self):
"""Returns true if it is win"""
if self._gem_counters[0] > self._gem_counters[1]:
self._turn = 1
return True
if self._gem_counters[1] > self._gem_counters[0]:
self._turn = 0
return True
return False
def is_draw(self):
"""Returns True if it is draw"""
if self._gem_counters[0] == self._gem_counters[1]:
return True
return False
def evaluate(self, player):
return self._gem_counters[player] -self._gem_counters[MyPlayer().get_opposite_color(player)] |