根据策梅洛定理,中国象棋是不是应该红方必胜或必和棋?

太长不看版:无法证明中国象棋红方有必胜或和的策略。涉及策梅洛定理、策略窃取、迫移局面。

策梅洛定理

知道策梅洛定理的人很多,我简单复述一下。

在二人完美信息回合制抽象策略游戏中,以下三者有且只有一项成立:

1、先手方有必胜策略;

2、后手方有必胜策略;

3、双方的最优策略将会导向平局。

策略窃取(围棋)

而在满足一定条件的某些游戏中,第二项“后手方有必胜策略”是可以被逻辑证否的。

比如不贴目的围棋。

证明(反证法):假设存在白方必胜策略 P。那么黑方可以开局时就选择“停一手”。若白方也选择“停一手”,则按照规则,棋局立即结束,平局。否则若白方在棋盘上落任意一子,黑方即可窃取后手方的策略 P;这样黑方变成了实质上的后手方,采取策略 P 必胜。然而这与“存在白方必胜策略 P”矛盾,因此不存在白方必胜策略 P。

这种证明的方式即“策略窃取”(strategy stealing argument/ copycat lemma)。

策略窃取的适用范围

适用策略窃取的游戏需要满足两个条件:

1、是对称游戏。

2、某方的行动永远不会帮倒忙。

满足以上条件的游戏包括无禁手的五子棋、六贯棋、井字棋等。

用同样的方式证明无禁、不允许停招的五子棋黑先必不败:

证明(反证法):假设存在白方必胜策略 P。那么黑方可以开局时就选择随便走一着棋 A。我们知道在五子棋中,任意“免费”的一招棋只会对局面有帮助,不会帮倒忙。因此接下来白方在棋盘上落任意一子,黑方即可窃取白方的策略 P;这样黑方变成了实质上的后手方,采取策略 P 必胜。然而这与“存在白方必胜策略 P”矛盾,因此不存在白方必胜策略 P。

不是对称游戏的例子包括带贴目的围棋、有禁的五子棋。

迫移局面(Zugzwang)

2、某方的行动永远不会帮倒忙。

这一条比较微妙。请看国际象棋的一个例子:

此局面若轮白走则是和棋,若轮黑走则黑负。所以这是一个先手方不利的局面,术语称“迫移局面(zugzwang)”。这种局面的存在,使得“策略窃取”证明在国际象棋上不成立。

象棋中不能停招,而围棋“停一招”永远合法,所以围棋中不存在“迫移局面”。

与国际象棋类似,中国象棋中也存在“迫移局面”。如下图:

因为“将帅不得见面”规则的存在,本局面红先红负,黑先黑负。

如果我们尝试用“策略窃取”证明中国象棋红方有必不败策略,仍然假设黑方有必胜策略 P;现在红方不能“停一招”。因此红方总得走一手棋 A,才能去窃取黑方的策略。然而我们不知道红方的这手棋 A 会不会让局面变得更糟(因为存在“迫移局面”),所以策略窃取证明失效。

因此我们不能通过逻辑推理证明中国象棋红方有必不败策略。

实际上,后手方有优势的对称棋类游戏是存在的,比如动物将棋。

已有研究者通过穷举证明,动物将棋的后手方拥有必胜策略。

不过,从现实出发考虑,中国象棋黑方有必胜策略的可能性非常非常低。事实上,黑方存在某种必胜策略 P,等价于中象的开局(S_0)就是迫行局面;直觉上来看这几乎不可能,但理论上我们不能排除黑棋有必胜策略的可能性——万一黑棋有办法将局面导向某种迫行残局呢?

 

觉得好的话记得打赏赞助小灰灰哦,小灰灰灰更有动力的,谢谢

小灰灰

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: