AL123 人文社科会员免费专区文学 2024-12-01

AI游戏开发和深度学习进阶_【日】伊庭齐志_AZW3_MOBI_EPUB_PDF_电子书（无页码）_【日】伊庭齐志

内容节选

3.5解开国际象棋谜题マーティン·ガードナー（著）、岩沢宏和·上原隆平（訳）、ガードナーの予期せぬ絞首刑（完全版マーティン·ガードナー数学ゲーム全集第4巻）、日本評論社、2017. マーチン·ガードナー（著）、赤摂也·赤冬子（訳）、マーチン·ガードナーの数学ゲーム2（別冊日経サイエンス182）、2011. 在3.2节中，我们介绍了皇后问题。许多类似的棋盘约束问题也很有名。让我们看看下面的一些问题。正如你通过解决方案所看到的，在搜索约束满足问题时，尽可能地利用先验知识来限制搜索空间非常重要。否则，计算量将是巨大的，并且无法进行有效的搜索。 3.5.1 尽可能放置多个棋子这个棋子在纵横方向上，一回合走多少步都可以。在8×8的棋盘上，根据以下条件放置棋子。这个谜题的目的是找到尽可能放置多个棋子的方式。如图3.25a所示的例子，尽可能放置多个车，并让它们彼此之间无法攻击。图3.25 国际象棋谜题该问题与兵的移动方式无关。无论彼此的攻击方式如何，只要其放置满足条件即可。 1）在同一条线上不放置3个以上的前提下，尽可能放置多个兵。除了垂直、水平和对角线外，还有不同方向的直线（最多可放置16个）。与将棋的桂马的动作相同，但不仅可以向前移动，还可以向右、向左和向后移动。 2）尽可能在彼此之间无法攻击的前提下，放置多个骑士（最多可以放置32个）。在对角线上，一回合可以走任意步数。 3）尽可能放置多个主教（最多能放置14个，有36种不同的放置方式）。垂直、水平、对角线，各个方向每回合能走一格。 4）尽可能放置多个国王。图3.25b显示了放置兵的一种答案（16个兵）的示例。我们知道在中央的格子里放置2个兵的解决方案只有一种。这个问题可以通过约束相关问题的纵向搜索来解决。但是，如果没有进行高效搜索，则无法完成计算。为防止冗余搜索，对节点进行扩展和分支时删除不再需要搜索的节点（即剪枝）。进行剪枝的条件是：当前放置的棋子数+接下来可以放置棋子位置的数量＜到目前为止找到的最大棋子数（3.9）因为即使在剩下的位置上都放置棋子也不会更新目前的最大值。（证明）以2×4的区块对棋盘进行分割（见图3.26）。在2×4的区块中最多只能放置4个骑士。也就是说，在棋盘上面2×4的区块有8块，所以可以放置骑士的最大数是32。对骑士问题进行搜索时，获得如图3.25c所示的解决方案。你可以看到，除了对称的情况以外，只有一种可能。在这里很容易证明可以放置骑士的数量最多为32 。当骑士所在的行号和列号的总和为奇数（偶数）时，骑士可以对行号和列号的总和为偶数（奇数）的位置进行攻击。因此，可以在行号和列号之和为偶数（奇数）的每个格子上放置一个骑士。这个时候，骑士的数量就是64/2=32。从中可以知道，在国际象棋棋盘上可以放置32个骑士。图3.26 国际象棋棋盘（有关骑士放置数量的证明）类似地，若在同一条线上不可以放置3个以上的兵，则最多可以放置的兵的数量为16。可以放置的主教的最大数为14。主教的搜索结果如图3.27所示（36种可能的其中一部分）。图3.27 国际象棋棋盘（主教）让我们用高明的方法对有关国王的场景进行搜索。国王在2×2的区块种不可能存在2个以上。也就是说，放置数量的最大值小于16。将8×8的棋盘用2×2的区块分割成16块的情况只有一种。接下来，再对这16块区块一个个放置棋子就能进行高效的搜索。图3.28展示了其中一部分解。图3.28 国际象棋棋盘（国王） 3.5.2 尽可能攻击多个区域接下来，我们来思考一下关于皇后的问题。・图3.29显示了如何在6×6的国际象棋棋盘上放置3个皇后并攻击所有空的格子。除图3.29的方法外让我们寻找其他放置方式。但是，对称和镜像的放置方法被认为是相同的方式。・将4个皇后排列在7×7的国际象棋棋盘上，以攻击所有空的格子，并找到各种方法防止皇后间互相攻击。・在8×8的国际象棋棋盘上找到用4个皇后和1个骑士攻击所有空的格子的方法。・找到在8×8的国际象棋棋盘上放置8个皇后的所有方法，以最大限度地减少不能攻击的格子的数量的放置方式。图3.29 国际象棋谜题（第一个皇后问题）在给皇后问题进行搜索时，从左上角开始依次搜索不受任何攻击的格子。找到正确的格子后，将皇后放置在可攻击该格子的位置。可以通过记住直到到达当前状态前皇后在哪个位置进行了搜索来减少搜索次数。图3.30a显示了一个7×7问题的答案。图3.30b显示了皇后和骑士问题的答案。除了对称的情况外，只有一种放置方法。图3.30 国际象棋谜题（第二个皇后问题）在最后一个问题中，我们知道无法攻击的格子数有11个以上。因此，应该至少有2行6列（或2列6行）作为不存在皇后的区块。也就是说，可以通过限定皇后的放置区块来进行探索。搜索的结果是，不能受......