ARTIFICIAL INTELLIGENCE- JNTUK R19- UNIT2-Problem Solving: State Space Search And Control Strategies

 

2.1. PROBLEM SOLVING: STATE-SPACE SEARCH AND CONTROL STRATEGIES

 

INTRODUCTION:

 

Problem solving is a method of deriving solution steps beginning from initial description of the problem to the desired solution. In AI, the problems are frequently modeled as a state space problem where the state space is a set of all possible states from start to goal states.

The 2 types of problem-solving methods that are generally followed include general purpose & special purpose methods. A general purpose method is applicable to a wide variety of problems, where a special purpose method is a tailor method made for a particular problem. The most general approach for solving a problem is to generate the solution & test it. For generating new state in the search space, an action/operator/rule is applied & tested whether the state is the goal state or not. In case the state is not the goal state, the procedure is repeated. The order of application of rules to the current state is called control strategy.

GENERAL PROBLEM SOLVING

 

Production System:

 

Production System (PS) is one of the formalisms that help AI programs to do search process more conveniently in state-space problems. This system consists of start (initial) state(s) & goal (final) state(s) of the problem along with one or more databases consisting of suitable & necessary information for a particular task. Production System consists of a number of production rules.

Example 1: Water Jug Problem

 

Problem Statement: There are two jugs a 4-Gallon one and 3-Gallon one. Neither has any measuring marker on it. There is a pump that can be used to fill the jugs with water. How can we get exactly 2- Gallon water into the 4- Gallon jug?

The state space for this problem can be described as the set of ordered pairs of integers (x, y) such that x

= 0, 1, 2, 3 or 4 and y = 0, 1, 2 or 3. x represents the number of gallons of water in the 4- Gallon jug. y represents the number  of  gallons  of  water  in  the  3-  Gallon  jug.  The start state is (0, 0). The goal state is  (2, n) for any value of n.

 

S.No	Rule	Result	Rule Description
1.	(x, y) if x<4	(4, y)	fill the 4-g jug
2.	(x, y) if y<3	(x, 3)	fill the 3-g jug

3.	(x, y) if x>0	(x-d, y)	pour some water out of the 4-g jug
4.	(x, y) if y>0	(x, y-d)	pour some water out of the 3-g jug
5.	(x, y) if x>0	(0, y)	Empty the 4-g jug on the ground
6.	(x, y) if y>0	(x,0)	Empty the 3-g jug on the ground
7.	(x, y) if x + y ≥ 4 & y>0	(4,y-(4-x))	Pour water from the 3-g jug into the 4-g jug until the 4-g jug is full
8.	(x, y) if x + y>3 & x>0	(x-(3-y), 3)	pour water from the 4-g jug into the 3-g jug until the 3-g jug is full
9.	(x, y) if x + y ≤ 4 & y>0	(x+y,0)	Pour all the water from 3-g jug into 4-g jug.
10.	(x, y) If x + y ≤ 3 & x>0	(0,x+y)	Pour all the water from the 4-g jug into

 

One Solution to the Water Jug Problem:

 

Gallon in the 4-Gallon Jug                  Gallon in the 3-Gallon Jug                  Rule Applied

 

 

0                                                                      0

2

0                                                                      3

9

3                                                                      0

2

3                                                                      3

7

4                                                                      2

5/12

0                                                                      2

9/11

2                                                                      0

Example 2: Water Jug Problem

 

 

Problem Statement: There are two jugs a 5-Gallon one and 3-Gallon one. Neither has any measuring marker on it. There is a pump that can be used to fill the jugs with water. How can we get exactly 4- Gallon water into the 5- Gallon jug?

 

The state space for this problem can be described as the set of ordered pairs of integers (x, y) such that x

= 0, 1, 2, 3, 4 or 5 and y = 0, 1, 2 or 3. x represents the number of gallons of water in the 5- Gallon jug. y represents the number of  gallons  of  water  in  the  3-  Gallon  jug.  The start state is (0, 0). The goal state is  (4, n) for any value of n.

 

Table: Production Rules for Water Jug Problem

 

 

One Solution to the Water Jug Problem:

 

 

Rule Applied	5-G Jug	3-G Jug
Start State	0	0
1	5	0
8	2	3
4	2	0
6	0	2
1	5	2
8	4	3
Goal State	4	0

Example 3: Missionaries & Cannibals Problem

Problem Statement: Three missionaries & three cannibals want to cross a river. There is a boat on their side of the river that can be used by either 1 (or) 2 persons. How should they use this boat to cross the river in such a way that cannibals never outnumber missionaries on either side of the river? If the cannibals ever outnumber the missionaries (on either bank) then the missionaries will be eaten. How can they cross over without eaten? Consider Missionaries as ‘M’, Cannibals as ‘C’ & Boat as ‘B’ which are on the same side of the river.

Initial State: ([3M, 3C, 1B], [0M, 0C, 0B])                Goal State: ([0M, 0C, 0B], [3M, 3C, 1B])

 

Production rules are as follows:

 

Rule 1: (0, M): One Missionary sailing the boat from Bank-1 to Bank-2. Rule 2: (M, 0): One Missionary sailing the boat from Bank-2 to Bank-1. Rule 3: (M, M): Two Missionaries sailing the boat from Bank-1 to Bank-2. Rule 4: (M, M): Two Missionaries sailing the boat from Bank-2 to Bank-1.

Rule 5: (M, C): One Missionary & One Cannibal sailing the boat from Bank-1 to Bank-2. Rule 6: (C, M): One Cannibal & One Missionary sailing the boat from Bank-2 to Bank-1. Rule 7: (C, C): Two Cannibals sailing the boat from Bank-1 to Bank-2.

Rule 8: (C, C): Two Cannibals sailing the boat from Bank-2 to Bank-1. Rule 9: (0, C): One Cannibal sailing the boat from Bank-1 to Bank-2. Rule 10: (C, 0): One Cannibal sailing the boat from Bank-2 to Bank-1.

S.No	Rule Applied	Persons on River Bank-1	Persons on River Bank-2
1	Start State	3M,3C,1B	0M,0C,0B
2	5	2M,2C,0B	1M,1C,1B
3	2	3M,2C,1B	0M,1C,0B
4	7	3M,0C,0B	0M,3C,1B
5	10	3M,1C,1B	0M,2C,0B
6	3	1M,1C,0B	2M,2C,1B
7	6	2M,2C,1B	1M,1C,0B
8	3	0M,2C,0B	3M,1C,1B
9	10	0M,3C,1B	3M,0C,0B
10	7	0M,1C,0B	3M,2C,1B
11	10	0M,2C,1B	3M,1C,0B
12	7	0M,0C,0B	3M,3C,1B

State Space Search:

