圍棋、國際象棋、中國象棋存在必定不敗的下法嗎？

01-02

雖然以目前的計算能力還無法模擬出所有可能的結果，但我們能否從理論上證明這樣一個或是一組最優解的存在與否。目前一些較簡單的殘局都已經得出了必勝的解法，那我們是否可以進一步推廣到更複雜的殘局甚至全局也存在著必勝的解法？

（參考文獻稍後補充）對於圍棋，目前已有的結論是：

5路棋盤，黑先，存在策略使得黑棋可以把白棋吃光；（這個結果應該說很直觀）

6路棋盤，黑先，無貼目，雙方最佳應對，黑勝2目。（有不少複雜變化，並不像想像的容易）

7路棋盤尚無定論。已經有一個結果，但未得到充分證明。

7路及以下的各種長方形棋盤（1*7，2*6，等等）多數有雙方最佳策略下黑勝x目的結論。

7路以上棋盤的相關結論遙遙無期。事實上9路棋盤到底應該貼多少目合適也是一個困難的問題。19路棋盤有大量職業對局統計來保證6.5目/3.75子貼目的相對公平，但是9路棋盤沒有這樣的數據。

至於19路棋盤，恐怕是一個未來的計算機也難以解的問題（注意是「解」，而不是戰勝所有人類。）

對於這類信息透明，沒隨機性質的零和遊戲，當然在理論上是有最優解。

只需要用Minimax演算法遍歷整個遊戲樹便可以，問題是這些遊戲樹的節點太多。

計算一些遊戲的所有可能局面會超出宇宙預計的壽命，見 http://en.wikipedia.org/wiki/Go_and_mathematics。

首先，對於雙方信息完全公開的零和遊戲而言，必定有一方存在必不敗策略。

目前來說，圍棋若不貼目，則黑有必勝策略的置信度是極高的。統計職業對局可以發現，若按黑不貼目計算，則黑勝率達85%以上，考慮到人類棋手不可避免的在對局中有所失誤，至少可以說圍棋中黑有壓倒性的優勢。因此現在日本和韓國規則規定黑貼6.5目，中國規則規定黑貼7.5目，以使黑白雙方勝率接近50%。不過值得注意的是，圍棋中目數一定是整數，故無論是貼6.5還是7.5，一般都不會出現平局（有極為稀少的平局情況，未知是否有必定導致此種情形的策略，不過既然極為稀少，想來應該是沒有的）。因此現代圍棋規則下仍然有一方必勝，只不過是黑必勝還是白必勝就很難說了，考慮到圍棋本身的複雜度（目前甚至連9*9的小棋盤也沒有明確結論），在可預見的將來恐怕誰也說不清。

中國象棋和國際象棋的規則、複雜度都極為相似，AI的棋力也早已超過人類頂級棋手很多個級別，但仍然很難確認是否存在必勝策略。目前頂級的幾個AI對局，先手勝率約35%，後手勝率約25%，平局率約40%。如此來看不太可能是後手必勝，但究竟是先手勝，又或是後手可以保和，短期內恐怕也是一個謎了。

我很希望19路圍棋能有最優解。

但是太陽系的每個原子都儲存一種可能的話。

對19路圍棋的變化也只是很小一部分吧。

所以我肯定是看不見了。

另：

反對將國際象棋、象棋同圍棋按一種演算法進行運算。

他們不是一種遊戲。

三種情況，必居其一：

* 先手必勝

* 先手不敗(如果雙方應對無誤的話，和棋)

* 後手必勝(先手會被逼死)

具體哪種，不知道。因為組合太多，目前還沒誰能窮舉出來。

但是，考慮到普遍認為先手有優勢，後手必勝的可能性不大。

可以證明：一個遊戲雙方每一步均是有限種選擇，並且遊戲只有勝負，沒有和局的情況下，必然存在必勝策略。

圍棋之類的太複雜了，必勝策略存不存在沒有什麼意義，反正一般情況下也找不到

目前的中國象棋軟體，切人類特級大師基本無懸念。

中國象棋和國際象棋已經有人論證過，存在最優招（不止一條路徑），先手必勝/必和。但目前還不知道必勝還是必和。從目前的象棋軟體和象棋理論的發展來看，先手必和的可能性較大。

圍棋過於複雜，暫時還不清楚。

目前國象，中象的計算機採用小的程序能打敗人類，基本可以認為存在最佳變化或者最佳分支。圍棋的話變化過於複雜，目前的計算機尚不能暴力破解或者說窮舉，那我們可以認為目前圍棋沒有必勝下法。

