MSN 寶石方塊五千萬分?

六月 5, 2005 @ 6:20 pm · Filed under Computer Technology

MSN 寶石方塊自走機是我在兩年前, MSN 寶石方塊 Game 剛出來不久的時候寫的.
那時候寶石方塊剛出來的時候, 真的是一天到晚都在玩這東西,
不過玩久了之後也會累, 所以那時候就想說要來寫一個自動玩的程式…

當初有很多朋友ㄧ起在拼寶石方塊, 大家都會在比誰誰誰創了最高紀錄,
我在玩了一陣子之後寫了這個自動玩的程式, 跑出了一個完全不可能的分數…
後來很多人就不玩了~~ 因為是人都不可能超越的 XD
而且之後似乎分數太離譜, 以至於我寶石方塊所有的戰績都被 MSN 官方砍掉了 XD
(X咧~~連我之前正常玩了幾百盤的紀錄都不見了..)
後來我不爽又去跑一次, 再弄一個超高的分數上榜, 結果沒過多久又被砍掉了 @@||
然後有一陣子沒有再去玩寶石方塊了,
最近因為在寫MSN 踩地雷的程式又想到它, 所以就拿出來玩一下..

MSN 的寶石方塊有兩種遊戲模式:
一種是不限時間, 但是玩到沒有方塊可以移的時候就 Game over…
另一種是有時間倒數, 當時間倒數到底就會 Game over,
可是玩到沒方塊可以移的時候他會清空給你一盤新的繼續玩…
但是時間倒數的速度會隨著遊戲的等級越高而越來越快,
到後面得要把方塊消快一點時間才會增加…所以到後面很容易 timeout 而 Game Over.

後來我發現的是, 要玩不限時間的方式又要玩到高分有點困難,
因為棋盤要都有路可走, 除了好的移動方式之外, 還要靠運氣!
一般來講玩這種模式的話分數都有個瓶頸, 很容易就莫名奇妙沒得移動而死掉..
而且要設計好一點的演算法讓他一直有路的話需要花比較多心血,
加上計算的時間也會比較長, 所以我不用這個模式去跑…

所以我採用的是第二種模式, 也就是限時間但是不用擔心沒有方塊可以移的模式.
反正電腦的運算速度就是快, 所以我不怕他時間倒數,
而且在分析移動方式的時候也不用一定要最佳解, 只要較好的解的就可以了,
反正沒得移的時候他會給你一盤新的 XD

我這邊也沒有用什麼精心設計的 AI 去玩它, 我只是用簡單的分析法則:
對於每個可移動的方式 (移動後會造成消去) 給予一個 bound, bound 的計算方式為:
(1).
bound1 為此進行此移動後可造成的棋盤最大「可消去連接」的方塊數,
這可能是橫向也可能是縱向, 若有橫向跟縱向的組合, 例如十字型或 L 型的連接,
則此 bound1 為縱向消去方塊去和橫向消去方塊數相加.
(2).
經過此移動, 可消去方塊消掉後, 計算消去的位置上面的方塊掉下來後的棋盤,
未知的部份 (也就是上方補進來的新方塊) 假設為沒有方塊,
然後把這個棋盤進行步驟 (1) 的計算, 並把 bound 乘兩倍後成為 bound2.
最後此移動得到的 bound 值為 bound1+bound2.
也就是多計算一層連鎖消去, 連鎖消去的方塊 bound 值會乘兩倍, 所以連鎖越多值越高.
(3).
並且在所有可移動方式中, 依照下面的項目找出最大值的來移動 (若相同則比較下一項):
a. bound (bound1+bound2).
b.連鎖消去後, 最後 stable 棋盤中可移動的數目.
c. 連鎖消去後, 最後 stable 棋盤中「兩個同色方塊連接在一起」的組數.

我會只算一層連鎖的關係是因為經過了一層連鎖之後,
棋盤內剩下確定的方塊差不多會只剩一半了, 其他都是後來上面補進來的方塊,
這些補進來的方塊我們沒辦法知道他是什麼顏色的, 所以多算太多應該也沒什麼用.

用程式抓取螢幕上的畫面, 分析出每個位置各是什麼顏色的方塊,
在依照這些 rules 去計算要怎移動棋盤中的方塊, 結果就成為寶石方塊自走機了.

另外我沒有設計更聰明的演算法有幾個原因:
1. 因為要求速度要很快, 如果演算法複雜速度不快的話很容易就 timeout 掛掉.
2. 當連鎖消去很多的時候很容易就晉級, 晉級的時候整個棋盤幾乎會被 bonus 消光,
如果這時候用了複雜的演算法, 去設計「可以造成連鎖的排列方式」也只是浪費掉而已.

下面有一些在玩的過程中的影片 (使用 DivX 格式壓縮):

Diamond.DivX.15fps_1.avi (9,972 KB) 剛開始的時候
Diamond.DivX.15fps_2.avi (18,976 KB) 七百萬分的時候
Diamond.DivX.15fps_3.avi (20,512 KB) 兩千多萬分的時候

我前幾天測試了一下, 看程式最高能玩到多少分,
結果後來跑到五千多萬分的時候我手賤不小心按到滑鼠, 結果程式變成抓不到畫面,
接下來在三秒鐘內下面的時間馬上倒數到底, 然後就掛掉了 XD
後來我也懶的再去跑一次, 因為這次跑到五千多萬分就跑了 12 個多小時…….. @@||
我本來還期待它的畫面會破表的 XD

diamon

引用資料:http://lcr.old-castle.org/

kissinwang 發表在 痞客邦 PIXNET 留言(0) 人氣()