DocumentCode
2652035
Title
A Tabled Prolog Program for Solving Sokoban
Author
Neng-Fa Zhou ; Dovier, A.
Author_Institution
Dept. of Comput. & Inf. Sci., CUNY Brooklyn Coll. & Grad. Center, Brooklyn, NY, USA
fYear
2011
fDate
7-9 Nov. 2011
Firstpage
896
Lastpage
897
Abstract
This paper presents our program in B-Prolog submitted to the third ASP solver competition for the Sokoban problem. This program, based on dynamic programming, treats Sokoban as a generalized shortest path problem. It divides a problem into independent sub problems and uses tabling to store sub problems and their answers. This program is very simple but quite efficient. Without use of any sophisticated domain knowledge, it easily solved 11 of the 15 instances used in the competition.
Keywords
PROLOG; computational complexity; dynamic programming; search problems; ASP solver competition; B-Prolog; Sokoban problem; dynamic programming; generalized shortest path problem; tabled Prolog program; Benchmark testing; Conferences; Dynamic programming; Information science; Programming; Shortest path problem; System recovery; Dynamic programming; Prolog; Tabling; Th Sokoban puzzle;
fLanguage
English
Publisher
ieee
Conference_Titel
Tools with Artificial Intelligence (ICTAI), 2011 23rd IEEE International Conference on
Conference_Location
Boca Raton, FL
ISSN
1082-3409
Print_ISBN
978-1-4577-2068-0
Electronic_ISBN
1082-3409
Type
conf
DOI
10.1109/ICTAI.2011.145
Filename
6103436
Link To Document