国际象棋：获得所有合法的国际象棋动作

Question

我正在下国际象棋，除了一件事，我几乎得到了所有的东西：我需要使棋手不可能将棋子移动到棋盘上。我很难解决这个问题。

我现在用伪html" target="_blank">代码生成的有效移动是：类getMoveLocations（我定义了一个位置为国际象棋中的一个方块）：如果这个位置在边界内，这个位置的棋子是敌人的棋子，并且模拟的移动不会导致棋盘被检查，然后将该位置添加到工件可以移动到的可能位置。

问题是我如何检查棋盘是否“在检查中”。在我的代码中，它通过收集所有敌人的移动位置，并查看是否有任何敌人的移动位置与国王的位置重叠，将棋盘视为处于“检查”状态。

不幸的是，这就是无限循环的起点；为了收集所有敌人的电影位置，每个敌人可能的移动位置需要确保其移动不会导致其受到控制。为了确保没有敌人的位置受到控制，它必须收集所有盟军的潜在移动位置，等等。。

我对如何得到一个有效的算法感到困惑。虽然我的代码“理论上”有逻辑意义，但它无法实现。我感兴趣的是A）一种更有效的方法来实现一种检查所有合法移动的方法，或者B）一种修复这个无限循环的方法

Answer 1

如果一个招式允许一个敌方棋子对你的国王进行攻击，那么这个招式会让你的队伍处于被控制状态（因此是不允许的）。

请注意，约束自己和约束对手是不同的——当你约束对手时，他们有一个轮到你回应的机会。如果你能控制住自己，你就没有机会做出回应。他们将能够俘获你的国王，这将永远是正确的举动，无论他们处于多么糟糕的地位，或者即使他们将“受到控制”——他们已经赢了！那之后什么都没有了。

所以，要想知道采取行动是否会让你受到控制，就要看看敌人是否能向你的国王发起攻击。就这样。你没有递归地解决未来的检查或类似的问题——如果他们现在可以攻击国王，那就是无效的。

Answer 2

修改getMoveLocations过程以接受一个标志，该标志指示是否担心进入检查状态。例如，如果一个棋子被钉住了，它仍然可以移动以捕获对方的国王。如果该标志设置为忽略检查风险，则跳过检查测试将中断递归。

或者（等价地）编写一个单独的方法来生成移动，忽略移动到检查中的问题。将该步骤作为“检查电路板”测试的一部分。

Answer 3

有一种更有效的方法来确定一方是否受到了控制：你只需从国王那里向外扫描，看看是否能找到可以攻击它的碎片。例如，从国王的位置，检查是否有任何敌人主教沿着对角线，等等。你根本不需要生成移动列表，因此不需要递归。以下是一些伪代码：

function leftInCheck(board, sideToCheck) {

   // one of the four rays for bishop/queen attacks
   d := 0
   while (king rank + d, king file + d) is on the board
      piece := board[king rank + d][king file + d]
      if piece is an enemy bishop or queen
         return true
      if piece is not an empty square   // a piece blocks any potential
         break                          // attack behind it so we can stop
      d := d + 1

   // do this for all the other forms of attack
   ...

   return false
}

如您所见，有一些代码重复，但您可以缩短它。我让它保持原样，所以很容易理解。您可以通过生成伪合法移动来生成合法移动，就像您现在所做的那样，制作每一个，并省略那些让您检查上面子程序的移动。这有额外的优势，自然通过。这里有一些伪代码：

function legalMoves(board, sideToMove) {
   moveList := empty
   for each move in pseudoLegalMoves()
      make(move)
      if not leftInCheck(board, sideToMove)
         moveList.add(move)
      unmake(move) // you may not need this
   return moveList
}

对于城堡，你仍然需要检查国王和车之间的广场上是否有攻击。幸运的是，这很容易，因为您可以扩展上面的子例程来处理国王以外的正方形。

我假设您没有使用位板或0x88，而是使用一个简单的数组表示。这使得实现合法移动生成（没有中间的伪合法移动）有点困难，因为它需要非常快地生成攻击地图来确定固定的部分。如果你雄心勃勃，这是可能的。

另外，我对这里的其他答案有些失望。我甚至不会向任何想写一个好的移动生成器的人推荐我自己的答案（它只适用于那些不熟悉国际象棋编程的人）。这是一个经过彻底审查并有众所周知的解决方案的主题，但正在引发原创想法。当然这没什么错，但是为什么要重新发明轮子，甚至更糟呢？研究移动生成的成熟方法。