cube files
Indexed Cube Lovers Archive
5x5 puzzle: Comparison between reduction chains (STM, 10000 instances)
Submitted by stannic on Tue, 10/09/2012 - 04:48.
The multi-chained approach used in kumi na tano allows to use multiple search chains at the same time. The main advantage is that the best chain can be choosen depending on the instance to be solved, rather than hard-coded into the search algorithm.
For example, the first of the following two 5x5 instances has its leftmost column solved, while second has solved four tiles in top-right corner.
[1] 1 17 9 10 18 18 3 16 4 5 6 0 2 3 8 11 7 17 9 10 11 5 22 7 4 19 2 23 0 21 16 15 20 23 13 6 20 14 12 1 21 19 12 14 24 13 8 15 22 24
We cah use multi-chained approach here. The following two partitioning schemes:
[2]
I II
1 2 3 3 3 2 2 1 1 1
1 2 3 3 3 2 2 2 1 1
1 2 4 4 4 3 3 4 4 4
1 2 4 4 4 3 3 4 4 4
1 2 4 4 - 3 3 4 4 -
- in combination lead to a two-chained four-phase search algorithm. The first of instances on diagram [1] can be better solved (probably) using scheme I, since with this scheme the instance has its 1st stage already solved. Second one can be probably solved better using scheme II since 4 of 5 tiles that must be solved in phase 1 are already solved.
There is a question: given the size of the puzzle (width and heigth), the move metric and the number of search phases, what is the best chain to be used in simple single-chained multi-phase search? For example, what of two schemes on diagram [2] has higher probability to give optimal solution in STM metric for the randomly choosen 5x5 puzzle instance?
So I decided to perform comparison between some possible chains and combinations of chains by solving the sample of 10,000 random instances of Twenty-Four puzzle in STM metric. I've used six different chains. All these chains are shown on diagram [3] as four-stage reductions from 5x5 puzzle to the solved state (I). I note that 5x4 is the puzzle with 5 columns and 4 rows, while 4x5 is the puzzle with 4 columns and 5 rows.
[3] 1) 5x5 > 5x4 > 5x3 > 5x2 > I 2) 5x5 > 5x4 > 5x3 > 3x3 > I 3) 5x5 > 5x4 > 4x4 > 3x3 > I 1a) 5x5 > 4x5 > 3x5 > 2x5 > I 2a) 5x5 > 4x5 > 3x5 > 3x3 > I 3a) 5x5 > 4x5 > 4x4 > 3x3 > I
Below are given some statistics for various sets of these chains. Each row of the table [4] represents single launch of the solver over the sample of 10,000 random instances. The sample is the same in all runs.
The first column lists the chains used in launch. For example, 3+3a means that the solver was using reduction chain 5x5 > 5x4 > 4x4 > 3x3 > I along with its mirror reflection.
For each set of chains used, I ran the solver three times.
First, the program was set to find only one solution by finding the only optimal solution for each of phases. These launches are denoted by "1st" code in "limits" column.
Next, kumi na tano was set to try also alternative optimal solutions in each phase in order to possibly optimize overall solution. These launches are denoted in the table as "sl0" in "limits" column (sl0 stands for slackness = 0).
Finally, the solver was set to allow also one non-optimal move in any one of search phases (that is, the search was performed with 0 ≤ slackness ≤ 1). These launches shown in the table with "sl1" in "limits" column.
I note that the full set of chains (1+1a+2+2a+3+3a) has been launched additionally with limit 2 on slackness (0 ≤ slackness ≤ 2). This launch is shown in the last row of the table [4] with "sl2" in "limits" column.
For each launch, the average time per instance, the minimum, maximum and average length of solution and average number of visited regions (i.e. started search phases) is shown in the corresponding columns of the table. Last column shows the number of instances solved with each of chains used. For example, after running two-chained search with chains 1 and 1a from diagram [3] and slackness value limited to 0, the number of instances solved with chain 1 was 4964, and the number of instances solved with chain 1a was 5036.
[4]
---------------------------------------------------------------------------------------------
chains limits time length rnodes proportion of chains
avg min max avg avg
---------------------------------------------------------------------------------------------
1 1st 3.272 ms 89 188 144.5478 4.0000 10000
sl0 46.150 ms 85 178 132.7038 1703.6038 10000
sl1 227.103 ms 85 166 129.4326 10243.3826 10000
2 1st 4.704 ms 87 186 138.6718 4.0000 10000
sl0 46.339 ms 81 168 128.7222 912.2307 10000
sl1 198.343 ms 81 163 126.0578 5487.0849 10000
3 1st 4.541 ms 89 177 137.6858 4.0000 10000
sl0 52.348 ms 85 165 127.4860 870.2424 10000
sl1 154.030 ms 85 163 124.9416 4646.3157 10000
1+1a 1st 3.564 ms 85 183 142.8618 4.0000 5194 + 4806
sl0 69.875 ms 84 167 128.7094 2697.4575 4964 + 5036
sl1 289.384 ms 84 161 125.8832 15015.9378 4945 + 5055
2+2a 1st 3.229 ms 87 183 137.1806 4.0000 5194 + 4806
sl0 56.624 ms 81 158 125.2678 1456.2104 5064 + 4936
sl1 222.304 ms 81 155 123.0036 8420.9046 5044 + 4956
3+3a 1st 3.159 ms 89 176 136.9672 4.0000 5194 + 4806
sl0 66.205 ms 85 159 124.5896 1459.2220 5100 + 4900
sl1 236.012 ms 81 157 122.4238 7646.5086 5074 + 4926
1+1a+2+2a+3+3a 1st 3.350 ms 89 183 138.0446 4.0000 2352 + 2179 + 143 + 136 + 2699 + 2491
sl0 110.230 ms 81 156 122.9030 2590.1651 468 + 486 + 1886 + 1897 + 2716 + 2547
sl1 410.076 ms 81 155 120.8876 13490.9681 491 + 524 + 1877 + 1877 + 2677 + 2554
sl2 2398.839 ms 79 149 117.5580 79379.3114 526 + 557 + 1950 + 1857 + 2564 + 2546
---------------------------------------------------------------------------------------------
The following table shows for each launch the number of configurations solved in n moves as function of n. Each column represents a single launch.
[5]
--------------------------------------------------------------------------------------------------------
chains 1 2 3 1+1a 2+2a 3+3a 1+1a+2+2a+3+3a
limits 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 sl2
--------------------------------------------------------------------------------------------------------
length the number of puzzle configurations
--------------------------------------------------------------------------------------------------------
79 - - - - - - - - - - - - - - - - - - - - - 1
80 - - - - - - - - - - - - - - - - - - - - - -
81 - - - - 1 1 - - - - - - - 1 1 - - 1 - 1 1 4
82 - - - - - - - - - - - - - - - - - - - - - 3
83 - - - - - - - - - - - - - - - - - - - - - 1
84 - - - - - - - - - - 1 1 - - 2 - - - - 1 2 3
85 - 1 1 - - - - 1 1 1 2 2 - - - - 1 1 - 1 1 1
86 - - - - - - - - - - - - - 2 - - 1 2 - 1 - 3
87 - 1 1 1 2 3 - - 2 - 1 1 1 2 3 - - 2 - 2 5 8
88 - - - - 1 1 - 1 2 - - - 1 1 1 - 1 2 - 1 2 3
89 1 - 1 1 1 - 1 2 5 1 1 2 1 2 1 2 2 6 2 4 6 4
90 - 1 1 - 2 2 - - 1 - 1 2 - 3 3 - 1 1 - 4 3 18
91 - 1 1 - 4 5 1 3 3 - 1 1 2 7 7 2 9 6 1 9 6 13
92 1 1 2 - - 1 1 4 7 - 4 4 - - 4 1 9 15 1 7 17 25
93 1 2 2 - 2 2 1 4 4 2 5 5 1 3 4 1 6 9 1 6 8 25
94 - 3 3 - 2 5 1 6 7 1 6 7 1 6 11 2 10 11 3 15 17 22
95 - 6 5 - 1 5 2 8 8 - 8 8 2 6 11 - 6 8 - 8 13 15
96 - 3 4 2 8 12 1 8 12 1 3 7 3 14 19 - 12 17 1 16 23 49
97 - 2 7 2 6 10 2 6 5 1 5 11 2 12 18 2 8 10 1 15 19 46
98 - 4 8 - 10 18 2 12 16 - 5 12 2 17 31 2 24 31 2 28 42 67
99 2 4 5 1 10 18 4 10 26 4 4 8 2 10 16 3 23 34 5 26 40 75
100 - 6 16 4 16 22 3 25 37 2 13 32 8 30 37 2 32 45 3 46 55 76
101 4 9 16 7 19 27 4 12 26 4 15 24 5 27 42 4 22 33 9 39 53 89
102 - 12 23 8 30 44 9 37 39 6 29 37 9 47 52 8 45 51 7 60 70 127
103 - 16 18 2 23 31 4 34 44 - 25 35 4 33 51 7 52 72 5 56 79 138
104 4 20 40 9 43 51 10 35 56 3 35 56 12 56 73 18 52 83 15 71 94 152
105 3 13 29 6 31 48 9 48 68 1 25 40 13 54 73 7 70 89 6 84 104 157
106 5 20 35 16 40 58 17 54 70 6 38 56 18 78 112 18 81 107 15 111 141 212
107 1 25 48 11 36 58 11 71 81 1 41 69 16 70 98 16 87 109 13 95 143 212
108 5 45 52 19 65 91 18 78 104 10 66 88 29 90 123 20 109 136 23 134 160 236
109 7 37 49 16 77 95 22 66 94 8 67 89 15 118 138 22 105 156 23 150 175 256
110 10 55 70 27 106 158 17 93 131 13 100 122 35 131 172 19 142 178 15 179 211 269
111 11 45 73 22 67 116 31 114 136 11 88 125 28 117 174 38 146 169 34 163 208 287
112 13 93 129 30 129 145 46 143 182 19 128 160 37 193 215 54 181 230 46 221 283 357
113 15 72 108 46 126 174 44 143 189 22 119 163 40 186 247 44 189 226 42 233 279 348
114 28 116 154 37 145 208 52 178 219 27 146 190 56 218 272 57 241 272 60 278 302 353
115 23 95 142 48 178 217 58 160 219 31 151 216 57 251 288 65 221 277 63 287 326 392
116 37 109 166 59 187 227 71 205 251 45 158 233 60 251 300 74 264 288 78 291 330 410
117 24 129 181 66 185 243 82 220 274 38 181 244 81 230 299 86 277 320 89 302 332 399
118 41 161 214 109 237 252 79 251 307 49 231 284 105 293 303 95 305 381 91 333 380 422
119 41 167 210 87 235 282 85 255 325 39 226 265 107 303 339 89 330 372 84 349 389 380
120 59 196 247 110 243 299 121 288 361 63 264 309 145 310 356 121 356 399 109 361 412 418
121 50 218 281 103 272 316 100 301 363 55 290 356 134 328 354 135 332 380 114 346 380 366
122 72 218 265 139 293 352 164 318 351 88 280 343 143 343 413 161 346 385 166 370 404 410
123 76 229 269 141 312 353 166 337 339 101 283 321 161 369 385 167 365 383 162 389 398 339
124 80 274 314 161 338 385 185 361 390 91 349 389 174 369 402 191 389 414 176 393 404 380
125 88 294 367 160 311 346 168 302 361 103 377 422 189 369 374 166 343 353 141 339 334 282
126 119 271 337 191 357 387 185 370 405 137 347 409 222 422 422 198 400 400 203 418 398 311
127 104 261 321 188 327 363 227 359 359 126 335 345 200 374 381 241 350 344 218 356 350 267
128 130 311 370 190 381 411 262 386 405 146 371 401 207 386 406 271 390 397 231 381 370 271
129 136 297 334 230 367 376 237 338 317 149 322 342 275 338 329 252 368 324 231 339 283 214
130 130 325 399 265 378 367 266 359 368 170 398 416 292 396 353 277 382 332 243 350 302 223
131 161 329 342 243 339 316 282 347 318 206 345 345 283 314 244 282 322 270 278 281 220 132
132 187 356 373 272 358 374 273 399 355 208 370 364 300 355 320 300 357 300 279 318 258 141
133 212 327 335 270 297 276 274 320 300 254 359 294 270 298 252 284 282 243 282 247 184 115
134 221 415 382 314 361 300 305 319 265 253 386 294 308 308 223 333 270 216 321 243 170 110
135 240 326 327 306 303 252 306 282 221 251 295 276 306 223 187 317 231 187 301 180 153 84
136 257 329 332 303 301 275 323 281 257 277 308 286 323 244 196 337 236 189 334 191 142 71
137 246 339 276 298 300 233 323 228 206 259 266 203 291 219 147 312 184 140 283 163 106 51
138 271 320 308 315 263 211 334 255 178 295 308 230 340 184 144 329 194 120 315 135 87 37
139 279 280 228 318 232 166 292 219 153 316 259 177 333 154 110 303 146 93 306 108 68 31
140 301 298 228 356 223 179 355 199 150 326 246 171 337 155 102 331 135 89 308 95 68 24
141 281 244 201 308 170 124 322 145 86 280 177 116 309 120 77 299 92 55 265 61 44 14
142 311 272 204 320 205 134 362 167 97 306 199 132 317 106 59 331 91 57 323 64 33 20
143 291 211 143 310 145 103 277 132 80 308 157 90 275 68 43 263 68 39 270 46 21 5
144 313 231 154 284 146 98 284 127 71 323 144 78 291 81 44 319 65 39 295 53 26 6
145 302 190 125 283 98 68 260 94 54 283 97 72 263 70 30 265 47 20 279 35 13 8
146 335 215 147 350 123 75 286 93 63 332 93 46 310 64 35 266 49 27 256 35 18 7
147 291 152 93 248 98 54 247 71 47 313 81 37 248 39 20 232 40 17 253 20 12 1
148 332 160 96 274 92 40 242 72 37 332 77 27 263 37 14 230 36 12 252 16 7 2
149 275 118 76 222 67 39 211 47 20 252 53 26 184 21 10 216 16 6 203 10 4 2
150 321 118 65 241 48 21 214 49 24 299 54 26 193 20 12 214 18 7 219 8 6 -
151 291 88 57 175 48 12 155 41 13 244 46 14 154 6 4 157 10 2 178 5 1 -
152 278 95 44 206 41 14 185 27 16 241 33 17 182 11 5 170 3 4 177 4 1 -
153 231 73 43 158 24 15 141 15 4 215 18 10 140 8 2 148 4 2 154 4 3 -
154 279 60 23 145 34 12 140 21 4 265 19 6 129 13 2 135 10 1 165 5 - -
155 215 60 16 150 21 7 128 10 6 208 15 4 122 10 3 103 5 3 121 3 1 -
156 227 52 14 125 11 5 140 9 - 206 17 3 115 1 - 116 1 - 140 1 - -
157 223 42 11 88 13 6 85 8 1 166 12 3 73 2 - 69 1 1 79 - - -
158 192 24 6 114 8 2 89 5 - 176 7 - 92 3 - 77 - - 108 - - -
159 142 24 6 75 6 1 63 4 2 149 3 - 60 - - 49 2 - 88 - - -
160 172 19 6 81 6 1 55 1 - 141 2 - 68 - - 54 - - 77 - - -
161 129 12 7 63 4 - 52 1 - 105 4 1 45 - - 51 - - 58 - - -
162 129 10 5 52 3 1 58 2 - 104 2 - 39 - - 43 - - 58 - - -
163 116 8 5 31 2 1 29 3 2 80 2 - 21 - - 21 - - 44 - - -
164 98 11 1 41 2 - 31 - - 80 - - 34 - - 26 - - 38 - - -
165 69 8 2 20 2 - 23 1 - 56 - - 18 - - 18 - - 30 - - -
166 87 3 1 24 - - 19 - - 65 - - 14 - - 9 - - 26 - - -
167 56 7 - 20 - - 12 - - 42 1 - 10 - - 12 - - 19 - - -
168 69 1 - 18 2 - 16 - - 47 - - 10 - - 14 - - 25 - - -
169 37 - - 16 - - 8 - - 27 - - 10 - - 2 - - 7 - - -
170 50 3 - 14 - - 8 - - 33 - - 9 - - 6 - - 12 - - -
171 26 - - 12 - - 10 - - 19 - - 3 - - 9 - - 10 - - -
172 25 1 - 3 - - 7 - - 26 - - 2 - - 6 - - 10 - - -
173 27 - - 6 - - 2 - - 14 - - 5 - - 1 - - 3 - - -
174 18 - - 7 - - 1 - - 9 - - 2 - - 1 - - 3 - - -
175 9 - - 2 - - - - - 6 - - 1 - - - - - 3 - - -
176 13 - - 2 - - 1 - - 7 - - - - - 2 - - 5 - - -
177 10 - - 1 - - 1 - - 3 - - - - - - - - - - - -
178 9 1 - - - - - - - 8 - - 1 - - - - - 3 - - -
179 7 - - - - - - - - 1 - - - - - - - - - - - -
180 5 - - - - - - - - 1 - - - - - - - - 1 - - -
181 5 - - 1 - - - - - 4 - - 1 - - - - - 2 - - -
182 2 - - - - - - - - 1 - - - - - - - - - - - -
183 2 - - - - - - - - 3 - - 1 - - - - - 2 - - -
184 1 - - - - - - - - - - - - - - - - - - - - -
185 2 - - - - - - - - - - - - - - - - - - - - -
186 - - - 1 - - - - - - - - - - - - - - - - - -
187 - - - - - - - - - - - - - - - - - - - - - -
188 1 - - - - - - - - - - - - - - - - - - - - -
--------------------------------------------------------------------------------------------------------
limits 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 1st sl0 sl1 sl2
chains 1 2 3 1+1a 2+2a 3+3a 1+1a+2+2a+3+3a
--------------------------------------------------------------------------------------------------------
Obviously the more various chains are used, the shorter are solutions both in each concrete instance and in average. For example, with all six chains used and slackness limited to 2, the maximum length of solution was 149 moves, which is the best result over all runs. This is because the solver was allowed to choose between all six chains, and limit on the slackness was higher.
Last three rows of the table [4] show that reduction 5x5 > 5x4 > 4x4 > 3x3 (or symmetric reduction) was used in more than 50% of all instances (5263 of 10000 with slackness limit 0, 5231 with slackness limit 1, 5110 with slackness limit 2). This agrees with the fact that this reduction chain uses largest region, "fringe 4x4" region with 518,918,400 configurations/entries in the lookup table.
Note however that the higher slackness limit, the less instances are solved using this reduction. It seems like with enough slackness allowed, other chains become more "popular".
I can check any other chain(s) on the same sample of 10,000 instances if anyone is interested. I am currently working on similar table for MTM metric. I will not probably perform comparison for other metrics (2TM or 3TM) unless someone is interested in these metrics.
- Bulat
