題:
一旦足夠高,深度(層數)是否仍然重要?
RikTelner
2014-03-02 18:56:04 UTC
view on stackexchange narkive permalink

這不是真實的,只是想像發生這種情況。

計算機A 是超級計算機。它可以在20秒內計算30層深。

計算機B 是超級計算機。它可以在20秒內計算出15層深度。

它們彼此對戰棋。

這15個深度真的重要嗎?我猜想在這15個深度之內,可能有數万億種方法可以逃脫將死或捕獲重要碎片。當然,計算機A 了解更多。但是在我看來, Computer B 也可以預測未來,足以保護自己。

在這種情況下,“深度”是指層數?乾杯。
是的,我是說
五 答案:
Wes
2014-03-03 05:01:09 UTC
view on stackexchange narkive permalink

是的,那15個深度非常重要。

考慮一下卡斯帕羅夫在 Immortal Game對Topalov中的位置。

  [白色“ Kasparov”] [黑色“ Topalov”] [FEN“ b2r3r / k4p1p / p2q1np1 / NppP4 / 3R1Q2 / P4PPB / 1PP4P / 1K2R3 b--0 24”]  

我用幾個引擎測試了這個位置。深度15處的一些引擎未能檢測到 24 ... cxd4 失敗的舉動,並認為它是獲勝的。那些相同的引擎在更大的深度上發揮了正確的作用 24 ... Kb6!

例如,即使是最初在深度21時像Stockfish 4一樣強大的引擎也認為丟失動作 24 ... cxd4 是正確的。

  Stockfish DD 64 SSE4.2:24 ... cxd4 25.Re7 + Kb6 26.Qxd4 + Kxa5 27.Qc3 + Kb6 28.Qd4 + Qc5 29.Qxf6 + Bc6 30.Qxc6 + Qxc6 31. dxc6 Rd1 + 32. Ka2 f5 33. c7 Rc8 34. Rxh7 Rxc7 35. Rh6 Rc6 36. g4 f4 37. g5 Rd2 38. c3 Rxc3 39. Rxg6 + Kc5 40. Bg4 Rcc2 41. Rxa6 Rxb2 + 42. Ka1 Rbc2 43. Kb1(-1.45 / 21) 

