Search

Search

Agent - Entity that perceives its environment and acts upon that environment.

State - A configuration of the agent and its environment.
ie: each state of a puzzle is another state.
Each of these are a state:

Screenshot not attached: Pasted image 20260630221822.png

Initial State - The state in which the agent begins.

Actions - Choices that can be made in a state.
Actions(s) returns the set of actions that can be executed in state s. Actions(puzzle) are 4 actions. They can move in each direction.
Actions in a puzzle:

Screenshot not attached: Pasted image 20260630221858.png

Transition Model - A description of what state results from performing any applicable action in any state.
Results(s, a) returns the state resulting from performing action a in state s.
Transition model in action:

Screenshot not attached: Pasted image 20260630222154.png

State Space - The set of all states reachable from the initial state by any sequence of actions.
Part of a state space of puzzle:

Screenshot not attached: Pasted image 20260630222331.png

Goal Test - Way to determine whether a given state is a goal state.

Path Cost - Numerical cost associated with a given path.
Costs of actions in a state space:

Screenshot not attached: Pasted image 20260630222754.png

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 - in a Search Problem, a data structure taht keeps track of:

  • a state
  • a parent (node that generated this node)
  • an action (action applied to parent to get node)
  • a path cost (from initial state to node)

Approach

  • Start with a frontier that contains the initial state.
  • Repeat:
    • if the frontier if 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.

Stack Based Approach - Last-in first-out data type.

Queue Based Search - First-in first-out data type.

Depth-first Search - Search algorithm that always expands the deepest node in the frontier.

Screenshot not attached: Pasted image 20260630230008.png

Breadth-first Search - Search algorithm that always expands the shallowest node in the frontier.

Screenshot not attached: Pasted image 20260703184441.png

Uninformed Search - Search strategy that uses no problem-specific knowledge. Like DFS BFS.

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 closest to the goal, as estimated by a heuristic function h(n).

Heuristic: Sezgisel. Hızlı karar vermek veya çözüm bulmak için kullanılan, kesin olmayan ama genellikle işe yarayan sezgisel yöntem.

Manhattan Distance - How many distance do I need to take to get from A to B.

Screenshot not attached: Pasted image 20260707022519.png

Numeric values of Manhattan distance of squares:

Screenshot not attached: Pasted image 20260707022603.png

A* Search - (A Star Search) Search algorithm that expands node wit lowest value of g(n) + h(n).
g(n): cost to reach node
h(n): estimated cost to goal

Screenshot not attached: Pasted image 20260707023047.png

Adversarial Search - Making decisions when there is an opponent actively trying to stop you from achieving your goal.

Minimax

Adversarial search algorithm used in two-player, zero-sum games. It chooses the move that gives you the best possible outcome, assuming your opponent always plays optimally.

1 -> O Winning
2 -> No one wins
3 -> O loosing:

Screenshot not attached: Pasted image 20260707024002.png

MAX (X) aims to maximize score.
MIN (O) aims to minimize score.

Game
S 0: intial 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): checks if state s is a terminal state
Utility(s): final numerical value for terminal state s

Instead of looking at each option, if one branch has the least number, stop looking at other actions under that branch. because there's already a better option

Screenshot not attached: Pasted image 20260813132536.png

Alpha-Beta Pruning
Alpha-Beta: the track of the best and the worst you can do.
Pruning: the idea of removing some of the nodes while searching something for optimisation.

Depth-Limited Minimax
After a certain a number of moves I will stop and not consider additional moves.

Evaluation Function
It's easy to evaluate if one choice is good when you see the result. but in depth-limited minimax, you don't see the result. So you need an additional function to evaluate which choice is better.

Back to notebook