两台绝顶聪明的电脑下棋对弈，谁会赢？ 理由是什么？
2015.8.25…………发现好多知友回答了，这个问题，在此表示感谢！…………
其实我想的绝顶聪明的电脑，则意味着他们能够预测出对手下一步的路数，而对方也会根据对方的预测进行调整
其实我想的绝顶聪明的电脑，则意味着他们能够预测出对手下一步的路数，而对方也会根据对方的预测进行调整
按投票排序按时间排序
234 个回答
如果真的是聪明绝顶的电脑，那情况只会是以下三者之一：
电脑1开局求和，电脑2接受（和）
电脑1开局认输，电脑2接受（先手输）
电脑1开局下了一步，电脑2认输，电脑1接受（先手赢）
补充一下，常见的围棋象棋之类的棋是finite sequential game of perfect information。
finite是指有限步内结束，比如国际象棋规定三次重复局面等情形：和局 (國際象棋)；中国象棋也有类似的规定。这些规定保证这些棋不可能永远下下去。
sequential game则是指博弈双方轮流做决定，和双方同时做决定的simultaneous game相对应。前者例子就是各种下棋，后者例子有猜拳。
perfect information是指双方完全掌握所有信息。perfect information的例子包括所有明棋；imperfect game的例子包括大多数牌类游戏，军棋，带战争迷雾的RTS（红警手动斜眼）。
Zermelo's theorem (game theory) 策梅洛定理说明，对于这类游戏，如果其中不包含随机因素（单指棋盘上的随机因素，比如发牌扔骰子。下棋的电脑被断电这类随机因素不算），那么可以通过递归推导使得至少一方获得必不败策略。
如果不要求排除随机因素，则这类游戏保证有pure strategy equilibrium。也就是说，均衡状态下，双方有确定策略，但是不保证确定结果。
与pure strategy equilibrium相对的是mixed strategy equilibrium，混合策略。例如，石头剪子布里面，均衡状态下就没有确定策略（你确定出剪刀的话一定会被确定出石头的克），只有混合策略（双方出手前按1/3，1/3，1/3的概率随机决定是石头还是剪刀还是布）。
总结一下就是，
如果是有限步内结束，双方轮流移动，局势对双方透明，不含随机因素的棋类游戏，则一定有确定的最优策略，以及对应的确定的结果。（象棋，围棋）
如果是有限步内结束，双方轮流移动，局势对双方透明，包含随机因素的棋类游戏，则一定有确定的最优策略，以及对应的不确定的结果。（大富翁）
如果是有限步内结束，双方轮流移动，局势对双方不完全透明的棋类游戏，则至少一定有混合的最优策略，以及对应的不确定的结果。（军棋；梭哈）
===============================================================
有人说这不是绝顶聪明而是预知未来，这是不对的。即使游戏中有随机因素，信息也不透明，但博弈树是确定的，计算机可以把所有可能结果以及对应概率都算出来，进而算出最优策略，简单的伪代码只要几十行就可以写清楚。
这结论与一些常识违背是因为，大多数情况下这棵博弈树太特么大了，大到现在最强的电脑做不到，可预见的将来也做不到。典型例子如围棋，状态数大概有一亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿这个级别。但题主问的是绝顶聪明的电脑，那咱就不考虑这麻烦了。
==============================================================
有些人可能不明白博弈树、必败态之类的概念，或者觉得为什么开局认输太傻了，一定要下到输。其实如果真的遍历完博弈树的话，在哪一步认输并没有区别。因为双方都计算力很高把博弈树遍历了，一方发现自己处于必败态，那么往下走就没意义了，因为你无论怎么走都是必败态，只要对手不失误，那就是从失败走向失败。
我举一个简单的例子，很多人都玩过井字棋（tic-tac-toe）。这个棋只有两万多种棋局，用电脑很容易搜完所有节点。如果双方都不犯错的话，结果只能是和棋。普通人甚至多玩几次就可以发现必不败走法。两个熟悉井字棋的成年人是不会玩井字棋的，因为这棋太简单以至于开始下之前胜负就分明了。我们觉得象棋、围棋之类的没有必胜走法，只是因为这棋太复杂，无论人还是电脑都无法遍历整个博弈树，甚至只能推算到几步之后。
所以在计算力不足（也就是不够绝顶聪明）的情况下怎么玩，是棋类的魅力所在。我抛个砖，电脑常用的算法是，不搜索整个博弈树，而是通过宽度或广度优先搜索加剪枝遍历接下来的若干步的可能走法（印象里当年的深蓝能往后推12步），并给每个最终状态打分（例如后100分，车50分，兵5分，关键位置200分，等等，数字是我胡诹的）来评判局势的好坏。
电脑1开局求和，电脑2接受（和）
电脑1开局认输，电脑2接受（先手输）
电脑1开局下了一步，电脑2认输，电脑1接受（先手赢）
补充一下，常见的围棋象棋之类的棋是finite sequential game of perfect information。
finite是指有限步内结束，比如国际象棋规定三次重复局面等情形：和局 (國際象棋)；中国象棋也有类似的规定。这些规定保证这些棋不可能永远下下去。
sequential game则是指博弈双方轮流做决定，和双方同时做决定的simultaneous game相对应。前者例子就是各种下棋，后者例子有猜拳。
perfect information是指双方完全掌握所有信息。perfect information的例子包括所有明棋；imperfect game的例子包括大多数牌类游戏，军棋，带战争迷雾的RTS（红警手动斜眼）。
Zermelo's theorem (game theory) 策梅洛定理说明，对于这类游戏，如果其中不包含随机因素（单指棋盘上的随机因素，比如发牌扔骰子。下棋的电脑被断电这类随机因素不算），那么可以通过递归推导使得至少一方获得必不败策略。
如果不要求排除随机因素，则这类游戏保证有pure strategy equilibrium。也就是说，均衡状态下，双方有确定策略，但是不保证确定结果。
与pure strategy equilibrium相对的是mixed strategy equilibrium，混合策略。例如，石头剪子布里面，均衡状态下就没有确定策略（你确定出剪刀的话一定会被确定出石头的克），只有混合策略（双方出手前按1/3，1/3，1/3的概率随机决定是石头还是剪刀还是布）。
总结一下就是，
如果是有限步内结束，双方轮流移动，局势对双方透明，不含随机因素的棋类游戏，则一定有确定的最优策略，以及对应的确定的结果。（象棋，围棋）
如果是有限步内结束，双方轮流移动，局势对双方透明，包含随机因素的棋类游戏，则一定有确定的最优策略，以及对应的不确定的结果。（大富翁）
如果是有限步内结束，双方轮流移动，局势对双方不完全透明的棋类游戏，则至少一定有混合的最优策略，以及对应的不确定的结果。（军棋；梭哈）
===============================================================
有人说这不是绝顶聪明而是预知未来，这是不对的。即使游戏中有随机因素，信息也不透明，但博弈树是确定的，计算机可以把所有可能结果以及对应概率都算出来，进而算出最优策略，简单的伪代码只要几十行就可以写清楚。
这结论与一些常识违背是因为，大多数情况下这棵博弈树太特么大了，大到现在最强的电脑做不到，可预见的将来也做不到。典型例子如围棋，状态数大概有一亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿这个级别。但题主问的是绝顶聪明的电脑，那咱就不考虑这麻烦了。
==============================================================
有些人可能不明白博弈树、必败态之类的概念，或者觉得为什么开局认输太傻了，一定要下到输。其实如果真的遍历完博弈树的话，在哪一步认输并没有区别。因为双方都计算力很高把博弈树遍历了，一方发现自己处于必败态，那么往下走就没意义了，因为你无论怎么走都是必败态，只要对手不失误，那就是从失败走向失败。
我举一个简单的例子，很多人都玩过井字棋（tic-tac-toe）。这个棋只有两万多种棋局，用电脑很容易搜完所有节点。如果双方都不犯错的话，结果只能是和棋。普通人甚至多玩几次就可以发现必不败走法。两个熟悉井字棋的成年人是不会玩井字棋的，因为这棋太简单以至于开始下之前胜负就分明了。我们觉得象棋、围棋之类的没有必胜走法，只是因为这棋太复杂，无论人还是电脑都无法遍历整个博弈树，甚至只能推算到几步之后。
所以在计算力不足（也就是不够绝顶聪明）的情况下怎么玩，是棋类的魅力所在。我抛个砖，电脑常用的算法是，不搜索整个博弈树，而是通过宽度或广度优先搜索加剪枝遍历接下来的若干步的可能走法（印象里当年的深蓝能往后推12步），并给每个最终状态打分（例如后100分，车50分，兵5分，关键位置200分，等等，数字是我胡诹的）来评判局势的好坏。
