forked from bupticybee/elephantfish
-
Notifications
You must be signed in to change notification settings - Fork 0
/
elephantfish.py
459 lines (410 loc) · 20.4 KB
/
elephantfish.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
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
#!/usr/bin/env pypy
# -*- coding: utf-8 -*-
from __future__ import print_function
import re, sys, time
from itertools import count
from collections import namedtuple
piece = { 'P': 44, 'N': 108, 'B': 23, 'R': 233, 'A': 23, 'C': 101, 'K': 2500}
# 子力价值表参考“象眼”
pst = {
"P": (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 9, 9, 9, 11, 13, 11, 9, 9, 9, 0, 0, 0, 0,
0, 0, 0, 19, 24, 34, 42, 44, 42, 34, 24, 19, 0, 0, 0, 0,
0, 0, 0, 19, 24, 32, 37, 37, 37, 32, 24, 19, 0, 0, 0, 0,
0, 0, 0, 19, 23, 27, 29, 30, 29, 27, 23, 19, 0, 0, 0, 0,
0, 0, 0, 14, 18, 20, 27, 29, 27, 20, 18, 14, 0, 0, 0, 0,
0, 0, 0, 7, 0, 13, 0, 16, 0, 13, 0, 7, 0, 0, 0, 0,
0, 0, 0, 7, 0, 7, 0, 15, 0, 7, 0, 7, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 11, 15, 11, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
),
"B":(
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 40, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 38, 0, 0, 40, 43, 40, 0, 0, 38, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 43, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 40, 40, 0, 40, 40, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
),
"N": (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 90, 90, 90, 96, 90, 96, 90, 90, 90, 0, 0, 0, 0,
0, 0, 0, 90, 96,103, 97, 94, 97,103, 96, 90, 0, 0, 0, 0,
0, 0, 0, 92, 98, 99,103, 99,103, 99, 98, 92, 0, 0, 0, 0,
0, 0, 0, 93,108,100,107,100,107,100,108, 93, 0, 0, 0, 0,
0, 0, 0, 90,100, 99,103,104,103, 99,100, 90, 0, 0, 0, 0,
0, 0, 0, 90, 98,101,102,103,102,101, 98, 90, 0, 0, 0, 0,
0, 0, 0, 92, 94, 98, 95, 98, 95, 98, 94, 92, 0, 0, 0, 0,
0, 0, 0, 93, 92, 94, 95, 92, 95, 94, 92, 93, 0, 0, 0, 0,
0, 0, 0, 85, 90, 92, 93, 78, 93, 92, 90, 85, 0, 0, 0, 0,
0, 0, 0, 88, 85, 90, 88, 90, 88, 90, 85, 88, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
),
"R": (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0,206,208,207,213,214,213,207,208,206, 0, 0, 0, 0,
0, 0, 0,206,212,209,216,233,216,209,212,206, 0, 0, 0, 0,
0, 0, 0,206,208,207,214,216,214,207,208,206, 0, 0, 0, 0,
0, 0, 0,206,213,213,216,216,216,213,213,206, 0, 0, 0, 0,
0, 0, 0,208,211,211,214,215,214,211,211,208, 0, 0, 0, 0,
0, 0, 0,208,212,212,214,215,214,212,212,208, 0, 0, 0, 0,
0, 0, 0,204,209,204,212,214,212,204,209,204, 0, 0, 0, 0,
0, 0, 0,198,208,204,212,212,212,204,208,198, 0, 0, 0, 0,
0, 0, 0,200,208,206,212,200,212,206,208,200, 0, 0, 0, 0,
0, 0, 0,194,206,204,212,200,212,204,206,194, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
),
"C": (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0,100,100, 96, 91, 90, 91, 96,100,100, 0, 0, 0, 0,
0, 0, 0, 98, 98, 96, 92, 89, 92, 96, 98, 98, 0, 0, 0, 0,
0, 0, 0, 97, 97, 96, 91, 92, 91, 96, 97, 97, 0, 0, 0, 0,
0, 0, 0, 96, 99, 99, 98,100, 98, 99, 99, 96, 0, 0, 0, 0,
0, 0, 0, 96, 96, 96, 96,100, 96, 96, 96, 96, 0, 0, 0, 0,
0, 0, 0, 95, 96, 99, 96,100, 96, 99, 96, 95, 0, 0, 0, 0,
0, 0, 0, 96, 96, 96, 96, 96, 96, 96, 96, 96, 0, 0, 0, 0,
0, 0, 0, 97, 96,100, 99,101, 99,100, 96, 97, 0, 0, 0, 0,
0, 0, 0, 96, 97, 98, 98, 98, 98, 98, 97, 96, 0, 0, 0, 0,
0, 0, 0, 96, 96, 97, 99, 99, 99, 97, 96, 96, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
}
pst["A"] = pst["B"]
pst["K"] = pst["P"]
pst["K"] = [i + piece["K"] if i > 0 else 0 for i in pst["K"]]
A0, I0, A9, I9 = 12 * 16 + 3,12 * 16 + 11, 3 * 16 + 3, 3 * 16 + 11
initial = (
' \n' # 0 - 9
' \n' # 10 - 19
' \n' # 10 - 19
' rnbakabnr \n' # 20 - 29
' ......... \n' # 40 - 49
' .c.....c. \n' # 40 - 49
' p.p.p.p.p \n' # 30 - 39
' ......... \n' # 50 - 59
' ......... \n' # 70 - 79
' P.P.P.P.P \n' # 80 - 89
' .C.....C. \n' # 70 - 79
' ......... \n' # 70 - 79
' RNBAKABNR \n' # 90 - 99
' \n' # 100 -109
' \n' # 100 -109
' \n' # 110 -119
)
# Lists of possible moves for each piece type.
N, E, S, W = -16, 1, 16, -1
directions = {
'P': (N, W, E),
'N': (N+N+E, E+N+E, E+S+E, S+S+E, S+S+W, W+S+W, W+N+W, N+N+W),
'B': (2 * N + 2 * E, 2 * S + 2 * E, 2 * S + 2 * W, 2 * N + 2 * W),
'R': (N, E, S, W),
'C': (N, E, S, W),
'A': (N+E, S+E, S+W, N+W),
'K': (N, E, S, W)
}
MATE_LOWER = piece['K'] - (2*piece['R'] + 2*piece['N'] + 2*piece['B'] + 2*piece['A'] + 2*piece['C'] + 5*piece['P'])
MATE_UPPER = piece['K'] + (2*piece['R'] + 2*piece['N'] + 2*piece['B'] + 2*piece['A'] + 2*piece['C'] + 5*piece['P'])
# The table size is the maximum number of elements in the transposition table.
TABLE_SIZE = 1e7
# Constants for tuning search
QS_LIMIT = 219
EVAL_ROUGHNESS = 13
DRAW_TEST = True
THINK_TIME = 5
###############################################################################
# Chess logic
###############################################################################
class Position(namedtuple('Position', 'board score')):
""" A state of a chess game
board -- a 256 char representation of the board
score -- the board evaluation
"""
def gen_moves(self):
# For each of our pieces, iterate through each possible 'ray' of moves,
# as defined in the 'directions' map. The rays are broken e.g. by
# captures or immediately in case of pieces such as knights.
for i, p in enumerate(self.board):
if p == 'K':
for scanpos in range(i - 16,A9,-16):
if self.board[scanpos] == 'k':
yield (i,scanpos)
elif self.board[scanpos] != '.':
break
if not p.isupper(): continue
if p == 'C':
for d in directions[p]:
cfoot = 0
for j in count(i+d, d):
q = self.board[j]
if q.isspace():break
if cfoot == 0 and q == '.':yield (i,j)
elif cfoot == 0 and q != '.':cfoot += 1
elif cfoot == 1 and q.islower(): yield (i,j);break
elif cfoot == 1 and q.isupper(): break;
continue
for d in directions[p]:
for j in count(i+d, d):
q = self.board[j]
# Stay inside the board, and off friendly pieces
if q.isspace() or q.isupper(): break
# 过河的卒/兵才能横着走
if p == 'P' and d in (E, W) and i > 128: break
# j & 15 等价于 j % 16但是更快
elif p in ('A','K') and (j < 160 or j & 15 > 8 or j & 15 < 6): break
elif p == 'B' and j < 128: break
elif p == 'N':
n_diff_x = (j - i) & 15
if n_diff_x == 14 or n_diff_x == 2:
if self.board[i + (1 if n_diff_x == 2 else -1)] != '.': break
else:
if j > i and self.board[i + 16] != '.': break
elif j < i and self.board[i - 16] != '.': break
elif p == 'B' and self.board[i + d // 2] != '.':break
# Move it
yield (i, j)
# Stop crawlers from sliding, and sliding after captures
if p in 'PNBAK' or q.islower(): break
def rotate(self):
''' Rotates the board, preserving enpassant '''
return Position(
self.board[-2::-1].swapcase() + " ", -self.score)
def nullmove(self):
''' Like rotate, but clears ep and kp '''
return self.rotate()
def move(self, move):
i, j = move
p, q = self.board[i], self.board[j]
put = lambda board, i, p: board[:i] + p + board[i+1:]
# Copy variables and reset ep and kp
board = self.board
score = self.score + self.value(move)
# Actual move
board = put(board, j, board[i])
board = put(board, i, '.')
return Position(board, score).rotate()
def value(self, move):
i, j = move
p, q = self.board[i], self.board[j]
# Actual move
score = pst[p][j] - pst[p][i]
# Capture
if q.islower():
score += pst[q.upper()][255-j-1]
return score
###############################################################################
# Search logic
###############################################################################
# lower <= s(pos) <= upper
Entry = namedtuple('Entry', 'lower upper')
class Searcher:
def __init__(self):
self.tp_score = {}
self.tp_move = {}
self.history = set()
self.nodes = 0
def bound(self, pos, gamma, depth, root=True):
""" returns r where
s(pos) <= r < gamma if gamma > s(pos)
gamma <= r <= s(pos) if gamma <= s(pos)"""
self.nodes += 1
# Depth <= 0 is QSearch. Here any position is searched as deeply as is needed for
# calmness, and from this point on there is no difference in behaviour depending on
# depth, so so there is no reason to keep different depths in the transposition table.
depth = max(depth, 0)
# Sunfish is a king-capture engine, so we should always check if we
# still have a king. Notice since this is the only termination check,
# the remaining code has to be comfortable with being mated, stalemated
# or able to capture the opponent king.
if pos.score <= -MATE_LOWER:
return -MATE_UPPER
# We detect 3-fold captures by comparing against previously
# _actually played_ positions.
# Note that we need to do this before we look in the table, as the
# position may have been previously reached with a different score.
# This is what prevents a search instability.
# FIXME: This is not true, since other positions will be affected by
# the new values for all the drawn positions.
if DRAW_TEST:
if not root and pos in self.history:
return 0
# Look in the table if we have already searched this position before.
# We also need to be sure, that the stored search was over the same
# nodes as the current search.
entry = self.tp_score.get((pos, depth, root), Entry(-MATE_UPPER, MATE_UPPER))
if entry.lower >= gamma and (not root or self.tp_move.get(pos) is not None):
return entry.lower
if entry.upper < gamma:
return entry.upper
# Here extensions may be added
# Such as 'if in_check: depth += 1'
# Generator of moves to search in order.
# This allows us to define the moves, but only calculate them if needed.
def moves():
# First try not moving at all. We only do this if there is at least one major
# piece left on the board, since otherwise zugzwangs are too dangerous.
if depth > 0 and not root and any(c in pos.board for c in 'RNC'):
yield None, -self.bound(pos.nullmove(), 1-gamma, depth-3, root=False)
# For QSearch we have a different kind of null-move, namely we can just stop
# and not capture anythign else.
if depth == 0:
yield None, pos.score
# Then killer move. We search it twice, but the tp will fix things for us.
# Note, we don't have to check for legality, since we've already done it
# before. Also note that in QS the killer must be a capture, otherwise we
# will be non deterministic.
killer = self.tp_move.get(pos)
if killer and (depth > 0 or pos.value(killer) >= QS_LIMIT):
yield killer, -self.bound(pos.move(killer), 1-gamma, depth-1, root=False)
# Then all the other moves
for move in sorted(pos.gen_moves(), key=pos.value, reverse=True):
#for val, move in sorted(((pos.value(move), move) for move in pos.gen_moves()), reverse=True):
# If depth == 0 we only try moves with high intrinsic score (captures and
# promotions). Otherwise we do all moves.
if depth > 0 or pos.value(move) >= QS_LIMIT:
yield move, -self.bound(pos.move(move), 1-gamma, depth-1, root=False)
# Run through the moves, shortcutting when possible
best = -MATE_UPPER
for move, score in moves():
best = max(best, score)
if best >= gamma:
# Clear before setting, so we always have a value
if len(self.tp_move) > TABLE_SIZE: self.tp_move.clear()
# Save the move for pv construction and killer heuristic
self.tp_move[pos] = move
break
# Stalemate checking is a bit tricky: Say we failed low, because
# we can't (legally) move and so the (real) score is -infty.
# At the next depth we are allowed to just return r, -infty <= r < gamma,
# which is normally fine.
# However, what if gamma = -10 and we don't have any legal moves?
# Then the score is actaully a draw and we should fail high!
# Thus, if best < gamma and best < 0 we need to double check what we are doing.
# This doesn't prevent sunfish from making a move that results in stalemate,
# but only if depth == 1, so that's probably fair enough.
# (Btw, at depth 1 we can also mate without realizing.)
if best < gamma and best < 0 and depth > 0:
is_dead = lambda pos: any(pos.value(m) >= MATE_LOWER for m in pos.gen_moves())
if all(is_dead(pos.move(m)) for m in pos.gen_moves()):
in_check = is_dead(pos.nullmove())
best = -MATE_UPPER if in_check else 0
# Clear before setting, so we always have a value
if len(self.tp_score) > TABLE_SIZE: self.tp_score.clear()
# Table part 2
if best >= gamma:
self.tp_score[pos, depth, root] = Entry(best, entry.upper)
if best < gamma:
self.tp_score[pos, depth, root] = Entry(entry.lower, best)
return best
def search(self, pos, history=()):
""" Iterative deepening MTD-bi search """
self.nodes = 0
if DRAW_TEST:
self.history = set(history)
# print('# Clearing table due to new history')
self.tp_score.clear()
# In finished games, we could potentially go far enough to cause a recursion
# limit exception. Hence we bound the ply.
for depth in range(1, 1000):
# The inner loop is a binary search on the score of the position.
# Inv: lower <= score <= upper
# 'while lower != upper' would work, but play tests show a margin of 20 plays
# better.
lower, upper = -MATE_UPPER, MATE_UPPER
while lower < upper - EVAL_ROUGHNESS:
gamma = (lower+upper+1)//2
score = self.bound(pos, gamma, depth)
if score >= gamma:
lower = score
if score < gamma:
upper = score
# We want to make sure the move to play hasn't been kicked out of the table,
# So we make another call that must always fail high and thus produce a move.
self.bound(pos, lower, depth)
# If the game hasn't finished we can retrieve our move from the
# transposition table.
yield depth, self.tp_move.get(pos), self.tp_score.get((pos, depth, True),Entry(-MATE_UPPER, MATE_UPPER)).lower
###############################################################################
# User interface
###############################################################################
# Python 2 compatability
if sys.version_info[0] == 2:
input = raw_input
def parse(c):
fil, rank = ord(c[0]) - ord('a'), int(c[1])
return A0 + fil - 16*rank
def render(i):
rank, fil = divmod(i - A0, 16)
return chr(fil + ord('a')) + str(-rank)
def print_pos(pos):
print()
uni_pieces = {'R':'车', 'N':'马', 'B':'相', 'A':'仕', 'K':'帅', 'P':'兵', 'C':'炮',
'r':'俥', 'n':'傌', 'b':'象', 'a':'士', 'k':'将', 'p':'卒', 'c':'砲', '.':'．'}
for i, row in enumerate(pos.board.split()):
print(' ', 9-i, ''.join(uni_pieces.get(p, p) for p in row))
print(' ａｂｃｄｅｆｇｈｉ\n\n')
def main():
hist = [Position(initial, 0)]
searcher = Searcher()
while True:
print_pos(hist[-1])
if hist[-1].score <= -MATE_LOWER:
print("You lost")
break
# We query the user until she enters a (pseudo) legal move.
move = None
while move not in hist[-1].gen_moves():
match = re.match('([a-i][0-9])'*2, input('Your move: '))
if match:
move = parse(match.group(1)), parse(match.group(2))
else:
# Inform the user when invalid input (e.g. "help") is entered
print("Please enter a move like h2e2")
hist.append(hist[-1].move(move))
# After our move we rotate the board and print it again.
# This allows us to see the effect of our move.
print_pos(hist[-1].rotate())
if hist[-1].score <= -MATE_LOWER:
print("You won")
break
# Fire up the engine to look for a move.
start = time.time()
for _depth, move, score in searcher.search(hist[-1], hist):
if time.time() - start > THINK_TIME:
break
if score == MATE_UPPER:
print("Checkmate!")
# The black player moves from a rotated position, so we have to
# 'back rotate' the move before printing it.
print("Think depth: {} My move: {}".format(_depth, render(255-move[0] - 1) + render(255-move[1]-1)))
hist.append(hist[-1].move(move))
if __name__ == '__main__':
main()