A State Space Search is another method of problem representation that facilitates easy search. Using this method, we can also find a path from start state to goal state while solving a problem. A state space basically consists of 4 components:

1.        A set S containing start states of the problem.

2.        A set G containing goal states of the problem.

3.        Set of nodes (states) in the graph/tree. Each node represents the state in problem-solving process.

4.        Set of arcs connecting nodes. Each arc corresponds to operator that is a step in a problem-solving process.

 

A solution path is a path through the graph from a node in S to a node in G. The main objective of a search algorithm is to determine a solution path in graph. There may be more than one solution paths, as there may be more than one ways of solving the problem.

 

Example: The Eight-Puzzle Problem

Problem Statement: The eight-puzzle problem has a 3X3 grid with 8 randomly numbered (1 to 8) tiles arranged on it with one empty cell. At any point, the adjacent tile can move to the empty cell, creating a new empty cell. Solving this problem involves arranging tiles such that we get the goal state from the start state.

A state for this problem should keep track of the position of all tiles on the game board, with 0 representing the blank (empty cell) position on the board. The start & goal states may be represented as follows with each list representing corresponding row:

 

1.   Start state: [ [3, 7, 6], [5, 1, 2], [4, 0, 8] ]

2.   Goal state: [ [5, 3, 6], [7, 0, 2], [4, 1, 8] ]

3. The operators can be thought of moving {Up, Down, Left, Right}, the direction in which blank space effectively moves.

Solution: Following is a Partial Search Tree for Eight Puzzle Problem

 

 

The search will be continued until the goal state is reached. Search Tree for Water Jug Problem:

Example: Chess Game (One Legal Chess Move)

Chess is basically a competitive 2 player game played on a chequered board with 64 squares arranged in an 8 X 8 square. Each player is given 16 pieces of the same colour (black or white). These include 1 King, 1 Queen, 2 Rooks, 2 Knights, 2 Bishops & 8 pawns. Each of these pieces move in a unique manner. The player who chooses the white pieces gets the first turn to play. The players get alternate chances in which they can move one piece at a time. The objective of this game is to remove the opponent’s king from the game. The opponent’s King has to be placed in such a situation where the king is under immediate attack & there is no way to save it from the attack. This is known as Checkmate.

For a problem playing chess the starting position can be described as an 8 X 8 array where each position contains a symbol standing for appropriate piece in the official chess opening position. We can define our goal as any board position in which the opponent does not have a legal move & his/her king is under attack. The legal moves provide the way of getting from initial state to goal state. They can be described easily as a set of rules consisting of 2 parts

·         A left side that serves as a pattern to be matched against the current board position

·        

A right side that describes the change to be made to the board position to reflect the move

Fig: One Legal Chess Move

Note: There will be several numbers of Rules.

 

Fig: Another way to Describe Chess Moves

Control Strategies:

Control strategy is one of the most important components of problem solving that describes the order of application of the rules to the current state. Control strategy should be such that it causes motion towards a solution. The second requirement of control strategy is that it should explore the solution space in a systematic manner. Depth-First & Breadth-First are systematic control strategies. There are 2 directions in which a search could proceed

·         Data-Driven Search, called Forward Chaining, from the Start State

·         Goal-Driven Search, called Backward Chaining, from the Goal State

 

Forward Chaining: The process of forward chaining begins with known facts & works towards a solution. For example, in 8-puzzle problem, we start from the start state & work forward to the goal state. In this case, we begin building a tree of move sequences with the root of the tree as the start state. The states of next level of the tree are generated by finding all rules whose left sides match with root & use their right side to create the new state. This process is continued until a configuration that matches the goal state is generated.

Backward Chaining: It is a goal directed strategy that begins with the goal state & continues working backward, generating more sub-goals that must also be satisfied to satisfy main goal until we reach to start state. Prolog (Programming in Logic) language uses this strategy. In this case, we begin building a tree of move sequences with the goal state of the tree as the start state. The states of next level of the tree are generated by finding all rules whose right sides match with goal state & use their left side to create the new state. This process is continued until a configuration that matches the start state is generated.

Note: We can use both Data-Driven & Goal-Driven strategies for problem solving, depending on the nature of the problem.

 

CHARACTERISTICS OF PROBLEM:

A problem may have different aspects of representation and explanation. In order to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions. Some of the main key features of a problem are given below.

 

àIs the problem decomposable into set of sub problems?

àCan the solution step be ignored or undone?

àIs the problem universally predictable?

àIs a good solution to the problem obvious without comparison to all the      possible solutions?

àIs the desire solution a state of world or a path to a state?

 àIs a large amount of knowledge absolutely required to solve the problem?

 àWill the solution of the problem required interaction between the computer and the person?

 

1.Is the problem decomposable into a set of independent smaller sub problems?

Example: Suppose we want to solve the problem of computing the integral of the following expression ∫(x2+ 3x + sin2x * cos2x) dx

 

Fig  Decomposition problem

 

•          We can solve this problem by breaking it down into three smaller sub problems, each of which we can then be solved using a small collection of specific rules.

•          Decomposable problems can be solved by the divide and-conquer technique.

•          Use of decomposing problems:

-Each sub-problem is simpler to solve

-Each sub-problem can be handed over to a different processor. Thus can be solved in parallel processing environment.

àUsing the technique of problem decomposition, we can often solve very large problems easily

 

 

2.Can solution steps be ignored or at least undone if they prove to be unwise?

 

To find out whether the solutions steps can be ignored or undone. We have three classes of problems mentioned below:-

 

1.Ignorable: In which solution steps can be ignored (e.g., Theorem Proving).

 

Suppose we are trying to prove a mathematical theorem. First we proceed with proving a lemma that we think will be useful. Later we realize that it is not useful. So, Are we in serious trouble?. No, Still we can prove the theorem, only we need to ignore the first approach and start with another one to prove the theorem.

 

2.Recoverable:        In which solution steps can be undone. (e.g., 8-Puzzle Problem)

 

 

Suppose we have a 8-puzzle problem as shown in above figure. While attempting to solve the 8-puzzle problem, mistakenly we make a wrong move and realize that mistake. Now to correct our mistake we need to undo incorrect steps.

 

To undo incorrect steps the control mechanism for an 8-puzzle solver must keep track of the order in which steps are performed, so that we can backtrack to the initial state and start with some correct move.

 

3.Irrecoverable: In which solution steps cannot be undone. (e.g., Chess).

Consider the problem of playing chess. Suppose playing chess program makes a wrong move and realize it after couple of moves. It cannot simply ignore the mistake. Neither it can be undone its move and start the game again. Here, once we make a move we never recover from that step. Only we can try to give the best of the current situation.

 

3.Is the universe predictable?

 

Consider that we are playing with the 8-Puzzle problem. Every time we make a move, we know exactly what will happen. This means that it is possible to plan an entire sequence of moves and be confident what the resulting state will be. We can backtrack to previous moves if they prove wrong.

 

