全球专业中文经管百科,由121,994位网友共同编写而成,共计435,726个条目

天使問題

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

什麼是天使問題

  天使問題是由英國數學家約翰·何頓·康威提出的一個博弈論問題,在2006年已獲解答。

  天使問題是關於一個叫天使與惡魔(Angels and Devils)的雙人游戲,其規則如下:

  1.兩名玩家分別扮演天使和惡魔

  2.游戲開始前,指定一個正整數 K,稱之為天使的力量

  3.游戲在一個無限大的方格棋盤上進行;開始時棋盤是空的,天使停留在棋盤上的某一個方格(稱為天使的起始點),惡魔並不存在於棋盤上

  4.每一輪中,惡魔可以在棋盤上放置一個路障,路障不可以放置在天使停留處

  5.每一輪中,天使可以向相鄰格移動至多 K 步,移動過程中可以穿過路障,但移動終點必須停留在沒有路障的格中;縱橫斜格均算作相鄰格

  6.從惡魔開始,雙方交替進行(若從天使開始,從上面的規則描述,亦可等價轉換為從惡魔開始的局面)

  7.若在一輪中,天使無法移動,則惡魔獲勝

  8.如果天使能夠無限地繼續游戲,則天使獲勝

  天使問題可以陳述為:是否存在某個K,使得力量為K的天使擁有必勝策略?   

天使問題的已知證明

  • K = 1 時,惡魔有必勝策略(康威, 1982)
  • 如果天使不可以降低其 y 坐標,則惡魔有必勝策略(康威, 1982)
  • 如果天使一直增加它到起始點的距離,則惡魔有必勝策略(康威, 1996)

  在2006年,有4位數學家獨立解決了天使問題。

  • 英國數學家布萊恩·鮑迪奇(Brian Bowditch)證明瞭K=4的時候,天使有必勝策略。
  • 挪威數學家Oddvar Kloster 和 András Máthé 各自證明瞭K=2的情況。
  • Péter Gács 則是證明瞭當 K 充分大時,天使有必勝策略
本條目對我有幫助12
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目投訴舉報

本条目由以下用户参与贡献

otf125.

評論(共0條)

提示:評論內容為網友針對條目"天使問題"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

以上内容根据网友推荐自动排序生成

下载APP

闽公网安备 35020302032707号