圍棋決策樹太過龐大，現在的計算機能力還不能令人滿意地求解。

其它棋類一般是minimax+alpha-beta剪枝來搜索最優著法。

其實這個問題，反而是最難的圍棋是有絕對優勢的必勝法的。當然，現在為了消弱這個絕對優勢我們一般採取的是貼目的方法解決，也就是說依靠圍棋本身是沒有辦法通過技術解決這個優勢的。這個必勝法就是「秀策的尖」，看過棋魂的應該知道，就是SAI的上一個主人本因坊秀策的無敵妙手，秀策憑藉這個妙手可以做到執黑子不敗的戰績。秀策的尖保證了黑子在開局的時候有一個高達數目的優勢，如果在平等技術的條件下，這個優勢是很難追上的。

在國際象棋中，儘管計算機引擎強大到人類棋手也難以應付，但也尚未計算出全局的最優解。事實上，哪怕是幾十步殺的排局，引擎也不能很快地算出來。

象棋大師水平以上基本上都認同一個觀點，只要時間充分而且沖著下和去，對手基本鐵定沒辦法（對手唯一的希望是守和方一時昏頭）。

之所以還能分出勝負是因為大家都想求勝。

從現代數學的理論上講：

我們把常接觸的棋類，比方說只討論圍棋，中國象棋和國際象棋。把它們的規則和行為都抽象出來，並且假設：他們的規則都是完善、正確的，沒有漏洞，也沒有衝突。

漏洞既是存在未定義的區間，一旦運算進行到這個區間程序就會跑飛。

衝突既是存在重複定義的區間，一旦運算進行到這個區間就會矛盾，程序會崩潰。

注意！！這是非常理想化的情況，也是到現在都沒有「能思考」的電腦AI的根本原因！！！

建立一個空間，在這個空間中存在一個定義域，一個值域以及從定義域到值域的對應規則。

這些棋類都受到棋盤和棋子在物理上的約束，這個空間一定是整型的，一定是有限的。

這些棋類都受到單次行為的約束，一次行為對應唯一的一個結果。所以空間中的定義域與值域的對應函數是一一對應的。

到這裡能理解嗎？

（如果有人提出：有可能10回合前白棋領先黑棋10目，10回合後白棋又領先黑棋10目了，就不是一一對應了，我在這裡解釋一下，

如果是我來定義圍棋的值域，我會定義值域中的一個值V=（回合數，白棋數，棋子數，棋子位置，白棋領先目數），10回合前的V1=(13,20,13,{(x1,y1);(x2,y2);…（x33,y33)},10)，10回合後的V2=(23,25,17,{(x1,y1);(x2,y2);…（x42,y42)},10)。這樣就是一一對應了）

好的接下來才是重頭戲：

國際象棋、中國象棋和圍棋都有兩個玩家，雖然棋盤上的行為不斷累加，空間中的總值是不斷增加的，但是為了判定輸贏，兩個玩家的值域必須被分開，或者以一回合（2次行為）為單位計算值域。

這樣會有一個問題，比方說圍棋，黑棋先手在19X19的棋盤上落子了，白棋的選擇就不再是19X19了，少了一個！這是非常明顯的不公平。這個問題也存在於國際象棋和中國象棋中，先攻的一方先佔據資源。

我們把圍棋的棋盤極端化：兩個人在一個1X1的棋盤上下圍棋，其餘規則不變，誰勝誰負顯而易見：誰先誰勝。

1X1太極端了，我們改成1X19，答案如何呢？答案是：佔據了最中間點的一方勝利。那先手只需要佔據最中間的點就勝利了。

我們把這種現象抽象出來，給予棋盤上的每個點位不同的勝負值即可。

（當然19X19的圍棋並沒有那麼簡單，因為圍棋是有「形狀」的概念的，我舉1X1和1X19的例子其實限制了圍棋的規則，用點線遊戲偷換了點面遊戲的勝負概念，規避了這個問題）

我想說的是，先手玩家的確存在優勢，所以圍棋是要讓子的，在一定程度上可以說解決了這個問題。

那國際象棋和中國象棋呢？目前在比賽中對先後手的公平問題只能用行棋時間來緩解。在規則本身上是沒有作出讓步的。