Suppose we want to play Bridge. We need to make some decisions like which card to play on the first trick. Then we need to make a plan for the entire hand before the first play, but we cannot plan and play with certainty since We cannot know where all the cards are or what the other players will do on their turns. So we have to investigate several plans and use probability of various outcomes to choose best plan for a good score. So, the outcome of this game is very uncertain.

 

These two games shows us difference between certain outcome (e.g. 8-Puzzle) and uncertain outcome (e.g. play bridge).

 

In case of certain outcome, we can make a plan to generate a sequence of operation that guaranteed to lead to a solution. So, that the outcome is very certain.

 

In case of uncertain outcome problems, we follow the process of plan revision as the plan is carried out and the necessary feedback is provided. The disadvantage is that the planning in this case is often very expensive.

 

4.Is a good solution Absolute or Relative?

Suppose we have the problem of answering questions based on the simple facts, such as following:

 

1.      Marcus was a man.

2.      Marcus was a Pompeian.

3.      Marcus was born in 50 A.D

4.      All men are mortal.

5.      All Pompeian died when volcano erupted in 79 A.D.

6.      No mortal lives longer than 150 years.

7.      It is now 1991 A.D.

 

Consider we ask the question “Is Marcus alive?”. By going through each of these facts, we can easily find the answer to the question. Suppose, two paths leads to the answer but we are interested in is the answer to the question, it does not matter which path we follow.

 

But now consider again the traveling salesman problem. In that we need to find the best solution (shortest path) among all of other solution.

 

5.Is the Solution a State or Path?

Examples:

àFinding a consistent interpretation for the sentence  “The bank president ate a dish of pasta salad with the fork”. We need to find the interpretation but not the record of the processing.

àWater jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.

 

6.What is the Role of knowledge?

Two examples: – Chess: Knowledge is required to constrain the search for a solution – Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.

àConsider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:

·        The names of the candidates in each party

·        The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans

·        The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.

·        The fact that if you are opposed to big government, you are probably supporting the Republicans.

 

7.Does the task require Interaction with a Person?

The problems can again be categorized under two heads.

 

1. Solitary in which the computer will be given a problem description and will produce an answer, with no intermediate communication and with he demand for an explanation of the reasoning process. Simple theorem proving falls under this category. Given the basic rules and laws, the theorem could be proved, if one exists.

Ex:- theorem proving (give basic rules & laws to computer)

2. Conversational, in which there will be intermediate communication between a person and the computer, wither to provide additional assistance to the

 

computer or to provide additional informed information to the user, or both problems such as medical diagnosis fall under this category, where people will be unwilling to accept the verdict of the program, if they can not follow its reasoning.

Ex:- Problems such as medical diagnosis.

 

8. Problem classification:

• There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:

Classification: ex: medical diagnostics, diagnosis of faults in mechanical devices

– Propose and Refine: ex: design and planning

EXHAUSTIVE SEARCHES (OR) UNIFORMED SEARCHES:

·         Breadth-First Search

·         Depth-First Search

·         Depth-First Iterative Deepening

·         Bidirectional Search

 

1.       Breadth-First Search (BFS):

·         BFS is the most common search strategy for traversing a tree or graph. This algorithm searches breadth wise in a tree or graph.

·         BFS algorithm starts searching from the root node of the tree and expands all successor node at the current level before moving to nodes of next level.

·         The breadth-first search algorithm is an example of a General-Graph search algorithm.

·         Breadth-first search implemented using FIFO queue data structure.

 

Algorithm:

1.        Create a variable called NODE-LIST and set it to the initial state.

2.        Loop until the goal state is found or NODE-LIST is empty.

a.        Remove the first element, say E, from the NODE-LIST. If NODE-LIST was empty then quit.

b.        For each way that each rule can match the state described in E do:

i.         Apply the rule to generate a new state.

ii.          If the new state is the goal state, quit and return this state.

iii.      Otherwise add this state to the end of NODE-LIST

 

 

Advantages:

·         BFS will provide a solution if any solution exists.

·         If there is more than one solution for a given problem, then BFS will provide the minimal solution which requires the least number of steps.

 

Disadvantages:

·         BFS requires lots of memory since each level of the tree must be saved into memory to expand the next level.

·         BFS needs lots of time if the solution is far away from the root node.

Example 1: S---> A--->B---->C--->D---->G--->H--->E---->F---->I---- >K.

Example 2: a---> b---> c---> d---> e---> f---> g---> h---> i---> j---- > k.

 

Example 3: BFS for Water Jug Problem

Example 4: 8-Puzzle Problem

 

Example 5:

 

2.       Depth-First Search (DFS):

·         DFS is a recursive algorithm for traversing a tree or graph data structure.

·         It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path.

·         DFS uses a stack data structure for its implementation.

Algorithm:

1.    If the initial state is a goal state, quit and return success.

2.    Otherwise, loop until success or failure is signaled.

a)    Generate a state, say E, and let it be the successor of the initial state. If there are no more successors, signal failure.

b)    Call Depth-First Search with E as the initial state.

c)    If success is returned, signal success. Otherwise continue in this loop.

 

 

Advantages:

·         DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node.

·         It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).

 

Disadvantages:

·         There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution.

·         DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.

 

Example 1:

 

Note: It will start searching from root node S, and traverse A, then B, then D and E, after traversing E, it will backtrack the tree as E has no other successor and still goal node is not found. After backtracking it will traverse node C and then G, and here it will terminate as it found goal node.

Example 2:

 

Example 3: Water Jug Problem

 

Example 4: 8- Puzzle Problem

Example 5: 8- Puzzle Problem

 

 

 

3.       Depth-First Iterative Deeping (DFID):

·         DFID is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.

·         This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing the depth limit after each iteration until the goal node is found.

·         This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency.

·         The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown.

 

Example:

Iteration 1: A

 

Iteration 2: A, B, C

 

 

Iteration 3: A, B, D, E, C, F, G

 

Iteration 4: A, B, D, H, I, E, C, F, K, G

In the fourth iteration, the algorithm will find the goal node. Advantages:

·         It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency. Disadvantages:

·         Repeats all the work of the previous phase.

4.       Bidirectional Search:

 

 

Bidirectional search is a graph search algorithm that runs 2 simultaneous searches. One search moves forward from the start state & other moves backward from the goal state & stops when the two meet in the middle. It is useful for those problems which have a single start state & single goal state.

 

Advantages:

·         Bidirectional search is fast.

·         Bidirectional search requires less memory

 

Disadvantages:

·         Implementation of the bidirectional search tree is difficult.

·         In bidirectional search, one should know the goal state in advance.

 

Example:

