State space search / blocks world problem by heuristic approach /TIC TAC TOE

A lot of AI is about SEARCH.

The "state space" is the set of states of the problem we can get to by applying operators to a state of the problem to get a new state.

A state contains all of the information necessary to predict the effects of an action and to determine if it is a goal state. State-space searching assumes that

• the agent has perfect knowledge of the state space and can observe what state it is in (i.e., there is full observability);
• the agent has a set of actions that have known deterministic effects;some states are goal states, the agent wants to reach one of these goal states, and the agent can recognize a goal state.
• a solution is a sequence of actions that will get the agent from its current state to a goal state.

Define the Problem as State Space Search

Consider the problem of “Playing Chess” . to build a program that could play chess, we have to specify the starting position of the chess board, the rules that define legal moves. And the board position that represent a win. The goal of the winning the game, if possible, must be made explicit.

The starting position can be described by an 8 X 8 array square in which each element square (x,y),(x varying from 1to 8 & y varying from 1 to 8) describes the board position of an appropriate chess coin, the goal is any board position in which the opponent does not have a legal move and his or her “king” is under attack. The legal moves provide the way of getting from initial state of final state.

The legal moves can be described as a set of rules consisting of two parts: A left side that gives the current position and the right side that describes the change to be made to the board position.

A state-space problem consists of

• a set of states;
• a distinguished set of states called the start states;
• a set of actions available to the agent in each state;
• an action function that, given a state and an action, returns a new state;
• a set of goal states, often specified as a Boolean function, goal(s), that is true when s is a goal state; and
• a criterion that specifies the quality of an acceptable solution. For example, any sequence of actions that gets the agent to the goal state may be acceptable, or there may be costs associated with actions and the agent may be required to find a sequence that has minimal total cost.This is called an optimal solution. Alternatively, it may be satisfied with any solution that is within 10% of optimal.

Heuristic

A function that estimates the cost of getting from one place to another (from the current state to the goal state.) 

Used in a decision process to try to make the best choice of a list of possibilities (to choose the move more likely to lead to the goal state.) 

Best move is the one with the least cost. 

The "intelligence" of a search process, helps in finding a more optimal solution. 

A more informed heuristic(blocks world)

Looks at each bottom position, but takes higher positions into account. Can be broken into 4 different cases for each bottom position. 

1. Current state has a blank and goal state has a block. 

+-------+    +-------+
|       |    |       |
|       |    |   A   |
| B   A |    |   B   |
| ----- |    | ----- |
| p q r |    | p q r |
+-------+    +-------+
 current       goal

Two blocks must be moved onto q. So increment the heuristic value by the number of blocks needed to be moved into a place. 

2. Current state has a block and goal state has a blank. 

+-------+    +-------+
|       |    |       |
|       |    |   A   |
| B   A |    |   B   |
| ----- |    | ----- |
| p q r |    | p q r |
+-------+    +-------+
 current       goal

One block must be removed from p. So increment the heuristic value by the number of blocks needed to be moved out of a place. 

3. Both states have a block, but they are not the same. 

+-------+    +-------+
|       |    |       |
|       |    |   A   |
| B A   |    |   B   |
| ----- |    | ----- |
| p q r |    | p q r |
+-------+    +-------+
 current       goal

On place q, the blocks don't match. The incorrect block must be moved out and the correct blocks must be moved in. Increment the heuristic value by the number of these blocks. 


4. Both states have a block, and they are the same. 

+-------+    +-------+
|       |    |       |
|       |    |   A   |
|   B A |    |   B   |
| ----- |    | ----- |
| p q r |    | p q r |
+-------+    +-------+
 current       goal

B is in the correct position. However, the position above it is incorrect. Increment the heuristic value by the number of incorrect positions above the correct block. 

TIC TAC TOE

• The first Game State will show nine moves, one for each of the empty spaces on its board.
• Similarly, the next level of Game States will show eight moves and continues for each Game State.
• The computer evaluates each of its current possible moves by representing the game as a game tree. This also helps to determine whether it will result into a win or a loss. 

Concepts for defining a Game Tree:

• A Game Tree is a structure for organizing all possible (legal) game states by the moves which allow transition from one game state to the next.
• This structure helps the computer to evaluate which moves to make because, by traversing the game tree, a computer (program) can easily see the outcome of a move and  can decide whether to take it or not.

The following states are used to represent a game tree.

1. The board state: This is an initial stage.
2. The current player: It refers to the player who will be making the next move. 
3. The next available moves: For humans, a move involves placing a game token while the computer selects the next game state.
4. The game state: It includes the grouping of the three previous concepts. 
5.Final Game States
In final game states, AI should select the winning move in such a way that each move assigns a numerical value based on its board state. 


The ranking should be given as:
a) Win: 1
b) Draw: O
c) Lose: -1 

• It is important to consider the aspects related to winning with the highest ranking, losing to the lowest, and a draw between the two players.
• The Max part of Mini max algorithm states that the user has to select the move with the highest value.
• Final Game States are ranked on the basis of their status of   winning, losing or a draw.
• Ranking of Intermediate Game States is based on the turn of player to make available moves.
• If it's X's turn, set the rank to that of the maximum available move. If a move results into a win, X can take it.
• If it's O's turn, set the rank to that of the minimum available move. If a move results into a loss, X can avoid it.