Again this algorithm is not the best solution: It's not always going to give us the optimal solution because in the bigger picture this won't give us a shortest path. How do we improve this algorithm? A* Search: expands a node with lowest value of g(n) [ Coast to reach node ] + h(n) [ Estimated cost to goal ].
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Consider the same maze: When it reaches 6, it considers 13, where 6 steps + 13 gives 19 where as 14 + 6 would give us 21 which is more when considered in terms of cost. h(n) is admissible (never overestimates true cost) and consistent (for every node n and successor n' with step cost c, h(n) <= h(n') + c). As long as these are true: the solution becomes optimistic.
Adverserial Search: Where an agent tries to make intelligent decisions where there is someone else who want then to fail. Consider Tic Tac Toe. A fair amount of reasonable decisions were made for a player to win by getting thre consecutive X's in a row or in column or diagonal.
MINIMAX
MAX (X): aims to maximize the score.
MIN (O): aims to minimize the score.
Game
S0: Initial state Player (s): returns which player to move in state x. Actions(s): returns legal moves in state s. Result(s, a): returns the overall state after a number of moves were made. Utility(s): Score of that utility of that state. Terminal(s): -1 for O wining, 0 for no one winning, 1 for X winning.
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Choosing the state that maximises/ minimizes the score.
The minimizing player choose the minimum possible value. MINIMAX MAX picks action a in Actions(s) that produces highest value of MIN-VALUE(Result(s, a)) and vice versa goes for MIN.
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
Oops! This image does not follow our content guidelines. To continue publishing, please remove it or upload a different image.
DEPTH-LIMITED MINIMAX After a certain number of moves: Not consider additional moves. However a problem arises when the game cannot be finished after a certain number of moves: so here, we use the evaluation function - a function that estimates the expected utility of a game from a given state.