Fig: Graph to be Searched using Bidirectional Search

 

 

If match is found, then path can be traced from start to the matched state & from matched to the goal state. It should be noted that each node has link to its successors as well as to its parent. These links will be generating complete path from start to goal states.

 

The trace of finding path from node 1 to 16 using Bidirectional Search is as given below. The Path obtained is 1, 2, 6, 11, 14, 16.

 

 

5.       Analysis of Search Methods:

 

 

Time Complexity:  Time required by an algorithm to find a solution.

Space Complexity:  Space required by an algorithm to find a solution.

 

Search Technique	Time	Space
BFS	O( bd )	O( bd )
DFS	O( bd )	O(d)
DFID	O( bd )	O(d)
Bidirectional	O( bd/2 )	O( bd/2 )

Table: Performance Comparison

Travelling Salesman Problem (TSP):

 

 

Statement: In travelling salesman problem (TSP), one is required to find the shortest route of visiting all the cities once & running back to starting point. Assume that there are ‘n’ cities & the distance between each pair of the cities is given.

 

The problem seems to be simple, but deceptive. All the possible paths of the search tree are explored & the shortest path is returned. This will require (n-1)! paths to be examined for ‘n’ cities.

 

·         Start generating complete paths, keeping track of the shortest path found so far.

·         Stop exploring any path as soon as its partial length becomes greater than the shortest path length found so far.

 

 

In this case, there will be 4!=24 possible paths. In below performance comparison, we can notice that out of 13 paths shown, 5 paths are partially evaluated.

Table: Performance Comparison

HEURISTIC SEARCH TECHNIQUES:

Heuristic: It is helpful in improving the efficiency of search process.

·         Generate & Search

·         Branch & Bound Search (Uniformed Cost Search)

·         Hill Climbing

·         Beam Search

·         Best-First Search (A* Algorithm)

 

Generate & Test:

The Generate and test strategy is the simplest of all approaches. This method generates a solution for the given problem and tests the generated solution with the required solution.

 

Algorithm:

 

 

Start

·         Generate a possible solution

·         Test if it is a goal

·         If not go to start else quit End

 

Advantage:

·         Guarantee in finding a solution if a solution really exists.

 

Disadvantage:

·         Not suitable for the larger problems

 

Branch & Bound Search (Uniform Cost Search):

Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. This algorithm comes into play when a different cost is available for each edge. The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. Uniform-cost search expands nodes according to their path costs from the root node. It can be used to solve any graph/tree where the optimal cost is in demand. A uniform-cost search algorithm is implemented by the priority queue. It gives maximum priority to the lowest cumulative cost.

Example:

Advantage:

·         Uniform cost search is optimal because at every state the path with the least cost is chosen.

Disadvantage:

·         It does not care about the number of steps involve in searching and only concerned about path cost. Due to which this algorithm may be stuck in an infinite loop.

 

Hill Climbing:

·         Simple Hill Climbing

·         Steepest-Ascent Hill Climbing (Gradient Search) Simple Hill Climbing:

Simple hill climbing is the simplest way to implement a hill climbing algorithm. It only evaluates the neighbor node state at a time and selects the first one which optimizes current cost and set it as a current state. It only checks it's one successor state, and if it finds better than the current state, then move else be in the same state.

Algorithm:

Step 1: Evaluate the initial state, if it is goal state then return success and Stop. Step 2: Loop Until a solution is found or there is no new operator left to apply. Step 3: Select and apply an operator to the current state.

Step 4: Check new state:

·         If it is goal state, then return success and quit.

·         Else if it is better than the current state then assign new state as a current state.

·         Else if not better than the current state, then return to step2. Step 5: Exit.

Steepest-Ascent Hill Climbing (Gradient Search):

The steepest-Ascent algorithm is a variation of simple hill climbing algorithm. This algorithm examines all the neighboring nodes of the current state and selects one neighbor node which is closest to the goal state. This algorithm consumes more time as it searches for multiple neighbors.

 

Algorithm:

Step 1: Evaluate the initial state, if it is goal state then return success and stop, else make current state as initial state.

Step 2: Loop until a solution is found or the current state does not change.

a)        Let SUCC be a state such that any successor of the current state will be better than it.

b)       For each operator that applies to the current state:

·         Apply the new operator and generate a new state.

·         Evaluate the new state.

·         If it is goal state, then return it and quit, else compare it to the SUCC.

·         If it is better than SUCC, then set new state as SUCC.

·         If the SUCC is better than the current state, then set current state to SUCC. Step 5: Exit.

 

Disadvantages of Hill Climbing:

 

 

1.       

Local Maximum: It is a state that is better than all its neighbours but not better than some other states which are far away. From this state all moves looks to be worse. In such situation backtrack to some earlier state & try going in different direction to find a solution.

 

 

2.        Plateau: It is a flat area of the search space where all neighbouring states has the same value. It is not possible to determine the best direction. In such situation make a big jump to some direction & try to get to new section of the search space.

 

 

3.       

Ridge: It is an area of search space that is higher than surrounding areas but that cannot be traversed by single moves in any one direction. It is a special kind of Local Maxima.

Beam Search:

Beam Search is a heuristic search algorithm in which W number of best nodes at each level is always expanded. It progresses level-by-level & moves downward only from the best W nodes at each level. Beam Search uses BFS to build its search tree. At each level of tree it generates all its successors of the states at the current level, sorts them in order of increasing heuristic values. However it only considers W number of states at each level, whereas other nodes are ignored.

Here,    W - Width of Beam Search B - Branching Factor

There will only be W * B nodes under consideration at any depth but only W nodes will be selected.

 

 

Algorithm:

1.        Node=Root_Node; Found= false

2.        If Node is the goal node, then Found=true else find SUCCs of Node, if any with its estimated cost and store in OPEN list;

3.        While (Found=false and not able to proceed further) do

{

·         Sort OPEN list;

·         Select top W elements from OPEN list and put it in W_OPEN list and empty OPEN list

·         For each NODE from W_OPEN list

{

·         If NODE=Goal state then FOUND=true else find SUCCs of NODE. If any with its estimated cost and store in OPEN list;

}

}

4.        If FOUND=true then return Yes otherwise return No;

5.        Stop

 

 

Example:

Below is the search tree generated using Beam Search Algorithm. Assume, W=2 & B=3. Here black nodes are selected based on their heuristic values for further expansion.

 

Best-First Search:

It is a way of combining the advantages of both Depth-First and Breadth-First Search into a single method. At each step of the best-first search process, we select the most promising of the nodes we have generated so far. This is done by applying an appropriate heuristic function to each of them.

In some cases we have so many options to solve but only any one of them must be solved. In AI this can be represented as OR graphs. In this among all available sub problems either of them must be solved. Hence the name OR graph.

 

