人與電腦下國際象棋，隨著計算機性能的提升，電腦最終會不可戰勝嗎？

01-11

1997年，美國卡內基梅隆大學的許峰雄博士開發的深藍電腦成功地在戰敗世界棋王卡西帕羅夫，我想很多人都有印象吧。我們知道，在國際象棋中第一步只能走馬或者兵，然後下一步能走的棋子和棋子可以走的位置也是有限的，那也就是說每走一步後對手能走的方案也是有限的。那麼如果有一台電腦性能非常之強大，它計算並存儲了對手每一種走法後可能出現的各種情況，並且知道最後的輸贏（當然這需要非常巨大的計算量，我也沒法算出來有多少）。那麼我們可以不可以說，隨著電腦性能的發展，有一天，我們將無法在國際象棋上戰勝電腦，因為電腦已經知道了國際象棋的所有可能性，它只需知道選擇不會輸的道路走，就一定能贏。同理，在中國象棋或者圍棋上是否也會發在同樣事？

樓上們雖然說得都是對的，但全都是答非所問嘛……

題主的核心問題在這裡：

我們知道，在國際象棋中第一步只能走馬或者兵，然後下一步能走的棋子和棋子可以走的位置也是有限的，那也就是說每走一步後對手能走的方案也是有限的。那麼如果有一台電腦性能非常之強大，它計算並存儲了對手每一種走法後可能出現的各種情況，並且知道最後的輸贏（當然這需要非常巨大的計算量，我也沒法算出來有多少）。那麼我們可以不可以說，隨著電腦性能的發展，有一天，我們將無法在國際象棋上戰勝電腦，因為電腦已經知道了國際象棋的所有可能性

所以題主是在問暴力打表啊你們扯DeepLearning做什麼！

在直接回答題主問題之前，首先給題主介紹另一種分析思路。

題主是通過開始狀態唯一（顯然）、狀態轉移有限（每次最多16個子可以動，每個子最多能動到63個地方，所以每次決策的集合大小不會超過16*63，這上界給得也太喪心病狂了）、有限步後終止（感謝長將和、逼和和三次重複局面大大簡化了這裡的論述……）這三個條件推出總狀態數有限的。這是對的。但還有另外的思路：

直接考慮棋盤上可能出現的狀態。

我們考慮任意在棋盤上擺棋子，成為一種棋盤「狀態」，而不要顧及這狀態是通過什麼走法走出來、以及一個智商正常的人可不可能走出這棋局的。考慮到你所設想的那台「知道所有可能性」的電腦是「知道所有可能性」的，顯然每一種擺法我們都應當考慮（我國際象棋下得不好，一下子想不出來有沒有狀態是無法走出的，除了沒王），包括白方十六子俱全，黑方只剩一個光頭王了這種狀態。正常人肯定下不出來，但是要考慮不正常的人，不能讓程序這時候茫然無措了呀。另外這個狀態對於該黑方走和對於該白方走肯定是不一樣的。

然後我們的電腦將把這些狀態全部存起來，並且開始提前做一些運算：計算每個狀態（布子情況+落子方）是對於黑方必勝，白方必勝，還是必和，同時把對於落子方而言的最優決策記下來。

怎麼計算？

從終態倒推。先把顯然可以區分勝負（將死，和棋）的狀態標記好，然後對於每一個狀態（方便陳述，假設此時由黑方落子）：

如果不管怎麼落子，之後形成的每一個的狀態都已經被標記好勝負態，那麼：

如果這些狀態每一個都是白方必勝，那麼當前狀態也只能是白方必勝，走到這兒黑方就可以滾粗了；
如果這些狀態中有至少一個是和棋，剩下都是白方必勝，那麼記下來此時黑方應該走那步能走到和棋狀態的，並把當前狀態標記成和棋；
如果這些狀態中至少有一個是黑方必勝，那麼記下來此時黑方應該走那步能走到黑方必勝狀態的，並把當前狀態標記為黑方必勝。

如果有一步落子之後，形成一個我還不知道它勝負態的狀態，那麼先不管它，以後再說。

容易知道，這樣倒推大概也是可以把所有狀態都標記好的（重複局面的和棋比較複雜，我覺得特殊處理應該能搞，等大神糾正）。如果我們通過這樣的提前運算，能知道對於所有的狀態的勝負態和最優決策，這遊戲確實就不用玩了，計算機必贏無疑，至少是和。

另外這裡還有個小推論：如果真的可以得到這個表，那麼最開始的局面：布子剛剛完成，其實最後的結局已經定了。因為開局也是一個狀態，也有其必勝、必負、必和態。

