O D E S A D

üObservable

Fully observable

üDeterministic

Strategic

üEpisodic

Sequential

üStatic

Semi dynamic

üAgent

Multi agent

üDiscrete

discrete

Formulation

üState

              Move chess parts to eat computer parts untle  Besieging king 

üintial state

Any state

üSuccessor function

Top , Down , Left , Right , diagonal

üGoal

King die

üPath cost

Time , each step cost 1

nTwo level from the tree but second level is a sample

Alpha–beta pruning algorithm

nAlpha–beta pruning algorithm

nAlpha-Beta Heuristic  is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of thegame tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and search for alternatives, onerefutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. 

function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
         for each child of node
              α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
              if β ≤ α
                    break (* β cut-off *)
              return α
    else
         for each child of node
               β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
              if β ≤ α
                  break (* α cut-off *)
         return β
 (* Initial call *) alphabeta(origin, depth, -∞, +∞, TRUE)

minmax Searching algorithm

n

nMinmax algorithm

Minimax is an algorithm used to determine the score in a zero-sum game after a certain number of moves, with best play according to an evaluation function.

The algorithm can be explained like this: In a one-ply search, where only move sequences with length one are examined, the side to move (max player) can simply look at the evaluation after playing all possible moves. The move with the best evaluation is chosen. But for a two-plysearch, when the opponent also moves, things become more complicated. The opponent (min player) also chooses the move that gets the best score. Therefore, the score of each move is now the score of the worst that the opponent can do.

function minimax(node, depth, maximizingPlayer)  if depth = 0 or node is a terminal node
       return the heuristic value of node
 if maximizingPlayer
     bestValue := -∞
     for each child of node
           val := minimax(child, depth - 1, FALSE)
           bestValue := max(bestValue, val)
           return bestValue
 else
         bestValue := +∞
         for each child of node
             val := minimax(child, depth - 1, TRUE)
             bestValue := min(bestValue, val);
       return bestValue
(* Initial call for maximizing player *) minimax(origin, depth, TRUE)