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()
This version, instead of putting the pawns on the third rank, shortens the board to seven ranks. The victory condition is king capture, but without castling the king is somewhat exposed.