但我們能不能拿到這個表呢？

現在我要開始算，所有的狀態數有多少。

首先從白方的16子中，選出在場上的棋子。王肯定在。所以，白方有x子存活，這x子不同組合的方案是（C代表組合數）：

$C(15, x-1) , 16 geq x geq 1$

顯然黑子也是一樣，為了方便理解換個變數名

$C(15, y - 1), 16 geq y geq 1$

然後把這 $x+y$ 個子放到棋盤上，顯然就是個排列數：

$P(64, x + y)$

統計所有的x和y，所以最後總的狀態數：

$|State| = sum_{x = 1}^{16}sum_{y = 1}^{16}C(15, x-1)C(15, y-1)P(64, x+y)$

這個狀態數大概是個什麼水平？

用斯特林漸近公式（感興趣自己查吧~）大約可以搞出一個精確近似？

不過我比較懶，暴力給個不精確下界，就算忽略兩個組合數當成1，只考慮排列數，而且只考慮最後一項 $P(64, 32)$

這個數就大約是 $2^{100}$ 以上了。

再乘上前面的組合數，然後對每一項求和……

我物理學得很爛，但我猜，就算我們以一個原子作為存儲單元，打碎月球來做我們的硬碟都不太夠……

所以，你所說的那個方案，思路是對的，現實是不可能的。現在的電腦玩國際象棋，還是要用Machine Learning，Monte-Carlo，或者暴力alpha-beta之類的搜索演算法和調參數技巧來解決。

出現不可戰勝的電腦？人幾乎不可戰勝的電腦，現在已經遍地是了。但這些「戰無不勝」的電腦，和電腦下，還能是「不可戰勝」的嘛？理論上戰無一敗的電腦，要等到上面說的那個暴力打表建立起來才行。

題主你多慮了，深藍是1997年的事情了，電子科技發展如此迅速的時代，還用97年的思維來考慮事情就不合適了。

實際上，在97年的深藍之後，國際象棋特級大師和電腦的標準比賽里，你們人類就沒贏過。

我們從97年深藍打敗卡斯帕羅夫說起吧

1998年：REBEL以5:3戰勝了當時世界排名第二的維斯瓦納坦·阿南德
2000年：Deep Junior和九位特級大師各戰一局，最後二勝五平二負，算平局
2002年：Fritz和拉基米爾·克拉姆尼克以4:4戰平，當時克拉姆尼克已經取代卡斯帕羅夫成為世界冠軍了
2003年：Deep Junior對卡斯帕羅夫，一勝六平一負，算平局
2003年：X3D Fritz對卡斯帕羅夫，一勝三平一負，算平局

2004年：國際象棋人機大戰，三台電腦對三位特級大師（波諾馬廖夫、托帕洛夫、卡爾亞金），一共十二局，電腦隊六勝五平一負，完敗特級大師隊
2005年：國際象棋人機大戰，同樣的三台電腦對三位特級大師（哈利夫曼、波諾馬廖夫、卡西姆扎諾夫，都是曾經國際棋聯的世界冠軍），最後電腦隊六勝六平，完敗特級大師隊
2005年：Hydra對當時世界排名第七的邁克爾.亞當斯，五勝一平
2006年：Deep Fritz對當時依然排名第一的克拉姆尼克，二勝四平。這一戰已經很有意思了，之前的國際象棋電腦多是專門用來下象棋的機器，而Deep Fritz是運行在一台搭載了一枚至強DC 5160處理器的電腦上跑的，這款處理器的硬體跑分比現在市面上的英特爾i3還差一點。
2009年：Pocket Fritz 4的棋力達到了特級大師級別，等級分2898。前面很多電腦已經能完勝特級大師了，為什麼這個要單獨拿出來說呢？因為這玩意兒是運行在手機上的，具體來說是HTC Touch HD。這還是五年前的手機了，處理器主頻528MHz，內存288MB，這配置放到現在比淘寶上200-300一台的山寨機都差了好多。

事實上，雖然硬體能力大幅度上升，但是演算法的進步更多，Pocket Fritz 4每秒處理20000步，而深藍每秒處理200000000步，但是兩者的棋力其實差不多，所以Pocket Fritz 4在手機上都能跑。

現在最好的國際象棋引擎等級分已經是3000-3300級別了，2500以上就是特級大師了，現在排名第一的馬格努斯·卡爾森也才2900不到。

