題:
有沒有人試圖用數學方法表徵國際象棋?
postoronnim
2019-12-10 02:02:49 UTC
view on stackexchange narkive permalink

從作為國際象棋的學生,研究人員和實踐者多年以來,我覺得它具有數學證明和理論中發現的完整和優雅。因此,自然而然地想到用數學術語描述國際象棋是可能的。我的意思是一個優雅的描述,例如一組緊湊的公式或證明國際象棋屬於此類數學領域的證明。憑直覺,感覺它應該能夠適應群體理論。有誰知道在這方面做了什麼嘗試?我想從討論中特別排除引擎,神經網絡等,因為儘管在提高比賽質量方面取得了明顯的成功,但這些嘗試並不構成理論上的證明。

如果我們有關於國際象棋的數學證明附近的任何東西,您是否認為遊戲會解決?如果對遊戲的完整描述類似於對組的完整描述,那麼我們將能夠形成比單純基於啟發式引擎更好的引擎。
@ NoseKnowsAll我知道遊戲沒有解決。我的問題是關於這樣做的嘗試。
@Rewan Demontay絕對是的。但是,我對完整的解決方案或至少是嘗試感到好奇。我只是有一種預感,國際象棋或其像棋子和姿勢之類的元素,如群論中的群一樣具有對稱性,有可能被歸類為這些群的集合。而且,群論是完整的,這意味著它可以結合任何數學對象,從而可以消除國際象棋某些先前未見的特性。
它看起來更像圖論,帶有(有向的)箭頭指示從另一位置移動一步即可到達哪些位置。我認為群體理論與國際象棋之間沒有任何關係;它們具有完全不同的特徵(例如,國際象棋中的動作通常是不可逆的)。
還沒有人提到[關於這個主題的維基百科頁面](https://en.wikipedia.org/wiki/Solving_chess)嗎?
@NoseKnowsAll:的“數學公式”與“數學證明”相去甚遠。在沒有證據的情況下,數學家有很多細節在談論。
你看過胡克多項式嗎?
五 答案:
Laska
2019-12-10 13:38:13 UTC
view on stackexchange narkive permalink

國際象棋有許多不同方面,可以用數學形式化。至少從19世紀開始,國際象棋就已經被視為推動數學創新的資源。因此,在討論國際象棋的數學特徵時,不是我們要討論的單一模型,它抓住了每個功能,而是許多模型,其中每個模型的功能都與之相反。 放手與該分析無關的國際象棋的某個方面。

也許最早的成功(不算盤中的米粒)是策爾梅洛定理(是採埃孚集理論的創始人之一)指出,在國際象棋中,“要么白方可獲勝,要么黑方可獲勝,或者雙方均可至少平局”。

組合遊戲理論(由著名數學家約翰·H·康威,埃爾溫·貝萊坎普和理查·蓋伊開發)已成功應用於國際象棋。但是,該理論中有兩個假設與它在國際象棋上的普遍適用性背道而馳。一個是CGT的勝利僅在於您的對手無法移動而不能解決僵局。其次,存在“允許移動”(例如,檢查)的概念,其中如果一個人玩,則另一個玩家必須做出響應,而不是第一個玩家再次玩。但是Noam Elkies通過計算象棋殘局的CGT值得出了一些非平凡的結果-在他的象棋頁面 http://www.math.harvard.edu/~elkies/chess.html中提供了參考:“關於數字和殘局”和“大型棋盤上的典當殘局中的高級木材”。

您提到了群論-很奇怪,組合下的組合遊戲確實形成了一個阿貝爾群!公平地說,上述兩個障礙確實阻止了國際象棋本身的這種行為。

圍繞棋盤進行了大量的組合工作。瓦茨拉夫·科特索韋茨(Vaclav Kotesovec)在網上出版了800頁的書,書上的內容是正好,這不涉及棋類的攻擊(廣泛地概括了8個皇后問題)。請參閱 http://www.kotesovec.cz/以獲得鏈接。這與魔術方塊,實驗設計等有關。

從芬蘭開始,從埃洛·邦斯多夫(Eero Bonsdorff)開始,在列舉路徑的國際象棋問題上有很長的血統,它在計算到達某個位置的方式數量。這通常涉及對Standard Young Tableaux的分析,該分析也支持對稱組的表示理論。斐波那契數,加泰羅尼亞數和歐拉數都經常在這裡找到,以及其他組合的標識,可以在巧妙的國際象棋組合中找到它們的實現。請參見 https://pdb.dieschwalbe.de/search.jsp,然後在搜索框中輸入g ='mathematics'。

騎士的旅遊問題也以幫助他人而聞名。推動漢密爾頓圖的研究,尤其是對此類對象的數量進行計數的挑戰。參見 https://www.mayhematics.com/t/t.htm

計算理論還詢問國際象棋是否是確定的。這就是在更大的電路板上佈置多套零件,以嘗試製造與圖靈機相當的機器。這將我們帶到了計算極限的主題,在這裡我要指出的是,如果數學理論完全描述了國際象棋,那麼我們應該比使用國際象棋本身發揮更多的推理能力。這可能使我們能夠逃避當前法律的一些語言挑戰(例如,是否可以定位典當)。

我認為在數學上描述國際象棋慣例如何一致地適用於包括童話象棋在內的象棋問題也具有研究價值。 Guus Rol有一個雄心勃勃的計劃,該計劃將每個轉彎減少到“微階段”,並聲稱能夠高精度地確定在復雜的“追溯”情況下(既需要逆向邏輯又需要向前邏輯)情況下仙境如何相互作用。我不知道他是否會完成他的理論。

我個人希望看到一個更適度的理論,該理論將每一步都視為原子運動,儘管它不能很好地涵蓋童話棋。至少可以涵蓋問題約定的追溯方面,例如castling和ep

數學物理學家羅傑·彭羅斯(Roger Penrose)大約在2年前發表了一個國際象棋立場,目的是辯稱他長期以來的立場,即人類所展示的是一種根本不同的推理紮根於“可計算功能”的AI所能證明的。即使是隨機理論,也請參見 https://en.chessbase.com/post/a-chess-problem-holds-the-key-to-human-意識

圖,並且蒙特卡洛分析已非常成功地應用於引擎,尤其是最新一代引擎,我認為這不會使它失去被視為數學理論的資格。

還有一種線性代數方法計算動作和位置。 “如果國際象棋是一張圖,它的最大特徵值是多少?”是一個非常現實而有趣的問題。請參見Francois Labelle的網站,網址為 http://wismuth.com/chess/statistics-games.html

線性代數可以成功應用於其他與國際象棋相關的問題,例如一個車隊到底有n次移動,從a1到h8有多少種方式?國王呢?

多年來,Noam Elkies & Richard Stanley一直在合作編寫有關國際象棋和數學的書。我不知道什麼時候最終會出現,或者他們是否已經放棄了。但是在前面鏈接的諾姆的象棋頁面上給出的“數學騎士”也許預示了那本書。理查德·斯坦利(Richard Stanley)是Combinatorics中的佼佼者:請參閱 http://www-math.mit.edu/~rstan/chess/queue.pdf,以及Noam的生日文章 https:/ /arxiv.org/pdf/math/0508645.pdf

已經有Miodrag S. Petkovic撰寫的《數學和國際象棋》一書,但我對其內容不熟悉。 / p>

其中一些想法在Wikipedia頁面中列出: https://en.wikipedia.org/wiki/Category:Mathematical_chess_problems,還有一個更具體的頁面 https ://en.wikipedia.org/wiki/Mathematical_chess_problem

如果其他人有其他國際象棋和數學示例,請在評論中提及它們,我將嘗試將其納入本回復中。如果有人鏈接說明了我提到的主題,請謝謝。

最後:math.stackexchange.com上有62頁國際象棋條目!

多年來,我一直在尋找這些數學和組合遊戲理論分析,這些分析真正關注國際象棋(而通常不關注組合遊戲)。我沒有找到很多結果。您知道一些與此主題相關的具體書籍/論文嗎?
嗨,負離子,最好的是Noam Elkies的兩篇殘局論文-我在他的國際象棋頁面上添加了鏈接,其中提供了詳細信息。
Mason
2019-12-10 11:09:39 UTC
view on stackexchange narkive permalink

這裡是閱讀博弈論的一些起點,博弈論是最適合於下棋的數學工具。

是一個光輝的歷史早期博弈論。國際象棋是一種“完美的信息遊戲”,對於這類游戲,可以說有些有趣的事情。例如,請參見。我還將閱讀克勞德·香農的文章。 香農數給出了遊戲複雜度樹的界限。對於標準象棋,我們有一個棘手的難題,但您可以做一些較小的變形來解決這些較小的遊戲。這是 this的示例。作者聲稱已經解決了較小的5x5國際象棋變體。

yobamamama
2019-12-10 04:09:53 UTC
view on stackexchange narkive permalink

不是。至少不是認真的數學家。

它在博弈論中有所涵蓋,但其他方法(例如“群論”)似乎並不適合;儘管可能會發現一些更高維度的非線性類型描述。

所以似乎也沒有包含組和拓撲的代數了,但是如果有人願意嘗試的話,也許可以適合Analysis。但這將是一位高級數學家,他更有可能嘗試解決一個更好的問題,從而導致他們獲得博士學位和工作指導。

感謝您的見解。如果這樣的嘗試成功了,它應該引起很多認可。試想一下到目前為止有多少人在努力解決它。
@postoronnim-值得認可。我不確定有多少合格的人認真嘗試過這個問題。
[Noam Elkies](http://www.math.harvard.edu/~elkies/chess.html)浮現在腦海。
orlp
2019-12-10 20:15:53 UTC
view on stackexchange narkive permalink

我不想這麼說,但是從數學上講,我們在下象棋時非常無聊。對於兩個交替的玩家來說,這是一款完美的信息遊戲,沒有任何不確定性。這意味著國際象棋要么是白贏,要么是黑贏,要么是平局。國際象棋的最佳策略是微不足道的,眾所周知:極小極大。就數學而言,象棋可以解決。

@emory-因為實際上執行最佳策略在計算上不可行? (由於組合爆炸)
@emery-也許您將數學的完成方式與其他工作的方式混淆了?考慮一下:當工程師,物理學家和數學家在辦公室前發生小火時正在工作,工程師驚慌失措並抓住滅火器,將其噴到各處,撲滅了大火,但對滅火器造成了額外的損害這個過程。物理學家進行了一些快速的計算,並使用了足夠的火來撲滅。數學家看到了火,看著滅火器並說“存在解決方案!”然後回到他的辦公室。
@emory您不了解。多虧了minimax,我們不僅知道*該做什麼[(在籃球中獲得更多分或在國際象棋中成為對手的同伴)),而且我們也知道*該怎麼做*。我們只是知道,如果在每次可能的棋步動作之前,我們都進行了遊戲發展的所有可能組合,然後選擇了最佳棋盤,那麼我們正在執行“最佳棋盤”策略。簡而言之,這就是minimax算法。這與您的籃球例子大不相同。
@Firzen,,但是,如果您不關心此類事情,那麼可以解決國際象棋。
@emory *“如果我沒記錯的話,這樣的計算機將比我們的太陽系大很多倍,並且將花費數百萬人的生命。這不是這樣的機器如此龐大,以至於會形成一個黑洞,它的計算結果無法逃脫其事件範圍。” *我對此不太確定。無論如何,建造計算機是相當自然的紀律。我們可能沒有*高效*的最佳國際象棋算法,但至少有一些。因此,如上所述,在數學上解決了國際象棋。
@emory不,minimax根本不需要很多內存。您的手機具有最佳求解像棋的計算能力-它只需要很長很長的時間。即使您需要一台巨大的計算機,直到宇宙熱死為止,數學也不用擔心。
同樣,在給定的alpha beta修剪,良好的移動啟發法和換位表的情況下,您只需要查看大約10 ^ 30個不同的位置即可。那隻有2 ^ 100,這雖然很棘手,但並不是那麼棘手。大約要破壞256位加密。
David Richerby
2019-12-11 02:56:47 UTC
view on stackexchange narkive permalink

國際象棋不是數學家感興趣研究的對象。數學家關心的問題在某種程度上是無限的:無限的對像或無限多的例子。國際象棋是完全有限的。只有一個國際象棋,它使用一個有限的棋盤,在有限的位置可能有很多。如果國際象棋是合理地下棋的(如果沒有這種假設我們就不能指望它來表徵),那麼遊戲的長度是有限的。 “理性”基本上是指任何一方都有權獲得平局,這意味著遊戲少於5900步,這意味著遊戲數量有限。數學家可能會研究素數,但他們不會研究單個數1827368429。這在文化上很重要,這一事實可能會鼓勵某人嘗試,但是很難看到有人有時間做那麼複雜的事情。這種事情需要數十年的全職工作,如果失敗了,您基本上一無所有。

大型數學不會對有限的事物產生影響,如果您四處看看,有很多例子。問題不關乎計算,而是關乎國際象棋在數學領域的理論基礎。
比如@postoronnim的例子是什麼?我已經為您提供了理論基礎:這是一個有限的對象。
有限的概率空間,矩陣,模型,有限圖,這個例子不勝枚舉。
@postoronnim所有這些東西都無窮無盡。只有一盤棋。就像有無限多個質數(每個質數都是有限的),但只有一個1827368429一樣。有成千上萬的數學家研究質數,而沒有一個人單獨研究1827368429。
“數學家(僅)關心在某種程度上是無限的問題。”抱歉,但是根據我的數學經驗,這完全是錯誤的,或者是嚴重的誤解。我建議你闡明你的觀點。
@YiFan我在句子中您沒有引用的部分中對此進行了澄清。如果這是非常錯誤的,請給我列出一些數學家研究單個有限對象的示例。
斯坦尼斯拉夫·烏蘭(Stanislav Ulam)將自己描述為:“一個純粹的數學家,沉沒得太低,以至於他的最新論文實際上包含帶小數點的數字”
@DavidRicherby`如果國際象棋合理地玩(如果沒有這樣的假設,我們就不能希望將其刻畫為特徵),那麼遊戲的長度是有限的。我認為我們可以基於以下規則來削弱這一假設:“如果棋子移動了50次(白棋50次,黑棋進行了50次棋子,而不是一個棋子或一個棋子被捕獲,則任何人都可以宣布平局。”)從“可以聲明”到“必須聲明”的規則,否則玩家可能會失去理性,並且遊戲仍然是有限的。
哦。在這種情況下,我確定我會誤讀你的著作。
通常將一個有限的對象放在方便的概括中並進行研究。當遊戲理論家聲稱像棋,圍棋,跳棋等遊戲的計算複雜性時,他們正在談論的遊戲是在n乘n的板上進行的。
@Mason對。但是那些關於在n×n棋盤上解圍棋的漸近資源需求的分析並沒有告訴我們關於8×8棋盤上的圍棋的任何信息。
你是對我提出挑戰的基本挑戰的正確挑戰:讓我以一種奇怪的方式回答。數學可以這樣構成(僅在某些情況下)。我們選擇我們想要的假設,因為它建立了我們想要的結構類型...如果我們假設OP詢問“(A)只有國際標準格式的象棋”和“(B)數學家不感興趣”在計算中。”那麼我們寫的答案應該是您寫的類型。但是,採用這些假設似乎並不能解決我想回答的問題。
我知道這可能是一種奇怪的批評,但是當我閱讀您的文章時,似乎發現您有一些假設/限制,OP不一定會置入他們的問題中。因此,為什麼我們不假設OP提出了一個有待解決的功績問題,答案可能是:“是的!但是自然的數學舉動將是研究泛化...”-答案。相對於“否。因為您似乎誤會了數學的類型……”答案。似乎更令人鼓舞。
@Mason這是一個合理的批評。我認為我並沒有真正添加限制,而是在回答所提出的問題。您建議將問題概括為得到我同意的答案是一個更有趣的答案,這也是一種完全合理的方法。
感謝您抽出寶貴時間閱讀評論。而且,我尊重這樣的願望:準確回答所要提出的問題,而不是對所得到的結果進行過多的不合理猜測。


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