牧葉的窩

[ Angel problem ]


這遊戲蠻有趣的，所以稍微紀錄一下~

在獵人知識家(HXH)休刊又休刊之後~~有人發問了：

10/29 fatedice     □ [問題] 有人知道這個數學問題的答案嗎

內容是：

睡不著，突然想到前一陣子看數字搜查線裡面提到的一個問題大致是這樣

在一個無限大的棋盤裡面有一位天使，天使一次只能移動一格，惡魔不能移動，
但是每次可以在棋盤上放置一個惡魔，惡魔最後有辦法堵住天使嗎？

好像有牽涉到很深奧的數學，不知道有沒有人知道答案，先謝過了。
題外話，在等待出刊的日子，不做些甚麼事情打發時間真的會受不了啊


在等待的日子裡引起了話題...
一般人其實對無限大的議題其實沒有很了解...
很多數字或定義在無限大的情況下都是無意義的...
但大家很熱烈的討論~~

其中有一篇jacky80336版友玩過一個遊戲還蠻有趣的：
這跟以前玩得圍貓遊戲很像
只是遊戲中是六方向的
附上連結：http://www.gamedesign.jp/flash/chatnoir/chatnoir.swf

大家繼續討論了很多篇之後
版友Xixan表示：
名字是 Angel problem
維基條目: http://en.wikipedia.org/wiki/Angel_problem
真的想認真了解的話可以看一下 External links 的那篇
The Angel Problem  John H Conway
http://www.msri.org/publications/books/Book29/files/conway.pdf

接著版友kerbi認真看完後發表了結論文：

以下有解答....你確定不再多想一下嗎XDDD

直接給想知道結論的人答案吧：
                                   ┌ 文章此處的確是寫32*33
                                   ↓
       "Berlekamp Conway已經證明在一個至少32*33的棋盤上，惡魔會贏過天使。"


然而他們還在繼續研究這種問題，稱為Angel Problem。
首先定義這種一次只能以國王方式移動一步的天使為 "Angel of power 1"
則Angel Problem即為：

       "驗證在某些power底下的Angel能否贏過惡魔。"

"Angel of power 1" 已經被solve
現在他們想往更高的power去解


Conway還證明了三個重要的結論：

1. 如果天使的每次移動從不減少她的y座標值的話，則惡魔有必贏策略。(1982)
2. 如果天使的每次移動都使她離(她的)原點越來越遠的話，則惡魔有必贏策略。(1996)
3. 如果某階天使擁有必贏策略的話，則在該策略中，如果天使跳開後，在她原本的起點
   所可能到的所有格子上都放上惡魔(不包括天使現在所在的格子)，天使依然必贏。
   (此動作不算是惡魔的一步，是附加在天使移動後的動作)
4. 剛剛找到的最新資料 在2006年已經有人證明2階天使有必贏策略
   證明pdf連結： http://0rz.tw/XYDrO




以上~共討論了31篇