國際象棋的最終解決方案/必勝策略還沒被發現，但是以人類的棋力，別說不可能戰勝的電腦了，不可能戰勝的山寨手機都不是新鮮事了。

參考資料：Human Computer Chess Matches

參與過圍棋AI的開發

明確的說：是的！

1 象棋和國際象棋，現在的主流比賽AI都是和AI對抗，人機對抗的都已經是作秀了。這個領域人完全不是機器的對手。

2 圍棋，現在機器還不是人的對手，但是已經越來越接近了。

看了上面的答案，發現多數人對棋類AI的理解不是暴力枚舉（笑）就是枚舉+招法匹配，完全無視機器學習的存在。實際上第一代的GnuGo（一個主流的開源圍棋AI）就是有限計算+招法匹配的思路，也就是大家普遍理解的人通過代碼去教機器下棋的思路。但實際上這個思路被淘汰很久了。後來的FueGo的基於棋類數學模型的AlphaBetaTree+蒙特卡洛AI，這個更依賴於硬體和訓練數據。再後來機器學習的思路被更多的加入到AI中。

可以說AI的棋力實際是隨著機器學習，和計算機運算存儲能力這兩個領域的發展而逐步提高的，而人類棋力的提高相對這兩個領域的發展真的是太慢了。可以說圍棋領域被趕上也是可預期的事情。

甚至我覺得，之所以圍棋AI還沒有超越人是因為沒有商業利益驅動，只有少數人因為興趣而投身在這個領域的研究。如果有商業級別的研究團隊加入，可能很快就····

我也來試著回答一下這個問題吧。第一次長答，希望你喜歡。

我自己小時候受過3年的國際象棋訓練，也考過級。現在學的是計算機方面的專業，大一的時候寫過一個黑白棋的AI，雖然也算不上非常厲害，但是和我自己下是沒輸過。關於交戰歷史，得票最高的答案已經說得非常清楚了。我可以從程序猿和一個業餘國象愛好者的角度再補充一些。

首先，題主提到

「那麼如果有一台電腦性能非常之強大，它計算並存儲了對手每一種走法後可能出現的各種情況，並且知道最後的輸贏（當然這需要非常巨大的計算量，我也沒法算出來有多少）」

這樣的電腦在可以預見的將來應該不存在。

我可以舉一個例子，國際象棋中的殘局

這是國際象棋中著名的馬象殺單王局面。這是一個白棋必勝局面。但是如果黑棋防守得當的話，白棋需要48步才能殺死黑王。而國際象棋中有一條規則是：雙方50步不吃子、不走兵即為和棋。所以說如果黑棋不下錯，白棋下錯一步，很可能就贏不了了。去年國象全國女子賽上就有棋手因為在馬象殺單王中失誤導致沒能贏棋

我曾經把這個局面扔給Fritz13算過。算了一個多小時，深度才到38，也就是離終局至少差10步。後來我實在沒耐心算了，因為從30步開始，深度每加深1時間都要長很多很多。搞不好一天都算不出來。

這樣一個簡單的局面都難以窮盡，可想而知要達到題主所說的，存儲所有局面有多難。

國際象棋中，第一步棋的合法棋步有20種（8個兵向前走1到2步，兩個馬分布有2種走法）。隨著棋局的發展，可以走動的棋子會比初始狀態更多

（比如白方在走了第一步王前兵之後，下一步合法棋步增加到30種：7個兵向前走1到2步，王前兵向前走一步，白格象走1到5步，皇后走1到4步，王走一步，王翼馬三種走法，後翼馬兩種走法）

一局棋，絕大多數情況不會低於20回合（雙方各走20步）。事實上20回合就結束算是非常非常非常短的對局，感覺40~60回合比較常見，不久前我還在一個比賽中看到了90回合以上的對局。

要計算題主所提到的「每一種走法後可能出現的各種情況」，我們可以樂觀地估計一下：每步棋都是20種變化，並且雙方下棋不超過20回合。這樣得到的棋局種類是 $20^{40}$ ,大約是 $10^{52}$

現在普通人使用的電腦每秒的計算速度差不多是 $10^8$ 這樣的級別。一年有不到 $10^8$ 秒。即使你有一台比普通電腦快上一億倍的超級電腦，這些變化還要算 $10^{28}$ 年。要知道宇宙的年齡也只有130億年，也就是 $10^{10}$ 這個數量級。所以說，國際象棋的變化是無法像你說的那樣算完的。計算機的速度很快，但是遠沒有快到那個程度。

