Week 13 - A* for Twiddle

A* Search Explained

The bulk of this week is going to be a 90 minute video explaining A* search. You should watch this early in the week

• https://uni.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=bcc48c7f-f111-4efa-8c8a-ab4d010ffa61
  • Yes, this was recorded at a live meetup with Cohort #1 and there are a few places you can't hear their response.  But I felt like the "meat" was there. PLEASE reach out to me if you have question.  I mean it!]
• PowerPoint Slides

Twiddle heuristic

For the remainder of the week (and part of next week) I am going to ask you to program the A* search for the Twiddle puzzle we looked at earlierl.

In order to help you conquer this program I'm going to suggest you do it in the following steps.

• Create the heuristic function. (this week)
• Update the Node class (next week)
• Modify the search

Create the heuristic function (Target date: Sunday, November 20)

This is really the substance of this whole activity.  It is, arguably, the hardest but it really isn't that bad.

Action:

Create a function called heuristic() that takes in a Twiddle board (a length 9 string) and returns a heurstic value of the board based on the modified Manhattan Distance as discussed in the discussion video.  This score should be the sum of the minimum number of moves required to move/slide each of the 9 numbers, individually, to it's target location, the whole thing divided by 4 (since each Twiddle action moves 4 numbers).

For example:

Has a value of:

since the numbers are  3 + 2 + 2 + 2+ 1 + 1 + 4 + 1 + 4 out of place (and 20/4 = 5)

In the class discussion we debated whether fractional results (such as heuristic("213456789")) should be left as 0.5, rounded down to 0.0 or, rounded up to 1.0. Since all of these actions will still allow the heurstic to be admissable (that is, it never OVER-estimates the value) it doesn't really matter.  I actually chose to leave it alone at 0.5

As we discussed in the meetup video, your first reaction to solving this program might be toward a lookup table of some sort.  For example, I have seen students write something like this:

However, there is a really clean way to do this using integer division and modulo which converts the one-dimensional index number to a two-dimensional coordinate number.  I strongly encourage you to play with finding this algorithm.

I will post my solution to this portion next week.