I modified Sunfish to play Simplified Chess. It probably is not very strong at it, but it will make a suitable sparring partner.
Code: Select all
#!/usr/bin/env pypy
# -*- coding: utf-8 -*-
from __future__ import print_function
import sys
from itertools import count
from collections import Counter, OrderedDict, namedtuple
# The table size is the maximum number of elements in the transposition table.
TABLE_SIZE = 1e6
# This constant controls how much time we spend on looking for optimal moves.
NODES_SEARCHED = 1e4
# Win value must be greater than 8*queen + 2*(rook+knight+bishop)
# King value is set to twice this value such that if the opponent is
# 8 queens up, but we got the king, we still exceed WIN_VALUE.
WIN_VALUE = 30000
# Our board is represented as a 120 character string. The padding allows for
# fast detection of moves that don't stay within the board.
A1, H1, A8, H8 = 91, 98, 21, 28
initial = (
' \n' # 0 - 9
' \n' # 10 - 19
' rnbqkbnr\n' # 20 - 29
' ........\n' # 30 - 39
' pppppppp\n' # 40 - 49
' ........\n' # 50 - 59
' ........\n' # 60 - 69
' PPPPPPPP\n' # 70 - 79
' ........\n' # 80 - 89
' RNBQKBNR\n' # 90 - 99
' \n' # 100 -109
' ' # 110 -119
)
###############################################################################
# Move and evaluation tables
###############################################################################
N, E, S, W = -10, 1, 10, -1
directions = {
'P': (N, N+W, N+E),
'N': (2*N+E, N+2*E, S+2*E, 2*S+E, 2*S+W, S+2*W, N+2*W, 2*N+W),
'B': (N+E, S+E, S+W, N+W),
'R': (N, E, S, W),
'Q': (N, E, S, W, N+E, S+E, S+W, N+W),
'K': (N, E, S, W, N+E, S+E, S+W, N+W)
}
pst = {
'P': (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 198, 198, 198, 198, 198, 198, 198, 198, 0,
0, 178, 198, 198, 198, 198, 198, 198, 178, 0,
0, 178, 198, 198, 198, 198, 198, 198, 178, 0,
0, 178, 198, 208, 218, 218, 208, 198, 178, 0,
0, 178, 198, 218, 238, 238, 218, 198, 178, 0,
0, 178, 198, 208, 218, 218, 208, 198, 178, 0,
0, 178, 198, 198, 198, 198, 198, 198, 178, 0,
0, 198, 198, 198, 198, 198, 198, 198, 198, 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, 797, 824, 817, 808, 808, 817, 824, 797, 0,
0, 814, 841, 834, 825, 825, 834, 841, 814, 0,
0, 818, 845, 838, 829, 829, 838, 845, 818, 0,
0, 824, 851, 844, 835, 835, 844, 851, 824, 0,
0, 827, 854, 847, 838, 838, 847, 854, 827, 0,
0, 826, 853, 846, 837, 837, 846, 853, 826, 0,
0, 817, 844, 837, 828, 828, 837, 844, 817, 0,
0, 792, 819, 812, 803, 803, 812, 819, 792, 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, 627, 762, 786, 798, 798, 786, 762, 627, 0,
0, 763, 798, 822, 834, 834, 822, 798, 763, 0,
0, 817, 852, 876, 888, 888, 876, 852, 817, 0,
0, 797, 832, 856, 868, 868, 856, 832, 797, 0,
0, 799, 834, 858, 870, 870, 858, 834, 799, 0,
0, 758, 793, 817, 829, 829, 817, 793, 758, 0,
0, 739, 774, 798, 810, 810, 798, 774, 739, 0,
0, 683, 718, 742, 754, 754, 742, 718, 683, 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, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 1258, 1263, 1268, 1272, 1272, 1268, 1263, 1258, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
'Q': (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 2529, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
'K': (0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 6098, 6132, 6073, 6025, 6025, 6073, 6132, 6098, 0,
0, 6119, 6153, 6094, 6046, 6046, 6094, 6153, 6119, 0,
0, 6146, 6180, 6121, 6073, 6073, 6121, 6180, 6146, 0,
0, 6173, 6207, 6148, 6100, 6100, 6148, 6207, 6173, 0,
0, 6196, 6230, 6171, 6123, 6123, 6171, 6230, 6196, 0,
0, 6224, 6258, 6199, 6151, 6151, 6199, 6258, 6224, 0,
0, 6287, 6321, 6262, 6214, 6214, 6262, 6321, 6287, 0,
0, 6298, 6332, 6273, 6225, 6225, 6273, 6332, 6298, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
}
###############################################################################
# Chess logic
###############################################################################
class Position(namedtuple('Position', 'board score')):
""" A state of a chess game
board -- a 120 char representation of the board
score -- the board evaluation
wc -- the castling rights
bc -- the opponent castling rights
ep - the en passant square
kp - the king passant square
"""
def genMoves(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 not p.isupper(): continue
for d in directions[p]:
for j in count(i+d, d):
q = self.board[j]
# Stay inside the board
if self.board[j].isspace(): break
# No friendly captures
if q.isupper(): break
# Special pawn stuff
if p == 'P' and d in (N+W, N+E) and q == '.': break
if p == 'P' and d == N and q != '.': break
# Move it
yield (i, j)
# Stop crawlers from sliding
if p in ('P', 'N', 'K'): break
# No sliding after captures
if q.islower(): break
def rotate(self):
return Position(
self.board[::-1].swapcase(), -self.score)
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, '.')
# Special pawn stuff
if p == 'P':
if A8 <= j <= H8:
score += WIN_VALUE
# We rotate the returned position, so it's ready for the next player
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()][j]
# Special pawn stuff
if p == 'P':
if A8 <= j <= H8:
score += WIN_VALUE
return score
Entry = namedtuple('Entry', 'depth score gamma move')
tp = OrderedDict()
###############################################################################
# Search logic
###############################################################################
nodes = 0
def bound(pos, gamma, depth):
""" returns s(pos) <= r < gamma if s(pos) < gamma
returns s(pos) >= r >= gamma if s(pos) >= gamma """
global nodes; nodes += 1
# Look in the table if we have already searched this position before.
# We use the table value if it was done with at least as deep a search
# as ours, and the gamma value is compatible.
entry = tp.get(pos)
if entry is not None and entry.depth >= depth and (
entry.score < entry.gamma and entry.score < gamma or
entry.score >= entry.gamma and entry.score >= gamma):
return entry.score
# Stop searching if we have won/lost.
if abs(pos.score) >= WIN_VALUE:
return pos.score
# Null move. Is also used for stalemate checking
nullscore = -bound(pos.rotate(), 1-gamma, depth-3) if depth > 0 else pos.score
if nullscore >= gamma:
return nullscore
# We generate all possible, pseudo legal moves and order them to provoke
# cuts. At the next level of the tree we are going to minimize the score.
# This can be shown equal to maximizing the negative score, with a slightly
# adjusted gamma value.
best, bmove = -3*WIN_VALUE, None
for move in sorted(pos.genMoves(), key=pos.value, reverse=True):
# We check captures with the value function, as it also contains ep and kp
if depth <= 0 and pos.value(move) < 150:
break
score = -bound(pos.move(move), 1-gamma, depth-1)
if score > best:
best = score
bmove = move
if score >= gamma:
break
# If there are no captures, or just not any good ones, stand pat
if depth <= 0 and best < nullscore:
return nullscore
# Check for stalemate. If best move loses king, but not doing anything
# would save us. Not at all a perfect check.
if depth > 0 and best <= -WIN_VALUE is None and nullscore > -WIN_VALUE:
best = 0
# We save the found move together with the score, so we can retrieve it in
# the play loop. We also trim the transposition table in FILO order.
# We prefer fail-high moves, as they are the ones we can build our pv from.
if entry is None or depth >= entry.depth and best >= gamma:
tp[pos] = Entry(depth, best, gamma, bmove)
if len(tp) > TABLE_SIZE:
tp.pop()
return best
def search(pos, maxn=NODES_SEARCHED):
""" Iterative deepening MTD-bi search """
global nodes; nodes = 0
# We limit the depth to some constant, so we don't get a stack overflow in
# the end game.
for depth in range(1, 99):
# The inner loop is a binary search on the score of the position.
# Inv: lower <= score <= upper
# However this may be broken by values from the transposition table,
# as they don't have the same concept of p(score). Hence we just use
# 'lower < upper - margin' as the loop condition.
lower, upper = -3*WIN_VALUE, 3*WIN_VALUE
while lower < upper - 3:
gamma = (lower+upper+1)//2
score = bound(pos, gamma, depth)
if score >= gamma:
lower = score
if score < gamma:
upper = score
# print("Searched %d nodes. Depth %d. Score %d(%d/%d)" % (nodes, depth, score, lower, upper))
# We stop deepening if the global N counter shows we have spent too
# long, or if we have already won the game.
if nodes >= maxn or abs(score) >= WIN_VALUE:
break
# If the game hasn't finished we can retrieve our move from the
# transposition table.
entry = tp.get(pos)
if entry is not None:
return entry.move, score
return None, score
###############################################################################
# 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]) - 1
return A1 + fil - 10*rank
def render(i):
rank, fil = divmod(i - A1, 10)
return chr(fil + ord('a')) + str(-rank + 1)
def main():
pos = Position(initial, 0)
while True:
# We add some spaces to the board before we print it.
# That makes it more readable and pleasing.
print(' '.join(pos.board))
# We query the user until she enters a legal move.
move = None
while move not in pos.genMoves():
crdn = input("Your move: ")
move = parse(crdn[0:2]), parse(crdn[2:4])
pos = pos.move(move)
# After our move we rotate the board and print it again.
# This allows us to see the effect of our move.
print(' '.join(pos.rotate().board))
# Fire up the engine to look for a move.
move, score = search(pos)
if score <= -WIN_VALUE:
print("You won")
break
if score >= WIN_VALUE:
print("You lost")
break
# The black player moves from a rotated position, so we have to
# 'back rotate' the move before printing it.
print("My move:", render(119-move[0]) + render(119-move[1]))
pos = pos.move(move)
if __name__ == '__main__':
main()