Efficiency of Recursive Checkers Legal Move Generator 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 &lt;= jx &lt; 8 and 0 &lt;= jy &lt; 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 &lt;= tx &lt; 8 and 0 &lt;= ty &lt; 8) and
                        ((ty, tx) == start or board[ty, tx] == EMPTY) and
                        (jy, jx) not in captured and
                        ((piece &amp; WHITE) and (board[jy, jx] &amp; BLACK) or
                         (piece &amp; BLACK) and (board[jy, jx] &amp; WHITE))
                        ):
                        # Normal pieces cannot continue capturing after reaching last row
                        if not piece &amp; KING and (piece &amp; WHITE and ty == 0 or piece &amp; 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 &amp; MAN:
                        break
                dist += 1
    yield (NUMBERING[py, px],)
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 &lt;= jx &lt; 8 and 0 &lt;= jy &lt; 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 &amp; WHITE) and (board[jy, jx] &amp; BLACK) or
 (piece &amp; BLACK) and (board[jy, jx] &amp; WHITE))


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

opponent = BLACK if piece &amp; WHITE else WHITE