To implement such a graph-search procedure, we will need to use two lists of nodes.

 

OPEN: This list contains all the nodes those have been generated and have had the heuristic function applied to them but which have not yet been examined. OPEN is actually a priority queue in which the elements with the highest priority are those with the most promising value of the heuristic function.

CLOSED: This list contains all the nodes that have already been examined. We need to keep these nodes in memory if we want to search a graph rather than a tree.

Algorithm:

1.    Start with OPEN containing just the initial state

2.    Until a goal is found or there are no nodes left on OPEN do:

a)    Pick the best node on OPEN

b)    Generate its successors

c)    For each successor do:

i.        If it has not been generated before, evaluate it, add it to OPEN, and record its parent.

ii.        If it has been generated before, change the parent if this new path is better than the previous one. In that case, update the cost of getting to this node and to any successors that this node may already have.

Example:

Fig: A Best-First Search

 

 

Step 1: At this level we have only one node, i.e., initial node A

Step 2: Now we generate the successors A, three new nodes are generated namely B, C, and D with the costs of 3, 5 and 1 respectively. So these nodes are added to the OPEN list and A can be shifted to CLOSED list since it is processed.

Among these three nodes D is having the least cost, and hence selected for expansion. So this node is shifted to CLOSED list.

 

Step 3: At this stage the node D is expanded generating the new nodes E and F with the costs 4 and 6 respectively. The newly generated nodes will be added to the OPEN list. And node D will be added to CLOSED list.

 

 

Step 4: At this stage node B is expanded generating the new nodes G & H with costs 6 and 5 respectively. The newly generated nodes will be added to the OPEN list. And node B will be added to CLOSED list.

 

 

Step 5: this stage node E is expanded generating the new nodes I & J with costs 2 and 1 respectively. The newly generated nodes will be added to the OPEN list. And node E will be added to CLOSED list.

A* Algorithm:

A* is a Best First Search algorithm that finds the least cost path from initial node to one goal node (out of one or more possible goals)

f l(x) = g(x) + hl(x)

Where,             f l = estimate of cost from initial state to goal state, along the path that generated current node. g = measure of cost getting from initial state to current node.

hl = estimate of the additional cost of getting from current node to a goal state.

 

Algorithm:

1.    Start with OPEN containing only the initial node. Set that node’s g value to 0, its h¹ value to whatever it is, and its f¹ value to h¹+0, or h¹. Set CLOSED to the empty list.

2.   Until a goal node is found, repeat the following procedure:

 

 If there are no nodes on OPEN, report failure. Otherwise, pick the node on OPEN with the lowest f¹ value. Call it BESTNODE. Remove it from OPEN place it on CLOSED.

See if BESTNODE is a goal node. If so, exit and report solution (either BESTNODE if all we want is the node or the path that has been created between the initial state and BESTNODE if we are interested in the path). Otherwise, generate the successor of BESTNODE but do not set BESTNODE to point to them yet. (First we need to see if any of them have already been generated). For each such SUCCESSOR, do the following:

a)     Set SUCCESSOR to point back to BESTNODE. These backwards links will make it possible to recover the path once a solution is found.

 

b)    Compute g(SUCCESSOR) = g( BESTNODE) + cost of getting from BESTNODE to SUCCESSOR.

 

c)     If SUCCESSOR is same as any node on OPEN (i.e., it has already been generated     but not processed). If so, call that node OLD. Since this node already exists in the      graph, we can throw SUCCESSOR away and add OLD to the list of BEST NODE’S successors. Now we must decide whether OLD’s parent link should be reset to point to BESTNODE. It should be if the path we have just found to SUCCESSOR is cheaper than the current best path to OLD (Since SUCCESSOR and OLD are really the same node). So see whether it is cheaper to get to OLD via its current parent or to SUCCESSOR via BESTNODE by comparing their g values. If OLD is cheaper (or just as cheap),

      then we need do nothing. If SUCCESSOR is cheaper, then reset OLD’s parent link to point to BESTNODE, record the new cheaper path in g(OLD), and update f1(OLD).

 

d)    If SUCCESSOR was not on OPEN, see if it is on CLOSED. If so call the node CLOSEDOLD and add OLD to the list of BESTNODE’s successors..

 

e)        If SUCCESSOR was not already on earlier OPEN or CLOSED, then put it on OPEN and add it to the list of BESTNODE’S successors.

Compute f’ (SUCCESSOR) = g (SUCCESSOR) +h’ (SUCCESSOR)

Example 1:

Example 2: Assuming all the values (arcs) as ‘1’

Optimal Solution by A* Algorithm:

·         Underestimation

·         Overestimation

Underestimation: From the below start node A is expanded to B, C & D with f values as 4, 5 & 6 respectively. Here, we are assuming that the cost of all arcs is 1 for the sake of simplicity. Note that node B has minimum f value, so expand this node to E which has f value as 5. Since f value of C is also 5, we resolve in favour of E, the path currently we are expanding. Now node E is expanded to node F with f value as 6. Clearly, expansion of a node F is stopped as f value of C is not the smallest. Thus, we see that by underestimating heuristic value, we have wasted some effort by eventually discovered that B was farther away than we thought. Now we go back & try another path & will find the optimal path.

Overestimation: Here we are overestimating heuristic value of each node in the graph/tree. We expand B to E, E to F & F to G for a solution path of length 4. But assume that there is direct path from D to a solution giving a path of length 2 as h value of D is also overestimated. We will never find it because of overestimating h(D). We may find some other worse solution without ever expanding D. So, by overestimating h, we cannot be guaranteed to find the shortest path.

 

Admissibility of A*:

A search algorithm is admissible, if for any graph, it always terminates in an optional path from start state to goal state, if path exists. We have seen earlier that if heuristic function ‘h’ underestimates the actual value from current state to goal state, then it bounds to give an optimal solution & hence is called admissible function. So, we can say that A* always terminates with the optimal path in case h is an admissible heuristic function.

 

ITERATIVE-DEEPING A*

IDA* is a combination of the DFID & A* algorithm. Here the successive iterations are corresponding to increasing values of the total cost of a path rather than increasing depth of the search. Algorithm works as follows:

 

·         For each iteration, perform a DFS pruning off a branch when its total cost (g+h) exceeds a given threshold.

·         The initial threshold starts at the estimate cost of the start state & increases for each iteration of the algorithm.

·         The threshold used for the next iteration is the minimum cost of all values exceeded the current threshold.

·         These steps are repeated till we find a goal state.

 

Let us consider as example to illustrate the working IDA* Algorithm as shown below. Initially, the threshold value is the estimated cost of the start node. In the first iteration, threshold=5. Now we generate all the successors of start node & compute their estimated values as 6, 8, 4, 8 & 9. The successors having values greater than 5 are to be pruned. Now for next iteration, we consider the threshold to be the minimum of the pruned nodes value, that is, threshold=6 & the node with 6 value along with node with value 4 are retained for further expansion.

 

