倉庫番遊戲之最少搬移演算法分析與研究

Abstract

倉庫番遊戲是一種搬移策略規劃的有趣問題，問題的挑戰來自於對死結盤面的偵測及如何以有用的策略減少搜尋的空間，過去的研究者以單一代理人搜尋法，透過對死結盤面動態建立盤面資訊做比對，得到了一些成果，但並未能得到最少搬移步數的答案。 我們的研究採反向搜尋的方式來減少死結情況的發生及使死結的偵測工作容易實行。在實驗中我們也發現了跳躍式串列(Skiplist)比AVL平衡樹在資料插入及搜尋上有較好的表現。我們的演算法經過實際程式的執行結果，與前人的研究比起來最大的突破在於我們成功地找到了90個XSokoban倉庫番遊戲中63個盤面的最少搬移步數的解答。

Sokoban game is a motion planning problem. The main challenge of this problem is to detect deadlock states and to reduce the search space with good stratagems. Previous researchers designed single-agent search methods to solve Sokoban game. Single-agnet search methods dynamically build patterns to detect deadlock, but it can not ensure that the result of moving steps is minimal. In this thesis, we use backward search method to decrease deadlock states and to make deadlock detecting easily. In our experiments, we also find out that Skiplist has better performance than AVL-tree in inserting and searching data. Our algorithm can solve 63 out of 90 XSokoban games and find out those games’ minimal moving steps successfully, This result is better than previous researches.