Deadlock and Optimizations

Deadlock detections

Simple corner deadlock detection

The simple corner deadlock that was already implemented aims to prevent a box from being pushed into a corner. If it is pushed into a corner, it is inaccessible and immovable, thus rendering that state unsolvable.

Freeze deadlock detection

Described here, freeze detection is about preventing two boxes from being adjacent against a wall when there is no goal in that location. This deadlock detection was chosen as there are many scenarios (such as in test_maps/test_map2 and test_maps/test_map3) where there are multiple boxes and a complex map layout. This deadlock detection saves a small amount time and reduces the number of nodes that are expanded.

The code for this detection is contained in utils.c, from lines 321 - 480. The function freeze_deadlock() is used to check if there is a box adjacent to the player, and if there is, then the function adjacent_box_check() is called to check for the freeze deadlock scenario.

Optimisation results

These results show the impact of implementing the freeze deadlock detection.

Hardware used:

CPU: AMD Ryzen 4800U
GPU: AMD Radeon RX Vega 8
Memory: 16GB

Summary of optimisation

The following table summarises some of the key statistics prior to implementing freeze deadlock detection, and after implementing freeze deadlock detection.

Test: test_map1

Statistic	Before implementation	After implementation	% improvement
Expanded nodes	13	13	0.00
Time (s)	0.050106	0.047723	4.76

Test: test_map2

Statistic	Before implementation	After implementation	% improvement
Expanded nodes	978745	944140	3.54
Time	3.456764	3.227685	6.63

Test: test_map3

Statistic	Before implementation	After implementation	% improvement
Expanded nodes	230041	215253	6.43
Time	1.828733	1.680901	8.08

Full output (before optimisation)

$ ./sokoban -s test_maps/test_map1

SOLUTION:
rrRRRR

STATS:
	Expanded nodes: 13
	Generated nodes: 48
	Duplicated nodes: 8
	Solution Length: 6
	Expanded/seconds: 259
	Time (seconds): 0.050106

$ ./sokoban -s test_maps/test_map2

SOLUTION:
rrrrrrdrdLLLLLLLLullluRRRRRRRururRRRRRRRRRR

STATS:
	Expanded nodes: 978745
	Generated nodes: 3914976
	Duplicated nodes: 2288345
	Solution Length: 43
	Expanded/seconds: 283139
	Time (seconds): 3.456764

$ ./sokoban -s test_maps/test_map3

SOLUTION:
drdrdrdrrruuuuuulllllddrdrdrDulululldRdRdrdRRllululuurdrdrDululldRuuluurrrrrdddddrddlUUUUUUruLLLLLulDDdrdddrdRRlluluurdrDulldruluulldRuuurrrrrdddddrddlUUUUUUruLLLLLulDDdrdrdddRRlluurDldRuulululldRdRluuuurrrrrdddddrddlUUUUUUruLLLLLulDDdrdrdrddRluulululldRdRluuuurrrrrdddddrddlUUUUUUruLLLLLulDD

STATS:
	Expanded nodes: 230041
	Generated nodes: 920160
	Duplicated nodes: 331571
	Solution Length: 292
	Expanded/seconds: 125792
	Time (seconds): 1.828733

Full output (after optimisation)

$ ./sokoban -s test_maps/test_map1

SOLUTION:
rrRRRR

STATS:
	Expanded nodes: 13
	Generated nodes: 48
	Duplicated nodes: 8
	Solution Length: 6
	Expanded/seconds: 272
	Time (seconds): 0.047723

$ ./sokoban -s test_maps/test_map2

SOLUTION:
rrrrrrdrdLLLLLLLLullluRRRRRRRurruRRRRRRRRRR

STATS:
	Expanded nodes: 944140
	Generated nodes: 3776556
	Duplicated nodes: 2199712
	Solution Length: 43
	Expanded/seconds: 292513
	Time (seconds): 3.227685

$ ./sokoban -s test_maps/test_map3

SOLUTION:
drdrdrdrrruuuuuulllllddrdrdrDulululldRdRdrdRRllululuurdrdrDululldRuuluurrrrrdddddrddlUUUUUUruLLLLLulDDdrdddrdRRlluluurdrDulldruululldRuuurrrrrdddddrddlUUUUUUruLLLLLulDDdrdrdddRRlluurDldRluuululldRdRluuuurrrrrdddddrddlUUUUUUruLLLLLulDDdrdrdrddRluulululldRdRluuuurrrrrdddddrddlUUUUUUruLLLLLulDD

STATS:
	Expanded nodes: 215253
	Generated nodes: 861008
	Duplicated nodes: 309654
	Solution Length: 292
	Expanded/seconds: 128058
	Time (seconds): 1.680901

4.4 KiB Raw Permalink Blame History