但是我們又注意到，如排名第一的答案所說，現在計算機的國際象棋水平非常高。我的老師曾經這樣和我形容（大意）：讓世界冠軍和最高水平的電腦下一盤棋，可能稍微有一點贏棋的機會。但是多下幾盤總成績基本上是不可能佔優的。所以說，計算機下棋並不是盲目地暴力計算的。它的設計方法某種程度上借鑒了人類下棋時的思考方式。

我們知道，水平再高的棋手也無法在只下幾手的情況下預見到終局的局面。剛開始學棋的時候，老師總是會說要「算三步」「算五步」。AI下棋也是如此。減少計算的深度，可以有效控制計算量。往往五步之後局面好的一方，獲勝的概率也高。比如你白賺了一個皇后，一般來說只要以後不犯低級錯誤就能贏棋。

另外，告訴計算機怎樣判斷局勢，也是減少計算量的必需手段。說一個最簡單的方法：統計雙方子力，後算9分，車算5分，馬和象算3分，兵算一分。哪方的分多就認為哪方局勢好。

如果計算機按這樣判斷局勢，大概就可以達到初學者的水平。在此基礎上可以加上一些更細緻的分析，比如根據哪方的子力更活躍（能下的地方多），兵的形狀和高低，對敵方王城的威脅程度等等來加分或減分。

知道了這些，就可以讓電腦來比較好地下棋了。當然，一些搜索演算法和優化手段也是必要的，像alpha-beta剪枝，A*演算法之類。如果你用過Fritz這樣的國際象棋軟體，也會看到它在下棋的時候會動態給出對局面的評分。這個評分很多時候比職業棋手的判斷更為精準。搜索深度根據局面的複雜程度，從六七步到二三十步不等。

此外在國際象棋的AI中，開局庫的使用也有很重要的作用。對於計算機來說，離棋局結束越近，也就越容易判斷局勢。相比之下，開局由於局勢尚不明確，不太適合各類搜索方法。而且在一些高手對決中，開局下得不好後面很難彌補。所以各類國象軟體都會有自己的開局庫，裡面存放了大量職業高手的對局，用這樣的手段來彌補開局水平的不足。

大概就說這些，想到了什麼再補上。希望可以幫到你。

Edit:

今天看到一個很好的答案，其實說得比我更專業，推薦:

象棋和國際象棋的電腦程序是如何設計的？

中yunor的回答。

TL;DR

答案是：就下國際象棋而言，能力水平：單純的人 &< 單純的電腦程序 &< 人加程序

人可以藉助機器的輔助，加強人的智能。以下為解釋。

---

凱文·凱利如是說 [1]

1997年，沃森電腦的前輩、IBM公司的深藍電腦在一場著名的人機大賽中擊敗了當時的國際象棋大師加里·卡斯帕羅夫（Garry
Kasparov）。在電腦又贏了幾場比賽之後，人們基本上失去了對這類比賽的興趣。

你可能會認為故事到此就結束了，但卡斯帕羅夫意識到，如果他也能像深
藍一樣立即訪問包括以前所有棋局棋路變化在內的巨型資料庫的話，他在對弈中能表現得更好。

也就是，人也可以利用電腦加強自己的下棋水平！

如果這一資料庫工具對於人工智慧設備來說是公平的話，為什麼人類不能使用它呢？為了探究這一想法，卡斯帕羅夫率先提出了「人加機器」（man-plus-machine）比賽的概念，即用人工智慧增強國際象棋選手水平，而非讓人與機器之間對抗。

「半人半機」的選手，人+國際象棋程序，是當代最好的國際象棋選手！意外嗎？

這
種比賽如今被稱為自由式國際象棋比賽，它有點兒像混合武術對抗賽，選手們可以使用任何他們想要用的作戰技巧。你可以單打獨鬥；也可以接受你那裝有超級聰明
的國際象棋軟體的電腦給出的幫助，你要做的僅僅是按照它的建議來移動棋子；或者你可以當一個卡斯帕羅夫所提倡的那種「半人半機」的選手。半人半機選手會聽
取人工智慧設備在其耳邊提出的棋路建議，但是也間或不會採用這些建議——頗似我們開車時候用的GPS導航一般。在接受任何模式選手參賽的2014年自由式
國際象棋對抗錦標賽上，純人工智慧的國際象棋引擎贏得了42場比賽，而半人半機選手則贏得了53場。當今世上最優秀的國際象棋選手就是半人半機選手
Intagrand，它是一個由多人以及數個不同國際象棋程序所組成的小組。

-----

補充閱讀：人+程序的前景

