we  realize that there is another case we should deal with and which is an example of strategic thinking.

People: Andres Perea

1. Introduction
2. Part I: Standard beliefs in static games
   1. Belief in the opponent’s rationality
   2. Common belief in rationality
   3. Simple belief hierarchies
3. Part II: Lexicographic beliefs in static games
   1. Primary belief in the opponent’s rationality
   2. Respecting the opponent’s preferences
   3. Assuming the opponent’s rationality
4. Part III: Conditional beliefs in dynamic games
   1. Belief in the opponents’ future rationality
   2. Strong belief in the opponent’s  rationality

Practical and Theoretical problems in every chapter.

Given a  search space, apply search and find the solution quickly and make sure that solution is optimal. i.e, both look up cost and execution cost must be minimum.

Brute force procedure

BritishMuseum (){

1. Explore the entire search space;
2. return the optimal solution;

}

Branch&Bound(){

1. open <- {(start, NIL, Cost(start))}
2. closed <- {}
3. while TRUE
4.   do if Empty(open)
5.                   then return FAILURE;
6.   pick  the cheapest node n from  open
7.   if GoalTest(Head(n))
8.            then return ReconstructPath(n)
9.    else  children <- MoveGen(Head(n))
10.              for each m ∈ children{
11.                       do Cost(m) <- Cost(n) + K(m, n)
12.                        Add  (m, Head(n), Cost(m) ) to open }

}

GeneralisedBranch&Bound(){

1. start with all possible solutions
2. repeat
3.      Refine the least ( Estimated cost ) solution further
4. until the cheapest solution is fully refined
   
5. return s

}

Dijkstra’s Alg(){

1. Color all nodes white
2. cost(start) <- 0
3. parent(start) <- NIL
4. for all other nodes n
5.        do cost(n) <- ∞
6. repeat
7.     select lowest cost white node n
8.      color n black
9.      for all white neighbors m of n
10.             do if (const(n) + k(n, m)) < cost(m)
11.                   then cost(m) = const(n) + k(n, m)
12.                             parent(m) <- n
13. until all nodes are colored black

}

A*(){

// heuristic fun f(n) = g(n) + h(n)

//g(n) =known cost of path found from S to n

//h(n) = Estimated cost of path from n to G

1. open <- List(start)
2. f(start) <- h(start)
3. parent(start) <- NIL
4. closed <- {}
5. while open is not EMPTY
6.    do
7.        Remove node n from open such that f(n) has the lowest value
8.        Add n to closed
9.        if GoalTest(n) == TRUE
10.             then return Reconstructpath(n)
11.        neighbors <- MoveGen(n)
12.        for each m ∈ neighbors
13.               do switch
14.                    case m ∉ open and m ∉ closed : /* new node */
15.                            Add m to open
16.                            parent(m) <- n
17.                            g(m) <- g(n) + k(n, m)
18.                            f(m) <- g(m) + h(m)
20.                     case m ∈ open :
21.                            if (g(n) + k(n, m) ) < g(m)
22.                                   then  parent(m) <- n
23.                                              g(m) <- g(n) + k(n, m )
24.                                              f(m) <- g(m) + h(m)
26.                     case m ∈ closed :
27.                            if (g(n) + k(n, m) ) < g(m)
28.                                   then  parent(m) <- n
29.                                              g(m) <- g(n) + k(n, m )
30.                                              f(m) <- g(m) + h(m)
31.                                             propagateImprovement(m)
32. return FAILURE

}

PropagateImprovement(m){

1.  neighbours <- MoveGen(m)
2. for each  s ∈ neighbours
3.         do newGvalue <- g(m)  + k(m, s)
4.               if newGvalue < g(s)
5.                   then parent(s) <- m
6.                             g(s) <- newGvalue
7.                             if s ∈ closed
8.                                   then PropagateImprovement(s)

}

Admissibility of A*

Assumptions:

1. The branching factor is finite

Board Games:

• two persons,
• Zero sum,
• complete information,
• alternative moves, and
• deterministic games.

Convention of game trees

• MiniMax()
• AlphaBeta()

In above figure, Max has found

• SSS*()
• B*()