7

我正在尝试确定奥赛罗棋盘的哪些圆盘是马厩的（在游戏的其余部分不能翻转）。

我读过光盘需要在所有四个方向（水平、垂直和两个对角线）上都保持稳定。为了让它在任何方向上都保持稳定，要么该方向上可以放满圆盘，不能再放置，要么靠近棋盘边缘，要么靠近同色的稳定圆盘。

我了解前两部分，但是我需要评估光盘稳定性的特定顺序，因为可能存在引起稳定性的连锁反应。我真的很难弄清楚如何确定所有稳定的光盘。

非常感谢任何见解！

4

4 回答 4

3

您现在考虑什么使光盘稳定的方式

为了让它在任何方向上都稳定，要么该方向可以满圆盘，不能再放置，要么靠近棋盘边缘，要么靠近同色的稳定圆盘。

使得设计一种正确可靠的方法来找到所有光盘的稳定性变得极其困难。相反，让我们从基本的角度考虑什么使光盘稳定，并从那里开始工作。

棋盘上任何一个方格周围有8个方向，有4对相反的方向，即向上和向下。为了将圆盘标记为稳定，那么对于每对相反的方向，它的任一侧都不能有对手可以放置以捕获该圆盘的空白方格。只有当每对的至少一个方向碰到棋盘的边界时才会出现这种情况（通过相同颜色的棋子） ——这就是为什么角盘总是稳定的，它们受到“保护”所有 4 个方向对。同样，边缘圆盘本身也不稳定，因为它们有一个未受保护的方向对平行于它们相邻的边界，即使其他 3 对受到保护。

所以蛮力方法似乎是遍历当前在棋盘上的每个圆盘，遍历该圆盘的所有方向对，并检查它们是否都至少击中边界一次（当允许通过相同的颜色）；如果是这种情况，那么我们会将该光盘标记为稳定。

但是，这可以通过两种主要方式进行优化。

  1. 请注意，任何圆盘稳定的唯一方法是任何角落都被占用。因此，如果没有一个角被圆盘占据，则自动将稳定圆盘的数量返回为 0。
  2. 我们还可以注意到，对于沿某个方向的相邻圆盘，对于相应的方向对，该颜色的所有圆盘都将受到保护或不受保护。因此，与其检查该方向对是否针对每个（该颜色的）光盘都受到保护，您可以在仅确定一个光盘后重用该值。

总而言之，只有在每对方向中，至少有一个方向能够到达边界（因此对手的圆盘不能“落后”它）或者它已经位于边界之间时，圆盘才是稳定的两个相反的色盘。然后要获得所有稳定的圆盘，首先确定是否有任何圆盘在角落。如果有，则递归检查该圆盘的所有 4 个方向对，更新与其相邻的圆盘的方向对，确保在适用时重用圆盘的受保护值。然后在最后，对于每个有 4 个方向对受到保护的圆盘，将该圆盘标记为稳定。

计算它的伪代码如下所示：

calculate_protection(board, discs, index):
    for each pair of directions that is marked as None:
        calculate what squares it passes through for that pair of directions
        i.e. either a border, blank square, or disc of opposing color
        (Take note of what it passes through)
        if for both directions in the pair at least one reaches a border
            mark that direction pair as protected
        else if both directions in the pair hits an opposing color disc
            mark that direction pair as protected 
        else
            mark that direction pair as not protected

        for every disc that it passed through for that pair of directions (including an opposing color disc if it reached it):
            if that disc is the same color:
                mark that disc's direction pair as the same value for this one
            
            call calculate_protection for that disc and update discs
    return discs

calculate_stable_discs(board, color):
    create a dictionary of discs where the key is the index of the disc, and it has a dictionary of direction pairs and their values (initially set as None)

    if none of the corners have a disc:
        return None

    call calculate_protection on the first index that has a token

    for every disc in the dictionary keys:
        if all the numbers in the direction pairs are 1:
            increment number of stable discs by 1

    return number of stable discs

请注意，要同时返回半稳定和不稳定光盘的数量，您必须更新calculate_stable_discs字典中的检查内容以及将calculate_protection方向对标记为的内容，但整体算法将保持不变。

于 2021-11-13T03:13:22.163 回答
1

简单的方法是迭代直到没有任何变化。从所有标记为不稳定的光盘开始。然后通过光盘查看是否有任何光盘符合稳定性标准。将满足标准的每个光盘的光盘状态从不稳定更改为稳定。

如果在传递过程中没有任何光盘改变状态，那么你就完成了。如果所有的圆盘在通过结束时都被标记为稳定，那么你就完成了。最坏的情况是 64 次通过，因为至少有一个盘必须在每次通过时改变状态。

于 2017-01-04T05:07:52.767 回答
0

我认为没有明确的算法（捷径）来解决它。

如果您不介意缓存，蛮力可以轻松解决您的问题。

蛮力=逐案解决。

起初，我有一个棋盘，上面放了一些棋子（2+2 棋子），第一个玩家可以将黑棋子放在{i1,i2,i3,...}.

如果第一个玩家选择i1，第二个玩家可以选择一个位置{i11,i12,i13,...}放置白盘。

如果第二个玩家选择i11，第一个玩家可以选择一个位置{i111,i112,i113,...}来放置黑盘。

... 等等。

它并不多（最多64-4步）。

做一个批次！....别管你的电脑（可能是几个小时）。
最后你会得到一个完整的数据库。

编写代码似乎是一项有趣的任务。
看到报告后，您可能会注意到更好算法的可能性。

于 2017-01-04T05:04:37.260 回答
-1

在 Vaishnavi Sannidhanam 和 Muthukaruppan Annamalai 的“奥赛罗启发式分析”中，这些人建议您将光盘分为 3 类：

  • 稳定 - 不能翻转（分配 +1 分）
  • 不稳定 - 下一步可以被对手翻转（分配-1分）
  • 半稳定 - 可以翻转，但不能在下一步移动（分配 0 分）

就像你说的，很容易找到稳定的光盘。然后你得到所有合法的对手动作，应用它们并测试新配置中的翻转光盘 - 那些翻转的光盘将不稳定。一旦你有了稳定和不稳定的集合，半稳定的就很容易计算了:)

于 2018-03-27T15:19:10.217 回答