題:
國際象棋是解決問題的遊戲嗎?
Tobi Alafin
2016-01-24 05:28:18 UTC
view on stackexchange narkive permalink

國際象棋是有限決策的零和遊戲。在任何給定點可能發生的移動數量以及棋盤上可能出現的狀態數量都是有限的。我不記得自從上次打井字遊戲以來已經有多少年了。象棋是否存在這樣的“最優策略”?對此有所了解。

請注意,如果知道了這樣的策略,國際象棋將是一個非常無趣的遊戲。該站點存在的事實很可能證明國際象棋沒有解決。
十一 答案:
ETD
2016-01-24 06:07:10 UTC
view on stackexchange narkive permalink

由於您所做的觀察,國際象棋可能的遊戲路徑樹是有限的,因此國際象棋確實可以解決可以,與井字遊戲的含義完全相同。因此,存在國際象棋的最佳策略。但是,沒人知道它們是什麼。井字遊戲由於可以玩的遊戲空間很小而得到了解決,而國際象棋卻遠遠沒有解決,因為其可能玩的遊戲空間遠遠超過了當前計算機技術所能解決的問題。

另一個答案是,底盤桌底展示了有限數量的所有位置的最佳遊戲。因此,在這些情況下,我們提供的解決方案與井字遊戲解決方案一樣明確而具體。但需要注意的是,重要的是,儘管人們可以輕鬆地教/記住井字遊戲的最佳策略並迅速成為一名完美的井字遊戲玩家,但背後的信息量卻很大,例如 7人羅蒙諾索夫表庫為140 TB。沒有最佳的7人策略的簡潔描述,人們可以學習/記住並在沒有幫助的情況下完美髮揮。

可能需要提及的是,關於初始位置是白人的強制勝利,平局還是什至(由某些奇怪的複雜的祖格旺)對於黑人的強制勝利,缺乏共識。這意味著我們甚至不知道採用最佳策略是否可以保證平局。
沒有“缺乏共識”。壓倒性的共識是“吸引”:https://en.wikipedia.org/wiki/First-move_advantage_in_chess。
@JeffY也許有些共識,但是直到擁有32個男人的數據庫,我們才能知道。
不,基於人與機器的結果和分析,“壓倒性的”共識。
@JeffY,我認為,凱文(Kevin)並不是去分散有關“缺乏共識”的說法,而是要著重關注“缺乏證據”。我認為我們都同意,無論是否存在任何壓倒性的共識(並且我也同意您的觀點,大多數人都認為遊戲是理論上的吸引力),而且無論是人類和/或玩家玩過的很多遊戲的任何經驗證據或引擎(兩者均發揮最佳效果),沒有一個可以肯定地排除國際象棋的任何理論可能性(白棋贏/平局/黑棋贏)。 .....
簡而言之,我認為JeffY絕對正確,因為*相信*國際象棋是一種理論上的繪圖,並且與凱文和11684的準確觀點完全吻合,我們仍然不知道*國際象棋是否是是否有理論上的吸引力。我認為大家乍一看似乎比上面的評論更親切。
我只是想知道,最大棋步數是多少,不同棋局的最大數是多少?
@TobiAlafin:不同的國際象棋遊戲的數目是未知的,因為尚未對移動樹中每個位置的可用移動數目進行分類。
有一個大概的數字。我們不能使用組合法來確定一個合適的上限嗎?
您沒有證明人類無法在其畢生的比賽中無法學會如何完美地玩國際象棋,並且您當然也沒有證明國際象棋需要花費與解決合法遊戲數量一樣多的時間。 50個移動規則。我的回答並沒有聲稱知道尚未證明的事情。
@Timothy,我同意我沒有證明這些事情;但我也不打算一開始就提出此類主張。例如,在我寫這篇文章的地方,“沒有人可以學習的最佳7人策略的簡潔描述,”我無意宣稱存在這樣一個簡潔的描述在理論上是不可能的。相反,我的意思不外乎是,目前,7人策略中最緊湊的表示形式是140 TB的數據庫。 (續)
...因此,如果一個人天真地希望像記憶一個人的腳趾腳趾策略那樣簡單地記住7人策略,那麼一個人用我們現有的7人解決方案根本無法做到這一點。那是我主張的範圍,不打算提出任何更強的主張。我希望這可以澄清。
我試圖將我的評論寫成對將來Stack Exchange答案的反饋,而不是絕對堅持要以某種方式來解決未來的問題。
11684
2016-01-24 05:37:53 UTC
view on stackexchange narkive permalink

