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 ，歡迎看看。

Original link: eopXD