-
Notifications
You must be signed in to change notification settings - Fork 0
/
game.py
428 lines (363 loc) · 12.1 KB
/
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
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
### GAME LOGIC ###
# Grid is defined as bits, e.g. 0000 0011 0010 0001 = 0 8 4 2
# i.e. 2 to the power of bits
import random, collections
from concurrent.futures import ThreadPoolExecutor
ROW_MASK = 0xFFFF
COL_MASK = 0x000F_000F_000F_000F
SCORE_MONOTONICITY_POWER = 4
SCORE_MONOTONICITY_WEIGHT = 47
SCORE_SUM_POWER = 3.5
SCORE_SUM_WEIGHT = 11
SCORE_MERGES_WEIGHT = 700
SCORE_EMPTY_WEIGHT = 270
SCORE_LOST_PENALTY = 200000
w = [SCORE_MONOTONICITY_WEIGHT, SCORE_SUM_WEIGHT, SCORE_MERGES_WEIGHT, SCORE_EMPTY_WEIGHT]
# Weights from calc_cma.py
weights = [0.98786212, 1.04484233, 1.03834599, 1.09304891]
SCORE_MONOTONICITY_WEIGHT, SCORE_SUM_WEIGHT, SCORE_MERGES_WEIGHT, SCORE_EMPTY_WEIGHT = list(map(lambda a,b:a*b, w, weights))
### HELPER FUNCTIONS ###
def transpose(x):
''' transpose the whole grid '''
a1 = x & 0xF0F00F0FF0F00F0F
a2 = x & 0x0000F0F00000F0F0
a3 = x & 0x0F0F00000F0F0000
a = a1 | (a2 << 12) | (a3 >> 12)
b1 = a & 0xFF00FF0000FF00FF
b2 = a & 0x00FF00FF00000000
b3 = a & 0x00000000FF00FF00
return b1 | (b2 >> 24) | (b3 << 24)
def reverse_row(row):
''' reverse a row in grid '''
return (row >> 12) | ((row >> 4) & 0x00F0) | ((row << 4) & 0x0F00) | (row << 12) & 0xffff
def flatten(bitrow):
''' flatten a row of bits to right '''
# check if bits are all 0000
x = 0
pastrow = bitrow
while x < 3:
cell = bitrow & (0b1111 << x*4)
if cell == 0:
# get first x*4 bits
firstbits = bitrow & ((2**(x*4))-1)
# set first x*4 bits to 0
newrow = bitrow & ~firstbits
# shift bits to the right
newrow >>= 4
# combine with first bits
bitrow = newrow | firstbits
if bitrow == pastrow:
x += 1
pastrow = bitrow
return bitrow
def combine(bitrow):
''' combine row of bits to right '''
bitrow = flatten(bitrow)
game_score = 0
# pairwise comparison
for x in range(1, 4):
prev = bitrow & (0b1111 << (x-1)*4)
curr = bitrow & (0b1111 << x*4)
if prev >> (x-1)*4 == curr >> x*4 and prev != 0:
bitrow += 0b0001 << (x-1)*4
# null curr bits
bitrow &= ~(0b1111 << x*4)
game_score += (2 ** (curr >> x*4)) *2
return flatten(bitrow), game_score
def grid_to_arr(grid, arr):
''' convert grid to array '''
for x in range(4):
row = grid & (0b1111_1111_1111_1111 << x*16)
for y in range(4):
cell = (row & (0b1111 << y*4)) >> y*4
if cell:
cell = 2 ** (cell)
arr[x][y] = cell
return arr
def count_distinct_tiles(grid):
''' count distinct tiles in grid '''
bitset = 0
while (grid):
bitset |= 1<<(grid & 0xf)
grid >>= 4
bitset >>= 1
count = 0
while (bitset):
bitset &= bitset - 1
count+=1
return count
### LOOP TO CREATE BITBOARD ###
l_combine_d = [0]* 65536
r_combine_d = [0]* 65536
empty_d = [0]* 65536
score_d = [0]* 65536
game_score_d = [0]* 65536
for x in range(65536):
l_combine_d[x], game_score_d[x] = combine(x)
r_combine_d[x] = reverse_row(combine(reverse_row(x))[0])
nums = [x & 0xf, (x >> 4) & 0xf, (x >> 8) & 0xf, (x >> 12) & 0xf]
sum = 0
empty = 0
merges = 0
prev = 0
counter = 0
for i in range(4):
rank = nums[i]
sum += rank ** SCORE_SUM_POWER
if (rank == 0):
empty+=1
else:
if (prev == rank):
counter+=1
elif (counter > 0):
merges += 1 + counter
counter = 0
prev = rank
if (counter > 0):
merges += 1 + counter
# calculate monotonicity
mono_left = mono_right = 0
for y in range(1,4):
if nums[y-1] > nums[y]:
mono_left += nums[y-1]**SCORE_MONOTONICITY_POWER - \
nums[y]**SCORE_MONOTONICITY_POWER
else:
mono_right += nums[y]**SCORE_MONOTONICITY_POWER - \
nums[y-1]**SCORE_MONOTONICITY_POWER
empty_d[x] = empty
### int comparison is much faster than float: https://hg.python.org/cpython/file/ea33b61cac74/Objects/floatobject.c#l285
score_d[x] = int((SCORE_LOST_PENALTY + \
empty * SCORE_EMPTY_WEIGHT + \
merges * SCORE_MERGES_WEIGHT - \
SCORE_MONOTONICITY_WEIGHT * min(mono_left, mono_right) - \
sum * SCORE_SUM_WEIGHT) * 100)
print('Tables generated!')
### GAME FUNCTIONS ###
def count_empty(grid):
''' count empty tiles in grid '''
res = empty_d[grid & 0xffff]
res += empty_d[(grid >> 16) & 0xffff]
res += empty_d[(grid >> 32) & 0xffff]
res += empty_d[(grid >> 48) & 0xffff]
return res
def add_random(grid):
''' add random tile to grid '''
i = random.randint(1, 10)
if i == 1:
tile = 2
else:
tile = 1
if grid == 0:
empty = 16
else:
empty = count_empty(grid)
index = random.randint(0, empty-1)
added = False
i = j = 0
while not added:
if (grid & (0xf << j*4)) == 0:
if i == index:
grid |= tile << j*4
added = True
else:
i += 1
j += 1
return grid
def left(grid):
''' move grid left '''
newgrid = l_combine_d[grid & 0xffff]
newgrid |= l_combine_d[(grid >> 16) & 0xffff] << 16
newgrid |= l_combine_d[(grid >> 32) & 0xffff] << 32
newgrid |= l_combine_d[(grid >> 48) & 0xffff] << 48
return newgrid
def right(grid):
''' move grid right '''
newgrid = r_combine_d[grid & 0xffff]
newgrid |= r_combine_d[(grid >> 16) & 0xffff] << 16
newgrid |= r_combine_d[(grid >> 32) & 0xffff] << 32
newgrid |= r_combine_d[(grid >> 48) & 0xffff] << 48
return newgrid
def up(grid):
''' move grid up '''
grid = transpose(grid)
newgrid = l_combine_d[grid & 0xffff]
newgrid |= l_combine_d[(grid >> 16) & 0xffff] << 16
newgrid |= l_combine_d[(grid >> 32) & 0xffff] << 32
newgrid |= l_combine_d[(grid >> 48) & 0xffff] << 48
return transpose(newgrid)
def down(grid):
''' move grid down '''
grid = transpose(grid)
newgrid = r_combine_d[grid & 0xffff]
newgrid |= r_combine_d[(grid >> 16) & 0xffff] << 16
newgrid |= r_combine_d[(grid >> 32) & 0xffff] << 32
newgrid |= r_combine_d[(grid >> 48) & 0xffff] << 48
return transpose(newgrid)
def score_hori(grid):
''' score horizontal moves '''
score = game_score_d[grid & 0xffff]
score += game_score_d[(grid >> 16) & 0xffff]
score += game_score_d[(grid >> 32) & 0xffff]
score += game_score_d[(grid >> 48) & 0xffff]
return score
def score_vert(grid):
''' score vertical moves '''
grid = transpose(grid)
score = game_score_d[grid & 0xffff]
score += game_score_d[(grid >> 16) & 0xffff]
score += game_score_d[(grid >> 32) & 0xffff]
score += game_score_d[(grid >> 48) & 0xffff]
return score
def check_survive(grid):
''' check if game is lost '''
if grid == left(grid) == right(grid) == up(grid) == down(grid):
return False
return True
def print_grid(grid):
''' print grid '''
for x in range(4):
for y in range(4):
cell = grid & 0xf
if cell:
cell = 2 ** (cell)
grid >>= 4
print(cell, end=' ')
print()
print()
def format_grid(grid):
''' format grid '''
res = []
for x in range(4):
t = []
for y in range(4):
cell = grid & 0xf
if cell:
cell = 2 ** (cell)
else:
cell = ' '
grid >>= 4
t.append(cell)
res.append(t)
return res
### AI PORTION ###
### AI CONSTANTS ###
CUR_DEPTH_MIN = 3
CUR_DEPTH_MAX = 15
CACHE_DEPTH_LIMIT = 15
DEPTH_MIN = 3
DEPTH_MAX = 6
DEPTH_DISCOUNT = 5
DEPTH_ARR = [DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, DEPTH_MIN, \
DEPTH_MIN+1, DEPTH_MIN+1, \
DEPTH_MIN+1, DEPTH_MIN+2, \
DEPTH_MIN+2, \
DEPTH_MIN+2][::-1]
MULTITHREAD = True
trans_table = collections.defaultdict()
move_ls = [left, right, up, down]
### AI FUNCTIONS ###
def score_grid(grid):
''' Score the grid '''
score = score_d[grid & 0xffff] \
+ score_d[(grid >> 16) & 0xffff] \
+ score_d[(grid >> 32) & 0xffff] \
+ score_d[(grid >> 48) & 0xffff]
grid = transpose(grid)
score += score_d[grid & 0xffff] \
+ score_d[(grid >> 16) & 0xffff] \
+ score_d[(grid >> 32) & 0xffff] \
+ score_d[(grid >> 48) & 0xffff]
return score
def score_tilechoose_node(trans_table, curdepth, depth_limit, grid, cprob):
''' Score the tile choose node '''
minprob = 1 / (1 << (2 * curdepth + 4))
if cprob < minprob or curdepth >= depth_limit:
if grid in trans_table:
if trans_table[grid][0] >= curdepth: # 0 is depth
return trans_table[grid][1] # 1 is heuristic score
return score_grid(grid)
if grid in trans_table:
if trans_table[grid][0] >= curdepth: # 0 is depth
return trans_table[grid][1] # 1 is heuristic score
empty_count = count_empty(grid)
cprob /= empty_count
tmp = grid
res= 0
tile = 1
while tile & 0xffff_ffff_ffff_ffff:
if (tmp & 0xf) == 0:
res += score_move_node(trans_table, curdepth, depth_limit, grid | tile, cprob * 0.9) * 0.9
res += score_move_node(trans_table, curdepth, depth_limit, grid | (tile << 1), cprob * 0.1) * 0.1
tmp >>= 4
tile <<= 4
res /= empty_count
trans_table[grid] = (curdepth, res)
return res
def score_move_node(trans_table, curdepth, depth_limit, grid, cprob):
''' Score the move node '''
curdepth += 1
lg = left(grid)
rg = right(grid)
ug = up(grid)
dg = down(grid)
best = 0
if grid != lg:
ev = score_tilechoose_node(trans_table, curdepth, depth_limit, lg, cprob)
if ev > best:
best = ev
if grid != rg:
ev = score_tilechoose_node(trans_table, curdepth, depth_limit, rg, cprob)
if ev > best:
best = ev
if grid != ug:
ev = score_tilechoose_node(trans_table, curdepth, depth_limit, ug, cprob)
if ev > best:
best = ev
if grid != dg:
ev = score_tilechoose_node(trans_table, curdepth, depth_limit, dg, cprob)
if ev > best:
best = ev
curdepth -= 1
return best
def score_toplevel_move(args):
''' Score the top level move '''
grid, move, trans_table, depth_limit = args
if move == 0:
lg = left(grid)
if grid != lg:
return score_tilechoose_node(trans_table, 0, depth_limit, lg, 1)
elif move == 1:
rg = right(grid)
if grid != rg:
return score_tilechoose_node(trans_table, 0, depth_limit, rg, 1)
elif move == 2:
ug = up(grid)
if grid != ug:
return score_tilechoose_node(trans_table, 0, depth_limit, ug, 1)
elif move == 3:
dg = down(grid)
if grid != dg:
return score_tilechoose_node(trans_table, 0, depth_limit, dg, 1)
return 0
def find_best_move(grid):
''' Find the best move '''
depth_limit = min(DEPTH_MAX, max(DEPTH_MIN, count_distinct_tiles(grid) - DEPTH_DISCOUNT))
if MULTITHREAD:
with ThreadPoolExecutor(max_workers=4) as executor:
scores = list(executor.map(score_toplevel_move, ((grid, move, trans_table, depth_limit) for move in range(4))))
else:
ls = ((grid, move, trans_table, depth_limit) for move in range(4))
scores = map(score_toplevel_move, ls)
bestmove, bestscore = max(enumerate(scores), key=lambda x:x[1])
if bestscore == 0:
return -1
return bestmove
def n_find_best_move(grid):
''' Find the best move (for cma) '''
depth_limit = 2
with ThreadPoolExecutor(max_workers=4) as executor:
scores = list(executor.map(score_toplevel_move, ((grid, move, trans_table, depth_limit) for move in range(4))))
bestmove, bestscore = max(enumerate(scores), key=lambda x:x[1])
if bestscore == 0:
return -1
return bestmove