但最令人驚訝的是：人工智慧的出現並未讓純人類的國際象棋棋手
的水平下降。恰恰相反，廉價、超級智能的國際象棋軟體吸引了更多人來下國際象棋，比賽比以前增多了，棋手的水平也比以前上升了。現在的國際象棋大師（譯者
註：國際象棋界的一種等級）人數是深藍戰勝卡斯帕羅夫那時候的兩倍多。現在的排名第一的人類國際象棋棋手馬格努斯·卡爾森（Magnus
Carlsen）就曾接受人工智慧的訓練，他被認為是所有人類國際象棋棋手中最接近電腦的棋手，同時也是有史以來積分最高的人類國際象棋大師。
如
果人工智慧能幫助人類成為更優秀的國際象棋棋手，那麼它也能幫助我們成為更為優秀的飛行員、醫生、法官以及教師。大多數由人工智慧完成的商業工作都將是有
專門目的的工作，嚴格限制在智能軟體能做到的工作之內，比如，（人工智慧產品）把某種語言翻譯成另一種語言，但卻不能翻譯成第三種語言。再比如，它們可以
開車，但卻不能與人交談。或者是能回憶起YouTube上每個視頻的每個像素，卻無法預測你的日常工作。在未來十年，你與之直接或者間接互動的人工智慧產
品，有99%都將是高度專一、極為聰明的「專家」。

[1]: 以為谷歌們真是在做搜索？只是在用搜索技術改善新人工智慧

在國際象棋與中國象棋領域，人類早已經不是電腦的對手。所以我們就不用操心這方面的事了。唯一可以讓我們安心的事，圍棋領域，電腦依然遠遠不如人類，甚至近期看不到超越人類的可能。

我們來看看棋盤大小，國象是8*8 =64 格，中象是9*10 =90格，圍棋是19*19=361格，電腦想用窮舉法來暴力征服人類的想法可以簡單的被排除了。361的棋盤上所形成的變化，比宇宙內的星星還要多。當然，在9*9的小棋盤上，電腦的表現已經相當不錯，完全可以職業棋手抗衡了。

如果不能用窮舉法，那麼從程序的角度來說，必須建立一個價值模型，來模擬人類下棋的過程。但是問題出現了，在象棋領域，每一個子力的價值大致都是固定的，一個車從開局到終局，價值基本不太會變。但是在圍棋卻完全不是那麼一回事了，每一顆圍棋子雖然都很平等，沒有等級區別，但在對局過程中的價值是會變化的。前面還是棋筋，必須要救的棋，幾手之後變成廢子，可以隨意捨棄的情況在圍棋盤上幾乎時時發生著。

但這還不是大問題，真正的大問題是，圍棋在絕大部分時候，連最優秀職業棋手也不知道最優的下法是什麼。看下面一段報道:

2006．8.30，東京。同為豐田杯被淘汰者的崔哲瀚與朴正祥邀請古力研究他兩天前被李昌鎬淘汰之局，不久「復盤求道派」李世石解決羽根直樹匆匆加入。當問及為何要在打入前作一個偏損的交換時，古力深謀遠慮的擺出一個刺刀見紅的搏命變化。
崔哲瀚見罷，大笑。
負責翻譯的朴正祥一邊附和著笑，一邊向古力解釋：「小崔說，以李昌鎬的風格是絕對不會這樣沖斷作戰的」
「他打包票，李昌鎬絕對不會的」

看：圍棋的樂趣就在於有太多的選擇性了，選擇多的連最一流職業棋手也無法判斷哪一手是最優解，大多數時候，棋手是根據每個人的風格以及一瞬間的靈感來進行選擇的。但是風格與靈感，電腦有這些東西嗎？

所以，在很長很長的一段時間裡，在象棋程序已經踏翻專業棋手無數遍的時候，電腦程序依舊俳徊在入門級別的水平。在演算法沒有突破之前，電腦別說打敗棋手，連剛入門的棋手都無法打敗。與象棋比起來，演算法才是電腦戰勝人類的唯一希望。這已經不是電腦與人類的抗衡，而是程序員與棋手的較量。

大概10年前後，某個程序員忽然靈光一現，電腦學不了人類，那我們學上帝扔骰子吧。於是，運用蒙特卡洛演算法的電腦程序出現了。蒙特卡洛演算法他並不直接判斷每一手棋的價值，而是用扔骰子的方式判斷棋盤上最有可能下的一手棋是哪一手。圍棋在電腦眼裡變成了一個概率遊戲。

