0. Search

August 17, 2020

Maze -> 길찾기

Using Stack => DFS (찾기만!)

Using Queue => BFS

갈래길 => DFS 끝까지, BFS

BFS -> leads us to optimal Solution

단점 : 너무 오래걸린다

Greedy Best-First Search

-> search algorithm that expands the node that is closest to the goal, as estimated by a heuristic function h(n)

=> Not guaranteed!

A* search

-> search algorithm that expands nodes with lowest value of g(n) + h(n)

g(n) = cost to reach node

h(n) = estimated cost to goal

A* search can find optimal search algorithm which can find a solution

A* search is optimal if

h(n) is admissible (never overestimates the free cost), and
h(n) is consistent(for every node n and successor n' with step cost c, h(n) <= h(n') + c)

Adversarial Search - Adversary

win -> 1

draw -> 0

lose -> -1

MINIMAX

for Tic-Tac-Toe

MAX(X) aims to maximize score

MIN(O) aims to minimize score

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))

pseudocode for MAX-VALUE (similar for MIN-VALUE)

function MAX-VALUE(state):

if TERMINAL(state):

return UTILITY(state)

v = -inf

for action in ACTIONS(state):

v = MAX(u, MIN-VALUE(RESULT(state, action))

return v

Alpha beta pruning (thinking of the opponent’s move also)

-> can save a lot of time

-> but not enough! (too much memory needed)

3- 1- 2

12 23

Alpha-beta pruning

=> 단점 : 너무 오래걸린다

Depth Limited Minimax -> will estimate after some moves

-> function that estimates the expected utility of the game from a given state