從某個角度上講，對這兩種棋來說棋子的多寡不如棋子的功能和位置對勝負關係的影響大。棋手們的單次行為要考慮：是否滿足行棋條件F（棋子名，棋子功能，棋子初位置，條件布爾值），行為T（棋子名，棋子初位置，棋子末位置，棋子功能）造成的局面Y（棋子狀態集合，將軍布爾值），有經驗的棋手要考慮對手下一回合的活棋數，可動棋的行棋可能性Y+的集合，再考慮自己應對各種Y+所造成的Y++，乃至於1、2...N回合之後的局面Yn。直至某一個回合，可動棋存在並滿足行棋條件Fx的條件布爾值=1，經過Tx行為造成的Yx的將軍布爾值=1。

把規則分解成函數，把動作和局面用特殊的數據結構存儲起來。我們假設以上的設計都是成立的，我們已經成功地設計出了一個完整的演算法來模擬行棋的思考。只要有一台計算能力足夠強的計算機，通過把演算法和數據結構整合起來，輸入到計算機中。會出現什麼狀況呢？

圍棋會百分之百存在「最優發展」，計算機能夠通過計算分析每個未落子的點位根據已有的棋形所具有的價值，來判斷哪個點位落子能夠收益最大化。通過向計算機輸入棋譜，計算機甚至能判斷目前局面上的棋形是否是陷阱，點位上的收益值是可以不斷通過修改公式來完善賦值的。

最後決定是否保持優勢或者減少劣勢的唯一標準是：先手讓子的數目。（如果規定先手讓100目，別說電腦了，神仙執先也得輸）如果先手讓多了，電腦執後手的「最優發展」一定會贏；如果先手讓少了，電腦執先的「最優發展」一定贏。反之，則一定會以最少的目數輸掉。

我們假設最後這一條可變的標準也確定下來了並且完美地解決了先手優勢的問題：比如先手讓子100目，「最優發展」就不一定能贏了，這裡的理論極限是和棋。現代圍棋大賽中存在著各種各樣的避免和棋的規則，像貼目後目數一樣，誰下最後一子誰勝這種單純根據開始到最後奇偶數手來判斷勝負的因素是與棋局分值無關的，電腦也能接受這種勝負。

特別提出，在完全對等的遊戲中增加杜絕和棋的規則，是對遊戲的一種破壞：比如貼目X又3/4目。必然對先手或者後手有至少1/4目的不公平。

之前說的規則當中不可以有矛盾，就是當你規定：貼目X又3/4時先手對後手優勢為0。這條規則與本身數域是整形的遊戲性質是衝突的，電腦公平地進行「最優運算」到最後卻被判負了……它會接受不了崩潰死機的……

說完了圍棋……象棋還有必要說嗎？象棋連平衡先手優勢的規則都沒有……是存在漏洞的遊戲規則。所以象棋的「最優行棋」程序一定會存在兩種結果：

1，這個漏洞是穩定的，有限的，整型的，可以利用這個漏洞得到一個先手一定會贏的行棋法。這也就宣告了這個遊戲本身是一個失敗的遊戲。

2，這個漏洞是不穩定的，演算法在這個漏洞中會跑飛到莫名其妙不明意義的數據中去，程序就死在這裡了。

從編程的角度上講，其實象棋的規則比圍棋複雜得多，因為參數比圍棋多。人們普遍覺得圍棋更精妙更複雜的原因1是圍棋的棋盤比象棋大得多，形成的形狀比象棋多；2是在象棋中是沒有加法的，棋子的數目只減不增，越是殘局行棋可能性越少計算量越少。如果把象棋改成19X19，棋子的數目應對棋盤，還能往上添子兒……那將是噩夢遊戲。

——————————————————————————————————

現在正式地回答你的問題：

以目前人類的數學理論來講，

圍棋根據先手讓子的規則是存在最優下法的，是否贏取決於讓子的數目，總之能達到「輸得最少」。

象棋（中國象棋/國際象棋）都「有可能」存在最優下法，並且一旦存在，就一定會導致先手獲勝。

以目前人類的數學能力來講，

人類只證明了五子棋是存在先手必勝的下法的，這份證明同時否認了五子棋這個遊戲本身，直到禁手規則出現才挽救了這個遊戲。

人類還沒有研發出能證明圍棋極限的儀器，樓上的哥們說的：宇宙級內存，只是可能遇到的一個阻礙。最麻煩的地方還在於點陣價值的即時計算，會受到「未形成的形狀」的影響。也就是說可想像的數學模型對點陣價值的計算公式是不正確的——很有可能正在形成一個陷阱。

