Algorithm for describing chess positions

I have an interesting problem with my chess application. The application reads PGN files, and at any time while viewing a game from the file, the function below, when called, iterates over the chessboard, gets the square names for each piece, and then constructs a string containing the description of which piece is where.

The function runs without errors, however it has a slight issue with respect to its performance: When the chess board is full, or close to full with 32 pieces, it runs pretty fast. Once the pieces go off the board and there remains a handful of pieces to describe, the function returns with a delay of around half a second. I have not tested the function with performance tools, but one can feel there is something strange going on: given the length of the function and its algorithm (please don't swear reading it), I can't understand why it will run faster when the board is full and slower when it's close to empty.

Can anyone spot what causes this issue? In addition, what can I try to optimize it?

def pos_text():
global node
#Dictionary of piece symbols to store their location on the board
d = {"K": [], "Q": [], "R": [], "B": [], "N": [], "P": [], "k": [], "q": [], "r":   [], "b": [], "n": [], "p": []}
piece_letters = "KkQqRrNnBbPp"
#Iterates over the board and assigns square names to the individual piece symbols in d
for x in range(64):
sq = str(node.board().piece_at(x))
if sq in piece_letters:
d[sq].append(chess.SQUARE_NAMES[x])
# now makes a string containing the description of pieces:
pos = "White pieces:\nKing: %s\n" % d["K"]
if d["Q"]:
pos += "Queens: %s\n" % ", ".join(d["Q"]) if len(d["Q"]) >= 2 else "Queen: %s\n" % d["Q"]
if d["R"]:
pos += "Rooks: %s\n" % ", ".join(d["R"]) if len(d["R"]) >= 2 else "Rook: %s\n" % d["R"]
if d["B"]:
pos += "Bishops: %s\n" % ", ".join(d["B"]) if len(d["B"]) >= 2 else "Bishop: %s\n" % d["B"]
if d["N"]:
pos += "Knights: %s\n" % ", ".join(d["N"]) if len(d["N"]) >= 2 else "Knight: %s\n" % d["N"]
if d["P"]:
pos += "Pawns: %s\n" % ", ".join(d["P"]) if len(d["P"]) >= 2 else "Pawn: %s\n" % d["P"]
pos += "Black pieces:\nKing: %s\n" % d["k"]
if d["q"]:
pos += "Queens: %s\n" % ", ".join(d["q"]) if len(d["q"]) >= 2 else "Queen: %s\n" % d["q"]
if d["r"]:
pos += "Rooks: %s\n" % ", ".join(d["r"]) if len(d["r"]) >= 2 else "Rook: %s\n" % d["r"]
if d["b"]:
pos += "Bishops: %s\n" % ", ".join(d["b"]) if len(d["b"]) >= 2 else "Bishop: %s\n" % d["b"]
if d["n"]:
pos += "Knights: %s\n" % ", ".join(d["n"]) if len(d["n"]) >= 2 else "Knight: %s\n" % d["n"]
if d["p"]:
pos += "Pawns: %s\n" % ", ".join(d["p"]) if len(d["p"]) >= 2 else "Pawn: %s\n" % d["p"]
return pos
• In general, loading global is pretty expensive. What happens if you make the board an argument to pos_text? Nov 14 '14 at 1:32

The slowness when having fewer pieces

Having fewer pieces on the board will make this slower:

piece_letters = "KkQqRrNnBbPp"
for x in range(64):
sq = str(node.board().piece_at(x))
if sq in piece_letters:
d[sq].append(chess.SQUARE_NAMES[x])

Consider these two (invalid) extremes:

• When the board is full of K, the evaluation of sq in piece_letters will terminate with True after checking the first letter
• When the board is empty, the evaluation of sq in piece_letters will have to check each letter in piece_letters until it can terminate with False

In the rest of the code, there are more evaluations performed in the full case compared to the empty case, but not enough to outweigh the effects of the sq in piece_letters check, due to the length of piece_letters.

Changing piece_letters to this would help:

piece_letters = frozenset("KkQqRrNnBbPp")

This way the evaluation of sq in piece_letters won't have to step through all letters.

But actually, since you already have a dictionary with the possible pieces in d, you don't need piece_letters at all, you can use simply this:

for x in range(64):
sq = str(node.board().piece_at(x))
if sq in d:
d[sq].append(chess.SQUARE_NAMES[x])

This is also better for another reason: if d doesn't have a predefined [] value for the sq key, then the original code wouldn't work anyway. When you write it this way, it's clear that d[sq] exists, and will not raise a KeyError, so it's more coherent and readable.

Actually the piece_letters string can be useful to initialize d itself:

piece_letters = "KkQqRrNnBbPp"
d = dict((c, []) for c in piece_letters)

And d is a very poor name. pieces would be better.

Other optimizations

Avoid using global variables if possible. It would be better to pass node.board() to the method if possible. Actually it seems the method should belong to the board itself, and I would rename it to print_board.

The printing of the pieces is very repetitive. It would be better to extract their logic to a helper function, for example:

def format_piece(marker, single_name, plural_name):
num = len(pieces[marker])
if num:
label = plural_name if num >= 2 else single_name
return "%s: %s\n" % (label, ", ".join(pieces[marker]))
return ''

pos = "White pieces:\nKing: %s\n" % d["K"]
pos += format_piece('Q', 'Queen', 'Queens')
pos += format_piece('R', 'Rook', 'Rooks')
# ...

1. Count the length of each pieces[marker] only once
2. Avoid duplication in the formatting, by setting label

I have now changed the function as follows and it works as I want. It is indeed costly to refer a global variable 64 times. It turns out iterating over piece_letters in the first version was not the problem either though it was redundant. But when copying the global name node with a local one it runs like a breeze.

def get_pos():
n = node.board()
d = {"K": [], "Q": [], "R": [], "B": [], "N": [], "P": [], "k": [], "q": [], "r": [], "b": [], "n": [], "p": []}
for x in range(64):
sq = str(n.piece_at(x))
if sq != 'None':
d[sq].append(chess.SQUARE_NAMES[x])
pos = "White pieces:\nKing: %s\n" % d["K"]
pos += format_pos(d["Q"], "Queen", "Queens")
pos += format_pos(d["R"], "Rook", "Rooks")
pos += format_pos(d["B"], "Bishop", "Bishops")
pos += format_pos(d["N"], "Knight", "Knights")
pos += format_pos(d["P"], "Pawn", "Pawns")
pos += "Black pieces:\nKing: %s\n" % d["k"]
pos += format_pos(d["q"], "Queen", "Queens")
pos += format_pos(d["r"], "Rook", "Rooks")
pos += format_pos(d["b"], "Bishop", "Bishops")
pos += format_pos(d["n"], "Knight", "Knights")
pos += format_pos(d["p"], "Pawn", "Pawns")
return pos

def format_pos(lst, sing, pl):
num = len(lst)
if num:
label = U"%s: %s\n" % (pl, ", ".join(l)) if num >= 2 else U"%s: %s\n" % (sing, lst)
return label
else:
return ""