圍棋有沒有必勝策略?

理論上來說,圍棋有沒有必勝策略?

補充:先手貼目從上古時代的零一直增加到現在的七目半,是否說明了正在向必勝策略逼近,未來貼目是否還會繼續增加?


簡單回答:存在必勝策略,可以證明存在必勝策略;但是人類現在沒有找到必勝策略,在可以看到的將來也很可能找不到必勝策略。
解釋:
「圍棋是否存在必勝策略」這一問題其實是一個並不複雜的數學問題,不過其中有一個難點。
我們首先需要以下這個重要定理:

策梅洛定理(英語:Zermelo"s theorem)是博弈論的一條定理,以恩斯特·策梅洛命名。定理表示在二人的有限遊戲中,如果雙方皆擁有完全的資訊,並且運氣因素並不牽涉在遊戲中,那先行或後行者當一必有一方有必勝/必不敗的策略。若運用至國際象棋,則策梅洛定理表示「要麼黑方有必勝之策略、要麼白方有必勝之策略、要麼雙方也有必不敗之策略」。

以上是策梅洛定理的非正式陳述。嚴格的陳述涉及博弈論的一些術語,稍微複雜,不過在這裡非正式陳述就足夠了。注意到,和國際象棋一樣,圍棋也是「二人、完全資訊、不涉及運氣因素」的回合制遊戲。
這裡唯一有可能產生爭議的地方是圍棋是否為「有限遊戲」,即一盤圍棋是否總會在有限步之內結束。這個小問題涉及到圍棋規則。目前圍棋界有中國規則、日本規則、韓國規則、應氏規則等主流規則,也有美國規則、紐西蘭規則等改進版。這些規則中,除了數目和數子的差異之外,另一個主要差異在於「禁全同」,即是否「禁止全局同形再現」。而圍棋規則研究者、數學家和計算機科學家一般公認採用「禁全同」的中國規則和類似規則(美國、紐西蘭)為邏輯自洽的規則,而日本、韓國規則有邏輯上的缺陷。

2002中國現行圍棋規則
-------------------
第一章 總則
第6條 禁止全局同形
著子後不得使對方重複面臨曾出現過的局面

以上即所謂「禁全同」規則。關於「禁全同」可能造成的所謂「悖論」,請移步你所知道的最冷的圍棋知識是什麼? - 專吃劉小羊的回答。
嚴格採取「禁全同」的中國規則下,三劫循環不判和,而等效於打一個單劫。包括長生、雙提二子等特殊棋形類似。這樣一來,與3又3/4子的貼子(貼目)一起,和棋(無勝負)就不可能出現了。(當然現有中國規則在執行中仍然將三劫循環判為無勝負,這只是一個暫時的妥協。)
同時,圍棋就變成了一個妥妥的有限遊戲。事實上,計算機科學家已經給出了一個(19路)圍棋所有可能局面的上界:2.08*10^170 (Counting Legal Positions in Go)。
那麼我們已經解決了採用策梅洛定理的所有小前提。根據策梅洛定理,在02版中國規則(黑貼3又3/4子,嚴格禁全同)下,對於19路圍棋,以下兩者之一有且只有一個成立:
1、黑方(先行者)有必勝策略;
2、白方(後行者)有必勝策略;
注意到,因為貼目(3.75子/7.5目)為非整數,和棋不存在,所以必不敗策略等價於必勝策略。
那麼到底是1還是2成立呢?我們不知道,也許我們很久以後也不能知道。
要證明其中之一成立,需要對圍棋的遊戲樹進行窮舉。然而10^170僅僅是局面(position)的數量而已,遊戲樹(棋局總數)是對所有局面的排列,不知道大到哪裡去了,窮舉談何容易!在計算機產生革命性的變化之前恐怕是不用想了。
然而,我們可以做出這樣一個大膽的猜測:
存在一個非負整數X, 使得:
1、當貼目小於X時,黑方有必勝策略;
2、當貼目大於X時,白方有必勝策略;
3、當貼目等於X時,雙方最佳應對,結果是和棋。

直觀上這很可能是對的,不過我不會證。
-----------------------------更新割----------------------------------
我嘗試證明一下,不知道對不對。第一遍閱讀以下部分可以直接跳過,哈哈
事實1:貼目為-361目(即白貼黑361目)時黑棋不敗;
事實2:貼目為361目時白棋不敗;
定理(策梅洛):當貼目值為Y時(Y為任意整數),以下三者有且只有一個成立:
a)黑棋有必勝策略;b)白棋有必勝策略;c)黑白雙方均有不敗策略,即最佳應對下雙方為和棋。
引理1:假設貼目為X時黑棋有不敗策略(X為任意整數),那麼貼目為X-1時黑棋有必勝策略;
同樣地,假設貼目為X時白棋有不敗策略,那麼貼目為X+1時白棋有必勝策略。
證明:假設貼目為X時黑棋有不敗策略,即存在一個黑方策略,使得(無論白棋怎麼下),黑方至少盤面X目;那麼黑棋在貼目為X-1時採取同樣策略即可獲勝。
推論1:假設貼目為X時雙方均有不敗策略,那麼貼目小於X時黑方有必勝策略,貼目大於X時白方有不敗策略。
證明:數學歸納法
引理2:假設貼目為X時黑棋有必勝策略,那麼貼目為X+1時以下兩者有且只有一個成立:
a)黑棋有必勝策略;b)黑白雙方均有不敗策略;
證明: 假設貼X目黑必勝。那麼對於黑棋,存在一種策略,使得不管白方怎麼應對,黑方在終局時都能夠至少盤面X+1目(否則貼X目黑棋不是必勝)。那麼在貼X+1目的情況下,黑棋只需採取相同的策略就可以至少保住和棋,即白方不能必勝。
定理:存在一個整數X(-361&1、當貼目小於X時,黑方有必勝策略;
2、當貼目大於X時,白方有必勝策略;
3、當貼目等於X時,雙方最佳應對,結果是和棋。
證明:假設不存在這樣的X。根據事實1和引理2,可以得出當貼目Y滿足(-361&這裡只能證明X是一個整數,而不是正整數。雖然直觀上看X幾乎一定是個自然數,但是想要證明黑棋在不貼目的情況下有不敗策略好像也很難(還是不可能?)。注意模仿棋可以被輕易破解。
-----------------------------------------------------------------------------
從現在棋手勝率的統計來看,這個X很可能就在7-8左右。
「柯潔認為貼6目半都多了。。僅供參考」
然而我們已經確定的是什麼呢?

First player scores MxN Go

19路不知道誰贏,小棋盤總知道誰贏吧。
從1*1到5*5的棋盤,包括一些長方形的(5*6,2*10, 等等)棋盤,學者已經通過窮舉找到了上述的X值,都在以上鏈接里。不管怎麼樣,這也是一個進步吧。有關於小棋盤上圍棋的拆解,可以移步一下答案。
人類對棋牌類遊戲的拆解到了什麼地步? - 專吃劉小羊的回答
----------------------------------------更新割---------------------------------
插播一篇文學作品。劉慈欣《詩云》節選

  「那好,我就讓你這個白痴蟲子看看它有多麼精練!」 大牙說著走到桌前,用爪指著上面的棋盤說:「你們管這種無聊的遊戲叫什麼,哦,圍棋,這上面有多少個交叉點?」
  「縱橫各19行,共361點。」
  「很好,每點上可以放黑子和白子或空著,共三種狀態,這樣,每一個棋局,就可以看作由三個漢字寫成的一首19行361個字的詩。」
  「這比喻很妙。」
  「那麼,窮盡這三個漢字在這種詩上的組合,總共能寫出多少首詩呢?讓我告訴你:3的361次冪,或者說,嗯,我想想,10的172次冪!」
  「這……很多嗎?」
  「白痴!」大牙第三次罵出這個詞,「宇宙中的全部原子只有……啊——」它氣惱得說不下去了。
  「有多少?」伊依仍然是那副傻樣。
  「只有10的80次冪個!你個白痴蟲子啊——」
  直到這時,伊依才表現出了一點兒驚奇:「你是說,如果一個原子存貯一首詩,用光宇宙中的所有原子,還存不完他的量子計算機寫出的那些詩?」
  「差遠呢!差10的92次冪呢!再說,一個原子哪能存下一首詩?人類蟲子的存貯器,存一首詩用的原子數可能比你們的人口都多,至於我們,用單個原子存貯一位二進位還僅僅處於實驗室階段……唉。」
  「使者,在這一點上是你目光短淺了,想像力不足,是吞食帝國技術進步緩慢的原因之一。」李白笑著說,「使用基於量子多態疊加原理的量子存貯器,只用很少量的物質就可以存下那些詩,當然,量子存貯不太穩定,為了永久保存那些詩作,還需要與更傳統的存貯技術結合使用,即使這樣,製造存貯器需要的物質量也是很少的。」


首先,謝邀。這是我第一個受邀請的回答,感謝 @taphor 的邀請。我盡我所言,千萬不要較真。

感謝@Adder的提醒。也算比較清晰的認識到了我論述的問題所在。回答確實有問題。似乎是出在——我默認是有必勝策論,可是在每一個時代卻又沒有被發現。而時代的進步讓我們不斷去發現這個必勝策略,或者說發現接近必勝策略的方法,從而更改規則來限制這個策略。可畢竟策略是建立在規則和棋力之上。所以到底該如何制定規則好讓這個策略在絕對棋力上可以忽略不計近乎公平公正是個大問題啊。

最直觀的就是你無法控制變數讓兩個完全一樣水平的人下棋比較。縱然是計算機也不行。再其次,就算找到了一些捷徑,也會立馬更改規則,帶來一些革命化的變化。畢竟沒有人會玩不公平的遊戲。當一個遊戲已經可以單純的通過訓練策略就可以取勝的時候,這個遊戲基本上已經要衰落了。圍棋當下能平衡這個策略最有效的辦法也就只有貼目了。可是貼目依舊不是最公平的。它實際上促進了黑的布局以攻為首,白以守為先。很難跳出來。黑上來就守,因為貼目的規則,肯定被動。所以,貼目其實是一種平衡的不能算辦法的辦法。但也正是這個,限制了黑先行的優勢。避免了所謂的「必勝策略」。

好的,以下是原答案,保留好了~矛盾的說,我又希望,渴求出必勝的策略,又希望沒有這策略好讓圍棋一直保留一個神聖的地位。願圍棋越來越好~

~~~~~~~~~~~~~~~~~~~我是分割線~~~~~~~~~~~~~~~~~~~

話說我有補充過答案。我說」沒有必勝策略「是建立在當下這個時代規則前提上。一旦發現有那麼一點可能必勝的策略,遊戲都會更改規則進一步限制。或貼更多目,或別的什麼。否則就會讓這個遊戲走向衰亡。

難道談論是否有必勝策略已經可以凌駕於遊戲規則限制之上了嗎?畢竟不會有人去玩一個從最開始就不公平,就會必勝活必輸的遊戲。可感覺似乎不少人不理解,單純的把我的答案理解為「沒有必勝策略「了啊。我是覺得有沒有必勝策略有前提。

感謝知友 @神之左手 的提醒,會不會存在有人感覺出必勝策略卻不提出來,然後繼續下棋的可能呢?畢竟他知道策略,別人不知道,那麼就算他處在了不利的一方,依舊可以扭轉劣勢。假設黑棋有優勢,他執黑必勝;白棋上來就有劣勢,可是他可以利用自己知道的策略來扭轉局面,畢竟對面和他下棋的人不知道啊。讓我想到了秀策御城棋十九連勝,終生執黑不敗的故事了。這樣看來吳清源大師和木谷實大師著實偉大。率先提出了貼目的理論來限制執黑的優勢啊。不爭了,不管有沒有必勝的策略,都隨它吧。以我的棋力也感受不到其中的奧妙,湊湊熱鬧罷了。

以下是原答案

作為一個非職業棋手,業餘圍棋愛好者來說,不管有沒有,我都是希望它沒有的。但凡一個遊戲,有了必勝的策略,必然會是這個遊戲的終點所在。或改變規則,或增添限制,從而延長這個遊戲的壽命。否則,這個遊戲就要結束了。即便是籃球,當奧尼爾出現,也會改變油漆區面積;當球員三分水平普遍提高,也會拉遠三分線,這是一個道理。

斗獸棋是否已經衰落?如果是,為什麼? - 知乎用戶的回答
這個答案是關於斗獸棋為什麼衰落的。具體詳見答案。簡而言之就是因為這種棋類慢慢被人發現有必勝的把握才逐漸衰落。遊戲,不管是什麼遊戲,重在公平競爭。重在利用有限的規則發揮無限的智慧。棋類多是兩個人對弈來角逐勝負。當一方可以跨越棋力高低且明顯有必勝的把握時,那棋盤對面的人存在的必要是幹什麼的呢?如果執黑有必勝的策略,以後大小賽事將沒有人願意執白,反之亦然。至少在每一個對應的時代里,執黑執白都能做到大體的公平,將執黑先行的優勢盡量通過規則來限制,好使得對弈雙方大體公正。這個規則目前來看時貼目。

這也就是為什麼在上世紀初吳清源大師和木谷實大師決定黑棋貼目的一個重要原因所在。發現了圍棋這個遊戲當下所有的規則里,不能做到儘可能的公平,會讓先手之人有更大的勝算,有更多的可乘之機,更多的先手之利。我等圍棋界的凡夫俗子是看不出什麼,可人家是圍棋界泰山北斗一樣的人物,是圍棋史金字塔頂端的人。他們覺得黑棋需要貼目,自然有他們的道理。至於貼多少合適,就不是我們能妄言的了。而之所以貼目,就是因為他們覺得在不貼目的情況下,同等條件下,黑棋優勢比白棋大。

所以,說來說去,規則是會隨著時代的進步,遊戲的進步而改動的。想想中國古代的圍棋還有座子制度。後來學習了日本,取消了座子,極大的豐富了圍棋的布局,增多了更多的定式,這是對中國圍棋史有著重大意義的。讓圍棋這門遊戲,這門藝術,這門競技有更大的發揮空間。而最初,眾所周知,圍棋也並非19道。有過17道,也有過21道。最後確定19道也是因為19道能最公平的保證實地與外勢的平衡。換句話說,如果17道,往往好實地就有必勝策略;21道,好外勢作戰者就更容易取勝。同理,後來的貼目也是圍棋的進步,為了更好的發展這門遊戲,藝術,競技。

綜上,圍棋在任何一個當下的時代里沒有必勝策略。準確的說,有個大前提,在歷史長河下每一個時代單獨拿出來是沒有的。就目前而言,在當下的規則下,同等競技水平,執黑執白的勝率是相當的。如果發現哪天即使貼目6目半或者7目半黑棋依舊有必勝的策略,一定會相應的修改規則,譬如貼更多的目之類,好達到一種平衡,使得圍棋繼續延續下去。倘若有必勝的辦法,也不會是這麼比例。真是掌握必勝策略也是建立在強大的棋力之上的。棋力沒達到就是知道了又如何?如果所謂的必勝策略可以無視棋力。讓一個剛學會下棋的人,讓其用這種策略和一個職業棋手下,結果不相上下甚至贏了,那麼我絕對相信有策略,甚至以普及這遊戲就玩完了,徹底衰敗,挽救都來不及。但凡不能無視棋力的,無非是優劣多少的差距。還是建立在棋力之上。而這個差距呢,又可以通過規則進行限制。在不同的時代里,其實大體能公平。真是萬一,一旦有高競技水平的人發現了一丟丟的破綻,一點點的必勝策略,要麼遊戲衰落,要麼更改規則,像程序員一樣去改BUG,好修復這門遊戲,讓它繼續在歷史的長河裡延續。

這裡插一個腦洞,前面說了吳清源和木谷實大師的偉大之處。倘若真有可能出現必勝策略,且建立在棋力之上,豈不是只有圍棋金字塔頂端的人才能發現?不然的話為什麼吳清源和木谷實能夠推行貼目最後成功呢?那會不會在這金字塔頂端的人中發現了這一必勝策略,然而他又藏著掖著不說,早就看出來需要貼目6目半或者7目半,可是那時候貼目沒有到這個數的時候他也不說出來,利用這個便捷去取勝呢?這樣就細思極恐了。

人類對棋牌類遊戲的拆解到了什麼地步? - 須盡歡的回答 反推,如果真是有必勝的策略,我們是不是可以編程程序,然後讓計算機去計算,然後真正和人類下棋呢?至少當下的計算機表示還是比較無奈的。這是另外一個我回答和圍棋相關的答案,和這一個回答不太一樣,相信加在一起能能對你有幫助。


我覺得可窮舉的回合制遊戲肯定至少有某一方有不敗策略的:
——————————————我是華麗的分割線——————————————
0、把所有可能的狀態(棋子擺放情況+下一步該誰行動)窮舉出來,記作一個個節點。
1、其中的一部分狀態是勝負已分,那麼就給它染色(黑方勝就染黑、白方勝就染白);
2、剩餘的節點未分勝負,那麼就用有向箭頭指向它可能的下一步。
3、遍歷每一個節點,把所有的有向箭頭窮舉完後,剔除那些由起點(一子未放+黑方行動)無法到達的節點。
4、按照下面兩個規則對所有節點染色(反覆考察每一個節點),直到沒有任何一個點能被染色為止。
規則一:如果某一個節點是白/黑方行動,而它的所有子節點(即下一步的節點)都被染黑/白,則這一節點染黑/白。————你的回合,你所有可能的下一步都會走到必敗情形時,你已經輸了。
規則二:如果某一節點是白/黑方行動,而它有某一個子節點被染白/黑,則將這一節點染白/黑。————你的回合,你有某一種方法走到必勝情形時,你已經贏了。
——————————————————再割—————————————————
倘若起點已經被染黑/白,則黑/白方必勝
倘若起點沒有被染色,則雙方均有不敗策略,證明如下:
——————————————————再再割————————————————
稱沒有被染色的點為「透明點」,則每一個黑/白方行動的透明點必沒有黑/白色的子節點(否則按規則二,該點已被染色而不透明)、且有至少一個透明子節點(否則按規則一,該點已被染色而不透明)。
則當一個處在透明點處行動的玩家(假設是黑方),總可以選擇走到下一個透明點,而下一步白方只能走到透明點或者黑點(投降)。因而雙方都可以在透明區裡面無限打轉,但誰也不能離開透明區(離開即投降),因而雙方均有不敗策略。


我覺得沒有,因為是悖論,兩個人同使必勝策略還有人贏么。貼目在增加實際上是一種平衡策略,為了讓先手不存在先手的優勢,因為圍棋是一種棋力的比拼,所以一定要公平。但是圍棋卻是回合制,而非同時進行,所以在兩人棋力相等的情況下,先出手的人一定存在優勢,為了讓後手的人彌補其劣勢,產生了貼目的規則。但是這個貼目卻不是通過算出來的,而是根據當代棋手的平均棋力,大概估計出先手的人會有多少目的優勢,由於圍棋在不斷發展,而且每個時代的平均棋力水平在不斷提升,所以先手的優勢會越來越大,所以貼目的棋子越來越大。個人愚見,未必正確。


路人回答一句(如無幫助請摺疊)。我完全贊同【專吃劉小羊】同學的看法,即必有必勝策略。推理過程看他答案就可以了。我這裡主要是想對【須盡歡】同學的回答提出一點看法,假如未來某天計算機可能有必勝法,但並不代表人類就有了必勝法。因為人類的「CPU」和「內存」有限,圍棋或者象棋為什麼能流行這麼多年就是因為人類的"CPU"和"內存"只有過「較小的更新」,並沒有「質的飛躍」。所以人類才會為突破他們的那層智力天花板而歡呼雀躍!
但就站在未來計算機的角度而言:it』s nothing!(這句話沒有任何現實意義,只是一種不可證實猜想,假設那時計算機能計算完圍棋所有可能性)如果往後人類大腦可以外置CPU和內存(及假設外置CPU能完成目前圍棋的計算任務,且外置CPU和內存其也算人身體的一部分),估計當時的圍棋規的複雜度則就會設置為當時運算速度最快的人的N倍(N要看制定者怎麼定義),「那時的圍棋」仍不可解。
這可能就是棋類遊戲的樂趣所在吧。


不知道圍棋是否有必勝策略,但我猜想,如果有,那麼結果必定是勝半目,吳清源說,不可過分,李昌鎬說,不得貪勝。


圍棋是分先遊戲,所以不可能平衡,別給我說貼目規則,貼目是圍棋不平衡最直接的表現,而且通過統計學計算的貼目標準只能是近似公平。只有在窮盡圍棋之後得出標準貼目,才能說在規則上平衡了,但是最終黑棋還是處於先手貼目佔劣的位置。
所以必勝的策略是存在的。而且是黑棋必勝的方法。


圍棋的魅力就在於其無窮無盡的變化。所以所謂必勝的秘訣顯然是不存在的


理論上有,但是不太可能出現。
簡單的說,當必勝法被算出來之後,規則立馬就有方式避免必勝法。
比如先手必勝法必然贏了10目,規則立刻就會為白棋貼10目以上。

另一個理念
黑棋第一步走A點。IF白棋走B點,黑棋則走C點必勝;IF白棋走D點,黑棋走E點必勝。一直這樣算下去,最後會算贏。
其實,我們現在的所謂定式,就是已經算出來了前幾步,你幾乎怎樣走是必勝的了。
我不懂編程,但我覺得圍棋遊戲里的電腦,應該就是這種模式。


不可能存在。
先不要急著吐槽我說的太絕對。我是說人類一定不可能發現。
我認為,圍棋的有趣就在於它複雜的變化。我感覺應該不會有人見過兩局完全相同的棋,足以見變化之多。
我能想到最多的結局也就是人類找到了更優勢的開局,然後發現執黑的勝率高了,就會提高貼目。
我也只是圍棋愛好者。棋力也不怎麼樣。
最後我一點小感覺,我個人覺得黑棋貼7.5目偏多了。不過我水平不夠,就請忽略這句話吧。


和貼目有關,理論上,黑先不貼目,黑必然有必勝走法,如果黑先貼10目必然白棋有必勝走法。所以,在不貼目和貼10目之間必然有個貼目值(這個值有可能是非整數)使得黑棋和白棋都有必和走法。貼目值離這個必和貼目值越遠,必勝走法越容易找到,越近越不容易找。目前的常用規則黑貼7.5目是很接近那個值的,在這個規則下現在靠人腦和電腦這個必勝走法還沒辦法找到。


推薦閱讀:

怎樣判斷平面上一個矩形和一個圓形是否有重疊?

TAG:圍棋 | 趣味數學 | 棋牌遊戲 | 策略 | 演算法設計 |