採用新演算法的電腦比之從前水平長進九子不止。很多業餘棋手已經可以從與電腦對弈中得到樂趣，但是，打敗人類還是遙不可及（現在電腦程序大約是職業棋手讓四子左右的水平)。而且，這種演算法已經沒有突破空間了，不會隨電腦的運算能力加強而提高水平。要想打敗人類，必須還要有更強大的演算法。甚至，我猜想，扔骰子也許是程序員走岔了路，最終解可能還是要回歸到模擬人類的想法來解決這個問題。

總之，我認為，在棋類領域，圍棋可能是唯一人類可以碾壓電腦的棋。而電腦要在圍棋上打敗人類，與電腦的強大與否關係不大，而在於程序員與數學家能不能設計出新的演算法。

請移步這裡：象棋和國際象棋的電腦程序是如何設計的？

兩年前答的，略顯粗糙……今天看了看，想的是：這是我說的么？

確實，現在象棋和國際象棋方面，電腦一般是要強於人的，但我認為必勝法是不存在的，或者無法求得。那些大師們與電腦對弈，電腦也從未能保證每戰皆勝，即使是10勝1負，也說明電腦無法徹底打敗人類。更何況，圍棋早已被證明了是個NPC問題。窮舉？等出了量子計算機的話試試吧。

假設這樣的電腦是存在的，且不只一台，那麼它們對戰結果會怎樣？

我覺得樓主是想問國際象棋是否存在必勝策略。也就是說電腦能否找到必不輸的走法。

簡單地說，根據策梅洛定理，國際象棋存在必勝策略，只不過以人類目前的計算能力來說還找不到。也許等量子計算機普及之後利用量子演算法就能找到了 &> &<

參見：

中國象棋的走法是有限的嗎？如果有限，有沒有先走或者後走的人必贏的可能？ - 數學

Solving chess

是不可戰勝的。但不等於會必然輸。如果雙方都下出最佳著法，守和和爭勝下法不同，風險也不同。卡爾森對鱈魚7，贏棋可能性1%都不到，但守和還是有一些希望的。慢棋，估計好好下，卡爾森執白能有40%和棋率，執黑能有10%的和棋率。

即便有一台算準所有可能性的電腦，你仍然有一些套路可以力爭守和。尤其是執白，還有一點希望。

所以，即使電腦算準了所有變化，也不是萬事大吉。電腦水平還是提升空間，它還需要尋找繼續提高勝率的辦法，在多種選擇中，選擇一些下法，導向對手不擅長的局面。

電腦是否會超越人腦並終結人腦一直是一個繞有興緻但又令人擔心的問題。最近的一個事件表明，電腦在戰勝人腦的進程中又向前跨出了一步。

看到上面談了很多, 有人認為棋譜(演算法)是人類交給機器的, 人類是機器的師傅, 自然應該人類更厲害. 那你輕視了計算機的發展, 在這幾十年里, 機器學習/遺傳演算法/分散式計算等技術的發展已經越來越完善, 人類逐漸的在告別向機器傳授特定領域的技巧, 而改為告訴機器已知問題的答案, 或給定目標準則並引入優選機制, 由機器去自我總結和進化, 推導出綜合或未知問題的最佳答案.

機器學習維基百科: 機器學習

遺傳演算法維基百科: 遺傳演算法

從Google的系統能自己學會如何找到一隻小貓開始(這可不是你相機的人臉識別, 沒有人給她貓臉的特徵, 而是餵了她數不清的照片, 告訴她這是貓或這不是貓, 她自己去總結貓的特徵), 到她再找到一隻狗或一個人都不會再遙遠了. 自從看了K.K的&<&<失控&>&>, 我覺得下棋或其他的智力遊戲誰戰勝誰將不重要了, 未來是人類與機器結合(配合)的共同進化.

----------------------------------------------------------- 補充點玩笑 -----------------------------------------------------------

但要小心Skynet(Skynet (Terminator))哦, 他可不單單想著跟你下象棋, 不知道哪天XFW(首字母為G是敏感詞?)會不會也產生意識發飆了.

演算法問題並沒有障礙，障礙只是機器性能問題。

有很多電腦程序，雖然人類中的頂級大師能戰勝它，但是業餘高手都幾乎不可能戰勝。

在很多事情上，比如單純的高精度計算，人類本來就不可能戰勝電腦。所以即使在象棋和國際象棋上，哪怕在圍棋上，人類也不能戰勝電腦了，也沒什麼可驚訝的，也並不說明人類就會被電腦控制。

