Search Algorithms
Project Goal: To write an AI program in python that finds a solution to the Hua Rong Dao game and compare the results using Depth First Search (DFS) and A* algorithms
Personal Goal: To apply my knowledge of search algorithms and their properties to solve the puzzle at hand
Hua Rong Dao
Objective: To slide the pieces until the red 2x2 block can exit the board through the slot at the bottom
DFS Algorithm
The depth-fist search algorithm on the left first initializes a list with the starting state of the board. This list, the frontier, will hold the unexplored states of the board since the possible moves following a current state will be appended at the end of the list as per line 410. What makes this a dfs approach is the order in which we explore the states in the frontier, we can see that the current state (denoted cur_state) becomes the last state that was appended to the frontier. This is done by the built-in python function '.pop()' on line 402. In such a manner, a Last-In-First-Out (LIFO) search corresponding to DFS is achieved. Consequently, we are essentially searching in depth for one move and going all the way before we consider the other moves at that stage. If a solution is found (measured by the goal_test func) then all the moves that lead to this point are written to the output file. In addition, I have implemented pruning to avoid getting stuck in a cycle (arriving at the same state multiple times) and making it complete (finishes), given that there is a solution to the game. The pruning is done via an explored set that keeps track of the states that have been explored so that only unseen states are appended to the frontier. This also has the advantage that the computational space used is decreased.
A* Algorithm
The A* algorithm works in a similar manner as DFS except for the order in which the states in the frontier are explored. The order of exploration depends on the sum of the cost function and the heuristic function. Starting with the cost function, it represents the actual cost to get to the current state. I decided to make this the number of moves (number of slides) made from the start until the current state. The heuristic function represents an estimate of the number of moves necessary to find the solution from a given state. I chose the Manhattan Distance heuristic which calculates the sum of the x and y coordinates differences from the 2x2 piece’s current position to its desired goal position. This is an admissible heuristic as it never overestimates the cheapest path from any given state to the goal state. The frontier is a heap data structure that orders the unexplored states by their cost and heuristic function sum, 'cur.f ', when appending them using 'heappush' and exploring the one with the smallest overall cost first. In case of a tie, I also implemented a hash id for each state to act as a tie-breaker in the heap order. Lastly, this algorithm also has pruning by using an explored set and keeping track of previously explored states.
Input & Output:
Input: A text file with a representation of the starting board state.
Output: A text file with all consecutive moves to the solution from the starting state.
The states are represented as follows:
2x2 -> 1
1x2 horizontal -> <>
1x2 vertical -> ^ on the top and v on the bottom
Single pieces -> 2
Empty space -> .
Github: Input File
Github: Output File
Brief Description of Code:
The code consists of three classes, some helper functions, and two search algorithm functions.
Classes:
Piece: Deals with the type of piece, their orientation, and their coordinates.
Board: Deals with the board layout and actions such as moving a piece in the grid.
State: Wraps the Board class with some additional information such as the parent state, the cost functions, and the depth of the solution.
Important Functions:
Possible Moves: Checks what the next moves can be and calls the update board function to make such possible moves.
Update Board: Creates a deepcopy of the current board before making a move such that this new state is added to the frontier without affecting the current state.
Get Solution: Backtracks to find the path to the solution; Given the final state return all the parent states
Last Remarks:
The solutions found via the DFS algorithm are much longer and slower to find than when A* is used. This is because A* is optimal, meaning that it finds the shortest path to the solution whereas DFS might not give the best solution path. Using pruning for DFS made it complete by avoiding cycles, thus similar to A*, it will always find a solution (given that there is one).
Since this is a school-related project I am unable to share all the code publicly but contact me for the entire code if you want it.