Artificial Intelligence with Python:-
Agent- Entity that perceives its environment and acts upon that environment.
Initial State- The state in which the agent begins.
Actions- Actions(s) returns the set of actions that can be executed in state s
Transition Model- A description of what state results from performing any applicable action in any state.
— RESULT(s, a) returns the state resulting from performing action a in state s
State Space- The set of all states reachable from the initial state by any sequence of actions.
Goal test- A way to determine whether a given state is a goal state.
Path Cost- Numerical cost associated with a given path.
Search Problems-
- initial state
- actions
- transition model
- goal test
- path cost function
Solution -
A sequence of actions that leads from the initial state to a goal state.
Optimal-Solution- A solution that has the lowest path cost among all solutions.
Node- A data structure that keeps track of
- a state
- a parent (node that generated this node)
- an action(action applied to parent to get code)
- a path cost(from initial state to node)
Approach-
-
Start with a frontier that contains the initial state.
-
Repeat:
* if the frontier is empty, then no solution. -
Remove a node from the frontier.
-
If node contains goal state, return the solution.
-
Expand node, add resulting nodes to the frontier.
Find a node from A to E.
Revised Approach:-
-
Start with a frontier that contains the initial state.
-
Start with an empty explored set.
-
Repeat:
if the frontier is empty, then no solution. -
Remove a node from the frontier
-
If node contains goal state, return the solution.
-
Add the node to the explored set.
-
Expand node, add resulting nodes to the frontier if they aren't already in the frontier or the explored set.
-
One of the simplest data structures for adding and removing elements is called Stack- last-in-first-out data type.
-
So when we treat the frontier like a stack, a last in, first out data structure, that's the result we get.
Depth-First-Search-
Is the search algorithm that always expands the deepest node in the frontier.
Breath-First-Search-
search algorithm that always expands the shallowest node in the frontier.
It means that instead of using a stack, which depth-first-search, or DFS, used where the most recent item added to the frontier is the one we'll explore next, in breath-first-search, or BFS, will instead use a queue— First-in-first-out data type.
Uninformed Search -
Search strategy that uses no problem- specific knowledge.
Informed Search-
Search strategy that uses problem-specific knowledge to find solutions more efficiently.
Greedy best-first search-
Search algorithm that expands the node that is closes to the goal, as estimated by a heuristic function h(n).
A* Search -
search algorithm that expands node with lowest value of g(n) + h(n)
g(n) = cost to reach node
h(n) = estimated cost to goal
optimal if
— h(n) is admissible (never overestimates the true cost), and
— h(n) is consistent (for every node n and successor n’ with step cost c, h(n)_<_h(n’)+c)
Minimax -
- Max(X) aims to maximize score.
- Min (O) aims to minimize score.
Minimax-
- Max(X) aims to maximize score.
- Min (O) aims to minimize score.
Game-
- So: initial state
- PLAYER(s): returns which player to move in state s
- Actions(s): returns legal moves in state s
- RESULT(s, a): returns state after action a taken in state s
- TERMINAL(s): check if state s is a terminal state
- UTILITY(s): Final numerical value for terminal state s
Minimax-
- Give a state s:
- Max PICKS action a in Actions(s) that produces highest value of Min-Value(RESULT(s, a))
- MIN picks action a in ACTIONS(s) that produces smallest value of MAX-VALUE(RESULT(s, a))
DEPTH-LIMITED MINIMAX-
ALPHA-BETA PRUNING-
EVALUATION-FUNCTION—
function that estimates the expected utility of the game from a given state.
