How can I make this code for finding legal chess moves more efficient?

Question

I am trying to make a chess engine without use of the python chess libraries, so I can learn more about chess programming. Have generated a set of pseudo legal moves (- castling and en passant) and have made a function to generate only the legal moves from the list. my code for this function is here:

def generateLegalMoves(currentPos, colourToMove):
    kingNumber = 1 if colourToMove == "b" else 9
    opponentColour = "w" if colourToMove == "b" else "b"
    legalMoves = []
    myKingSquare = currentPos.index(kingNumber)
    pseudoLegalList = GeneratePsuedoLegalMoves(currentPos, colourToMove)
    for pseudoMove in pseudoLegalList:
        newPos = makeMove(currentPos, pseudoMove[0], pseudoMove[1])
        newPosPsuedoLegalMoves = GeneratePsuedoLegalMoves(newPos, opponentColour)
        isLegal = True
        for j in newPosPsuedoLegalMoves:
            if j[1] == myKingSquare:
                isLegal = False
        if isLegal:
            legalMoves.append(pseudoMove)
    return legalMoves

How can I code a more efficient version?

@ti7 I tested it up to a depth of 3 and it took over 10 seconds. — bbqribs, Aug 27 '23 at 19:44
I would have probably coded this fundamentally different. I would've created a `class Piece` that has a method `def legal_moves` whose only job is to determine legal moves of a piece. I (probably) would've created a `class` for each piece type (pawn, bishop, knight, rook, queen, and king) with its color and current square that it is on and that overrides the `def legal_moves` method. I would have a `class Board` that keeps up with the piece instances. You can then create a Board method `def legal_moves()` that can return a list of pieces and their moves. — Shmack, Aug 27 '23 at 20:05

score 1 · Answer 1 · answered Aug 27 '23 at 20:26

It is not the most efficient implementation. Your code is a little bit hard to read, but here is what I think I understand to be improvable.

First:

for j in newPosPsuedoLegalMoves:
    if j[1] == myKingSquare:
       isLegal = False

If isLegal is set to False once, there is no reason to continue the loop. You can break and move on. Otherwise, you continue to loop for no reason, even though you already know isLegal is False.

Second, you may want to switch to using a Set instead of a List, especially if you are going to go multiple depths. In general, the time complexity when working with Sets (search is O(1)) is much better than working with Lists (search is O(n)). See here: [1] [2] [3]

How can I make this code for finding legal chess moves more efficient?

1 Answers1