線上遊戲眾包定理

現在你有機會證明一些定理,即使你不知道它們是什麼意思!費爾菲爾德大學的數學家克里斯·斯塔克建立了遊戲“友好的鄰居”,以獲得數字拓撲學領域中問題的眾包解決方案。

加入我們的科學愛好者社群!

本文發表於《大眾科學》的前部落格網路,僅反映作者的觀點,不一定反映《大眾科學》的觀點


現在你有機會證明一些定理,即使你不知道它們是什麼意思!克里斯·斯塔克是費爾菲爾德大學的一位數學家,他建立了遊戲友好的鄰居,以獲得數字拓撲學領域中問題的眾包解決方案。無論這對你來說意味著什麼,你或許都能幫助斯塔克和他的同事證明一些定理。

“友好的鄰居”未解決的 9 點關卡截圖。截圖來自克里斯·斯塔克的“友好的鄰居”。

遊戲玩法很簡單:拖動點,看看你是否可以做到沒有任何紅線,但至少有一個空格是空的。遊戲的一些關卡已被解決,而另一些則尚未解決。如果遊戲視窗的右下角有一個燒杯,那麼你正在玩一個實驗性關卡,它可能沒有解決方案。如果你解決了它,你就成功地證明了一個關於數字同倫的新定理!


關於支援科學新聞

如果您喜歡這篇文章,請考慮透過以下方式支援我們屢獲殊榮的新聞報道: 訂閱。透過購買訂閱,您正在幫助確保關於塑造我們今天世界的發現和想法的具有影響力的故事的未來。


太接近了!我們不能把這個四捨五入嗎?截圖來自克里斯·斯塔克的“友好的鄰居”。

如果你想在不閱讀任何數學知識的情況下玩遊戲,請不要讓我阻止你。但如果你對遊戲背後的數學原理感興趣,請繼續閱讀。

數字拓撲學是經典拓撲學的一個變體,它研究具有有限數量點的空間。值得問一下,我們為什麼可能希望能夠在有限空間上進行拓撲學研究。數字這個詞暗示了答案:動機來自計算機圖形和數字影像。我們在計算機上看到的每個影像都是由有限數量的畫素組成的,如果能夠僅使用關於那些彼此相鄰的畫素顏色的資訊來說明兩個影像在某種程度上是相關的,那就太好了。例如,我們能否僅使用關於哪些畫素顏色彼此相鄰的資訊來區分“B”和“D”,無論它們的方向如何?這是一個數字拓撲學問題。沒錯,潛在的未來應用之一是使 CAPTCHA——網站用來確定使用者是否是人類的那些扭曲的單詞影像——對計算機來說更容易,因此對我們來說更難,在一場搖擺不定、模糊不清的軍備競賽中。

經典拓撲學是研究形狀的屬性的學科,這些屬性在您拉伸或彎曲它們時保持不變,只要您不撕裂它們即可。經典拓撲學對於理解具有無限數量點的空間(例如平面或球體)最有幫助——它不是研究僅具有有限數量點的空間的好工具。

經典拓撲學和數字拓撲學之間的關鍵區別在於連續性的定義。我們習慣於將函式的連續性視為與其圖形有關的東西。連續函式的圖形不能跳躍或有孔。這個定義取決於能夠測量平面中點之間的距離,並且能夠使這些距離任意小。這一切都很好,但是當涉及到有限空間時,它對我們的幫助不大,在有限空間中,點之間距離的縮小是有限制的。如果你的空間中只有三個點,那麼最多有三個距離,其中一個必須是最小的。如果點之間存在最小(非零)距離,我們正常的連續性概念就不能很好地工作。在數字拓撲學中,連續性不是基於距離(對於那些更喜歡擺脫度量約束的更抽象的拓撲學家來說,它也不是基於開集),而是基於空間中點之間的連線。

數字影像是點的有限集合,以及關於哪些點彼此連線的資訊。如果原始影像中連線的每對點都對映到新影像中連線的一對點(或對映到同一點),則兩個數字影像之間的對映稱為連續的。在經典拓撲學中,同倫的概念是基於能夠以連續的方式移動路徑,就像在籃球上滑動橡皮筋一樣。數字同倫的定義與經典拓撲學中的定義相同,但連續性的定義不同。新定義有一些意想不到的後果,你可以在斯塔克與他的夏季研究專案學生傑森·哈曼、梅格·墨菲和凱西·彼得斯*合寫的一篇論文中閱讀到。

該遊戲所基於的夏季專案是確定哪些數字影像是不可約的,也就是說,哪些數字影像與點數較少的數字影像不同倫。在他們的研究中,他們對七個或更少點的數字影像進行了分類,並發現了兩個數字影像同倫的標準。這些標準導致了線上遊戲的規則。

他們只對最多七個點的影像進行分類這一事實應該能緩解你與 CAPTCHA 相關的擔憂。數字拓撲學不會讓你更難釋出你關於彩虹蛋糕和/或共產主義的非常重要的意見。隨著點數的增加,問題的難度增長得非常快。“友好的鄰居”旨在將分類擴充套件到八點和九點空間。他們能夠將八點情況的案例數量減少到 160 個,九點情況的案例數量減少到 3,251 個(如果你知道有 11,117 種可能的八點數字影像和 261,080 種九點數字影像,這會更令人印象深刻)。

從技術上講,該遊戲只能顯示數字影像是可約的。要最終證明影像是不可約的,就相當於證明某物不存在,這比透過找到某物來證明某物存在更難。但是,如果許多使用者未能解決其中一個關卡,這就有力地證明了影像是不可約的,斯塔克或其他研究人員可以嘗試最終證明影像是不可約的。目前,大約有 30 個未解決的八點影像,斯塔克認為它們可能是不可約的。只有幾百個九點關卡被解決,所以還有很多事情要做。

當斯塔克第一次想到製作這個遊戲時,他不確定它是否會有趣。“對於普通遊戲,你對你想要遊戲的內容有一些想法,然後你製作遊戲,並且你可能會更改規則以使其更容易或更難或更有趣,”他說。“對於這個遊戲來說,這實際上是不可能的。我先有了規則,然後不得不圍繞它們製作遊戲。它有點不得不按照它現在的方式設計,而且它是否會很有趣實際上不由我決定。”

斯塔克受到了圖論遊戲 planarity.net 的啟發。顧名思義,該遊戲的目標是重新排列圖的圖片,直到它明顯是平面的,也就是說,直到沒有邊彼此交叉。Planarity 和“友好的鄰居”都出奇地上癮,所以玩遊戲風險自負!

*這句話最初拼錯了凱西·彼得斯的名字。對不起,凱西!

© .