Chapter 1 Search

Some Terminology

  • agent:
    Entity that perceives its environment (is able to perceive something around it) and acts upon that environment in some way.

  • state:
    Just some figuration of the agent in its environment.

  • initial state:
    One such state where we are going to start from, the starting point of search algorithm.

  • actions:
    Choices that can be made in a state.
    We are going to effectively define a function called actions.
    Actions(s) returns the set of all actions that can be executed in state s.
    Only valid in certain states, like s.

  • transition model:
    A description of what state results from performing any applicable action in any state. Focusing on how it is that states and actions are related to each other.
    Define as a function. Result(s, a) returns the state resulting from performing action a in state s. 2 inputs, state s and action a.

  • state space
    The set of all states reachable from the initial state by any sequence of actions.
    Simplified to a directed graph, the nodes represent one of the state and the edges represent the actions we can take in any particular state.

  • goal test
    Way to determine whether a given state is a goal state.

  • path cost
    Numerical cost associated with a given path. Let AI find the minimum path cost.

Graph Searching

  • stack
    A data structure that is last-in first-out.
    Applied in DFS algorithm.

  • queue
    A data structure that is a first-in first-out.
    Applied in BFS(Breadth first searching) algorithm.

Improment

  • uninformed search
    Search strategy that uses no problem-specific knowledge.
    Based on BFS and DFS algorithm, no need to care about where the final destination is.

  • informed search
    Search strategy that uses problem-specific knowledge to find soulutions more effectively.

Improved algorithm on BFS & DFS

  • greedy best-first search (GBFS)
    Search algorithmn that expands the node that is cloest to the goal, as estimated by a heuristic function h(n)
    Why is greedy? It’s only making the best desition, locally.

Manhattan Distance
One specific type od heurstic, only veetically and horizontally allowed, to calculate the distance and comapare.

  • A* search
    Search algorithm that expands node with lowest value of g(n) + h(n)
    h(n) is the estimated cost to goal, equal to that in GBFS.
    g(n) is the cost to reach node, which means how many steps that I have to take in order to get to the current position.

Optimal Only If

  1. h(n) is admissible (never overestimate the true cost)
  2. h(n) is consistent (for every node n, and successor n’ with step cost c, h(n) ≤ h(n’) + c. The distance you except must be shorter than the actual distance, or just equal to the actual distance. In this way we call that h(x) is admissable and optimistic.
  • Minimax (recursive algorithm)
    The situation is defined in a tic-tac-toe game. The final result of the game has been reduced mathematically to just this idea of, try and maximaze the score. X player wants the score be higher, O player wants the score be lower as possible.
    MAX(X) : maximize the score that X will get.
    MIN(O) : minimize the score that O will get.

A Determination of the Game Rules
If O player win the game, the final result of the game is -1, by contrary, the result is 1 if O player win the game; the result will be 0 if neither of 2 players win the game.

Functions

  1. $ S_{0} $: initial state.
  2. PLAYER(s): returns which player to move in state s.
  3. ACTIONS(s): returns legal moves in state s.
  4. RESULTS(s, a): returns stater after actions a taken in state s.
  5. TERMINAL(s): checks if state s is a terminal state.
  6. UTILITY(s): final numerical value for terminal state s.

Given 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)).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
functiuon MAX_VALUE(state):
    if TERMINAL(state):
        return UTILITY(state) 
        # the utility function just knows what the value is
    v = -∞  
    # the value of the state, the initial value is as small as possible
    for action in ACTIONS(state):
        v = MAX(v, MIN_VALUE(RESULT(action, state)))
    return v

function MIN_VALUE(state):
    if TERMINAL(state):
        return UTILITY(state) 
        # the utility function just knows what the value is
    v = ∞  
    # the value of the state, the initial value is as big as possible
    for action in ACTIONS(state):
        v = MIN(v, MIN_VALUE(RESULT(action, state)))
    return v

Figure out what the best move to make is by recursively using these maxValue and minValue, maxValue calls minValue, minValue calls maxValue, back and forth, all the way until we reach a terminal state, at which our algorithm can simply return the utiliyu of that particular state.

  • Alpha-Beta Pruning
    When there is a sub-selection with a lower or higher score than the Alpha-choice appears in the Beta-choice, abandon the exploration of the remaining sub-selection in the Beta-choice. It depends on either you are a value-maximized player or a valur-minimized player.

  • Depth-Limited Minimax
    Minimax algorithm atarts with an initial state, cosiders all the possible actions and all the possible actions after that.

    An added new function

evaluation funtion
Function that estimated the expected utility of the game from a given state.

When there are too many choices to obtain results at an acceptable cost(time or space), then approximately limit the number of depth levels.