同一引擎在打開更深的位置時會顯示 24 ... Kb6 正確的動作。

  Stockfish DD 64 SSE4.2:24 ... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Rhe8 29. Rxe8 Rxe8 30. Nb3 Re1 + 31. Kb2 Re2 32. Rxh7 Nxb4 33. Kc3 Nd5 + 34. Kd3 Rxh2 35. Rh4 Ne7 36.Nd4 Nc6 37.Nxc6 Bxc6 38.f4 Kc5 39.Be6 Rxh4 40.gxh4 Bd5 41.f5 gxf5 42.Bxf5 a5(-0.78 /  

深度為15的Fritz 11 SE也失敗了。但是它在16深度發現了正確的移動!

  Fritz 11 SE:24 ... cxd4 25. Qxd4 + Qb6 26. Re7 + Nd7 27. Qe5 f6 28. Qc3 Qg1 + 29. Ka2 Bxd5 + 30. Nb3 f5 31. Qc7 + Ka8 32. Rxd7 Rxd7 33. Qxd7 Bxf3 34. Qd6 Qa7(-1.44 / 15)Fritz 11 SE:24 ... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Nxb4 29. Nb3 Bd5 30. Rf6 + Nc6 31。 Nd4 Rdf8 32. Rd6 Kc5 33. Rxc6 + Bxc6 34. Ne6 + Kd6 35. Nxf8(-0.59 / 16) 

也考慮這個難以置信的問題,例如我在這裡在這裡找到的位置一個>。

Stockfish無法找到獲勝線1. Be2 +!直到深度31為止,直到那時它才認為這是一個不好的舉動。我在這裡展示勝利。關鍵是黑方由於同伴的威脅而進入楚格旺,必須放棄女王或移動棋子,這將允許白方創建經過的棋子並獲勝。

  [FEN“ 8 / 2p1q3 / p3P3 / 2P4p / 1PBP2kP / 2N3P1 / 7K / 8 w--0 1”] 1. Be2 + $ 1 Kf5 2. Nd5 $ 1 Qxe6 3. Bd3 + Kg4 4 .Be4 $ 3 Qh6(4 ... Qxe4 5. Nf6 +)5. Nf4 Qg7 6. Nd3 $ 1 Qxd4 7. c6 $ 1 a5(7 ... Qxe4 8. Nf2 + Kf3 9. Nxe4 Kxe4 10. Kg2 Kd4 11. g4 hxg4 12. h5 Ke5 13. h6 Kf6 14. Kg3 Kg6 15. Kxg4 Kxh6 16. Kf5 Kg7 17. Ke6 Kf8 18. Kd7 Kf7 19. Kxc7)8. b5 $ 1 a4 9. b6 cxb6 10. c7 Qxe4(10 ... Qc3(11. Nf2#)11. Nf2 + Kf3 12. Nxe4 1-0在深度31!  
 乾魚DD 64 SSE4.2:1. Be2 + Kf5 2.Bc4 c6 3. Ne2 Qf6 4. Kg2 Kg4 5. Nf4 Qxd4 6. Bd3 Qe3 7. Be2 + Kf5 8. Bf3 Qd2 + 9 。Kh3 Qxb4 10. e7 Qe1 11. Ne2 Qf1 + 12. Kh2 Qf2 + 13。 Kh3 Qe3(-1.05 / 22)Stockfish DD 64 SSE4.2:1. Be2 + Kf5 2. Bc4 Qf6 3. Ne2 c6 4. Bxa6 Qxe6 5. Bd3 + Kf6 6. Nf4 Qe1 7. d5 Qxb4 8. dxc6 Qxc5 9. Be4 Ke7 10. c7 Kd7 11. Nd5 Kd6 12. Kh3 Qc4 13. Bg2 Qg4 + 14. Kh2 Qc8 15. Be4(-1.15 / 26)Stockfish DD 64 SSE4.2:1. Be2 + Kf5 2. Bc4 Qf6 3. Ne2 c6 4 。d5 cxd5 5. Bxd5 Qb2 6. Bc4 Kf6(-1.01 / 28)Stockfish DD 64 SSE4.2:1. Be2 + Kf5 2. Nd5 Qxe6 3. Bd3 + Kg4 4. Be4 Qh6 5. Nf4 Qf6 6. Nd3 Qxd4 7。 c6 Qxe4 8. Nf2 + Kf3 9. Nxe4 Kxe4 10. Kg2 Ke5 11. Kf3 Kf5 12. g4 + Kf613。 gxh5 Kg7 14. Kf4 Kf6 15. h6 Kg6 16. h5 + Kh7 17. Kg5 Kg8 18. h7 + Kxh7 19. Kf5 Kg720。 Ke6 Kh6 21. Kd7 Kxh5 22. Kxc7 Kg5 23. Kd7(6.06 / 31) 
但是我的意思是每移動15步。不只是開始。
是的,一舉一動。如果在第一次移動時計算深度為15並犯了一個錯誤,那麼在隨後的每次移動中計算15個深度將無法保存。
tbischel
2014-03-04 04:38:43 UTC
view on stackexchange narkive permalink

在計算機國際象棋編程社區中,很長一段時間以來,性能提升與搜索深度之間的關係實際上一直是研究的活躍領域。有一種理論認為,搜索深度的增加會導致強度的減少……這似乎在實驗結果中得到了證實。

從我的角度來看,這是一個直觀的基礎為了這。想像一下,從終端遊戲桌位置開始,兩個超級計算機之間的假設匹配。在表層中,大多數強制性獲勝發生在少於(例如)50層的地平線上。剩下的大多數位置都是平局,只有一小部分決心贏得更高深度的勝利。一台以100層搜索的計算機比50層計算機具有有限的優勢,因為(如您所提到的)較弱的程序能夠瀏覽幾乎所有失敗的行,所有行都在更有限的深度出現。實際上,50層程序比25層程序具有更大的優勢... 4層程序比2層程序具有更大的優勢。

我首先遇到了這個概念大約15年前,在有關黑暗思想的系列論文中,進行了深度搜索實驗。如果您對計算機國際象棋感興趣的話,這是一本很好的讀物。

儘管我找不到在線參考,但是去年有一篇關於該主題的論文...

Diogo R.Ferreira(2013年)。搜索深度對下棋實力的影響。 ICGA Journal,第一卷36,第2名

Fabian Fichter
2018-02-25 17:23:47 UTC
view on stackexchange narkive permalink

問題是:您是說詳盡搜索的15/30層,還是像Stockfish這樣的現代國際象棋引擎的標稱深度/迭代為15/30?

如果您是說後者,則是15/30層不一定意味著太多。現代國際象棋引擎會大量修剪並減少本來不好的動作,因此可能是乍一看似乎是不好的犧牲,標稱深度/迭代次數為15時實際上只搜索到例如5-10。在深度/迭代次數30處,可能仍僅搜索到減小的深度,但是隨後可能是有效深度15-20,足以發現犧牲確實是好的,並且在引擎一發動發現移動是有希望的,它將減少減少,因此移動被搜索到更接近30層的深度(由於擴展和靜態搜索,甚至更深)。因此,是的,即使組合在15層的標稱範圍內,我認為也會有所作為。

如果您指的是詳盡搜索,那麼我認為深度為15的引擎將非常強大,前提是它具有良好的評估功能和某種靜態搜索(在離開節點位於深度15)。由於收益遞減,我認為將深度增加一倍所獲得的收益將遠小於將兩個深度為15的現代引擎與深度為30的現代引擎進行匹配所獲得的收益。但這當然只是理論上的,因為對深度15所需的時間比引擎通常達到深度/迭代15所需的時間長幾個數量級,因此這樣的實驗僅在深度較小時才可行。

Stephen Streater
2018-02-25 15:34:22 UTC
view on stackexchange narkive permalink

FWIW當ARM是新產品時,我編寫了經過優化的ARM窮舉搜索程序,該程序僅在第1層之後進行了僅材質的位置評估。

我使用了具有優化機器代碼,迭代加深,alpha-beta窗口的技巧在經過排序的移動上(幾乎所有位置的值都為0,因此得到了接近最佳的alpha-beta修剪)-哈希表將分支因子減小到遠小於alpha-beta的理論平方根,最壞的部分通常為4

在當時與標準程序的競爭中,我的E6P程序陷入了可怕的境地,但與當時的專業軟件相比,額外多了一層或兩次詳盡的搜索(即通常為6在最壞的階段進行詳盡的層級+靜態搜索,簡化後最多可搜索12層),儘管它得到了對手的信任,但它仍然避免了實際的失敗。幾個小時後,幾乎所有遊戲都進入了裁定階段,因為相反的程序實際上無法獲勝。

後來,我針對StrongARM對其進行了優化,使其達到了10層。這個版本可以輕易擊敗所有非國際象棋玩家,儘管顯然它缺乏任何戰略意識,所以著名的評論適用:是的,它們是國際象棋棋子,但不是國際象棋!

幾年前,但是我很想再次嘗試在層1上進行更具戰略意義的位置評估,並且比起4MIPS ARM2 Acorn Archimedes,理論上採用Intel XEON理論上要快10,000-100,000x(並且哈希表內存增加30k倍) 。

公認不是主流,但玩起來很有趣。

Yuriy Pylypenko
2014-11-28 14:35:56 UTC
view on stackexchange narkive permalink

+1層估計可增加+ 55..70的ELO增益(有關此主題的大量研究)

我想在這15個深度中,可能有數万億個逃逸將軍

問題是,所有這些“萬億”都是由A @ D = 30計算的,如果A選擇獲勝而選擇了舉動,則意味著它已經計算了全部這個“萬億美元”,無論“萬億美元”中的哪一個舉動,對手都會做出回應-舉動仍然是贏家

歡迎參加討論。您有什麼證據可以證明您的說法嗎?我認為沒有任何具體的關係。


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