Pukoban Solver

Sokoban(推箱子) is a classic single agent game. It has a sufficient of game state and is a classic problem in the field of game AI.
Pokoban is a variation of the game, adding “Pull” to the game. You can pull a box when there is an empty space behind you and a box in front. This additional action gives the game even wider branching factor, making the search harder.
Here is the game interface that you can actually play the game:

Checkout my repository for the game: Single agent game – Pukoban

距離結束半年終於要開始寫助教心得,很感謝徐贊昇教授給一個仍然在大學部的人這次機會擔任助教。我相信我也是傾盡全力讓大家有最好的修課體驗。
以下是第 108 學年擔任電腦對局理論中助教時出的第一份作業。

No deadlock

原本 Sokoban 因為只有 “Push” 這個移動箱子的方法,所以有很多 deadlock 。但是加上 “Pull” 的操作之後非常大部分 deadlock 就不見了。這使得剪枝變得十分困難。可以往不一樣的地方嘗試。這裡希望寫作業的人可以觀察到這點而把解題方向轉往 heuristic 或別的搜尋方法嘗試。

Heuristic Solution

對 heuristic 來說有許多可能設計的方法。對整張圖你依照箱子的可能走向把他轉成一個有向圖,因為給的盤面面積大小都不大,所以可能的節點好與邊不大。

轉成有向圖之後,你可以用很多方法來嘗試匹配箱子與他對應的終點:

  • 經典的匈牙利匹配演算法
  • 對箱子們與終點們做簡易的 Dijkstra

利用以上你可以嘗試啟發式搜尋 IDA* 。

Bi-Directional BFS Solution

因為巨大的 branching factor ,另一個很直覺的解決方法是用雙向 BFS 。在此你還可以用 multi-threading 來達到平行化計算。

Bit State Optimization

在搜尋的過程中要不斷紀錄盤面來避免重複拜訪。這是在搜尋過程中最常做的操作,所以在這上面做優化可以帶來相當好的回報。既然盤面面積在 50 以下而且有長寬的限制,可以在 64 bit 內來紀錄當前盤面狀態(箱子所在位置,玩家位置) 這樣判斷重複盤面就是在查詢 hashmap 中是否出現過該數字。而且在盤面的改變上也可以用 bit operation 來實現。這樣的常數優化可以帶來 3 倍以上的加速,在狀態極多的狀態下是很好的優化。

結語

我想在電腦對局理論這門課對經典搜尋的認識仍然是必不可少的。但還有更多複雜的問題,我想 reinforcement learning 可以被加入這門課的未來發展中,因為還有更多遊戲不會有一個終端的 win/lose ,而是 score-base 而且可以是 infinite game 。可能會有遊戲是我們無法解決而可以用 DL 來看到 pattern 。

但在這份出來之後原本 40 個人修課到繳交日剩下 24 個人了,看來還不是時候出更難的作業?不過這也應該能讓有寫出作業的人更有成就感。最上面的連結中也有我寫出來的 bi-directional BFS with bit state representation ,歡迎看看。

Author: eopXD

Hi 我是 eop ,希望人生過得有趣有挑戰XD

Leave a Reply