Solution to in-class Westeros search problem

Dijkstra’s

  1. Expand Winterfell (which is not a goal state), discovering Castle Black, Deepwood Motte, Moat Cailin, and Dreadfort. Frontier is now:
    1. Castle Black: g(n)=40
    2. Deepwood Motte: g(n)=80
    3. Dreadfort: g(n)=100
    4. Moat Cailin: g(n)=120
  2. Expand Castle Black (which is not a goal state), discovering The Wall. Frontier is now:
    1. The Wall: g(n)=40+1=41
    2. Deepwood Motte: g(n)=80
    3. Dreadfort: g(n)=100
    4. Moat Cailin: g(n)=120
  3. Expand The Wall (which is not a goal state), discovering Eastwatch by the Sea and Mance Rayder’s hut. Frontier is now:
    1. Deepwood Motte: g(n)=80
    2. Dreadfort: g(n)=100
    3. Moat Cailin: g(n)=120
    4. Eastwatch by the Sea: g(n)=40+1+200=241
    5. Mance Rayder’s hut: g(n)=40+1+200=241
  4. Expand Deepwood Motte (which is not a goal state), discovering Pyke. Frontier is now:
    1. Dreadfort: g(n)=100
    2. Moat Cailin: g(n)=120
    3. Eastwatch by the Sea: g(n)=40+1+200=241
    4. Mance Rayder’s hut: g(n)=40+1+200=241
    5. Pyke: g(n)=80+2100=2180
  5. Expand Dreadfort (which is not a goal state), discovering Tyrosh. Frontier is now:
    1. Moat Cailin: g(n)=120
    2. Eastwatch by the Sea: g(n)=40+1+200=241
    3. Mance Rayder’s hut: g(n)=40+1+200=241
    4. Tyrosh: g(n)=100+1600=1700
    5. Pyke: g(n)=80+2100=2180
  6. Expand Moat Cailin (which is not a goal state), discovering The Twins and Harrenhal. Frontier is now:
    1. The Twins: g(n)=120+100=220
    2. Eastwatch by the Sea: g(n)=40+1+200=241
    3. Mance Rayder’s hut: g(n)=40+1+200=241
    4. Harrenhal: g(n)=120+400=520
    5. Tyrosh: g(n)=100+1600=1700
    6. Pyke: g(n)=80+2100=2180
  7. Expand The Twins (which is not a goal state), discovering a better path to Harrenhal (440<520). Frontier is now:
    1. Eastwatch by the Sea: g(n)=40+1+200=241
    2. Mance Rayder’s hut: g(n)=40+1+200=241
    3. Harrenhal: g(n)=120+100+220=440 (updated value)
    4. Tyrosh: g(n)=100+1600=1700
    5. Pyke: g(n)=80+2100=2180
  8. Expand Eastwatch by the Sea (which is not a goal state), discovering Pentos. Frontier is now:
    1. Mance Rayder’s hut: g(n)=40+1+200=241
    2. Harrenhal: g(n)=120+100+220=440
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  9. Expand Mance Rayder’s hut (which is not a goal state), discovering the Fist of the First Men. Frontier is now:
    1. Harrenhal: g(n)=120+100+220=440
    2. Fist of the First Men: g(n)=40+1+200+500=741
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  10. Expand Harrenhal (which is not a goal state), discovering King’s Landing. Frontier is now:
    1. King’s Landing: g(n)=120+100+220+150=590
    2. Fist of the First Men: g(n)=40+1+200+500=741
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  11. Expand King’s Landing (which is not a goal state), discovering Highgarden and Storm’s End. Frontier is now:
    1. Fist of the First Men: g(n)=40+1+200+500=741
    2. Highgarden: g(n)=120+100+220+150+210=800
    3. Storm’s End: g(n)=120+100+220+150+290=880
    4. Tyrosh: g(n)=100+1600=1700
    5. Pyke: g(n)=80+2100=2180
    6. Pentos: g(n)=40+1+200+8000=8241
  12. Expand the Fist of the First Men (which is not a goal state). Frontier is now:
    1. Highgarden: g(n)=120+100+220+150+210=800
    2. Storm’s End: g(n)=120+100+220+150+290=880
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  13. Expand Highgarden (which is not a goal state), discovering Oldtown and also a worse way to Storm’s End. Frontier is now:
    1. Storm’s End: g(n)=120+100+220+150+290=880
    2. Oldtown: g(n)=120+100+220+150+210+90=890
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  14. Expand Storm’s End (which is not a goal state), discovering Storm’s End Castle. Frontier is now:
    1. Storm’s End Castle: g(n)=120+100+220+150+290+3=883
    2. Oldtown: g(n)=120+100+220+150+210+90=890
    3. Tyrosh: g(n)=100+1600=1700
    4. Pyke: g(n)=80+2100=2180
    5. Pentos: g(n)=40+1+200+8000=8241
  15. Expand Storm’s End Castle (which is not a goal state). Frontier is now:
    1. Oldtown: g(n)=120+100+220+150+210+90=890
    2. Tyrosh: g(n)=100+1600=1700
    3. Pyke: g(n)=80+2100=2180
    4. Pentos: g(n)=40+1+200+8000=8241
  16. Expand Oldtown (which is not a goal state), discovering Sunspear. Frontier is now:
    1. Sunspear: g(n)=120+100+220+150+210+90+400=1290
    2. Tyrosh: g(n)=100+1600=1700
    3. Pyke: g(n)=80+2100=2180
    4. Pentos: g(n)=40+1+200+8000=8241
  17. Expand Sunspear, which is a goal state. The shortest path is thus Winterfell → Moat Cailin → The Twins → Harrenhal → King’s Landing → Highgarden → Oldtown → Sunspear, for a total distance of 1290 miles. We expanded 17 nodes in the process.
  1. From Winterfell, the estimated closest unexplored node to Sunspear is Moat Cailin (est: 700 miles).
  2. From Moat Cailin, the estimated closest unexplored node to Sunspear is Harrenhal (est: 400 miles).
  3. From Harrenhal, the estimated closest unexplored node to Sunspear is King’s Landing (est: 300 miles).
  4. From King’s Landing, the estimated closest unexplored node to Sunspear is Storm’s End. (est: 100 miles).
  5. From Storm’s End, the estimated closest unexplored node to Sunspear is Storm’s End Castle. (est: 102 miles).
  6. No unexplored ways out of Storm’s End Castle.
  7. From Storm’s End, the estimated closest unexplored node to Sunspear is Highgarden (est: 175 miles).
  8. From Highgarden, the estimated closest unexplored node to Sunspear is Oldtown (est: 200 miles).
  9. From Oldtown, the estimated closest unexplored node to Sunspear is Sunspear (est: 0 miles).
  10. Therefore, our chosen path is Winterfell → Moat Cailin → Harrenhal → King’s Landing → Highgarden → Oldtown → Sunspear, for a total distance of 1370 miles. We visited 9 nodes in the process.