Advantages:

·         Simpler to implement over A* is that it does not use Open & Closed lists

·         Finds solution of least cost or optimal solution

·         Uses less space than A*

Fig: Working of IDA*

 

 

CONSTRAINT SATISFACTION:

Many problems in AI can be viewed as problems of constraint satisfaction in which the goal is to discover some problem state that satisfies a given set of constraints instead of finding a optimal path to the solution. Such problems are called Constraint Satisfaction (CS) problems. Constraint satisfaction is a two step process.

·         First, constraints are discovered and propagated as far as possible throughout the system. Then, if there is still not a solution then the search begins. A guess about something is made and added as a new constraint

·         Propagation then occurs with this new constraint.

 

Start State: all the variables are unassigned.

Goal State: all the variables are assigned which satisfy constraints. Rules:

·         Values of variables should be from 0 to 9

·         No 2 variables have same value

 

Algorithm:

1.  Propagate available constraints. To do this, first set OPEN to the set of all objects that must have values assigned to them in a complete solution. Then do until an inconsistency is detected or until OPEN is empty:

a)        Select an object OB from OPEN. Strengthen as much as possible the set of constraints that apply to OB.

b)       If this set is different from the set that was assigned the last time OB was examined or if this is the first time OB has been examined, then add to OPEN all objects that share any constraints with OB

c)        Remove OB from OPEN.

2.  If the union of the constraints discovered above defines a solution, then quit and report the solution.

3.  If the union of the constraints discovered above defines a contradiction, then return failure.

4.  If neither of the above occurs, then it is necessary to make a guess at in order to proceed. To do this, loop until a solution is found or all possible solutions have been eliminated

a)        Select an object whose value is not yet determined and select a way of strengthening the constraints on that object.

b)       Recursively invoke constrain satisfaction with the current set of constraints augmented by the strengthening constraint just selected.

Example:

 

 

Let us consider M=1, because by adding any 2 single digit number, at maximum we get one as carry.

 

Assume that S=8 (or) 9, S + M = 0 (or) S + M + C3 = 0 If S = 9, S + M = 9 + 1 =10 (with no carry)

If S = 8, S + M + C3 = 8 + 1 + 1 = 10 (with carry). So, we get O value as 0. Therefore, M = 1, S = 9 & O = 0.

So, here E + 0 = N. Then E =N (It is not possible because no 2 variables should have same value). E + O + c2 = N

E + 0 + 1 = N which gives E + 1 = N

Estimate E value from the remaining possible numbers i.e.., 2, 3, 4, 5, 6, 7, 8. So, from our estimation the E & N values satisfies at E = 5. So, E + 1 = 5 + 1 = 6 i.e.., N = 6 (E + 1 = N)

Therefore, M = 1, S = 9, O = 0, E = 5 & N = 6.

 

So, here N + R + C1 = E. We already know that E = 5. So, the E value is satisfied by taking R = 8. 6 + 8 + 1 = 15.

Therefore, M = 1, S = 9, O = 0, E = 5, N = 6 & R = 8

 

 

 

 

 

 

.

Here, D + E = Y. It has to satisfy C1 = 1, so that D = 7. Then, 7 + 5 = 12. So, Y = 2.

Final Values are M = 1, S = 9, O = 0, E = 5, N = 6, R = 8, D = 7 & Y = 2.

By substituting all the above values,

Some other Examples of Constraint Satisfaction are as below, Example 2:

 

 

 

Example 3:

 

Example 4:

 

Example 5:

Example 6:

 

 

 

 

                                                                                                                                                                    

 

 

 

 

 

 

 

 

2.2  PROBLEM REDUCTION AND GAME PLAYING

INTRODUCTION:

An effective way of solving a complex problem is to reduce it to simpler parts & solve each part separately. Problem Reduction enables us to obtain an elegant solution to the problem. The structure called AND-OR graph (or tree) is useful for representing the solution of complicated problems. The decomposition of a complex problem generates arcs which we call AND arcs. One AND arc may point to any number of successors, all of which must be solved.

 

PROBLEM REDUCTION (AND-OR Graph) (or) AO* ALGORITHM:

In real-world applications, complicated problems can be divided into simpler sub-problems. The solution of each sub-problem may then be combined to obtain the final solution. A given problem may be solved in a number of ways. An AND-OR Graph provides a simple representation of a complex problem that leads to better understanding. For instance, if you wish to own a cellular phone then it may be possible that either someone gifts one to you or you earn money & buy one for yourself. The AND-OR graph which depicts these possibilities is as shown below

 

Fig: A simple AND-OR Graph

 

 

Let us consider a problem known as Towers of Hanoi to illustrate the need of problem reduction concept. The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks being stacked in descending order of their sizes, with the largest at the bottom of the stack & the smallest at the top thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod by using the following rules:

·         Only one disk can be moved at a time.

·         Each move consists of taking the uppermost disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.

·         No larger disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ − 1, where n is the number of disks which is as follows

 

 

Consider an AND-OR graph where each arc with a single successor has a cost of 1. Let us assume that the numbers listed in parenthesis ( ) denote the estimated costs, while the numbers in the square brackets [ ] represent the revised costs of the path. Thick lines indicate paths from a given node.

 

 

Let us begin search from start node A & compute the heuristic values for each of its successors, say B & (C,D) as 19 and (8,9) respectively. The estimated cost of paths from A to B is 20 (19 + cost of one arc from A to

B) & that from A to (C,D) is 19 (8 + 9 + cost of 2 arcs, A to C & A to D). The path from A to (C,D) seems to be better than that from A to B. So, we expand this AND path by extending C to (G,H) and D to (I,J). Now, heuristic values of G, H, I & J are 3, 4, 8 & 7 respectively which lead to revised costs of C & D as 9 & 17 respectively. These values are then propagated up & the revised costs of path from A to (C,D) is calculated as 28 (9 + 17+ Cost of arc A to C & A to D).

Note that the revised cost of this path is now 28 instead of the earlier estimation of 19. Thus, this path is no longer the best path now. Therefore, choose the path from A to B for expansion. After expansion we see that the heuristic value of node B is 17 thus making the cost of the path from A to B equal to 18. This path is the best so far. Therefore, we further explore the path from A to B. The process continues until either a solution is found (or) all paths lead to dead ends, indicating that there is no solution.

 

AO* Algorithm :

The problem reduction algorithm is a simplification algorithm of this AO* algorithm. Instead of using OPEN and CLOSED lists, this algorithm uses a structure GRAPH representing the part of the search graph generated so far. Each node in the graph represents both its successors and its predecessors to represent the solution path once it has been found. Each node in the graph will have an associated with it an h1 value, an estimate of cost of the path from itself to the set of solution paths.

 