國際象棋還沒有得到解決,並且不會在未來幾十年內出現(除非涉及量子計算的荒謬計算技術進步或如此劇烈的變化)。

您可以為第一步而腦子裡計算:白色有20個選項,黑色有20個響應;我們已經有400個可能的職位。這個數字飛快增長,一場80局比賽的可能位置數量之大令人難以置信。

此外,如果解決了國際象棋,國際象棋錦標賽和錦標賽基本上都是一種記憶式練習,這毫無意義。 (編輯:這被高估了,請參閱註釋。)

當前,國際象棋可以用七個棋子(包括國王)在任何位置上求解。我聽到的有關8人桌的最新估計是在2020年代,當然,增加一塊的時間也成倍增長。我不希望在我的一生中能解決的任何地方都會出現國際象棋(再次,除非真正出色的計算技術進步)。

已經有7人數據庫。
真?哪裡?然後我記錯了,請用7代替6,用8代替7。@TonyEnnis
6在線免費提供。 7是要購買的。 http://tb7.chessok.com/
根據ETD的評論,即使解決了國際象棋,人類也將*無法*記住該解決方案。因此,有關“毫無意義”的評論是不正確的。
採取@JeffY積分,儘管解決國際象棋會大大改變錦標賽的性質。
@11684怎麼辦?具有7件式桌腳會極大地改變錦標賽中殘局遊戲的性質嗎?我沒看到
@JeffY即使沒有記憶具體的線條,我們也將獲得有關遊戲的大量信息。我們從表庫中了解到,一些通常被認為是平局的殘局最終是勝利,反之亦然。我們從32個表庫中可以學到的東西將更為重要。開放理論將需要徹底更新。也許還有一些未知的微妙之處。但是,當然,所有這些只是在國際象棋完全解決之前的推測。
@11684完全正確。但是,比賽將如何改變?我可以看到它可能會打開更多*更多*的開頭行(作為非失敗者),儘管我看不出要記住玩這些行了。而且我可以看到它肯定會改變遊戲的事後檢驗。但是,我只是沒有看到人類與人類的遊戲受到任何重大影響,就像人類與人類的7件式終局遊戲不受7件台式機的影響一樣。
-1
@11684我認為John Nunn嘗試通過端遊戲和桌面數據庫來做到這一點。 http://www.amazon.com/Nunns-Chess-Endings-John-Nunn/dp/1906454213這些評論聽起來像是很難消化的消息。但是也許你是對的,大師們將能夠收集一些東西...
@11684我想您是在低估國際象棋的解決速度。 “增加一塊零件所需的時間(可能會成倍增長)”,但是我們計算機的速度也是如此。 http://chess.stackexchange.com/questions/16117/when-will-we-solve-chess
@mattdipasquale儘管我們的計算機的速度確實成倍增長,但增長因子僅為2,而添加另一台計算機的因子要大得多。
現在的增長因子可能是2,但根據[雷·庫茲韋爾的加速收益定律](http://www.kurzweilai.net/the-law-of-accelerating-returns)呈指數增長。
我不知道這條法律。我的回答和評論均基於摩爾定律,此外,我還期望處理速度的上升曲線趨於平坦,因為我們已經到達了CPU達到硬極限的程度,例如電信號從RAM傳輸到RAM的最大速度。 CPU。在不改變CPU基本結構的情況下,很快我們將以最快的速度前進。 @mattdipasquale
Tony Ennis
2016-01-24 05:35:47 UTC
view on stackexchange narkive permalink

國際象棋比賽可能是有限的,但可能的比賽次數卻超出了想像。

沒有已知的舉棋順序可以保證雙方獲勝或平局。

Sylvain Julmy
2016-05-20 15:57:41 UTC
view on stackexchange narkive permalink

另一點是,象棋遊戲是有限的,但只有75步法則(如果沒有75步的俘獲或典當步,則下棋。)以前,此規則是通過連續重複三倍重複該位置來平局的規則,即所謂的“德國規則”,允許無限次遊戲如Max Euwe所示。

用相同位置的三倍規則,遊戲顯然是有限的。只需認為存在有限的可能位置,並且每個位置最多可以重複兩次。鏈接的文章顯示,在“德國規則”下,遊戲可以是無限的,該規則要求從相同位置開始播放相同的序列*連續* 3次
謝謝,我弄亂了我的解釋,是相同順序的動作的三倍:)。
Markku Litola
2017-11-30 19:07:44 UTC
view on stackexchange narkive permalink

