扫雷AI的实现要点

2025新年已至,自己用C++实现了一个简单的扫雷AI,功能是对任意给定的局面,判断出尽可能多的格子的状态(有雷或者无雷).当确定某个格子无雷时,由布雷器返回该格子里的数字,然后继续猜测,直到所有可猜的格子都被翻开为止.

下面是一个简单的例子.比如设地雷的实际分布图如下所示:E为非雷格,X为地雷格.整个地图大小为10*10,有10个地雷

     1   2   3   4   5   6   7   8   9  10
1  | E | E | E | E | E | E | E | E | E | E |
2  | E | E | E | E | X | E | E | X | E | E |
3  | E | E | E | X | E | E | E | E | E | E |
4  | E | E | E | E | E | E | E | X | X | X |
5  | E | E | E | E | E | E | E | E | E | E |
6  | E | E | X | E | E | E | E | E | E | E |
7  | E | E | E | E | E | E | E | E | E | E |
8  | E | E | E | E | X | E | E | E | E | E |
9  | E | E | X | E | E | E | E | E | E | E |
10 | E | X | E | E | E | E | E | E | E | E |

要得到的答案为

     1   2   3   4   5   6   7   8   9  10
1  | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
2  | 0 | 0 | 1 | 2 | X | 1 | 1 | X | 1 | 0 |
3  | 0 | 0 | 1 | X | 2 | 1 | 2 | 3 | 4 | 2 |
4  | 0 | 0 | 1 | 1 | 1 | 0 | 1 | X | X | X |
5  | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 2 | 3 | 2 |
6  | 0 | 1 | X | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
7  | 0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
8  | 0 | 1 | 1 | 2 | X | 1 | 0 | 0 | 0 | 0 |
9  | 1 | 2 | X | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
10 | 1 | X | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

程序运行时,首先布雷器只告诉位置(9,9)处的数字为0,然后扫雷器可以自动算出其他格子的状态.

自动扫雷用到的推理规则如下.这里设已经知道某个格子为安全格,且周围有n个地雷

(1)如果n=0则周围的8个格一定都是安全格,则自动翻开这8个格子,得到它们对应的数值,然后继续推理

(2)若已经知道某个格子P为安全格,设Q为P的一个邻居(P周围的8个格子之一),则此时Q周围的已知安全格又多了一个,如果此时Q周围的已知格均确定为安全格,且剩余格的数目等于Q的数字,那么Q的剩余格一定都是雷,然后继续推理

(3)若已经知道某个格子P为安全格,设Q(数字为n)为P的一个邻居则此时Q周围的已知雷又多了一个,如果此时Q周围的已知地雷数等于n那么Q的剩余格一定都是安全格,然后继续推理

(4)减法规则,设P和Q为已知的两个安全格且它们有公共邻居,(此时P和Q可能直接相邻也可能中间隔一行或者一列),那么，对区域P-Q和Q-P,这两个区域的地雷数目的差一定等于P和Q的数字之差.这里P-Q类似于表示集合的差运算,即从第一个集合(P的所有邻居)中去掉所有属于第2个集合(Q的所有邻居)的元素,且还要去掉元素Q本身.

证明如下: 用符号S(P)表示格子P周围的地雷集合,C(P,Q)表示P和Q的公共邻居.

设P和Q互为邻居,则P周围的地雷由如下三部分组成：P-Q中的地雷,公共部分的地雷,以及格子Q本身的地雷(因为Q为安全格,故为0)

即S(P)=S(P-Q)+C(P,Q)+0,

类似的S(Q)=S(Q-P)+C(P,Q)+0

于是可得S(P)-S(Q) = S(P-Q)-S(Q-P)

当P和Q中间隔了一行或者一列时,证法类似.

现在对两个区域(P-Q)和(Q-P)

符号b1,s1,u1分别表示第一个区域的已知地雷数,已知安全格数,未知格的数目

符号b2,s2,u2分别表示第二个区域的已知地雷数,已知安全格数,未知格的数目

又知道S(Q)-S(P)=d>=0.则可得下面两条推理规则

(5)若u1=0,即第一个区域的信息均为已知时,若还知道d==b2-b1,即地雷差的约束已经得到满足,则此时区域2的剩余格一定全是安全格.

(6)若u1=0且b2==0,u2==d,即区域2的已知格全是安全格,而未知格的数目等于地雷差,则此时区域2的剩余格一定都是雷.