-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithms.py
180 lines (156 loc) · 6.24 KB
/
algorithms.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
# a file to simply implement some key algorithms in a procedural fashion
from collections import namedtuple
import logging
import math
class SolutionContext:
def __init__(self
, board=None
, alpha=None
, beta=None
, depth=None
, timeout=None
, previous_move=None
, fn_fitness=None
, fn_terminate=None):
self.beta = beta
self.alpha = alpha
self.previous_move = previous_move
self.board = board
self.depth = depth
self.timeout = timeout
self.fn_fitness = fn_fitness
self.fn_terminate = fn_terminate
class Solution:
def __init__(self
, move=None
, board=None
, is_max=None):
self.board = board
self.is_max = is_max
self.move = move
MinMove = namedtuple('MinMove', ['is_max', 'x', 'y', 'tile', 'prob'])
MaxMove = namedtuple('MaxMove', ['is_max', 'direction'])
def minimax(context: SolutionContext, solution: Solution):
log = logging.getLogger('PlayerAI')
log.info("minimax")
if context.fn_terminate(context, solution):
return context.fn_fitness(context, solution)
moves = solution.board.get_moves(not solution.is_max)
if solution.is_max:
results = []
for m in moves:
new_context, new_solution = create_call_vars(m, context, solution)
results.append(minimax(context=new_context,
solution=new_solution))
return max(results)
else:
results = []
for m in moves:
new_context, new_solution = create_call_vars(m, context, solution)
r = minimax(context=new_context, solution=new_solution)
r2 = r * new_solution.move.prob
results.append(r2)
return min(results)
def minimax_with_ab_pruning(context: SolutionContext, solution: Solution):
log = logging.getLogger('PlayerAI')
if context.fn_terminate(context, solution):
return context.fn_fitness(context, solution)
moves = solution.board.get_moves(solution.is_max)
if solution.is_max:
best_result = -float("inf")
for m in moves:
new_context, new_solution = create_call_vars(m, context, solution)
result = minimax_with_ab_pruning(context=new_context, solution=new_solution)
best_result = max(result, best_result)
context.alpha = max(best_result, context.alpha)
if context.alpha <= context.beta:
log.debug("alpha cut")
break
return best_result
else:
# PROBLEM:
# - MIN is not playing to minimise the eventual score of MAX, it is generating tiles at random
# The result from MIN should be the average score achieved given the move by MAX.
# So, how is beta calculated to allow the alpha-beta pruning algorithm to be implemented?
# KNOWN:
# - MIN should return the average across all possible moves
# - MAX can maximise the alpha based on that
# - MIN will be called on across several possible moves by MAX
# IDEA:
# - Just set beta to the average?
#
best_result = float("inf")
for m in moves:
new_context, new_solution = create_call_vars(m, context, solution)
result = minimax_with_ab_pruning(context=new_context, solution=new_solution)
best_result = min(result, best_result)
context.beta = min(best_result, context.beta)
if context.alpha <= context.beta:
log.debug("beta cut")
break
return best_result
# acc = 0.0
# for m in moves:
# new_context, new_solution = create_call_vars(m, context, solution)
# r = minimax_with_ab_pruning(context=new_context, solution=new_solution)
# acc += r * new_solution.move.prob
# avg_score = acc / (len(moves) / 2)
# context.beta = min(context.beta, avg_score)
# return avg_score
def create_call_vars(move, context, solution):
new_context = SolutionContext(board=solution.board,
depth=context.depth + 1,
timeout=context.timeout,
previous_move=move,
fn_fitness=context.fn_fitness,
fn_terminate=context.fn_terminate)
new_solution = Solution(move=move,
board=new_context.board.move(move),
is_max=not solution.is_max)
return new_context, new_solution
def prairie_fire(g):
def set_fire_to(B, x, y, t, code):
# if off edge
if x < 0 or x > 3 or y < 0 or y > 3:
return False
# if done already
if B[x, y] == code:
return False
# if no match
if B[x, y] != t:
return False
B[x, y] = code
set_fire_to(B, x - 1, y, t, code)
set_fire_to(B, x + 1, y, t, code)
set_fire_to(B, x, y - 1, t, code)
set_fire_to(B, x, y + 1, t, code)
return True
B = g.clone()
result = dict()
tiles = [2 ** l if l > 0 else 0 for l in range(0, 17)]
for t in tiles:
result[t] = []
for t in tiles:
code = -1
for x in range(0, 4):
for y in range(0, 4):
lit = set_fire_to(B, x, y, t, code)
if lit:
code -= 1
# now gather the stats
for c in range(-1, code - 1, -1):
stats = {'count': 0, 'minx':1000, 'maxx': -1, 'miny':5, 'maxy': -1, 'adjacent_tiles': []}
for x in range(0, 4):
for y in range(0, 4):
if B[x,y] == c:
stats['count'] += 1
stats['minx'] = min(stats['minx'], x)
stats['maxx'] = max(stats['maxx'], x)
stats['miny'] = min(stats['miny'], y)
stats['maxy'] = max(stats['maxy'], y)
B[x,y] = 0
if stats['count'] > 0:
result[t].append(stats)
return result
def sigmoid(x):
return 1 / (1 + math.exp(-x))