Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban
Authors: André G. Pereira, Robert Holte, Jonathan Schaeffer, Luciana S. Buriol, Marcus Ritt
IJCAI 2016 | Venue PDF | 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 EMAIL Robert Holte and Jonathan Schaeffer University of Alberta, Canada EMAIL Luciana S. Buriol and Marcus Ritt Federal University of Rio Grande do Sul, Brazil EMAIL |
| 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. |