如何使这段寻找合法国际象棋走法的代码更加高效？

Question

我正在尝试制作一个不使用Python国际象棋库的国际象棋引擎，这样我就可以了解更多有关国际象棋编程的知识。 生成了一组伪合法动作（- 王位易位和过路），并创建了一个仅从列表中生成合法动作的函数。 我的这个函数的代码在这里：

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

如何编写更高效的版本？

Answer 1

这不是最有效的实施方式。你的代码有点难以阅读，但我认为我理解的是可以改进的。

第一：

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

如果

isLegal

设置为

False

一次，就没有理由继续循环。您可以

break

继续前进。否则，即使您已经知道

isLegal

是

False

，您也会无缘无故地继续循环。

其次，您可能想改用

Set

而不是

List

，尤其是当您要进入多个深度时。一般来说，使用

Sets

（搜索为 O(1)）的时间复杂度比使用

Lists

（搜索为 O(n)）要好得多。请参阅此处：[1] [2] [3]