奥赛罗稳定盘的测定

Question

我正试图确定奥赛罗板的哪一盘是稳定的(那些不能在剩下的比赛中翻转)。

我读过，光盘需要在所有四个方向上稳定(水平，垂直和两个对角线)。为了使它在任何方向上都是稳定的，要么这个方向充满了圆盘，这样就不能再把它放置在那个方向上，要么它位于板的边缘，或者它毗邻一个稳定的相同颜色的盘。

我理解前两部分，但是否有一个特定的顺序，我需要评估光盘的稳定性，因为可能有一个链式反应诱导稳定性。

Answer 1

简单的方法是迭代，直到什么都没有改变。从标记为不稳定的所有光盘开始。然后通过盘片，看看它们是否符合稳定性标准。对于每个符合标准的磁盘，将磁盘状态从不稳定状态更改为稳定状态。

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

Answer 2

我不认为有明确的算法(捷径)来解决它。

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

蛮力=逐案解决。

首先，我有一个板与一些光盘放置(2+2光盘)，第一个播放器可以放置黑色光盘在{i1,i2,i3,...}。

如果第一播放器选择i1，则第二播放器可以选择位置{i11,i12,i13,...}中的一个放置白色光盘。

如果第二播放器选择i11，则第一播放机可以选择位置{i111,i112,i113,...}中的一个放置黑盘。

..。诸若此类。

这并不多(最多64-4步)。

一批一批！.离你的电脑远点(可能几个小时)。

最后，您将得到一个完整的数据库。

这似乎是一个有趣的任务编码。

在您看到报告之后，您可能会注意到有可能采用更好的算法。

Answer 3

你在想什么才能让光盘现在稳定下来

为了使它在任何方向上都是稳定的，要么该方向可以充满圆盘，这样就不能再放置它，要么它可以靠近板的边缘，或者它与同一颜色的稳定盘相邻。

这使得设计一个正确和可靠的方法来寻找所有光盘的稳定性是非常困难的。相反，让我们从一个基本的角度来考虑什么才能使光盘稳定，然后从那里开始工作。

在棋盘的任意正方形周围有8个方向，有4对相反的方向，即上下方向。为了使光盘被标记为稳定的，那么对于每一对相反方向的，不能在任何一方都有一个空白的正方形，而对手可能会将其放置在那里以捕获该光盘。只有当每对至少有一个方向击中板的边框(通过相同颜色的盘)时才是这样--这就是为什么角盘总是稳定的，它们对所有4个方向对都是“受保护的”。同样，边缘盘本身是不稳定的，因为它们有一个与它们相邻的边界平行的无保护方向对，即使其他3对受到保护。

所以，蛮力法似乎是遍历当前在板上的每一张光盘，遍历该光盘的所有方向对，并检查它们是否至少击中边界一次(允许穿过相同颜色的光盘时)；如果是这样的话，我们就会将该光盘标记为稳定的。

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

1. 请注意，任何光盘都要稳定的唯一方式是，如果任何角落被占用。因此，如果没有一个角被一个光盘占用，自动返回稳定的光盘数为0。
2. 我们还可以注意到，对于向某个方向移动的相邻光盘，对于对应的方向对，该颜色的所有光盘要么受到保护，要么不受保护。因此，与其检查该方向对是否对每个磁盘(该颜色)都受到保护，您还可以在确定一个方向对后重用该值。

总之，一个光盘是稳定的，只有当每一对方向中，至少有一个方向能够到达边界(因此，对手的光盘不能“后面”it) 或，它已经在两个对立的彩色光盘之间。然后，要得到所有稳定的光盘，首先确定是否有任何光盘在角落。如果存在，则递归检查该光盘的所有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标记方向对的内容，但是总体算法将保持不变。