Heuristics Search & Game Playing in AI

What is Heuristic?

• The word heuristic is derived from the Greek word heuriskein, which means to find or to discover.
• Heuristic search can be implemented by using a thumb rule, a judgment or a guess.
• Trial and error is simplest form of heuristics. It provides facility to fit some variables in an algebraic equation so that it can be solved easily.
• Heuristic methods are used to increase the speed of process with a proper solution through shortcuts. Due to this, decision making becomes an easier task.

Some popular heuristic techniques are as follows:

1. Generate and test

This algorithm is used for simple problems and inefficient for problems with large space or complicated.

Following are the steps for Generate and Test Algorithm:

1. Generate a possible solution.
2. Test to see, if this is actually a solution for given task.
3. Stop, if solution is found. Otherwise, return to step 1.

Example: In n-queen problem generate and test algorithm is used to find solution for board size n*n in such a way that no queen can attack each other.

2. Hill Climbing

• Hill climbing is a technique that uses mathematical approach for optimization purpose. It belongs to the category of local search algorithms.
• It is an iterative algorithm that starts with arbitrary solution. It plays an important role in  finding better solution by incrementing a single element of the solution.
• Hill climbing technique is vey useful in Robotics.

Hill Climbing Algorithm

Aim:
i. To search for a goal state = Climbing to the top of a hill 
ii. To generate and test direction to move.
iii. Apply heuristic function to estimate, how close is a given state with goal state.

Following are the steps for hill climbing algorithm:

i. Pick a random point in the search space.
ii. Consider all the neighbors of the current state.
iii. Choose the neighbor with the best quality and move to that step.
iv. Repeat step2 until all the neighboring states are of lower quality.
v. Return the current state as a solution state.

Challenges in Hill climbing:

Although hill climbing provides the optimum solution for enhancing search optimization but it has some challenging drawbacks. They are:

a) Local maxima
It is a state that is better than all of its neighbors, but not better than some other states.

b) Plateau
It refers to a flat area of the search space. This area consists of neighboring states which may have the same value.

c) Ridges

• Ridges mainly denote the orientation of the high region, compared to the set of available moves. However, it becomes impossible for the ridges to climb up due to the set of such available moves.
• If the sides of ridge are very steep, then the climber prefers to take zigzag steps towards a better position. This tends to  increase the length and time of the journey.

Solutions to overcome the drawbacks of Hill Climbing: 

1. Backtracking.
2. Perform big jumps to handle plateaus or poor local maxima.
3. Apply multiple heuristic rules before testing.

3. Production System

• Production system is a system that provides rules (states) to reach a solution.
• It includes a set of rules in the form of Ci→Ai , where 'Ci' refers to starting state and 'Ai' represents the consequent state. Hence, 'Ci' is a condition part while 'Ai' is an action part.
• In this system, knowledge representation form has a set of condition-action rules (Production Rules or Operators), a modified database with the rules, and a Production System Interpreter to control the operation of the rules.
• A system that uses this form of knowledge representation is called as a production system.

A production system consists of rules and factors. Knowledge is encoded in a declarative form, which consists of a set of rules such as,

Situation ------------ Action 
SITUATION that implies ACTION. 

Example:
IF an initial state is a goal state THEN quit. 

The major components of an AI production system are:

i. A global database 
ii. A set of production rules and 
iii. A control system 

• The global database is the central data structure used by an AI production system.
• The production rules operate on the global database. Each rule has a precondition that may or may not be satisfied by the database. If the precondition is satisfied, the rule can be applicable.
• Application of the rule changes the database. The control system selects the rule to be applied and stops computation when a termination condition is satisfied on the database.
• If several rules are fired at the same time, the control system has a potential to resolve the conflicts.

Advantages of Production Systems

Production Systems provides several benefits in terms of tools and modular approach for the set of rules. Some of them are given below:

1. Production systems provide an excellent tool for structuring AI programs. 
2. Production Systems are highly modular because the individual rules can be added, removed or modified independently.

4. State Space Search

• State space search is a process in which successive states are taken into consideration for finding a goal state with a desired property.
• It is different from traditional search methods such as sequential, indexed sequential, binary search etc. These traditional search methods occupy more space in memory and results in the formation of large graph.
  For example: In tic-tac-toe game, every move of player generates a state space while the three similar (O or X) consecutive symbols (in row, column or diagonal) generate the goal states.

5. Constraint Satisfaction Problem

• A constraint satisfaction problem (or CSP) is a special kind of problem that satisfies some additional structural properties corresponding to general problems.
• In a CSP, the states are defined by the values of a set of variables and the goal test specifies a set of constraints that the values must follow.
• CSP represents values for all the variables as a solution so that the constraints are satisfied.
  For example: The 8-queens problem is referred to as CSP. Here, the arrangement is in such a way that variables are the locations of each of the eight queens square denote the possible values on the board  and no two queens can be placed in the same row, column or diagonal for the constraint state.

Application of Game playing 

• Game playing is a very important topic in AI. Game playing attracts many people because its states are well defined and it is intelligent. 
  For example: State plays a very important role in two player game. States of each player are dependent on actions of another player.
• Search techniques are commonly used in game.

Minimax Algorithm

• The Min-Max algorithm is generally used for a game consisting of two players such as tic-tac-toe, checkers, chess etc.
• All these games are logical games, so they can be described by set of rules. It is possible to determine the next available moves from a given point in the game.
• Consider that the game has two players MAX and MIN. MAX will move first and then MIN. A game can be defined as a kind of search problem with the following components.
  i. Initial State: It includes the board position and indicates the move made by one of the two players.
  ii. Set of Operators: It defines the legal moves that a player can make.
  iii. Terminal Move: It determines the end of the game.
  iv. Utility function: It gives a numeric value for the result of the game. 
  For example: In Chess or Tic-tac-toe game, the result is declared in the form of points such as +1 for win, -1 for loose, 0 for draw.

Example: Tic Tac Toe Game.

• 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. This game tree representation is shown in fig (a,b and c).

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 Minimax 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.