回覆列表
  • 1 # 老唐漫談

    都同一水平的話,應該是互有勝負。

    如果真的是聰明絕頂的電腦,那情況只會是以下三者之一:

    電腦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分,等等,數字是我胡諏的)來評判局勢的好壞。

  • 中秋節和大豐收的關聯?
  • 哪一部國產劇陣容超豪華?