1.      Let GRAPH consists only of the node representing the initial state. (call this node INIT.)   Compute h¹(INIT)

2.      Until INIT is labeled SOLVED or until INIT’s h¹ value becomes greater than FUTILITY,   repeat the following procedure.

 

a)     Trace the labeled arcs from INIT and select for expansion one of the as yet unexpanded nodes that occurs on this path. Call the selected node NODE.

b)     Generate the successors of NODE. If there are none, then assign FUTILITY as the h¹ value of NODE. This is equivalent to saying that NODE is not solvable. If there are successors then for each one ( called SUCCESSOR) that is not also an ancestor of NODE do the following:

i)       add SUCCESSOR to GRAPH

ii)    If SUCCESSOR is a terminal node, label it SOLVED and assign it an h¹ value of 0.

iii)  If SUCCESSOR is not a terminal node, compute its h¹ value.

c)     Propagate the newly discovered information up the graph by doing the following: Let S be a set of nodes that have been labeled SOLVED or whose h¹ values have been changed and so need to have values propagated back to their parents. Initialize S to NODE. Until S is empty, repeat the following procedure:

 

i)       If possible select from S a node none of whose descendants in a GRAPH occurs in S. If there are no such nodes select any node from

S. Call this node CURRENT, and remove it from S.

ii)    Compute the cost of each of the arcs emerging from CURRENT. The cost of each arc is equal to the sum of the h¹ values of each of the nodes at the end of the arch plus whatever the cost of the arc itself is. Assign as CURRENT’s new h¹ value the minimum of the costs just computed for the arcs emerging from it.

iii)  Mark the best path out of CURRENT by marking the arc that had the minimum cost as computed in the previous step.

iv)  Mark CURRENT SOLVED if all of the nodes connected to it through the new labeled arc have been labeled SOLVED.

v)     If CURRENT has been labeled SOLVED or if the cost of CURRENT was just changed, then its new status must be propagated back up the graph. So add all of the ancestors of CURRENT to S.

 

.

GAME PLAYING:

Game playing is a major topic of AI as it requires intelligence & has certain well-defined states & rules. A game is defined as a sequence of choices where each choice is made from a number of discrete alternatives. Each sequence ends in a certain outcome & every outcome has a definite value for opening player.

Games can be classified into 2 types

·         Perfect Information Games

·         Imperfect Information Games

Perfect Information Games are those in which both the players have access to the same information about the game in progress. Examples are Tic-Tac-Toe, Chess etc.

Imperfect Information Games are those in which players do not have access to the complete information about the game. Examples are Cards, Dice etc.

 

Game Problem versus State Space Problem:

In state space problems, we have a start state, intermediate states, rules or operators & a goal state. In game problems also we have a start state, legal moves & winning positions (goals).

 

State Space Problems	Game Problems
States	Legal board positions
Rules	Legal moves
Goals	Winning Positions

                              Table: Comparisons between State Space Problems & Game Problems

 

A Game begins from a specified initial state & ends in a position that can be declared a win for one, a loss for the other or possible a draw. A Game Tree is an explicit representation of all possible plays of the game. The root node is an initial position of the game. Its successors are the positions that the first player can reach in one move; their successors are the positions resulting from the second player’s move & so on. Terminal or leaf nodes are represented by WIN, LOSS (or) DRAW.

Game theory is based on the philosophy of minimizing the maximum possible loss and maximizing the minimum gain. In game playing involving computers, one player is assumed to be the computer, while the other is a human. During a game, 2 types of nodes are encountered, namely MAX & MIN. The MAX node will try to maximize its own game, while minimizing the opponent’s (MIN) game. Either of the 2 players MAX & MIN can play as first player.

 

Status Labelling Procedure in Game Tree:

Status labeling procedure for a node with WIN, LOSS or DRAW in case of a game tree is as follows:

 

A Game Tree in which MAX Plays First:

 

A Game Tree in which MIN Plays First:

 

 

 

Nim Game Problem:

 

Nim game was developed by Charles L. Bouton of Harward University at china in 1901.

 

 

The Game: There is a single pile of matchsticks (>1) and two players. Moves are made by the players alternately. In a move, each player can pick up a maximum of half the number or matchsticks in the pile. Whoever takes the last match sticks loses. Let us consider for explaining the concept with single pile of 7 matchsticks

The convention used for drawing a game tree is that each node contains the total number of sticks in the pile and is labeled as W or L in accordance with the status labeling procedure. The player who has to pick up the last sticks loses. If a single stick is left at the MAX level then as a rule of the game, MAX node is assigned the status L, whereas if one stick is left at the MIN level, then W is assigned to MIN node as MAX wins. The label L or W have been assigned from MAX’s point of view at leaf nodes. Arcs carry the number of sticks to be removed; Dotted lines show the propagation of status. The complete game tree for Nim with MAX playing first is as follows

 

 

The complete game tree for Nim with MIN playing first is as follows

MINIMAX PROCEDURE:

MINIMAX procedure is a recursive or backtracking algorithm which is used in decision-making and game theory. This is mostly used for game playing in AI, such as Chess, Checkers, tic-tac-toe & various tow- players game. In this 2 players play the game, one is called MAX and other is called MIN, where MAX will select the maximized value and MIN will select the minimized value. The minimax algorithm performs a depth- first search algorithm for the exploration of the complete game tree. The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion.

Working of MINIMAX Algorithm:

·         The working of the minimax algorithm can be easily described using an example. Below we have taken an example of game-tree which is representing the two-player game.

·         In this example, there are two players one is called Maximizer and other is called Minimizer.

·         Maximizer will try to get the Maximum possible score, and Minimizer will try to get the minimum possible score.

·         This algorithm applies DFS, so in this game-tree, we have to go all the way through the leaves to reach the terminal nodes.

·         At the terminal node, the terminal values are given so we will compare those values and backtrack the tree until the initial state occurs. Following are the main steps involved in solving the two-player game tree:

Step 1: In the first step, the algorithm generates the entire game-tree. Let's take A is the initial state of the tree. Suppose maximizer takes first turn and minimizer will take next turn.

 

Step 2: Now, first we find the utilities value for the Maximizer. It will find the maximum among the all.

·         For node D            max(-1,4) = 4

·         For Node E            max(2, 6) = 6

·         For Node F           max(-3,-5) = -3

·         For node G            max(0, 7) = 7

 

Step 3: In the next step, it's a turn for minimizer,

·         For node B= min(4,6) = 4

·         For node C= min (-3, 7) = -3

Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value and find the maximum value for the root node. In this game tree, there are only 4 layers, hence we reach immediately to the root node, but in real games, there will be more than 4 layers.

 

·         For node A max(4, -3) = 4

