为什么下象棋有认输，没有认赢？ 第1页

这个是对 @Richard Xu 的回答的补充:

中国象棋棋至少比NP难.

NP是所有可以在多项式时间内被验证的语言. 也就是说如果要查一个input 是否属于某个NP的语言 , 存在一个多项式长度的证明 可以连着 丢进一个多项式时间的verifier , 然后 输出YES当且仅当 . 考虑象棋的语言 Chess={ 'pos' |如果棋局处于 'pos' 我方赢}. 这个时候我们能不能找到多项式长度证明呢? 为了方便, 我们考虑双方都只下一步棋的情况. 令 为一个验证我方是否已经赢的图灵机, 棋局的转移函数为 , 我方的move为 , 敌方的move为 那我们的算法就要evaluate

若熟悉polynomial hierarchy, 可看出 .

更推广到双方各走n步

这个就更难了. 但是一个NP 的oracle只能做 , i.e., .

P.S. 认输问题是认赢问题的dual

也不能在P或NP时间内确定.

中国象棋具体是什么复杂度?

更难处理的是 nchess 的 n 也不知道是不是poly-length的. 从这个表里面看来, 中国象棋具体复杂度还是open的, 不过看到chess, checkers 还有go 都是EXPTIME-complete的. 那很可能中国象棋也是EXPTIME-complete. 如果事实如此, 那中国象棋认输认赢不能在 NP 里面, 即使P=NP. 这个是因为根据 time hierarchy theorem , 我们有

因为认输是P，认赢是NP的。

当一方认输时，裁判无需验证当前局面是否必输，可以直接判负，时间复杂度为常数。

当一方“认赢”时，裁判可以在常数时间复杂度内验证任意局面是否已经有一方赢或者输（即NP中要求的“可以在多项式时间复杂度内验证一个解”）但通常无法在多项式时间复杂度内验证当前局面是否必赢（“无法在多项式时间复杂度内找出一个解”）

作为对比，大多数棋类在进入残局后都可以变相“认赢”，因为此时可以直接根据当前局面以及一些简单的经验规则（比如“单车胜双士”，或者围棋中空地已经较为明确，且目数差距远超过剩余官子数量的情形）判断是否已经有一方必赢或必输（而无需讨论后续的可能着法）。这里面其实有一点Obvious Dominance的意味。

别说下象棋，就是翻现代汉语词典，他也找不到“认赢”啊！

我认为 @Richard Xu 和 @王希 的回答有一些道理。Richard 说裁判认定“认赢”成立是NP问题，但还应该考虑问题的规模，在规模足够小的情况下，NP问题也是可以求解的，但即便如此，也不应该存在“认赢”规则，因为要杜绝第二类错误。

总结起来，象棋中不存在“认赢”的原因是：问题大规模情形下（局面不清楚）裁判无法判定“认赢”是否是成立的；小规模下（按经验必胜的局面）即便可能推演出一方是必胜的，但无法保证裁判推演不出错，也无法保证选手执行不出错，因此应杜绝第二类错误；极小规模下（几步内的定式杀招）存在“认赢”的合理性，但没有必要性，而且不能因此剥夺对方的行棋权力，因为规则上，在必胜局面（除困毙外）也可以通过对方选手放弃将杀而形成翻盘或者和棋。

用一句话总结原因的话，就是人的理性和认知是有限的。而如果不是这样的话，象棋也就没有意义了。

-------------以下为原答案-------------

简而言之，因为人类的理性有限，目前无法知道或完美实施象棋的最优应对，所以要杜绝第二类错误。

这个问题首先要把什么是“认赢”定义清楚。假设定义“认赢”是在某个局面下，一方证明对方不论怎么走，自己都能有必胜的应对策略而直接判自己获胜。

那么这个证明过程在局面复杂的情况下（均势、大优、胜势）几乎无法实现（NP问题），在特别简化的局面（一两步就将死了）中又没有必要证明。

争议点在一般简化的局面中（如象棋界总结出来的必胜局面）。这里虽然由经验甚至严谨的推导能够得到一方必胜的结论，但对弈双方以及裁判都是人，就有可能犯错误。假如在某个局面下，裁判错误地认为一方已经赢了，就犯了第二类错误即取伪，责任应当规则方裁判负。这里的第二类错误的危害是比第一类错误大的，如果存在“认赢”，那么规则上将不再完美。而本该赢却“认输”属于第一类错误，责任是选手自负。

同时，选手也不一定明确地知道最优策略，选手在执行策略的时候也是会犯错误的，下棋并不单单是理论上的较量，还要看犯不犯糊涂，棋子有没有摆错，看没看走眼等等。

对弈双方在一开始都以自己赢为假设，通过零和博弈去证明自己是对的，象棋之所以存在它的意义，就是因为人的理性和认知是有限的，并不知道象棋中蕴含的最优策略，所以理论上一开始就有的胜负，却需要到最后一刻通过实践的方式来“认赢”。

我个人认为 @Richard Xu 的回答讲的内容都是符合事实的，但并不能作为这个问题的回答。

下棋有认输而没有认赢，唯一的原因是双方的战略目的都是赢，和P还是NP没有关系。我们可以做一个假设：有一台谕示机（Oracle）可以在可忽略的常数时间给出一个局面哪方有必胜方法，它是全知的。现在让裁判可以随意访问这台谕示机，那么P和NP没有任何区别，裁判总是可以迅速判断双方谁有必胜策略。甚至根据策梅洛定理，裁判一开始就知道先手或者后手有必胜策略。

我们假设中国象棋先手有必胜策略。那么两个人下棋时，先手能不能直接认赢？反正裁判根据谕示机可以知道，先手有必胜策略。但是下棋所竞争的，就是双方的智力能不能达到那个必胜策略，根据谕示机的结果相当于消灭了下棋的意义。

而他所说的“变相认赢”，其本质还是认输：只有双方和裁判同时认可双方的棋力在一个定值以上。反过来说，如果两个新手，即使下到了单车对双象，也不一定有人认输。只有双方都有一定水平，才会认为“以他的水平，我输定了”从而认输（这也就是变相认赢）。如果一方坚持，另一方也必须下完。

---

  zzc2422 网友的相关建议: 
      

这就一基本逻辑问题啊！

你认输，对方显然不会反对，OK，双方达成共识。

你认赢，对方说凭啥？当然如果对方同意了，那这盘棋按对方认输处理，还是属于认输。对方不同意，那你这个认赢显然无效。

---

  UNSC711 网友的相关建议: 
      

“白方宣布已经将黑方去军事化”

---

  xiao-xiao-yi-98-74 网友的相关建议: 
      

保守治疗吧。

---