Efficiency of Recursive Checkers Legal Move Generator

Question

I'm implementing a checkers engine for a scientific experiment. I found out through profiling that this is one of the functions that takes up a lot of time. I'm not looking for an in-depth analysis, because I don't expect you to dive super deep into my code.

Just: are there any obvious inefficiencies here? Like, is it slow to do those starting for loops (dx, dy) just for 2 values each?

def captures(self, (py, px), piece, board, captured=[], start=None):
    """ Return a list of possible capture moves for given piece in a 
        checkers game. 

        :param (py, px): location of piece on the board
        :param piece: piece type (BLACK/WHITE|MAN/KING)
        :param board: the 2D board matrix
        :param captured: list of already-captured pieces (can't jump twice)
        :param start: from where this capture chain started.
        """
    if start is None:
        start = (py, px)
    # Look for capture moves
    for dx in [-1, 1]:
        for dy in [-1, 1]:
            dist = 1 
            while True:
                jx, jy = px + dist * dx, py + dist * dy # Jumped square
                # Check if piece at jx, jy:
                if not (0 <= jx < 8 and 0 <= jy < 8):
                    break
                if board[jy, jx] != EMPTY:
                    tx, ty = px + (dist + 1) * dx, py + (dist + 1) * dy # Target square
                    # Check if it can be captured:
                    if ((0 <= tx < 8 and 0 <= ty < 8) and
                        ((ty, tx) == start or board[ty, tx] == EMPTY) and
                        (jy, jx) not in captured and
                        ((piece & WHITE) and (board[jy, jx] & BLACK) or
                         (piece & BLACK) and (board[jy, jx] & WHITE))
                        ):
                        # Normal pieces cannot continue capturing after reaching last row
                        if not piece & KING and (piece & WHITE and ty == 0 or piece & BLACK and ty == 7):
                            yield (NUMBERING[py, px], NUMBERING[ty, tx])
                        else:
                            for sequence in self.captures((ty, tx), piece, board, captured + [(jy, jx)], start):
                                yield (NUMBERING[py, px],) + sequence
                    break
                else:
                    if piece & MAN:
                        break
                dist += 1
    yield (NUMBERING[py, px],)

Answer 1

A couple of little things that caught my eye:

You could simplify this

dist = 1 
while True:
    jx, jy = px + dist * dx, py + dist * dy 
    dist += 1

to this:

jx, jy = px, py
while True:
    jx += dx
    jy += dy

---

You don't need this range check

if not (0 <= jx < 8 and 0 <= jy < 8):
    break
if board[jy, jx] != EMPTY:

because, assuming board is a dict indexed by tuple, you can just catch KeyError when out of bounds:

try:
    if board[jy, jx] != EMPTY:
        ...
except KeyError:
    break

---

Instead of

((piece & WHITE) and (board[jy, jx] & BLACK) or
 (piece & BLACK) and (board[jy, jx] & WHITE))

you could use board[jy, jx] & opponent if you determine the opponent's color in the beginning of the function:

opponent = BLACK if piece & WHITE else WHITE