電腦的話是一個尋找最優解的過程，與其說是它在思考怎麼和你下棋，倒不如說它在引誘你下棋

它走的每一步，都是它認為最容易達到最優解的步驟

而這個最優解，則取決於資料庫里的數據

而且電腦走棋最大的一個問題在於它是嚴格的，也就是其實是一個閉式解的問題，而人類走棋則不一樣，比方說走到了同樣一個棋局，電腦接下來的走法可能每次都是相同的，但是人類則可以走出不同的走法。

但是歸根結底，人類和電腦下棋等同於一個已經知道每道題答案的老師在看著學生作答一樣，如果學生只是老老實實答題，那麼答案全在老師預料之中。如果學生突然一下發散思維了，老師可能就會預料不及了

讓兩台電腦對著下，如果電腦下國際象棋的演算法中不存在隨機因素的話，那麼按理說每次下棋的套路都是一樣的。觀察結果，如果只有和棋，那沒辦法了，估計國際象棋的規則所限，在雙方都按照「最優策略」下的情況下得到的只有和棋；如果一方贏一方輸，那太好了，把贏棋的電腦那一方的棋譜記錄下來，然後讓人就按照這個棋譜跟電腦下，把把贏！~~如果電腦下國際象棋的演算法中有隨機因素的話，這個就會比較麻煩，但是可以從數學上證明國際象棋的不同的棋局數目是可數的，另外我不太了解國際象棋的規則是否有足夠嚴格的限制所謂的「磨棋」，如果限制足夠嚴格的話，那麼不同的能夠分出勝負和的棋局數目將會是有限的，儘管這個數字會很大。在默認不同的棋局數目是有限的情況下，我們考慮把一盤國際象棋的走法排成一棵（假想的）樹，樹的最底層的節點是所有的分出了勝負和的棋局。現在我們逆向考慮，先考慮「殘局」，同時做出一個斷言（或者也可以稱之為定義）：在進入「殘局」時，必有一方存在必勝策略（或者不輸策略）。（這個斷言應該可以完全轉化成用純圖論的語言來描述）。然後我們理論上就可以用純數學的手段去分析這棵（假想的）樹，找到進入「殘局」的結點等等，然後我們就會發現電腦是否會變的不可戰勝本質上只與國際象棋的規則有關，與「計算機性能的提升」與否無關。

我從象棋角度來說這個問題，想來從棋理上國象和圍棋也不會差太多。

象棋水平主要就是兩個東西一是算度，就是預測對手以後的幾步會怎麼走；二是形勢判斷，就是判斷走完了之後形勢和其他的形勢的優劣。

胡榮華老師說象棋的算度不難，難的是對形勢的判斷。因為面對一個局面，大部分招法是一看就行不通的，而剩下可走的就那麼十多步棋，而且其中壞棋還佔了一半，就算是業餘棋手，只要水平不差，一步一步來分析，只要給夠時間，心能沉下來，總能算出來。但是形勢判斷就不同，這沒有固定的套路和標準，完全是依賴對以前經歷過的盤面的記憶和感覺。而且有兩個特點，不能推理：由於雙方都可能走出漏著，所以不能說棋下贏了就是好局面，輸了就是壞局面；認識非常主觀：棋書上常說某盤棋中某一步「似劣實佳」的棋，就是說一般水平的棋手，甚至一般高手都感覺不好，但實際上是一步好棋的棋，而且高手之間也時不時達不成一致：某局面甲特大可能覺得是雙方互有顧忌的兩分局面，乙特大可能則覺得紅方稍有一些優勢，這就造成了對局面判斷的主觀性。

計算機的優勢在於窮舉，而劣勢在於感覺。

如果不加演算法優化，單用窮舉，每多預測一步就複雜十多倍，顯然不是目前摩爾定律所能追上的。這必然要求演算法進行優化，而優化實際上就是用某些辦法製造出計算機的「棋感」，然後根據「棋感」的優劣排除一些比較差的走法。但由於上面說的主觀性，這些優化演算法很有可能做的在一大部分情況下判斷正確，但在一些情況下卻把好棋誤判為臭棋而捨棄掉。目前電腦上常見的軟體都是做了優化的，可是把棋賽中見到的一些精彩的局面拿到電腦上模擬，也時常會出現電腦算不出的情況。當然，電腦最大的優勢在於不會犯低級錯誤，而人往往會在幾個小時的對弈之後由於疲憊走出隨手棋或者昏招。

以目前的情況來看，象棋比國象好一點，主要原因是象棋的殘局比國象複雜得多，越往後越難預測，而圍棋的複雜度比兩者都要高很多，目前還遠超電腦的計算能力。

