Algorithm for describing chess positions
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 &gt;= 2 else single_name
        return "%s: %s\n" % (label, ", ".join(pieces[marker]))
    return ''

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


This achieves 2 additional optimizations:


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