A*

  1. Expand Winterfell (which is not a goal state), discovering Castle Black, Deepwood Motte, Moat Cailin, and Dreadfort. Frontier is now:
    1. Moat Cailin: g(n)+h(n)=120+700=820
    2. Dreadfort: g(n)+h(n)=100+750=850
    3. Castle Black: g(n)+h(n)=40+840=880
    4. Deepwood Motte: g(n)+h(n)=80+850=930
  2. Expand Moat Cailin (which is not a goal state), discovering The Twins and Harrenhal. Frontier is now:
    1. The Twins: g(n)+h(n)=120+100+500=720
    2. Dreadfort: g(n)+h(n)=100+750=850
    3. Castle Black: g(n)+h(n)=40+840=880
    4. Harrenhal: g(n)+h(n)=120+400+400=920
    5. Deepwood Motte: g(n)+h(n)=80+850=930
  3. Expand The Twins (which is not a goal state), discovering a better path to Harrenhal (840<920). (Note that Harrenhal now jumps to the top of the priority queue with its new path cost.) Frontier is now:
    1. Harrenhal: g(n)+h(n)=120+100+220+400=840
    2. Dreadfort: g(n)+h(n)=100+750=850
    3. Castle Black: g(n)+h(n)=40+840=880
    4. Deepwood Motte: g(n)+h(n)=80+850=930
  4. Expand Harrenhal (which is not a goal state), discovering King’s Landing. Frontier is now:
    1. Dreadfort: g(n)+h(n)=100+750=850
    2. Castle Black: g(n)+h(n)=40+840=880
    3. King’s Landing: g(n)+h(n)=120+100+220+150+300=890
    4. Deepwood Motte: g(n)+h(n)=80+850=930
  5. Expand Dreadfort (which is not a goal state), discovering Tyrosh. Frontier is now:
    1. Castle Black: g(n)+h(n)=40+840=880
    2. King’s Landing: g(n)+h(n)=120+100+220+150+300=890
    3. Deepwood Motte: g(n)+h(n)=80+850=930
    4. Tyrosh: g(n)+h(n)=100+1600+50=1750
  6. Expand Castle Black (which is not a goal state), discovering The Wall. Frontier is now:
    1. The Wall: g(n)+h(n)=40+1+841=882
    2. King’s Landing: g(n)+h(n)=120+100+220+150+300=890
    3. Deepwood Motte: g(n)+h(n)=80+850=930
    4. Tyrosh: g(n)+h(n)=100+1600+50=1750
  7. Expand The Wall (which is not a goal state), discovering Eastwatch by the Sea and Mance Rayder’s hut. Frontier is now:
    1. King’s Landing: g(n)+h(n)=120+100+220+150+300=890
    2. Deepwood Motte: g(n)+h(n)=80+850=930
    3. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    4. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    5. Tyrosh: g(n)+h(n)=100+1600+50=1750
  8. Expand King’s Landing (which is not a goal state), discovering Highgarden and Storm’s End. Frontier is now:
    1. Deepwood Motte: g(n)+h(n)=80+850=930
    2. Highgarden: g(n)+h(n)=120+100+220+150+210+175=975
    3. Storm’s End: g(n)+h(n)=120+100+220+150+290+100=980
    4. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    5. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    6. Tyrosh: g(n)+h(n)=100+1600+50=1750
  9. Expand Deepwood Motte (which is not a goal state), discovering Pyke. Frontier is now:
    1. Highgarden: g(n)+h(n)=120+100+220+150+210+175=975
    2. Storm’s End: g(n)+h(n)=120+100+220+150+290+100=980
    3. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    4. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    5. Tyrosh: g(n)+h(n)=100+1600+50=1750
    6. Pyke: g(n)+h(n)=80+2100+1150=3330
  10. Expand Highgarden (which is not a goal state), discovering Oldtown and also a worse way to Storm’s End. Frontier is now:
    1. Storm’s End: g(n)+h(n)=120+100+220+150+290+100=980
    2. Oldtown: g(n)+h(n)=120+100+220+150+210+90+200=1090
    3. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    4. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    5. Tyrosh: g(n)+h(n)=100+1600+50=1750
    6. Pyke: g(n)+h(n)=80+2100+1150=3330
  11. Expand Storm’s End (which is not a goal state), discovering Storm’s End Castle. Frontier is now:
    1. Storm’s End Castle: g(n)+h(n)=120+100+220+150+290+3+102=985
    2. Oldtown: g(n)+h(n)=120+100+220+150+210+90+200=1090
    3. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    4. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    5. Tyrosh: g(n)+h(n)=100+1600+50=1750
    6. Pyke: g(n)+h(n)=80+2100+1150=3330
  12. Expand Storm’s End Castle (which is not a goal state). Frontier is now:
    1. Oldtown: g(n)+h(n)=120+100+220+150+210+90+200=1090
    2. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    3. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    4. Tyrosh: g(n)+h(n)=100+1600+50=1750
    5. Pyke: g(n)+h(n)=80+2100+1150=3330
  13. Expand Oldtown (which is not a goal state), discovering Sunspear. Frontier is now:
    1. Eastwatch by the Sea: g(n)+h(n)=40+1+200+900=1141
    2. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    3. Sunspear: g(n)+h(n)=120+100+220+150+210+90+400+0=1290
    4. Tyrosh: g(n)+h(n)=100+1600+50=1750
    5. Pyke: g(n)+h(n)=80+2100+1150=3330
  14. Expand Eastwatch by the Sea (which is not a goal state), discovering Pentos. Frontier is now:
    1. Mance Rayder’s hut: g(n)+h(n)=40+1+200+950=1191
    2. Sunspear: g(n)+h(n)=120+100+220+150+210+90+400+0=1290
    3. Tyrosh: g(n)+h(n)=100+1600+50=1750
    4. Pyke: g(n)+h(n)=80+2100+1150=3330
    5. Pentos: g(n)+h(n)=40+1+200+8000+1300=9541
  15. Expand Mance Rayder’s hut (which is not a goal state), discovering the Fist of the First Men. Frontier is now:
    1. Sunspear: g(n)+h(n)=120+100+220+150+210+90+400+0=1290
    2. Tyrosh: g(n)+h(n)=100+1600+50=1750
    3. Fist of the First Men: g(n)+h(n)=40+1+200+500+1400=2141
    4. Pyke: g(n)+h(n)=80+2100+1150=3330
    5. Pentos: g(n)+h(n)=40+1+200+8000+1300=9541
  16. Expand Sunspear, which is a goal state. The shortest path is thus Winterfell → Moat Cailin → The Twins → Harrenhal → King’s Landing → Highgarden → Oldtown → Sunspear, for a total distance of 1290 miles. We expanded 15 nodes in the process.

Takeaways

Turns out A* didn’t do much better than Dijkstra’s did here, since it only avoided expanding one node (Fist of the First Men) of those that Dijkstra expanded. Also, greedy search’s solution wasn’t all that bad – 1370 instead of 1290 miles, since it got fooled by the straight (but longer) shot from Winterfell to Harrenhal.

These less-than-exciting results occurred mainly because we have such a tiny map. If we had 21,000,000,000 (or even 21,000,000, or 21,000) nodes to explore instead of 21, you would see a much bigger difference.