我正试图确定《奥赛罗》棋盘上哪些圆盘是稳定的(那些在游戏的剩余时间里无法翻转的)。
我读到光盘需要在所有四个方向(水平、垂直和两个对角线)上保持稳定。为了使其在任何方向上都稳定，要么该方向上满是圆盘，这样就不能再在该方向上放置任何圆盘，要么它在板的边缘上，要么它与相同颜色的稳定圆盘相邻。
我理解前两部分，但是否有一个特定的顺序需要评估椎间盘的稳定性，因为可能存在引发稳定性的连锁反应。
简单的方法是迭代，直到没有任何变化。从标记为不稳定的所有光盘开始。然后对制动盘进行检查，看看是否有任何制动盘符合稳定性标准。将符合条件的每个光盘的光盘状态从不稳定更改为稳定。
如果在传球过程中没有一张光盘改变状态，那么你就完了。如果在一次传球结束时，所有的圆盘都被标记为稳定，那么你就完成了。最坏的情况是64次通过，因为每次通过至少有一张光盘必须改变状态
我不认为有明确的算法(捷径)来解决它。
如果你不介意缓存，暴力可以很容易地解决你的问题。
残酷的力量=逐个解决。
起初，我有一块放了一些光盘的板(2+2光盘)，第一个播放器可以在{i1,i2,i3,...}放置黑色光盘。
如果第一播放器选择i1，则第二播放器可以选择位置{i11,i12,i13,...}中的一个来放置白色光盘。
如果第二播放器选择i11，则第一播放器可以选择位置{i111,i112,i113,...}中的一个来放置黑色光盘。
等等
它不多(最多64-4步)。
一批一批地做。。。。把你的电脑放在一边(可能需要几个小时)
最后你会得到一个完整的数据库。
编写代码似乎是一项有趣的任务
看到报告后，您可能会注意到可能会有更好的算法。
您思考光盘现在是否稳定的方式
为了在任何方向上都稳定，任何一个方向都可以是满的的边缘，这样就不能再放置了或者它与相同颜色的稳定盘相邻。
使得设计一种正确可靠的方法来寻找所有光盘的稳定性变得极其困难。相反，让我们从基本的角度来思考什么才有资格使椎间盘稳定，并从那里开始我们的工作。
板中任何正方形周围都有8个方向，有4对相反的方向，即上下方向。为了将一个圆盘标记为稳定，那么对于每对相反的方向，它的两侧都不能有一个空白的正方形，对手可以将其放置在该正方形上以捕获该圆盘只有当每对的至少一个方向碰到板的边界时(通过穿过相同颜色的圆盘)才是这种情况——这就是为什么角圆盘总是稳定的；"受保护"；对于所有4个定向对。同样，边缘盘本身也不稳定，因为它们有一个平行于它们相邻边界的非保护方向对，即使其他3对受到保护。
因此，蛮力方法似乎是遍历板上当前的每个光盘，遍历该光盘的所有定向对，并检查它们是否都至少击中边界一次(当允许遍历相同颜色的光盘时)；如果是这样的话，那么我们会将该光盘标记为稳定光盘。
然而，这可以通过两种主要方式进行优化。
- 请注意，任何光盘都要稳定的唯一方法是任何角落都被占用。因此，如果没有一个角被光盘占据，则自动将稳定光盘的数量返回为0
- 我们还可以注意到，对于朝某个方向行进的相邻圆盘，对于相应的方向对，该颜色的所有圆盘都将受到保护或不受到保护。因此，您可以在仅为一张光盘确定该值后重复使用该值，而不是检查该方向对是否为每个光盘(该颜色)都受到保护
总之，只有当对于每一对方向，该对方向中至少有一个方向能够到达边界(因此对手的圆盘不能"落后")时，圆盘才是稳定的或它已经位于两个相反颜色的圆盘之间。然后，要获得所有稳定的制动盘，首先确定是否有制动盘在拐角处。如果存在，则递归检查该光盘的所有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将定向对标记为的内容，但总体算法将保持不变
在Vaishnavi Sannidhanam和Muthukaruppan Annamalai的《奥赛罗中的启发式分析》中，这些人建议你将光盘分为三类：
- 稳定-不能翻转(分配+1分)
- 不稳定-下一步可以被对手翻转(指定-1分)
- 半稳定-可以翻转，但不能在下一步中翻转(0分)
就像你说的，稳定的光盘很容易找到。然后，你得到所有合法的对手动作，应用它们，并测试新配置中的翻转光盘——那些翻转的光盘将不稳定。一旦你有了稳定和不稳定的集合，半稳定就很容易计算了：)