java - 国际象棋 : Getting All Legal Chess Moves

Question

我正在制作游戏国际象棋，几乎得到了所有东西，但只有一件事:我需要制作它，这样玩家就不可能将棋子移动到检查中。我在解决这个问题时遇到了麻烦。

我现在用伪代码生成有效移动的是:getMoveLocations 类(我将位置定义为国际象棋中的那些方 block 之一):如果这个位置在边界内，并且这个位置的棋子是敌人的，并且模拟的移动不会导致棋盘被检查，那么将这个位置添加到棋子可以移动到的可能位置。

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

不幸的是，这是无限循环开始的地方；为了收集所有敌人的电影位置，每个敌人可能的移动位置需要确保其移动不会导致其受到检查。为了确保没有敌人的位置在检查中，它必须收集所有盟友的潜在移动位置等。

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

Answer 1

有一种更有效的方法来确定一方是否处于被检查状态:您只需从国王向外扫描，看看是否找到可以攻击它的棋子。例如，从国王的位置，检查是否有敌方主教沿着对角线等。您根本不需要生成移动列表，因此不需要递归。这是一些伪代码:

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，而是使用简单的数组表示。这使得合法移动生成(没有中间的伪合法移动)变得有点困难，因为它需要非常快速地生成攻击图来确定固定的棋子。如果你雄心勃勃，这是一种可能性。

作为附加说明，我对这里的其他答案有些失望。而且我什至不会向任何想要编写好的移动生成器的人推荐我自己的答案(它仅适用于那些不熟悉国际象棋编程的人)。这是一个已经过彻底检查并具有众所周知的解决方案的主题，但正在引发原创想法。这当然没有错，但为什么要重新发明轮子，甚至更糟呢？查看well established methods of move generation .