兩台絕頂聰明的電腦下棋對弈，誰會贏？ 理由是什麽？
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分，等等，數字是我胡諏的）來評判局勢的好壞。
選擇“Disable on www.wenxuecity.com”
選擇“don't run on pages on this domain”
