The 3 main methods we would use for solving a single player problem like these are:

• Breadth First Search.
• Depth First Search.
• Heuristic Search.
• A* search.

The code to all these searches is almost identical, however the way they work very differently.

All the methods use a list. Initially the list has only 1 item in it, the playing grid in its initial or problem-state. This item is then expanded into all of its possible child states (every possible move is played) and these child states are then added to the list. This is done in a loop until 1 of the child states is a goal state (in other words, until the game is solved).

The pseudo code for most simple single player programs is as follows.

Do
    Current_Item = Remove_Item_From_List
    Child_State_Array = Expand (Current_State)
    Add_to_List(Child_State_Array)
    If child_State_Array Holds the solution then IsGameOver = true
Loop while (IsGameOver = false)

That code can be found in all the above AI methods. The only difference is how they are ordered in the list.

• In a breadth first search, Items are always added to 1 side of the list, and removed from the opposite side.
• In a depth first search, Items are added, and removed from the same side of the list.
• In a heuristic search, Items are added to any side of the list. However, before an item is removed from the list, each item is given a score by a “heuristic” function.. ( a higher score for states that are closer to the goal state) the item with the highest score is the 1 that is removed from the list.
• An A* search uses two heuristic functions, and adds the core together. Using 2 heuristics greatly improves the programs ability to spot the best state to expand next, but slows down the execution of the program.

An example of a heuristic function for the game we are playing could be a function that counts the number of squares that are in the correct grid position, or maybe 100 – the depth of the state.

Using a heuristic in a search has advantages and disadvantages. In this example, using a heuristic causes the programs main loop to run about 10 times slower. However, it reduces the amount of loops needed to complete the search from 6 million to about 4 thousand !!!! Saving LOADS of memory, and time in this example. (which reminds me, the initial state I am using takes 25 moves to solve…. This may not seem like much, but without a heuristic, the search uses about 300 megabytes of ram in about 1 second ! Unless you are using a powerful machine ( I am using a 1.3 Ghz, 256 meg ram Pc) you may need to reduce the number of moves needed to complete the puzzle down to about 10)

OKAY, so, we know of a few different methods, we know their advantages and disadvantages. On the next page, we will talk about how to code this program.