目前的計算機的能力局限於：判斷1/0—1,作出行動。遇到無法判斷1/0的情況——硬碟中沒有存儲過這個形狀，就只能依照已有的公式計算，一旦這是一個棋手新發明的陷阱，這次計算就是錯誤的，並將導致接下來的局勢無法挽回。

但是19X19大小的棋盤能形成的黑白棋形狀何止天文數字！還未出現過的棋形比起已經出現過的又何止天文數字的倍數！人類不僅需要宇宙級的內存，還需要宇宙級的硬碟和宇宙級的棋譜！

可是這些棋譜都還未誕生_(:з」∠)_也就宣布了寫出完全正確的計算公式是：不可能的。

沒有正確的公式這個程序就不會誕生的。

只是如今的計算機已經能接受「輸棋」這件事了，這是一件非常可怕的事，這意味著計算機開始有自我記憶能力了，並很有可能在將來誕生反省的能力：這陷阱我中過，這辦法我試過……人類啊……快醒醒……

人類正在研發解析象棋極限的儀器，難題在於徹底地分析象棋的參數，如果這些參數是有限的，穩定的，規則的漏洞只會成為證明遊戲極限的利器（就像五子棋）。如果這些參數在漏洞區間內是無限的，有多義性或多值性的……也會被證明：象棋不存在必勝行棋，從而否定先手優勢。用矛盾來解決漏洞……這是人類經常用來填補「無法解釋的神秘現象」的辦法。

你要相信進步的人類遲早有一天會證明：古人的遊戲不過如此，這些遊戲存在著他們的極限。

也要相信這些古人留下來的遊戲的意義：遊戲是給人玩的，不是給數學理論，也不是給計算機玩的，只有人類才能在輸贏中找到快樂，找到朋友，找到榮耀與自信。

否則為什麼你看了我分析的這麼一大堆讓電腦玩遊戲的答案會覺得這麼蛋疼？

看了上面不少回答，大多從程序運行的角度進行闡述，沒有一個數學上的證明，略為不美。上面有2位答友都已提到可以證明存在必勝策略，其實這個證明並不複雜（正因如此，當年我和小夥伴們都驚呆了），錄於此供參考。

求證:一種兩人對弈遊戲滿足

1，每一步只有有限種選擇；

2，遊戲在有限步後必以某方取勝結束；

則兩人中的某個人必有必勝策略。

證明:假設遊戲至多進行n步就結束，對n進行歸納。

n=1，遊戲至多只進行1步，顯然某方有必勝策略。

設n=k結論成立。n=k+1時，設雙方為A,B,A為先手開步，則A只有有限種選擇，不妨設為p種。在A開步後，遊戲只餘下k步，則由歸納假設，這樣的遊戲A,B中的一方存在必勝策略。

下面分類討論:

1，若在A的p種開步選擇中，存在一種選擇，使得之後k步遊戲A必勝，則A進行這種開步選擇，則A對k+1步的原遊戲已經有必勝策略。

2，若p種選擇，都使得之後的k步遊戲都是B有必勝策略，則顯然B對k+1步的原遊戲已經有必勝策略。

綜上，由歸納原理，雙方中的一方必有必勝策略，證畢。

如果條件將必勝改為不敗，也可作類似證明。所以我們得出結論:圍棋比賽中，必有一方有必勝策略。象棋、國際象棋比賽中，總有一方有不敗策略。

數學上可以證明存在，只是描述這樣的下法大概需要宇宙級的內存

Maybe quantum computer can solve it in the fufufufuture.

如果雙方都按最優策略來下棋的話我猜結果是:

1)圍棋黑每次贏白固定目數(不貼目的話)

2)中國象棋雙方和棋，兩個AI最後卡在N個局面里無限循環(N個局面隨機出現)(有點像隱馬爾科夫鏈模型hhhh概率取決於演算法)

3)國際象棋估計和中國象棋差不多

接下來就是等alphago什麼時候迭代到接近最優解啦

我覺得沒有必定不敗的走法，還是得見招拆招吧。

目前圍棋的人工AI水平僅達到業餘1段-2段這個水平，約相當於正常智力的成年人學習2,3年即可達到的水平。最強的圍棋職業棋手可以讓最強AI8-9個子，就連我這種業餘5段都可以讓最強AI6個子左右。圍棋的變化過於複雜，且機制完全不同於國際象棋，沒辦法用深藍的類似窮舉法的手段處理圍棋的問題，簡單的說19*19的空白棋盤，子力越來越多，在布局至中盤和官子前期變化達到峰值，而國際象棋比8*8且一開始就佔了32個格子，且子力越下越少，接近殘局有必然解。