-
Notifications
You must be signed in to change notification settings - Fork 0
/
RndMinMaxAgent.py
183 lines (159 loc) · 6.29 KB
/
RndMinMaxAgent.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
#
# Copyright 2017 Carsten Friedrich ([email protected]). All rights reserved
#
from Board import Board, EMPTY, GameResult
from Player import Player
import random
class RndMinMaxAgent(Player):
"""
A computer player implementing the Min Max algorithm.
This player behaves non-deterministically. That is, for a given board position the player if more than one move
with the maximum evaluation exist, the player will randomly choose one of those moves.
Already evaluated board positions are cached for efficiency.
"""
WIN_VALUE = 1
DRAW_VALUE = 0
LOSS_VALUE = -1
def __init__(self):
"""
Getting ready for playing tic tac toe.
"""
self.side = None
"""
Cache to store the evaluation of board positions that we have already looked at.
This avoids repeating a lot of work as we do not look at all the possible continuation from this position again.
"""
# `cache` now contains a list of best moves
self.cache = {}
super().__init__()
def new_game(self, side: int):
"""
Setting the side for the game to come. Nothing else to do.
:param side: The side this player will be playing
"""
if self.side != side:
self.side = side
self.cache = {}
def final_result(self, result: GameResult):
"""
Does nothing.
:param result: The result of the game that just finished
:return:
"""
pass
def _min(self, board: Board) -> int:
"""
Evaluate the board position `board` from the Minimizing player's point of view.
Notable changes with the `MinMaxAgent` are indicated with `#$`
:param board: The board position to evaluate
:return: returns the best Move in this situation. Returns -1 for best move if the game has already
finished
"""
#
# First we check if we have seen this board position before, and if yes just return a random choice from the cached values
#
board_hash = board.hash_value()
if board_hash in self.cache:
#$
return random.choice(self.cache[board_hash])
#
# If the game has already finished we return. Otherwise we look at possible continuations
#
winner = board.who_won()
if winner == self.side:
#$ Adds an entry
best_moves = {(self.WIN_VALUE, -1)}
elif winner == board.other_side(self.side):
#$
best_moves = {(self.LOSS_VALUE, -1)}
else:
#
# Init the min value as well as action. Min value is set to DRAW as this value will pass through in case of a draw
#
min_value = self.DRAW_VALUE
action = -1
best_moves = {(min_value, action)}
# cf `MinMaxAgent.py`
# for index in [i for i, e in enumerate(board.state) if board.state[i] == EMPTY]:
for index in [i for i, e in enumerate(board.state) if e == EMPTY]:
b = Board(board.state)
b.move(index, board.other_side(self.side))
res, _ = self._max(b)
if res < min_value or action == -1:
min_value = res
action = index
#$
best_moves = {(min_value, action)}
elif res == min_value:
action = index
#$
best_moves.add((min_value, action))
best_moves = tuple(best_moves)
self.cache[board_hash] = best_moves
# Choose randomly among the equally best moves
return random.choice(best_moves)
def _max(self, board: Board) -> int:
"""
Evaluate the board position `board` from the Maximizing player's point of view.
:param board: The board position to evaluate
:return: Best Move in this situation. Returns -1 for best move if the game has already finished
"""
#
# First we check if we have seen this board position before, and if yes just return a random choice
# from the cached values
#
board_hash = board.hash_value()
if board_hash in self.cache:
#$
return random.choice(self.cache[board_hash])
#
# If the game has already finished we return. Otherwise we look at possible continuations
#
winner = board.who_won()
if winner == self.side:
#$
best_moves = {(self.WIN_VALUE, -1)}
elif winner == board.other_side(self.side):
#$
best_moves = {(self.LOSS_VALUE, -1)}
else:
#
# Init the min value as well as action. Min value is set to DRAW as this value will pass through in case
# of a draw
#
max_value = self.DRAW_VALUE
action = -1
best_moves = {(max_value, action)}
# cf `MinMaxAgent.py`
# for index in [i for i, e in enumerate(board.state) if board.state[i] == EMPTY]:
for index in [i for i, e in enumerate(board.state) if e == EMPTY]:
b = Board(board.state)
b.move(index, self.side)
res, _ = self._min(b)
if res > max_value or action == -1:
max_value = res
action = index
#$
best_moves = {(max_value, action)}
elif res == max_value:
action = index
#$
best_moves.add((max_value, action))
best_moves = tuple(best_moves)
self.cache[board_hash] = best_moves
# Choose randomly among the equally best moves
return random.choice(best_moves)
def move(self, board: Board) -> (GameResult, bool):
"""
Making a move according to the MinMax algorithm. If more than one best move exist, chooses amongst them
randomly.
:param board: The board to make a move on
:return: The result of the move
"""
score, action = self._max(board)
_, res, finished = board.move(action, self.side)
return res, finished
def name(self):
return "Random MinMax"
def copy(self):
return RndMinMaxAgent()