Example 1:

 

Time Complexity: As it  performs  DFS  for  the  game-tree,  the  time  complexity  of  MINIMAX  algorithm  is O(bm), where b is branching factor of the game-tree, and m is the maximum depth of the tree.

Space Complexity: Space complexity of MINIMAX algorithm is also similar to DFS which is O(bm).

 

 

Limitations of MINIMAX Algorithm:

·         Gets really slow for complex games such as Chess, go, etc.

·         This type of games has a huge branching factor, and the player has lots of choices to decide. Note: This limitation of the MINIMAX algorithm can be improved from alpha-beta pruning.

Example 2:

Fig: A Game Tree generated using MINIMAX Procedure

ALPHA-BETA PRUNING:

Alpha-beta pruning is a modified version of the MINIMAX algorithm. It is an optimization technique for the MINIMAX algorithm. There is a technique by which without checking each node of the game tree we can compute the correct MINIMAX decision, and this technique is called Pruning. This involves two threshold parameter Alpha and beta for future expansion, so it is called ALPHA-BETA pruning.

·         Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only prune the tree leaves but also entire sub-tree.

·         The two-parameter can be defined as:

a)                 Alpha: The best (highest-value) choice we have found so far at any point along the path of Maximizer. The initial value of alpha is -∞.

b)                Beta: The best (lowest-value) choice we have found so far at any point along the path of Minimizer. The initial value of beta is +∞.

·         Pruning of nodes makes the algorithm fast.

 

 

Condition for Alpha-beta pruning: α>=β

 

Key points:

·         The Max player will only update the value of alpha.

·         The Min player will only update the value of beta.

·         While backtracking the tree, the node values will be passed to upper nodes instead of values of alpha and beta.

·         We will only pass the alpha, beta values to the child nodes.

 

Working of Alpha-beta pruning:

Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β= +∞, these value of alpha and beta passed down to node B where again α= -∞ and β= +∞, and Node B passes the same value to its child D.

 

 

Step 2: At Node D, the value of α will be calculated as its turn for Max. The value of α is compared with firstly 2 and then 3, and the max (2, 3) = 3 will be the value of α at node D and node value will also 3.

 

Step 3: Now algorithm backtracks to node B, where the value of β will change as this is a turn of Min, Now β=

+∞, will compare with the available subsequent nodes value, i.e. min (∞, 3) = 3, hence at node B now α= -∞, and β= 3.

 

In the next step, algorithm traverse the next successor of Node B which is node E, and the values of α= -∞, and β= 3 will also be passed.

 

Step 4: At node E, Max will take its turn, and the value of alpha will change. The current value of alpha will be compared with 5, so max (-∞, 5) = 5, hence at node E α= 5 and β= 3, where α>=β, so the right successor of E will be pruned, and algorithm will not traverse it, and the value at node E will be 5.

Step 5: At next step, algorithm again backtrack the tree, from node B to node A. At node A, the value of alpha will be changed the maximum available value is 3 as max (-∞, 3)= 3, and β= +∞, these two values now passes to right successor of A which is Node C. At node C, α=3 and β= +∞, and the same values will be passed on to node F.

Step 6: At node F, again the value of α will be compared with left child which is 0, and max(3,0)= 3, and then compared with right child which is 1, and max(3,1)= 3 still α remains 3, but the node value of F will become 1.

 

Step 7: Node F returns the node value 1 to node C, at C α= 3 and β= +∞, here the value of beta will be changed, it will compare with 1 so min (∞, 1) = 1. Now at C, α=3 and β= 1, and again it satisfies the condition α>=β, so the next child of C which is G will be pruned, and the algorithm will not compute the entire sub-tree G.

 

Step 8: C now returns the value of 1 to A here the best value for A is max (3, 1) = 3. Following is the final game tree which is the showing the nodes which are computed and nodes which has never computed. Hence the optimal value for the maximizer is 3 for this example.

 

 

Example 2:

 

 

 

Time Complexity: O (b^m/2).

 

 

 

 

 

TWO-PLAYER PERFECT INFORMATION GAMES:

·         Chess

·         Checkers

·         Othello

·         Go

·         Backgammon

 

Chess: Chess is basically a competitive 2 player game played on a chequered board with 64 squares arranged in an 8 X 8 square. Each player is given 16 pieces of the same colour (black or white). These include 1 King, 1 Queen, 2 Rooks, 2 Knights, 2 Bishops & 8 pawns. Each of these pieces move in a unique manner. The player who chooses the white pieces gets the first turn to play. The players get alternate chances in which they can move one piece at a time. The objective of this game is to remove the opponent’s king from the game. The opponent’s King has to be placed in such a situation where the king is under immediate attack & there is no way to save it from the attack. This is known as Checkmate.

 

Checkers: Checkers (or) Draughts a 2 player game played on a chequered 8 X 8 square board. Each player gets 12 pieces of the same colour (dark or light) which are played on the dark squares of the board in3 rows. The  row closest to a player is called the king row. The pieces in the king row are called kings, while others are called men. Kings can move diagonally forward as well as backward. Men can move only diagonally forward. A player can remove opponent’s pieces from the game by diagonally jumping over them. When men pieces jump over king pieces of the opponent, they transform into Kings. The objective of this game is to remove all the pieces of the opponent from the board or by leading the opponent to such a situation where the opposing player is left with no legal moves.

 

Othello: Othello (or) Reversi is a 2 player board game which is played on an 8 X 8 square grid with pieces that have 2 distinct bi-coloured sides. The pieces typically are shaped as coins, but each possesses a light & a dark face, each face representing one player. The objective of this game is to make your pieces constitute a majority of the pieces on the board at the end of the game, by turning over as many of your opponent’s pieces as possible.

 

Go: It is a strategic 2 player game in which the players play alternatively by placing black & white stone on the vacant intersections of a 19 X 19 board. The objective of the game is to control a larger part of the board than the opponent. To achieve this, players try to place their stones in such a manner that they cannot be captured by the opposing player. Placing stones close to each other helps them support one another & avoid

capture. On the other hand, placing them far apart creates an influence across a larger part of the board. It is a strategy that enables players to play a defensive as well as an offensive game & choose between tactical urgency & strategic planning. A stone or a group of stones is captured & removed if it has no empty adjacent intersections, that is, it is completely surrounded by stones of the opposing colour. The game is declared over & the score is counted when both players consecutively pass on a turn, indicating that neither side can increase its territory or reduce that of its opponent’s.

 

Backgammon: It is also a 2 player board game in which the playing pieces are moved using dice. A player wins by removing all of his pieces from the board. All though luck plays an important role, there is a large scope for strategy. With each roll of the dice a player must choose from numerous options for moving his checkers & anticipate the possible counter moves by the opponent. Players may raise the stakes during the game.