Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban
Authors: André G. Pereira, Robert Holte, Jonathan Schaeffer, Luciana S. Buriol, Marcus Ritt
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present a novel admissible pattern database heuristic (D) and tie-breaking rule (L) for Sokoban, allowing us to increase the number of optimally solved standard Sokoban instances from 20 to 28 and the number of proved optimal solutions from 25 to 32 compared to previous methods. 5 Experimental Results In this section, we compare our proposed heuristic D and tiebreaking rule L with the state-of-the-art heuristic I and tiebreaking rule F. |
| Researcher Affiliation | Academia | Andr e G. Pereira Federal University of Rio Grande do Sul, Brazil agpereira@inf.ufrgs.br Robert Holte and Jonathan Schaeffer University of Alberta, Canada {holte,jonathan}@cs.ualberta.ca Luciana S. Buriol and Marcus Ritt Federal University of Rio Grande do Sul, Brazil {buriol,marcus.ritt}@inf.ufrgs.br |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | Yes | The standard test set x Sokoban of 90 instances is used. [Myers, 2016] Andrew Myers. Standard set. www.cs.cornell.edu/andru/xsokoban.html, February 2016. |
| Dataset Splits | No | The paper mentions using 'The standard test set x Sokoban of 90 instances' but does not specify training, validation, or test dataset splits needed for reproduction beyond this. |
| Hardware Specification | Yes | All experiments were run on a PC with an AMD FX-8150 CPU running at 3.6 GHz with 32 GB of RAM. |
| Software Dependencies | No | The paper does not provide specific software dependency names with version numbers. |
| Experiment Setup | Yes | PDBs built with k0 = 4 are the largest that can be built for all instances in one hour, and previously provided the best results. Thus, we fix the size of k0 = 4 in all our experiments. We use the standard limits for Sokoban of 20 million expanded nodes or one hour of CPU time. |