1949年,信息科學家Shannon做出估計,用1 MHz的計算機解決國際象棋需要10到90年。從那以後,計算機電源和存儲技術有了很大的改進(又名摩爾定律),計算機電源和存儲容量每年都翻一番。考慮到這一點,想出一台計算機大約需要300年的時間,其功能是Shannon的1 MHz機器的10 ^ 90倍。在計算機開發中沒有可預見的限制。例如,英特爾的4004採用10微米光刻技術製造,而當前的i9s採用14納米技術製造。當核心變得越來越強大和越來越小時,很容易在相同物理尺寸中填充比前幾年一半的強大祖先更多的核心。在光刻中,我們剛剛輸入了低於10 nm的紫外線波長類別,但是存在諸如伽瑪射線的波長為1皮克(更小10.000)的波長。氫原子的大小為0.1 nm,但夸克的大小比1皮克小約200倍(即0.43 x 10 ^ −15 mm, https://www.theguardian.com/science/life- and-physics / 2016 / apr / 07 / how-big-is-a-quark

user10321
2016-05-18 22:48:48 UTC
view on stackexchange narkive permalink

我們知道存在一種最佳策略,因為在遊戲中有有限數量的玩家並且每位玩家都有有限數量的策略時,可以表明存在納什均衡(因此您正在對Nash進行最佳響應)

問題是,即使我們知道存在這樣的策略,但由於計算上的限制,我們也不知道到底是哪種策略。

Timothy
2017-05-01 03:46:05 UTC
view on stackexchange narkive permalink

這是我最初在 https://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess/38102#38102上寫的答案

一個完美的國際象棋棋手總是可以在贏得勝利的同時強迫贏得勝利,在可以進行平局的情況下總是可以平局。當然,在任何時候只要他們可以強迫勝利,他們也可以強迫平局。同樣,當一個球員不能強迫勝利時,另一名球員可以強迫平局。沒有50移動規則或3折重複規則的國際象棋可能不會像您想的那樣難解決。可以看出,添加3倍重複規則對玩家可以強制贏還是平局沒有區別。 n次移動後遊戲可能進行的方式數目隨n呈指數增長。另一方面,在n次移動之後可能發生的狀態數量不會呈指數增長,因為它不能超過合法遊戲中可能發生的狀態總數。根據 https://en.wikipedia.org/wiki/Game_complexity的說法,合法的國際象棋遊戲可能會出現大約10 ^ 47個狀態。

國際象棋可以通過以下方式解決:採取一組可以證明的狀態,其中包含沒有合法的三折重複規則或50移動規則的合法像棋遊戲中可能出現的所有狀態。兩個不同的州可能具有相同的棋子排列方式,並且輪到誰,您是否有權傳人俘獲,以及給定的國王或白宮是否有權再次防禦。接下來,採取所有狀態,在這些狀態下,白色可以強制贏得的最小移動次數為1,這必須在白色的回合中發生。接下來,進入所有狀態,其中白色可以強制贏得勝利的最少舉動數為2,這意味著輪到黑人了,無論他們能做出哪種舉動,白色都可以迫使自己贏得一招。接下來,進入所有狀態,其中白色可以強制贏得勝利的最少舉動數為3,這意味著白色具有的舉動將使他們在2步中獲得強制勝利,但不能在1步中獲得勝利。接下來,進入所有狀態,其中白色可以強制贏得勝利的最少舉動數為4,這意味著輪到黑人了,無論他們採取哪種行動,白色都可以強制贏得3步勝利,但是白色目前不能強制贏得勝利。 2招。一旦我們得出一個數字,使得沒有任何狀態可以讓白方強制獲勝的最小移動數就是該數目,那麼我們已經找到了所有可以使白方強制獲勝的狀態。我們可以找到所有黑色可​​以以類似的方式迫使勝利。其餘所有州都是兩個玩家都可以平局的狀態。

由於在合法的國際象棋比賽中可能會發生約10 ^ 47個狀態,因此使用蠻力構建一台無論對手如何下棋都能完美下棋的計算機將花費我們一生的時間。我相信尚未證明,沒有什麼短算法可以告訴您如何無論對手如何比賽都完美髮揮。例如,在合法遊戲中可能只有一小部分狀態會發生在您按照算法告訴您玩的方式進行遊戲的遊戲中,即使算法僅告訴您如何在所有狀態下完美玩耍,自遊戲開始以來您始終遵循該算法,而並非在合法遊戲中可能出現的所有狀態下,都可能發生這種情況。也許除此之外,該算法是一種複雜的算法,對於您一直遵循的遊戲中可能發生的每個狀態,計算最佳移動所花費的步驟要少於遊戲中可能發生的狀態數量。您一直都遵循它。根據 http://onlinelibrary.wiley.com/doi/10.1002/sres.2171/abstract,進化學習實驗室正計劃解決複雜的問題。也許有一天,他們會想出一種完美的下棋策略。即使在您一直遵循的算法不存在的情況下,即使算法很短且僅需很少步驟即可計算出最佳狀態的算法,這仍然不會阻止人類學習如何完美地下棋。也許一個人可以不斷地找出事物並保留他們所發現的事物,通過一些複雜的方法從先前的事物中發現更多事物並加以保留,並能夠從他們先前認為的如何完美玩耍的信息中找出來基本時間為90分鐘,在他們以自己的方式玩遊戲的遊戲中可能發生的任何狀態下,以30秒的增量學習信息的方式比在以自己的方式玩遊戲的遊戲中可能出現的狀態數更少的信息做到這一點,他們可以在一生中學習到,特別是如果發明了可以生存6000年的技術。

對於一個球員來說,制定一種策略來確保如果對手打得很好,他們也會打得更好,這可能會更簡單。我懷疑兩位球員從比賽開始就都被迫平局。強制平局的策略可能比保證對手獲勝的策略更簡單,因為如果對手給您強制勝利,您就不會輸。強制平局的策略也是確保對手完美髮揮的策略。如果他們表現出色,那麼他們不會一開始就給您強制勝利,因此在給您勝利之後您也不會輸掉強制勝利。

更新:

根據 https://www.youtube.com/watch?v=mOqmLYlFdBo,AlphaZero是一個神經網絡,其下象棋的行為優於包括Stockfish在內的任何其他像棋程序。創建之後,它僅在幾個小時內就獲得了該功能。我不確切知道它是如何工作的,但是我相信它的作用類似於在國際象棋策略中模擬自然選擇。假設您有一些人以90分鐘的基本時間和30秒的增量參加額定的國際象棋錦標賽,除了沒有3重複規則或50規則並且沒有辭職,並且如果沒有人在4,000步之後結對,則每場比賽都算作平局。此外,假設他們彼此之間沒有任何互動,只是錦標賽是隨機配對的,他們與某個評級非常相似的人配對,並且每次在遊戲中克隆自己的可能性很小,大約是十億分之一。賽后,評分隨他們的評分線性變化,並且有十億個人,每次創建一個人時,一個隨機選擇的人就會消失。您可能會認為,如果沒有有利的途徑,自然選擇就無法選擇新特徵。我不確定是這種情況。一些個體可能具有的基因組在產生剋隆時很少有機會進行部分有序的重大重排。然後很少會(偶爾)進行重新安排,以改善下棋策略。然後,單個突變體克隆的後代將大量繁殖。然後,它將選擇以隨機方式很少且偶爾發生變異的趨勢。然後,這可能導致進化出真正善於嘗試不同思維方式的生物,直到他們提出解決方案。

指向您關於計算機科學SE的答案的鏈接很有幫助。但是,我不確定是否值得複制粘貼整個文本。
原始鏈接的死鏈接?另外,我認為“在任何時候只要他們可以強迫勝利,他們也可以強迫平局”是不對的。
joe sixpak
2016-02-06 10:14:24 UTC
view on stackexchange narkive permalink

我們不能說誰應該贏還是應該平局

有太多的移動組合,甚至無法嘗試通過當前技術來計算答案所有可能的動作並查看結果

,那麼我們將不得不向後修剪以查看答案是什麼,以及答案是否唯一

,如果可以,那麼遊戲就不會很有趣不再

“如果可以的話,遊戲將不再有趣”->人們仍然在玩connect-4和其他一些已解決的遊戲。
Alexandre Aksenov
2016-05-19 17:42:19 UTC
view on stackexchange narkive permalink

在20世紀初,人們普遍認為國際象棋很快就會解決(被稱為“國際象棋的平局死亡”)。世界冠軍J.-R.卡帕布蘭卡傾向於相信這一點。卡帕布蘭卡·阿萊欣(Capablanca-Alekhine)比賽的比賽(幾乎全都在女王的《甘比特》中被拒絕)也證實了這一信念。例如,請參見: https://en.wikipedia.org/wiki/Capablanca_chess

現代開放的革命(國王的印第安人等),然後是人工智能的革命提供了直觀的證據證明解決國際象棋不是那麼簡單。實際上,當今的大師遊戲經常使用程序進行分析,這揭示了玩家(甚至是最好的)在遊戲過程中監督的線。

話雖這麼說,“絕對計算能力”確實可以解決國際象棋在計算理論的意義上。

Fred
2016-01-29 04:46:34 UTC
view on stackexchange narkive permalink

人的頭腦比井字遊戲複雜得多。因此,您可以找到一種玩這種遊戲的好策略。

國際象棋非常不同。國際象棋是一種啟發式遊戲。

您不能將一名士兵掌管在將軍之上。用軍事術語來說,將軍的思想比士兵的思想複雜得多。

複雜性才是最重要的。

您需要比國際象棋更加複雜。這是不可能的,但是您必須嘗試,您需要嘗試。您可以在多個級別上實現它。涉及許多因素。努力固然重要,但我們許多人做出巨大努力,但成效不佳。但是有些人卻付出了很少的努力,卻取得了出色的成績。

當然,如果您小時候曾經在電視前呆很多時間,那會浪費您的智力。

最後但並非最不重要的一點,對不起我的英語。

Lyudmil Tsvetkov
2017-12-01 13:15:21 UTC
view on stackexchange narkive permalink

要達到完美狀態還要花2000-3000埃洛斯,因此目前的頂級引擎至少可以使其實力翻倍。國際象棋實際上更接近其起步階段,而不是後期階段。例如,目前的頂級引擎可能只猜出其中之一最佳的5個開門動作。任重道遠。

你怎麼知道那個數字?
在互聯網上最先進的國際象棋論壇Talkchess論壇上進行了不同的測試並報告了這些測試,但是我的觀察也指向這個方向。另外,通過比較20年前的發動機評估結果,以及在該領域仍有待改進的地方。


該問答將自動從英語翻譯而來。原始內容可在stackexchange上找到,我們感謝它分發的cc by-sa 3.0許可。
Loading...