Homework 2: The Rush Hour Problem
Chris Tralie
Competition Results Fall 2021
Click here to see the assignment description
Below are the results on the 40 puzzles, sorted in descending order of number of average nodes expanded over all the puzzles. People who broke consistency and hence ended up with a non-optimal length of steps from start to finish are disqualified, so Kevin is the winner!
I bolded the number of expansions if that particular entry got the best score on a particular puzzle. I crossed out the number of steps if that particular entry did not compute an optimal sequence from the start to the goal. A few observations:
- Greedy best-first blows other techniques out of the water in terms of number of expansions needed. But it's not guaranteed to return an optimum
- The best performing techniques all did some combination of distance of goal car to goal + number of cars blocking. Note that the number of cars blocking is stronger than the blocking heuristic.
- No two people had exactly the same scores across all puzzles. Even techniques that did very similar things ended with different scores. This shows how very subtle changes (e.g. the order in which neighbors were expanded) can affect the results. This is why we have to be very careful when drawing conclusions about what changes in AI/ML pipelines have led to improvements, and why we need good controls and many experiments!
Name | Heuristic Description | Puzzle 0 | Puzzle 1 | Puzzle 2 | Puzzle 3 | Puzzle 4 | Puzzle 5 | Puzzle 6 | Puzzle 7 | Puzzle 8 | Puzzle 9 | Puzzle 10 | Puzzle 11 | Puzzle 12 | Puzzle 13 | Puzzle 14 | Puzzle 15 | Puzzle 16 | Puzzle 17 | Puzzle 18 | Puzzle 19 | Puzzle 20 | Puzzle 21 | Puzzle 22 | Puzzle 23 | Puzzle 24 | Puzzle 25 | Puzzle 26 | Puzzle 27 | Puzzle 28 | Puzzle 29 | Puzzle 30 | Puzzle 31 | Puzzle 32 | Puzzle 33 | Puzzle 34 | Puzzle 35 | Puzzle 36 | Puzzle 37 | Puzzle 38 | Puzzle 39 |
Avg 1967.3 Expansions | Greedy best-first |
509 Expansions |
1655 Expansions |
809 Expansions |
233 Expansions |
2032 Expansions |
536 Expansions |
2626 Expansions | 23 steps 355 Expansions |
1234 Expansions |
2877 Expansions |
690 Expansions |
493 Expansions |
5917 Expansions |
3545 Expansions |
371 Expansions |
2774 Expansions |
2127 Expansions |
1563 Expansions |
525 Expansions |
784 Expansions |
252 Expansions |
1325 Expansions |
1857 Expansions |
3060 Expansions |
5703 Expansions |
3451 Expansions |
939 Expansions |
706 Expansions |
3923 Expansions |
1000 Expansions |
3740 Expansions |
545 Expansions |
1864 Expansions |
3847 Expansions |
3751 Expansions |
2915 Expansions |
1597 Expansions |
2845 Expansions |
2091 Expansions |
1628 Expansions |
Avg 2546.2 Expansions | Distance to goal + # of cars blocking | 17 steps 991 Expansions | 15 steps 1395 Expansions |
733 Expansions | 23 steps 359 Expansions | 19 steps 2034 Expansions | 19 steps 1505 Expansions | 22 steps 1939 Expansions | 23 steps 910 Expansions | 18 steps 452 Expansions | 33 steps 1745 Expansions |
820 Expansions | 34 steps 621 Expansions | 33 steps 9402 Expansions | 35 steps 8750 Expansions | 33 steps 525 Expansions | 42 steps 2513 Expansions | 48 steps 2070 Expansions | 61 steps 1587 Expansions | 45 steps 482 Expansions | 19 steps 779 Expansions | 50 steps 262 Expansions | 47 steps 3664 Expansions | 50 steps 1861 Expansions | 51 steps 4199 Expansions | 53 steps 8417 Expansions | 50 steps 4164 Expansions | 58 steps 2417 Expansions | 52 steps 1880 Expansions |
4303 Expansions | 56 steps 1163 Expansions | 70 steps 3840 Expansions | 63 steps 565 Expansions | 78 steps 3184 Expansions |
4373 Expansions | 76 steps 3879 Expansions | 64 steps 2061 Expansions |
1942 Expansions | 78 steps 3339 Expansions |
3807 Expansions | 82 steps 2914 Expansions |
KevinAvg 2573.8 Expansions | Distance to goal + # of cars blocking | 17 steps 1039 Expansions | 15 steps 1612 Expansions | 34 steps 667 Expansions | 23 steps 368 Expansions | 19 steps 2126 Expansions | 19 steps 1639 Expansions | 22 steps 2194 Expansions | 23 steps 944 Expansions | 18 steps 378 Expansions | 33 steps 1722 Expansions | 57 steps 830 Expansions | 34 steps 654 Expansions | 33 steps 9281 Expansions | 35 steps 8728 Expansions | 33 steps 523 Expansions | 42 steps 2432 Expansions | 48 steps 2057 Expansions | 61 steps 1572 Expansions | 45 steps 476 Expansions | 19 steps 830 Expansions | 50 steps 261 Expansions | 47 steps 3938 Expansions | 50 steps 1904 Expansions | 51 steps 4133 Expansions | 53 steps 8518 Expansions | 50 steps 4333 Expansions | 58 steps 2477 Expansions | 52 steps 1856 Expansions | 55 steps 4300 Expansions | 56 steps 1167 Expansions | 70 steps 3784 Expansions | 63 steps 587 Expansions | 78 steps 3365 Expansions | 72 steps 4389 Expansions | 76 steps 3855 Expansions | 64 steps 2049 Expansions | 66 steps 1940 Expansions | 78 steps 3362 Expansions | 83 steps 3756 Expansions | 82 steps 2906 Expansions |
MattAvg 2654.8 Expansions | Distance to goal + blocking heuristic | 17 steps 1030 Expansions | 15 steps 1771 Expansions | 34 steps 767 Expansions | 23 steps 375 Expansions | 19 steps 2277 Expansions | 19 steps 1725 Expansions | 22 steps 2244 Expansions | 23 steps 951 Expansions | 18 steps 435 Expansions | 33 steps 1838 Expansions | 57 steps 828 Expansions | 34 steps 698 Expansions | 33 steps 9993 Expansions | 35 steps 9076 Expansions | 33 steps 524 Expansions | 42 steps 2441 Expansions | 48 steps 2114 Expansions | 61 steps 1587 Expansions | 45 steps 479 Expansions | 19 steps 901 Expansions | 50 steps 262 Expansions | 47 steps 3975 Expansions | 50 steps 2149 Expansions | 51 steps 4161 Expansions | 53 steps 8652 Expansions | 50 steps 4619 Expansions | 58 steps 2541 Expansions | 52 steps 1864 Expansions | 55 steps 4300 Expansions | 56 steps 1169 Expansions | 70 steps 3867 Expansions | 63 steps 589 Expansions | 78 steps 3613 Expansions | 72 steps 4381 Expansions | 76 steps 3837 Expansions | 64 steps 2143 Expansions | 66 steps 1945 Expansions | 78 steps 3474 Expansions | 83 steps 3736 Expansions | 82 steps 2863 Expansions |
Avg 2665.5 Expansions | Distance to goal + number of cars blocking + # of blocking cars that are blocked | 17 steps 1057 Expansions | 15 steps 1791 Expansions | 34 steps 777 Expansions | 23 steps 355 Expansions | 19 steps 2313 Expansions | 19 steps 1751 Expansions |
2787 Expansions | 23 steps 931 Expansions | 18 steps 366 Expansions | 33 steps 1839 Expansions | 57 steps 841 Expansions | 34 steps 630 Expansions | 33 steps 9102 Expansions | 35 steps 10836 Expansions | 33 steps 523 Expansions |
2408 Expansions | 48 steps 2078 Expansions | 61 steps 1606 Expansions | 45 steps 481 Expansions | 19 steps 1412 Expansions | 50 steps 261 Expansions | 47 steps 4159 Expansions |
2139 Expansions | 51 steps 4198 Expansions | 53 steps 8591 Expansions | 50 steps 3860 Expansions | 58 steps 2443 Expansions | 52 steps 1841 Expansions |
4300 Expansions | 56 steps 1165 Expansions |
3868 Expansions | 63 steps 600 Expansions | 78 steps 3195 Expansions |
4202 Expansions | 76 steps 3873 Expansions |
2269 Expansions | 66 steps 1947 Expansions |
3469 Expansions |
3612 Expansions | 82 steps 2743 Expansions |
JonAvg 2687.3 Expansions | Blocking heuristic + distance of goal car to end | 17 steps 1032 Expansions | 15 steps 1881 Expansions | 34 steps 781 Expansions | 23 steps 378 Expansions | 19 steps 2286 Expansions | 19 steps 1774 Expansions | 22 steps 2335 Expansions | 23 steps 951 Expansions | 18 steps 479 Expansions | 33 steps 1876 Expansions | 57 steps 832 Expansions | 34 steps 698 Expansions | 33 steps 10059 Expansions | 35 steps 9542 Expansions | 33 steps 524 Expansions | 42 steps 2447 Expansions | 48 steps 2119 Expansions | 61 steps 1587 Expansions | 45 steps 479 Expansions | 19 steps 965 Expansions | 50 steps 262 Expansions | 47 steps 4024 Expansions | 50 steps 2176 Expansions | 51 steps 4170 Expansions | 53 steps 8673 Expansions | 50 steps 4645 Expansions | 58 steps 2573 Expansions | 52 steps 1874 Expansions | 55 steps 4300 Expansions | 56 steps 1169 Expansions | 70 steps 3877 Expansions | 63 steps 594 Expansions | 78 steps 3613 Expansions | 72 steps 4391 Expansions | 76 steps 3837 Expansions | 64 steps 2193 Expansions | 66 steps 1946 Expansions | 78 steps 3516 Expansions | 83 steps 3758 Expansions | 82 steps 2876 Expansions |
DylanAvg 2786.9 Expansions | Distance of goal car to end | 17 steps 1051 Expansions | 15 steps 2101 Expansions | 34 steps 805 Expansions | 23 steps 398 Expansions | 19 steps 2391 Expansions | 19 steps 1840 Expansions | 22 steps 2679 Expansions | 23 steps 950 Expansions | 18 steps 558 Expansions | 33 steps 2001 Expansions | 57 steps 839 Expansions | 34 steps 768 Expansions | 33 steps 10371 Expansions | 35 steps 10262 Expansions | 33 steps 524 Expansions | 42 steps 2613 Expansions | 48 steps 2138 Expansions | 61 steps 1600 Expansions | 45 steps 481 Expansions | 19 steps 1129 Expansions | 50 steps 261 Expansions | 47 steps 4248 Expansions | 50 steps 2327 Expansions | 51 steps 4209 Expansions | 53 steps 8745 Expansions | 50 steps 4727 Expansions | 58 steps 2658 Expansions | 52 steps 2016 Expansions | 55 steps 4306 Expansions | 56 steps 1169 Expansions | 70 steps 3939 Expansions | 63 steps 611 Expansions | 78 steps 3742 Expansions | 72 steps 4404 Expansions | 76 steps 3878 Expansions | 64 steps 2329 Expansions | 66 steps 1949 Expansions | 78 steps 3625 Expansions | 83 steps 3838 Expansions | 82 steps 2995 Expansions |
Tom SAvg 2787.9 Expansions | Distance To Goal | 17 steps 1052 Expansions | 15 steps 2102 Expansions | 34 steps 806 Expansions | 23 steps 399 Expansions | 19 steps 2392 Expansions | 19 steps 1841 Expansions | 22 steps 2680 Expansions | 23 steps 951 Expansions | 18 steps 559 Expansions | 33 steps 2002 Expansions | 57 steps 840 Expansions | 34 steps 769 Expansions | 33 steps 10372 Expansions | 35 steps 10263 Expansions | 33 steps 525 Expansions | 42 steps 2614 Expansions | 48 steps 2139 Expansions | 61 steps 1601 Expansions | 45 steps 482 Expansions | 19 steps 1130 Expansions | 50 steps 262 Expansions | 47 steps 4249 Expansions | 50 steps 2328 Expansions | 51 steps 4210 Expansions | 53 steps 8746 Expansions | 50 steps 4728 Expansions | 58 steps 2659 Expansions | 52 steps 2017 Expansions | 55 steps 4307 Expansions | 56 steps 1170 Expansions | 70 steps 3940 Expansions | 63 steps 612 Expansions | 78 steps 3743 Expansions | 72 steps 4405 Expansions | 76 steps 3879 Expansions | 64 steps 2330 Expansions | 66 steps 1950 Expansions | 78 steps 3626 Expansions | 83 steps 3839 Expansions | 82 steps 2996 Expansions |
Avg 2805.2 Expansions | Number of blocking cars | 17 steps 1059 Expansions | 15 steps 2012 Expansions | 34 steps 813 Expansions | 23 steps 411 Expansions | 19 steps 2349 Expansions | 19 steps 1833 Expansions | 22 steps 2723 Expansions | 23 steps 951 Expansions | 18 steps 495 Expansions | 33 steps 2021 Expansions |
843 Expansions | 34 steps 770 Expansions | 33 steps 10171 Expansions | 35 steps 11133 Expansions | 33 steps 525 Expansions | 42 steps 2557 Expansions | 48 steps 2152 Expansions | 61 steps 1614 Expansions | 45 steps 490 Expansions | 19 steps 1201 Expansions | 50 steps 262 Expansions | 47 steps 4417 Expansions | 50 steps 2382 Expansions | 51 steps 4227 Expansions | 53 steps 8771 Expansions | 50 steps 4723 Expansions | 58 steps 2718 Expansions | 52 steps 1910 Expansions | 55 steps 4300 Expansions | 56 steps 1170 Expansions | 70 steps 3903 Expansions | 63 steps 605 Expansions | 78 steps 3777 Expansions | 72 steps 4399 Expansions | 76 steps 3837 Expansions | 64 steps 2373 Expansions | 66 steps 1947 Expansions | 78 steps 3680 Expansions | 83 steps 3801 Expansions | 82 steps 2882 Expansions |
VincentAvg 2846.6 Expansions | 0.5*(Distance to goal + # of cars blocking) | 17 steps 1061 Expansions | 15 steps 2337 Expansions | 34 steps 802 Expansions | 23 steps 411 Expansions | 19 steps 2476 Expansions | 19 steps 1926 Expansions | 22 steps 3084 Expansions | 23 steps 951 Expansions | 18 steps 539 Expansions | 33 steps 1991 Expansions | 57 steps 845 Expansions | 34 steps 811 Expansions | 33 steps 10330 Expansions | 35 steps 11133 Expansions | 33 steps 525 Expansions | 42 steps 2543 Expansions | 48 steps 2146 Expansions | 61 steps 1602 Expansions | 45 steps 482 Expansions | 19 steps 1291 Expansions | 50 steps 262 Expansions | 47 steps 4459 Expansions | 50 steps 2440 Expansions | 51 steps 4210 Expansions | 53 steps 8775 Expansions | 50 steps 4784 Expansions | 58 steps 2721 Expansions | 52 steps 2029 Expansions | 55 steps 4303 Expansions | 56 steps 1170 Expansions | 70 steps 3903 Expansions | 63 steps 606 Expansions | 78 steps 3822 Expansions | 72 steps 4407 Expansions | 76 steps 3872 Expansions | 64 steps 2348 Expansions | 66 steps 1949 Expansions | 78 steps 3712 Expansions | 83 steps 3827 Expansions | 82 steps 2977 Expansions |
Avg 2854.7 Expansions | Distance of goal car to end | 17 steps 1063 Expansions | 15 steps 2194 Expansions | 34 steps 813 Expansions | 23 steps 414 Expansions | 19 steps 2359 Expansions | 19 steps 1764 Expansions | 22 steps 3771 Expansions | 23 steps 951 Expansions | 18 steps 554 Expansions | 33 steps 2028 Expansions |
847 Expansions | 34 steps 942 Expansions | 33 steps 9708 Expansions | 35 steps 10947 Expansions | 33 steps 525 Expansions | 42 steps 2541 Expansions | 48 steps 2171 Expansions | 61 steps 1620 Expansions | 45 steps 492 Expansions | 19 steps 1272 Expansions | 50 steps 264 Expansions | 47 steps 4712 Expansions | 50 steps 2489 Expansions | 51 steps 4252 Expansions | 53 steps 8747 Expansions | 50 steps 4836 Expansions | 58 steps 2815 Expansions | 52 steps 1953 Expansions | 55 steps 4303 Expansions | 56 steps 1170 Expansions | 70 steps 3904 Expansions | 63 steps 608 Expansions | 78 steps 3961 Expansions |
4392 Expansions | 76 steps 3878 Expansions | 64 steps 2555 Expansions | 66 steps 1950 Expansions | 78 steps 3763 Expansions |
3917 Expansions | 82 steps 2743 Expansions |
Avg 2960.8 Expansions | Number of blocking cars | 17 steps 1069 Expansions | 15 steps 2337 Expansions | 34 steps 830 Expansions | 23 steps 425 Expansions | 19 steps 2454 Expansions | 19 steps 1942 Expansions | 22 steps 3457 Expansions | 23 steps 951 Expansions | 18 steps 632 Expansions | 33 steps 2183 Expansions |
851 Expansions | 34 steps 868 Expansions | 33 steps 10523 Expansions | 35 steps 12893 Expansions | 33 steps 525 Expansions | 42 steps 2742 Expansions | 48 steps 2174 Expansions | 61 steps 1632 Expansions | 45 steps 515 Expansions | 19 steps 1500 Expansions | 50 steps 264 Expansions | 47 steps 4640 Expansions | 50 steps 2574 Expansions | 51 steps 4312 Expansions | 53 steps 8851 Expansions | 50 steps 4797 Expansions | 58 steps 2851 Expansions | 52 steps 2060 Expansions |
4317 Expansions | 56 steps 1170 Expansions | 70 steps 3965 Expansions | 63 steps 620 Expansions | 78 steps 3915 Expansions |
4417 Expansions | 76 steps 3889 Expansions | 64 steps 2589 Expansions | 66 steps 1952 Expansions | 78 steps 3844 Expansions | 83 steps 3901 Expansions | 82 steps 3002 Expansions |
SeraiahAvg 3014.8 Expansions | Blocking heuristic + 1 if the last car blocking is sandwiched in beteween two other cars | 17 steps 1068 Expansions | 15 steps 2730 Expansions | 34 steps 829 Expansions | 23 steps 421 Expansions | 19 steps 2571 Expansions | 19 steps 2051 Expansions | 22 steps 4023 Expansions | 23 steps 950 Expansions | 18 steps 671 Expansions | 33 steps 2171 Expansions | 57 steps 850 Expansions | 34 steps 900 Expansions | 33 steps 10620 Expansions | 35 steps 13400 Expansions | 33 steps 524 Expansions | 42 steps 2613 Expansions | 48 steps 2178 Expansions | 61 steps 1627 Expansions | 45 steps 513 Expansions | 19 steps 1723 Expansions | 50 steps 263 Expansions | 47 steps 4713 Expansions | 50 steps 2659 Expansions | 51 steps 4276 Expansions | 53 steps 8848 Expansions | 50 steps 4828 Expansions | 58 steps 2900 Expansions | 52 steps 2083 Expansions | 55 steps 4314 Expansions | 56 steps 1169 Expansions | 70 steps 3957 Expansions | 63 steps 619 Expansions | 78 steps 3985 Expansions | 72 steps 4416 Expansions | 76 steps 3868 Expansions | 64 steps 2536 Expansions | 66 steps 1951 Expansions | 78 steps 3905 Expansions | 83 steps 3900 Expansions | 82 steps 2971 Expansions |