国际象棋:获得所有法律国际象棋动作

Question

我正在制作游戏棋,除了一件事之外我几乎得到了所有东西:我需要做到这一点,以便玩家不可能将棋子移动到支票上.我在如何解决这个问题上遇到了麻烦.

我现在在伪代码中生成有效移动的是:类getMoveLocations(我将一个位置定义为国际象棋中的那些方格之一):如果此位置在边界内,并且此位置的棋子是敌人的棋子,AND模拟的移动不会导致板被检查,然后将此位置添加到块可以移动到的可能位置.

这个问题是我如何检查棋盘是否"正在检查".在我的代码中,它通过收集所有敌人的移动位置,并查看是否有任何敌人的移动位置与国王的位置重叠来认为棋盘处于"检查"状态.

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

我很难理解如何获得一个有效的算法.虽然我的代码"理论上"具有逻辑意义,但它无法实现.我感兴趣的是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,而是使用简单的数组表示.这使得实现合法移动生成(没有中间伪合法移动)有点困难,因为它需要非常快速地生成攻击图以确定固定块.如果你雄心勃勃,这是可能的.

作为补充说明,我对这里的其他答案感到有些失望.而且我甚至不会向想要编写好的移动生成器的人推荐我自己的答案(它仅适用于那些不熟悉国际象棋编程的人).这是一个经过彻底检查并具有众所周知的解决方案的主题,但却引出了原创性的想法.当然这没有什么不妥,但为什么重新发明轮子,更糟糕呢？研究完善的移动生成方法.

Answer 2

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

或者（等效地）编写一个单独的方法来生成移动，忽略移动到检查的问题。使用该过程作为“使电路板受到检查”测试的一部分。