Problems and concepts

 1. Problems that can be solved with AI

a) Search - Using AI to search for solutions to a problem. Eg Get driving directions from point A to point B or trying to figure out how to play a game

b) Knowledge- AI to be able to know information to be able to represent that information and draw inferences from that information. To be able to use the information it knows and draw additional conclusions.

c) Uncertainty- Ideas of if a computer is not sure of a fact but may be is sure with a certain probability. How computers can begin to deal with uncertain events in order to be more intelligent in that sense as well. 

d) Optimization- Problems when the computer is trying to optimize for some sort of goal, especially in situation when there might be multiple ways that a computer might solve a problem. But we are looking for a better way or potentially the best way if that's at all possible.

e) Machine Learning- Using data to learn intelligently from that data and learning from experience, being able to perform a task better and better based on greater access to data 

Agent- Entity that perceives an environment and acts on that environment.

State- is the configuration of the agent and its environment.

Initial State- State where the agent begins. Starting point for the search algorithm.

Actions- Choices that can be made in a given state.

Actions(s)- return the set of actions that can be taken in a given state. Eg in the case of puzzle there are 4 possible actions either slide the tile to the left, right, up or down. Its a function that takes as input the state and returns all sets of possible states

Transition Model- A description of what state results from performing any action in any particular state. Its anopther function which takes two inpouts the state and the action

Results(s,a)- returns the resulting state from performing action a in state s.

State Space- The set of all states that can be reached from initial state by performing 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.

Optimal Solution- The solution that has the lowest path cost among all the possible solutions.

Node is a data structure that keeps track of - a state, a parent(node that generated this node), an actions(actions performed on the parent to get to this node), path cost (from the initial state to the node).

Frontier- is a data structure that represents all the options we can explore next that we haven't explored or visited.

Expand Node means to look at all the neighbors of the node.

Approach- 1. start with frontier containing the inital state Loop- 1. If the frontier is empty then no solution. 2. Remove a node from the frontier 3. If the node is the goal state then return the solutions 4. Else expand the node and add the resulting nodes to the frontier.

Revised Approach- 1. Start with a frontier that contains the initial state. 2. Start with an empty explored set. Repeat 1. If the frontier is empty then no solution. 2. Remove a node from the frontier. 3. If node contains the goal state return the solution. 4. Add the node to the explored set. 5. Expand the node, add the resulting nodes to the frontier if they aren't in the frontier or in the explored set. 

Frontier is a data structure and one of the simplest data structures for adding and removing elements is stack. if we use stack approach in frontier we end up with depth first search algorithm.

Depth First Search algorithm- Search algorithm that expands the deepest node in the frontier. It uses stack data structure(last in First out)

Breadth First search- Search algorithm that always expands the shallowest node in the frontier. It uses queue data structure (first in first out)

With Depth first search we might end up not finding a best solution, when a better solution is available.

Depth first search in some cases there might be some memory savings. 

Search Strategies:- Informed search and uninformed search

Uninformed search- Search strategies like Depth First Search (DFS) and Breadth First Search (BFS) that use no problem specific information.

Informed Search- Search strategies that use problem specific knowledge to find solutions more efficiently. 

Number Of Informed search algorithms:-

1. Greedy Best-First search algorithm- Search algorithm that expands the node closest to the goal as estimated by a heuristic function h(n).

Example of Heuritic function in case of maze problem is Manhattan Distance- The distance between two points as measured along axes at right angles. Whenever we have a decision between multiple nodes we could explore lets explore the node which has the smallest value of heuristic h(n)

Heuristic isnt a guarentee. Its an attempt to try and approximate.

One thing to take into consideration is that we need to come up with a good heuristic. How good the heuristic is going to affect how good the algorithm is. And coming up with a good heuristic can be often times challenging. 

Is the Algorithm optimal. Will it always find the shortest path from the initial state to the goal.

Greedy Best first search- If I am in a state right now, the only thing I care about is what is the estimated distance, the heuristic value, between me and the goal.

A star Search- Will take into consideration two pieces of information - how far do I estimate I am from the goal, how far did I have to travel to get here.

A * search algorithm- Algorithm that expands the node with the lowest value of h(n) + g(n)

g(n) = cost to reach the node

h(n) = estimated cost to the goal

A star search is optimal if - 1. h(n) is admissible (never overestimates the true cost), and 2. h(n) is consistent (for every node n and successor n' with step cost c, h(n) <= h(n') + c)

Adversarial search - Sometimes in search situations though, we'll enter an adversarial situation where I am an agent trying to make intelligent decisions, and there is someone else fighting against me, that has an opposite objective, someone where I am trying to succeed someone else that wants me to fail. Games like tic tac toe.

Algorithms for adversarial search 

MiniMax Algorithm- Max(X) Tries to maximise the score

Min(o) tries to minimise the score

Game:-

S0- Initial State

Player(S)- returns which player to move in state s.

Action(s)- returns which are the legal moves in state s.

Result(s,a)- return the resulting state after action a is taken in state s.

Terminal(s)- checks if state s is a terminal state.

Utility(s)- Final numerical value for terminal state(s)

Given a state(s) :-

1. Min- Chooses an action a in actions(s,a) which produces the minimum value of maxValue(Results(s,a))

2. Max- Chooses an action a in Actions(s) which produces the maximum value of min(Results(s,a))

Function Max-value(state):

  if terminal (state):

       return Utility(state)

 v = -∞

for action in Actions(s):

     v = Max(v, Min-value(Results(s,a))

return v

Function Min-Value(s):

       if Terminal(state):

             return utility(state)

v = ∞

for action in actions(s):

     v = min(v, max-value(Results(s,a))

return v

Optimization of MiniMax algorithm is called alpha beta pruning.

Alpha-Beta stands for the two values you will have to keep a track of - the best you can do so far, the worst you can do so far. Pruning is the idea of if I have a big long deep search tree I might be able to search it more efficiently if I dont need to search through everything, If I can remove some of the nodes to try and optimize the way that I look through this entire search space. 

Depth-Limited MiniMax algorithm- After a certain number of moves maybe I will look 10 moves ahead maybe I will look 12 moves ahead but after that I am going to stop and not consider additional moves that might come after that because it would be computationally intractable to consider all the possible actions. But what do we do after we get 10 or 12 moves deep and we arrive at a situation where the game is not over. Minimax needs a way to assign a score to that game to figure out what its current value is which is easy to do if the game is over but not so easy if the game is not over. To do this we add an additional feature to the MinMax algorith called the evaluation function. which is some function which is going to evaluate the expected utility of a game from a give state.