圍棋的複雜度y與路數x是個鐘形曲線，中間高，兩頭低。

我簡單的科普說法，非嚴格證明：棋盤遠大於19路時，角對邊，邊對中腹的影響力都越來越弱化，一顆子在邊、中腹的存活難度大大低於19路。整盤棋會裂成為局部戰鬥，而和全局脫離。

另外，出土過歷史上的多於19的棋盤，後來剩下了19路。

致匿名id：

回復匿名用戶（作者）：是你主張就是你舉證好不好？你既然先給圍棋下了這個結論，那你對圍棋了解多少？你的圍棋棋力如何？你就有必要給出個相應的答案。

一個國際象棋大師，再強大，再不可戰勝，運算元能力再強，也只是人類而已，人類的運算能力終有盡頭，他的能力反而受到了肉體的局限。他面對的是什麼？他面對的是一堆專研於博弈論，用數學去研究遊戲，拿game當research field當飯吃的，可能戰鬥力提升1%就可以發論文的研究人員，而當這些人類中最智慧的研究者組合在一起形成了演算法，再配合來自於材料學，電力學等等等等專家和研究者的智力結晶組成的cpu，最終才是看上去棋力無比強大的計算機。

所以，人類國際象棋玩家輸給電腦，是一件早晚會發生的事情。或者說，象棋大師沒有輸給電腦，他輸給的是人類智慧和汗水累積起來的奇蹟。

更糟糕的是，人類的棋手受到壽命的局限，一個新人，學10年棋，戰鬥到60歲，已經精力不再，而計算機的演進並不受時間地點的限制，而且經驗和智慧可以複製。

智力上的失敗，從我們發明算盤就是已經註定了的事情，100位的加法這一比賽項目上，人類顯然不能戰勝算盤。而圍棋，只是另一個加法而已

這個問題的最高票答案應該是不對的。

人是有可能打敗計算機的。或者準備的說，一個棋手是有可能打敗無數個大師的聯手。人不是輸給機器，是輸給無數過往大師的綜合。

首先一個問題：國際象棋有沒有先手必勝的走法？

答案是沒有。

一旦發現了這樣的走法這個遊戲也就沒有意義了。

計算機的運算能力並不是無窮的。假設計算機能夠運算到30步後的所有形式共計100萬億種，那麼請問他怎樣選出對自己最優的局面？

注意：這個時候的計算機已經不能再繼續運算更多了。

所以這個時候計算機就會去對應的選擇他儲存的棋譜。根據這些棋譜去選擇最優的解法。比如在國際象棋棋譜中時常會有先人在復盤的時候標註符號：「？」「！」，甚至「！！！」來表示一步棋對以後局勢的影響。

這些棋譜經歷了諸多專家長時間的反覆修訂絕大多數的情況下是幾乎不可能出錯的。一個人想要在短時間內擊敗這些專家的判斷是幾乎不可能的。

但是，在計算機中儲存的大量棋譜當中會不會有錯誤？

一定會。

所以只要我們能夠拿到這個資料庫，找出裡面的引用棋譜錯誤，依舊可能獲勝。當然，事實上棋手拿不到這樣的保密數據。而且事實上過往的棋譜依舊是經過計算機本身演算法的反覆修訂的。

所以為了擊敗計算機，棋手需要的就是研發新的，計算機內沒有儲存的布局。計算機在面臨新的對局時是沒有辦法拿出固有的取勝套路的。這個時候計算機依靠的就是「人設計的權重」來判斷局面。你要是有這些權重，你就可以擊敗他。

既然存在可能，那麼事實上只要你運氣夠好，能力夠強，依舊是有希望戰勝超級計算機的。尤其是在一局定勝負的情況下。

事實上，卡斯帕羅夫贏過深藍一局。在那場世紀對決當中，他贏了第一局。最後也只是2.5比3.5惜敗。（一勝三平兩負）。

一個人，輸給無數程序員和過往的所有偉大棋手，真的不是件丟臉的事情。人不是輸給機器，因為那台機器並沒有自主的智慧。

有沒人能夠在一個領域裡面比過往的人的綜合都強？

我覺得有可能。

因為已經過去的人是沒有能力再創新的。

--------------------------------------------------

更新：本來更新是想詳細介紹下幾個演算法和設計難點的，看了評論之後發現好多人都分不清楚科幻和科學了。總覺得計算機是可以有超越人類的自主思維的。我反正是真沒辦法了。