-
Notifications
You must be signed in to change notification settings - Fork 0
/
investigate_game.py
352 lines (307 loc) · 12.8 KB
/
investigate_game.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
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
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
from game import Game, Move, Player
from copy import deepcopy
from itertools import product
from typing import Literal, Any
from utils.symmetry import Symmetry
import numpy as np
from collections import defaultdict
POSSIBLE_MOVES = []
# for each piece position
for from_pos in set(product([0, 4], range(Game()._board.shape[0]))).union(
set(product(range(Game()._board.shape[1]), [0, 4]))
):
# create a list of possible slides
slides = list(Move)
# for each slide
for slide in slides:
# make a copy of the current game state
state = deepcopy(Game())
# create an action
action = (from_pos, slide)
# perfom the action (note: _Game__move is necessary due to name mangling)
ok = state._Game__move(from_pos, slide, 0)
# if it is a valid action
if ok:
# append to the list of possible moves
POSSIBLE_MOVES.append(action)
class MissNoAddDict(defaultdict):
"""
Class extending defaultdict to not add a new key if it is not present.
"""
def __missing__(self, __key: Any) -> Any:
"""
If the key is missing, don't create a new dictionary entry
and return the default value.
Args:
__key: the key used to index the dictionary.
Returns:
The default factory value is returned.
"""
return self.default_factory()
class InvestigateGame(Game):
'''
Class representing an extension of the Game class which
is used by the players to simulate the game or to train them.
'''
def __init__(self, game: 'Game') -> None:
'''
Constructor for creating a copy of the game to investigate.
Args:
game: the current game state.
Returns:
None.
'''
super().__init__()
self._board = game.get_board()
self.current_player_idx = game.get_current_player()
self._player_to_symbol = {-1: '⬜️', 0: '❌', 1: '⭕️'}
def print(self) -> None:
'''
Print the board in a fancy way.
Args:
None.
Returns:
None
'''
# for each row
for i in range(self._board.shape[0]):
# for each column
for j in range(self._board.shape[1]):
# print the element in position (i, j)
print(self._player_to_symbol[self._board[i, j]], end='')
# go to the beginning of the next line
print()
def __eq__(self, other: 'InvestigateGame') -> bool:
'''
Equality check for the class. Games are equal if the boards are equal.
Args:
other: another game instance.
Returns:
The equality of two games is returned.
'''
return (self._board == other._board).all()
def get_hashable_state(self, player_id: int) -> int:
'''
Get a unique representation of a state that can be used as a key for a dictionary.
Args:
player_id: the player's id.
Returns:
An integer representation of the state is returned.
'''
# map the game state to an integer in base 3
return int(''.join(str(_) for _ in (self._board + 1).flatten()) + str(player_id), base=3)
def generate_possible_transitions(self) -> list[tuple[tuple[tuple[int, int], Move], 'InvestigateGame']]:
'''
Generate all possible game transitions that the current player can make.
Args:
None.
Returns:
A list of 3-length tuples of actions, corresponding game states and their
representations is returned.
'''
# define a list of possible transitions
transitions = []
# for each piece position
for from_pos, slide in POSSIBLE_MOVES:
# check the validity of the action
ok = (
self._board[from_pos[1], from_pos[0]] == -1
or self._board[from_pos[1], from_pos[0]] == self.current_player_idx
)
# if it is a valid action
if ok:
# make a copy of the current game state
state = deepcopy(self)
# perfom the action (note: _Game__move is necessary due to name mangling)
state._Game__move(from_pos, slide, self.current_player_idx)
# update the current player index
state.current_player_idx = 1 - state.current_player_idx
# append to the list of possible transitions
transitions.append(((from_pos, slide), state, state.get_hashable_state(self.current_player_idx)))
return transitions
def generate_canonical_transitions(self) -> list[tuple[tuple[tuple[int, int], Move], 'InvestigateGame']]:
'''
Generate all possible canonical game transitions that the current player can make.
All transitions that have the same canonical representation of the resulting game
state are not returned.
Args:
None.
Returns:
A list of 3-length tuples of actions, corresponding game states and their
canonical representations is returned.
'''
# define a list of possible transitions
transitions = []
# define a set of canonical states
canonical_states = set()
# for each piece position
for from_pos, slide in POSSIBLE_MOVES:
# check the validity of the action
ok = (
self._board[from_pos[1], from_pos[0]] == -1
or self._board[from_pos[1], from_pos[0]] == self.current_player_idx
)
# if it is a valid action
if ok:
# make a copy of the current game state
state = deepcopy(self)
# perfom the action (note: _Game__move is necessary due to name mangling)
state._Game__move(from_pos, slide, self.current_player_idx)
# get the equivalent canonical state
canonical_state = Symmetry.get_canonical_state(state, self.current_player_idx)
# if it is a new canonical state
if canonical_state not in canonical_states:
# update the current player index
state.current_player_idx = 1 - state.current_player_idx
# append to the list of possible transitions
transitions.append(((from_pos, slide), state, canonical_state))
# appens to the list of canonical states
canonical_states.add(canonical_state)
return transitions
def evaluation_function(self, player_id: int, enhance: bool = False) -> int | float:
"""
Given the current state of the game, a static evaluation is performed
and it is determined if the current position is an advantageous one
for the Chosen Player or the Opponent player.
Values greater than zero indicate that Chosen Player will probably win,
zero indicates a balanced situation and values lower than
zero indicate that Opponent Player will probably win.
The value is calculated as:
(number of complete rows, columns, or diagonals that are still open
for Chosen Player) - (number of complete rows, columns, or diagonals that are
still open for Opponent Player)
Args:
game: the current game state;
player_id: the player's id.
enhance: choose whether to weight a row according to the number of items taken.
Return:
An estimate value of how much a Chosen Player is winning
or losing is returned.
"""
# check if the game is over
value = self.check_winner()
# take the current player id
current_player = player_id
# take the opponent player id
opponent_player = 1 - player_id
# if the current player wins return +inf
if value == current_player:
return float('inf')
# if opponent player wins return -inf
elif value == opponent_player:
return float('-inf')
# turn each player id into a type compatible with the game board
current_player = np.int16(current_player)
opponent_player = np.int16(opponent_player)
# define the current player's value
current_player_value = 0
# define the opponent player's value
opponent_player_value = 0
# get the board
board = self.get_board()
# define which board lines to examine
lines = (
# take all rows
[board[y, :] for y in range(board.shape[0])]
# take all columns
+ [board[:, x] for x in range(board.shape[1])]
# take the principal diagonal
+ [[board[y, y] for y in range(board.shape[0])]]
# take the secondary diagonal
+ [[board[y, -(y + 1)] for y in range(board.shape[0])]]
)
# for each board line
for line in lines:
# count the taken pieces by the current player
current_player_taken = (line == current_player).sum()
# count the taken pieces by the opponent player
opponent_player_taken = (line == opponent_player).sum()
# if all the pieces are neutral or belong to the current player
if opponent_player_taken == 0 and current_player_taken > 0:
# increment the current player's value
current_player_value += current_player_taken if enhance else 1
# if all the pieces are neutral or belong to the opponent player
if current_player_taken == 0 and opponent_player_taken > 0:
# increment the opponent player's value
opponent_player_value += opponent_player_taken if enhance else 1
return current_player_value - opponent_player_value
def play(
self,
player1: 'Player',
player2: 'Player',
max_steps_draw: int,
) -> Literal[-1, 0, 1]:
'''
Play a game between two given players.
Args:
player1: the player who starts the game;
player2: the second player of the game;
max_steps_draw: define the maximum number of steps before
claiming a draw (avoid looping).
Returns:
0 is returned if the first player has won;
1 is returned if the second player has won;
-1 is returned if no one has won.
'''
# print beginning of the game
print('-- BEGINNING OF THE GAME --')
# print the board
self.print()
# define the players
players = [player1, player2]
# set the moving player index
self.current_player_idx = 1
# define a variable to indicate if there is a winner
winner = -1
# define counter to terminate if we are in a loop
counter = 0
# save last played actions
last_actions = [None, None]
# if we can still play
while winner < 0 and counter < max_steps_draw:
# update the current moving player index
self.current_player_idx += 1
self.current_player_idx %= len(players)
# define a variable to check if the chosen move is ok or not
ok = False
# while the chosen move is not ok
while not ok:
# let the current player make a move
from_pos, slide = players[self.current_player_idx].make_move(self)
# check if now it is ok
ok = self._Game__move(from_pos, slide, self.current_player_idx)
# if we play the same action as before
if last_actions[self.current_player_idx] == (from_pos, slide):
# increment the counter
counter += 0.5
# otherwise
else:
# save the new last action
last_actions[self.current_player_idx] = (from_pos, slide)
# reset the counter
counter = 0
# print the move
print(
f'Player {self._player_to_symbol[self.current_player_idx]} chose to move {from_pos} to the {slide.name.lower()}'
)
# print the board
self.print()
# check if there is a winner
winner = self.check_winner()
# print who won
if winner == -1:
print(f"Early Stopping: Draw!")
else:
print(f"Winner: Player {winner}")
# print the end of the game
print('-- END OF THE GAME --')
# return the winner
return winner
if "__main__" == __name__:
import timeit
r = timeit.timeit(
setup="from investigate_game import InvestigateGame, Game; g = InvestigateGame(Game())",
stmt="g.generate_possible_transitions()",
number=1000,
)
print(r)