State Search Algorithms - Uninformed and Heuristic search

This project contains python algorithms that solve a state search represented by a chessboard.

Problem domain

We have a chessboard with random pieces placed on it. Our agent, a piece (can be any piece in the game), has to find for the best path from the top row of our board, to the bottom. The piece, algorithm used and the disposal of the chessboard will be part of the user input, as well as the solution found.

Definition of action

An action is any posible and legal movement that our agent can perform (castling not included).

Definition of state

The state is formed by the chessboard and every piece on it. This means that everytime an agent moves, the state changes. We can distinguish between:

• Initial state: first state of the problem. Any chessboard, of any size, with any possible piece disposition and with our agent(s) in the first row.
• Non-final state: any state generated by our agent(s) movement that is not a final state.
• Final state: a state in which our agent(s) has reached the bottom of the board.

Search algorithms

Once we have created the code structure that creates a state (board, chess pieces, agents, etc), its time to program an algorithm that will find the best solution depending on a given strategy.

Uniformed Search

The search is perfomed using only the information available in the definition of the problem. The algorithms used will be:

• Random Search
• Breath First Search
• Depth First Search
• Limited Depth First Search
• Iterative Depth First Search
• Uniform Cost

Informed Search

For these algorithms, we are introducing an heuristic that will help us find a better solution based on the knowledge we have about the problem. The heuristic we are using is the Manhattan distance, which is the closest distance to the bottom of the chessboard if the movements were legal. This heuristic is both admisible and consistent. The algorithms used will be:

• Best First
• A*

Comparative study

WIP