AI - Search & Planning

본 포스트는 Stuart Russell 과 Peter Norvig의 Artifical Intelligence : A Modern Approach (4th edition) 의 Search 부분을 다룬다.

시작에 앞서

AI

What is AI?

• AI는 기계를 만들어서 지능적인 행동을 하게 하는 학문
• 지능의 4가지 관점
  • 인간처럼 생각
  • 인간처럼 행동
  • 합리적으로 생각
  • 합리적으로 행동

현대 AI는 대부분 Act rationality (합리적 행동) 기반

AI = Rational Decision (합리적 의사결정)

• 합리적이란?
  • 미리 정해진 목표를 최대한 잘 달성하는 것
• 중요한 개념
  • Utility (효용)
  • Expected Utility (기댓값 기반)
  • Rational = maximize expected utility : 기댓값 기준으로 가장 좋은 선택

What about humans?

• 인간은 합리적으로 행동하려고 함.
• 완벽하지는 않다.
  • 목표는 더 최적화된 의사결정

Agent : 환경을 보고 행동하는 존재

• Input : Percepts (지각)
• Output : Actions (행동)

Rational Agent = expected utility를 최대화하는 행동을 선택하는 시스템

총 3가지의 핵심 분야

• Search & Planning : 지금 상황에서 최적 선택 찾기
• Reinforcement Learning : 경험을 통해 정책 학습
• Supervised Learning : 데이터로부터 학습

AI = 환경을 보고, 행동하며, 기대 효용을 최대화하는 Rational Agent를 만드는 학문

---

Search & Planning

Search

핵심 질문 : 어떻게 최적의 경로/결정을 찾을까?

• Knight 문제 : 최소 이동 횟수
• Maze 문제 : 출구까지 최단 경로

Agent가 최선의 행동을 찾는 방법

• 그냥 움직이는 것이 아니라 미래를 고려해서 계획하는 것

Agent : 목표를 가지고 행동하는 존재

• perception 기반으로 action 선택
• Rational Agent : expected outcome이 가장 좋은 행동 선택

1. Reflex Agent : 현재 상태만 보고 행동하는 Agent

• 현재 perception 기반으로 미래를 고려하지 않는다.
• Rule 기반으로 움직인다.

1. Planning Agent : 미래를 가정하고 행동하는 Agent

• what if? 질문을 한다.
  • 이렇게 하면 어떻게 될까?
• 행동 결과를 미리 시뮬레이션하며, 목표 기반으로 선택

Environment

• Agent는 환경에 따라 난이도가 달라진다.

• Complex environment의 특징

  • Partially Observable : 상태를 완전히 알 수 없음.
  • Stochastic : 결과가 랜덤, 확률적임
  • Multi-agent : 다른 agent가 존재
  • Dynamic : 환경이 계속 변함.

Serach Problem의 6가지 요소

• State Space : 가능한 모든 상태
  • 상태 = 현재 세계 상태의 snapshot
• Start State : 시작 위치
• Goal Test : 목표인지 판단하는 함수
• Actions : 각 상태에서 가능한 행들
• Transition Model : 행동 -> 다음상태
• Cost :행동 비용

World State vs Search State

• World State : 현실의 모든 정보
• Search State : 문제 해결에 필요한 정보만

state를 잘못 정의하게 된다면..

• state가 기하급수적으로 증가하여 모든 경우를 다 보는 것은 불가능

정답 : Action Sequence

• 시작에서 목표까지 가는 경로

State Space Graph

• Search 문제를 그래프로 표현
• 구성
  • Node = 상태 (state)
  • Edge = 행동 (action)
  • Goal = 특정 node 도달
• 왜 전체 graph를 못 만드는가?
  • 필요한 부분만 탐색해야 함. (상태가 너무 많다)

Search Tree

• What if 시뮬레이션 트리
• Node는 상태지만, 사실은 그 상태까지 온 경로를 의미

State Space Graph vs. Search Trees

두 가지의 차이점이 무엇일까?

1. Node

• Graph node = state
• Tree node = plan (path)
  • 같은 상태라도 다른 경로로 도착하면 tree에서는 다른 node이다.

2. Construction

• 둘 다 너무 커서 전체적인 생성이 불가능하다.
  • on-demand 생성
• cycle이 있으면 tree는 무한 확장이 가능하다.
  • 같은 상태가 계속 반복되므로 비효율적이다.

3. Algorithms

• 실제 알고리즘은 Search Tree 기반
  • 알고리즘 구현이 쉽다.
  • 경로 기반의 판단이 가능하다.
  • 각 node = 하나의 계획이다.

Tree Search

Frontier

• 아직 확장되지 않은 노드들의 집합
  • 현재 가능한 다음 선택지들로 알고리즘이 선택할 대상
• Search Process
  • 시작 상태에서 시작
  • frontier를 유지
  • 하나 선택하여 확장

General Tree Search

frontier ← initial state 넣기

while frontier not empty:
    node ← POP(frontier)
    
    if goal이면 return
    
    children ← EXPAND(node)
    frontier에 추가

EXPAND 함수

for action in ACTIONS:
    s' = RESULT(s, action)

즉, 탐색 알고리즘의 차이로 frontier를 선택하는 방식에 따라 다르다.

Tree Search는 frontier에서 무엇을 선택하느냐가 전부다.

Depth-First Search (DFS)

DFS = 끝까지 파고 들어가기

• 위에서 시작해서한 방향으로 계속 내려간다.
• 막히면 다시 올라옴 (backtracking)
• Stack (Last-In First-Out) 사용
  • 가장 최근에 넣은 노드를 통해 가장 먼저 탐색

DFS 특징

b = branching factor (자식 수)
m = 최대 depth

- 전체 노드 수
1 + b + b² + ... + b^m ≈ O(b^m)

• Time Complexity : O(b^m)
  • 최악 : 끝까지 다 탐색
  • 깊이가 깊으면 매우 크다.
• Space Complexity : O(bm)
  • 경로가 하나 + 형제 노드만 저장한다
  • BFS보다 훨씬 적게 사용한다.
• Complete 여부 : X
  • depth가 무한이면 끝까지 갈 수 없다.
  • cycle이 있으면 무한 루프를 가진다.
  • 다만 cycle을 방지할 수 있으면 가능하다.
• Optimal 여부 : X
  • 가장 먼처 찾은 해를 반환
  • 최소 비용이라는 보장이 없다.

요약 :

DFS = “가장 깊은 노드부터 탐색하는 stack 기반 탐색”

Breadth-First Search (BFS)

BFS = shallowest frontier node 먼저 선택

• 가장 얕은 노드부터 탐색
• Queue (First-In First-Out) 사용
  • 먼저 들어온 노드부터 먼저 탐색하고, 자연스럽게 shallow 노드부터 처리 가능

BFS 특징

• Time Complexity : O(b^s)
  • DFS 보다 보통 빠르다
• Space Complexity : O(b^s)
  • frontier에 마지막 레벨이 다 쌓인다.
  • 메모리를 많이 사용 (단점)
• Complete 여부 : O
  • (조건) s가 유한하면 무조건 찾는다.
• Optimal 여부 : O
  • (조건) edge cost 가 1일 때

DFS vs BFS

BFS가 더 좋은 경우

• shallow solution (해가 가까울 때)
• 최단 경로가 필요
• complete 필요

DFS가 좋은 경우

• 메모리 제한
• 깊은 해 가능성
• 빠르게 아무해나 찾을 때

Iterative Deepening : DFS + BFS

• DFS는 메모리가 적고, BFS는 shallow solution을 찾는다.
• 중복 탐색 문제 : 대부분 노드는 마지막 레벨에 존재해서 overhead가 적다.

Uniform Cost Search (UCS)

Cost-Senstivie Search

• BFS는 최단 경로가 아니다.
  • Action 수를 기준으로 하기에 cost에 대한 고려가 X

UCS = cheapest node를 먼저 선택

• 지금까지이 누적 비용이 가장 작은 노드부터 확장
• 비용이 낮은 영역부터 퍼져나간다. (동심원처럼 확장 느낌)
• Priority Queue 사용
  • 기준 : cumulative cost g(n)
  • 보통 Binary Heap 사용

priority queue에 start 넣기 (cost=0)

while:
  가장 cost 작은 node pop
  goal이면 return
  아니면 expand → push

UCS 특징

• 노드 확장 : 최적해보다 cost가 작은 모든 노드

• effective path \(\text{depth} ≈ \frac{C^*}{\epsilon}\)

  • C* = optimal solution cost
  • ε = 최소 edge cost
• Time Complexity : O(b^(C/ε))
• Space Complexity : O(b^(C/ε))
  • BFS처럼 크다.
• Complete 여부 : O
  • (조건) cost finite + 음수가 아닌 경우
• Optimal 여부 : O

Uninformed Search

• 모든 방향을 탐색 X, goal의 위치 정보가 없다.
• 즉 UCS는 맹목적이지만 정확한 탐색이다.

BFS / DFS / UCS 는 다 같은 알고리즘이다.

• 차이점은 frontier 선택 기준만 다르다.
• 구현 관점 : 전부 priority queue로 가능

Search 는 현실이 아니라 모델 위에서 수행

• 실제 행동이 아니고, 시뮬레이션 내부 탐색
• 모델이 구리면 결과가 구리다.

---

Informed Search

Pancake Problem

• State : 팬케이크가 쌓인 상태
• Action : 위에서 k개 뒤집기
• Cost : 뒤집은 개수
• Goal : 크기 순으로 정렬

-> 최소 flip으로 정렬하려면? : Search 문제

UCS의 장단점

• 장점 : Complete, Optimal
• 단점 : 방향성이 없다.모든 방향을 탐색한다. (Uninformed Search)

Informed Search

• BFS/DFS/UCS는 goal의 위치를 모른다.
  • 만약 조금이라도 방향 정보가 있다면?
• goal에 얼마나 가까운지를 알려주는 정보

Heuristics

h(x) : 현재 상태가 goal에 얼마나 가까운지 추정하는 함수

• goal까지 남은 거리 (estimate)
• 정확한 값이 없어서 문제마다 다르다.
• 예시) Manhattan distance, Euclidean distance
• 추정 값 : 실제 경로 != 직선 거리, 다만 좋은 근사값

Pancake Heuristic 적용

• 제자리에 있지 않은 가장 큰 pancake 크기
  • 큰 팬케이크가 틀려 있으면 최소한 그만큼은 뒤집어야 함.

Greedy Search

핵심 아이디어 : 지금 당장 제일 좋아 보이는 방향으로 가자

• 현재 기준에서 가장 가까운 것을 선택
• 미래를 고려하지 않고, 현재의 휴리스틱만 사용
  • 비용 (g) 무시, 오직 h(x) 만 본다.
• 알고리즘 : frontier 중에서 h(x)가 최소인 노드 선택
  • 장점 : 빠르고, goal 방향으로 직진한다.
  • 단점 : 최적해 보장 X, 길이 막히면 돌아가기에 잘못된 방향도 가능
    • 최악의 상황 : Bad DFS처럼 행동

A* Search

• UCS : 느리지만 정확
• Greedy : 빠르지만 들릴 수 있다.
• A* Search : 빠르면서 정확 (UCS + Greedy)

두 가지 지표 : f(n) = g(n) + h(n)

• g(n) : 지금까지 온 비용 (real cost)
• h(n) : 앞으로 남은 비용 (estimate)

두 지표 다 각각 보면 불완전

• 선택 기준 : frontier 에서 f(n)이 최소인 노드 선택

• Goal을 발견하면 끝인건가?
  • NO : dequeue 시에 종료
  • 더 좋은 경로가 뒤에 있을 수도 있다.
• 문제상황 : bad path 실제 비용 < good path 추정 비용
  • 결과 : 잘못된 경로 선택
  • 해결 방법 : h(n) ≤ 실제 cost

Admissible Heuristics

• Inadmissible (비관적) : 실제 비용보다 크게 추정
  • h(n) > 실제 비용
  • 좋은 경로를 과대평가하여 탐색에서 밀려남
  • 최적해를 놓침
• Admissible (낙관적) : 실제 비용보다 작거나 같게 추정
  • h(n) ≤ 실제 비용

A* Serach는 admissible heuristic일 때 optimal

• 0 ≤ h(n) ≤ h*(n)
  • h(n) : 우리가 추정한 비용
  • h*(n) : 실제 최단 거리

Optimality Theorem

• admissible 하면 A* Search 는 항상 Optimal
  • 이유 : 틀린 길을 더 좋아보이게 만들지 않는다.
  • H(n) = 0 이여도 admissible 한 것이다.

Proof

목표 : n이 A보다 먼저 선택 \(f(n) = g(n) + h(n)\)

• admissible 사용 \(h(n) ≤ h*(n)\)

  \[f(n) ≤ g(n) + h*(n)\]
  • g(n) + h*(n) : n에서 goal까지 실제 최적 비용
    • 이 값은 A로 가는 비용과 같다.

A = Optimal Goal

B = SubOptimal Goal \(g(A) < g(B)\)

• Heuristic \(h(A) = h(B) = 0\)

  \[f(A) < f(B)\]

• admissible -> f(n)이 실제보다 작다. -> 최적 경로가 항상 먼저 선택

Designing Heuristics

A* Search 를 잘 쓰기 위해서는 admissible heuristic을 잘 만들어야 한다.

어떻게 만들까?

\[0 ≤ h(n) ≤ h*(n)\]

• Lower bound : 남은 비용의 최소 하한선
• Relaxed problem : 원래 문제에서 제약을 일부 없앤 더 쉬운 문제

예시) 8-puzzle example

• UCS로 해결
  • goal의 방향을 모르고, cost가 작은 순서대로 전부 퍼져 나가기에
  • Optimal 하긴 하지만, 굉장히 느리다.

1. misplaced tiles

• 제자리에 있지 않은 타일 개수
  • 타일 하나가 제자리에 없으면 최소한 적어도 한 번은 움직여야 함.
  • 잘못된 타일 수는 실제 필요한 이동 횟수보다 절대 클 수 없다.

1. Manhattan Distance

• 각 타일이 goal 위치까지 가려면 상하좌우로 몇 번 움직여야 하는지 모두 더한 값
  • 대각선 이동이 안되기 때문에 더 자연스러움.
  • Misplaced : 틀렸나.? 맞았나? 만 반영
  • Manhattan은 얼마나 멀리 틀렸는지를 반영하기에 정보량이 더 많다.

1. True Cost

• 그냥 진짜 남은 최적 비용 h*(x)를 heuristic으로 사용하기
  • admissible : 실제 비용과 같으니까 당연히 yes
  • 노드 확장 수 : 거의 최고 수준으로 줄어든다.
  • 왜 안쓰는가?
    • true cost를 알기 위해서 이미 문제를 풀어야 한다.

요약

• 좋은 휴리스틱은 실제 최적 비용에 가깝지만, 그보다 훨씬 싸게 계산할 수 있어야 한다.

좋은 Heuristic

Heuristic 이 true cost에 가까울수록 확장하는 노드는 줄어들지만, 계산 자체는 더 비싸진다.

• 품질이 낮은 경우
  • 계산은 매우 빠르지만 정보량이 적어서 노드를 많이 확장해야 함.
• 품질이 높은 경우
  • goal의 방향을 더 정확히 알려주고, 쓸데없는 상태를 덜 탐색함.
  • 노드 확장수가 크게 줄어들지만, h(n) 계산하는 비용이 커짐

Graph Search

왜 Tree Search는 비효율적일까?

• 같은 state가 search tree에서는 여러 번 나타날 수 있다.
  • 같은 계산을 반복, 또 만들고, 탐색량이 기하 급수적으로 커짐
• repeated node는 굳이 다시 확장할 필요가 없다.
  • 한 번만 확장하도록 막기 : graph search

A* Grpah Search : 같은 상태를 두 번 확장하지 말자

• expanded nodes 의 집합 closed set을 추가하기
  • frontier에서 노드 하나를 꺼냄.
  • 그 노드의 state가 예전에 이미 확장된 적 있는지 확인
  • 이미 확장했으면 건너 뜀
  • 처음 보는 state면 확장하고 closed set에 넣음
• 같은 state를 한 번 봤으면 무조건 다시 안 본다는 것은 안전하지 않음
  • 같은 state여도 더 싼 cost로 나중에 다시 도달 가능
  • Closed set 추적과, 각 state까지의 최소 cost도 같이 기록해야 함.
  • Dictionary 사용

reached = an empty dict mapping nodes to the cost to each one

• 노드를 pop 했을 때
  • 그 state가 처음이면 저장
  • 이미 있었더라도 지금 cost가 더 싸면 갱신
  • 지금 cost가 더 비싸면 버림

Consistency of Heuristics

• f-value가 경로를 따라 감소할 수도 있다.
  • 부모 state를 비싼 값으로 먼저 닫아버렸는데, 나중에 자식을 따라 더 싼 방향이 발견
  • Consistency 문제

1 admissibility \(h(A) ≤ actual cost from A to goal\)

• 한 상태에서 goal까지의 실제 비용보다 heuristic이 크지 않으면 된다.

2. consistency \(h(A) - h(C) ≤ cost(A to C)\)

\[h(A) ≤ cost(A,C) + h(C)\]

• A에서 Goal까지의 추정치는
  • A에서 C로 가는 실제 비용 + C에서 Goal까지의 추정치보다 크면 안된다.
• 인접한 상태끼리도 heuristic이 부드럽게 변화해야 한다. (stronger condition)

---

Adversarial Search

게임은 여러 가지 기준으로 나눌 수 있다.

• 결과가 Deterministic vs Stochastic
• 플레이어 수가 1, 2, N..?
• Zero-sum vs Non-zero-sum?
  • 무엇이든 strategy (=policy) 찾기가 중요

Deterministic Game Formalization

• States : S : 모든 가능한 게임 상태
• Players : P = {1, 2, ..., N}
  • 보통 번갈아가면서 (turn-based) 게임을 진행
• Actions : 상태마다 가능한 행동
• Transitions : 행동하면서 다음 상태로 이동
• Utility : 결과 상태의 점수
  • 승리 + 1 / 패배 - 1/ 무승부 0
• Goal Test : 끝났나?

Zero-Sum Games

• 한쪽 이득 = 다른쪽 손해
  • MAX : 점수 최대화
  • MIN : 점수 최소화

Game Tree

• 구조
  • 현재 상태 -> 가능한 모든 행동 -> 상대 행동 -> 반복 … -> Terminal State
• 레벨마다 플레이어가 바뀐다.
• MAX는 어떤 선택을 해야 하는가?
  • 그냥 좋은 것을 고르면 안된다.
  • 왜? : 상대 (MIN)가 있기 때문
    • 상대는 항상 나를 망치려는 선택을 함.

Single-Agent Trees

• Pacman이 혼자 있다고 가정
  • Utility : 펠렛 하나 먹기 : + 10 / 한번 움직일 때마다 : -1
  • 빨리 펠릿을 먹을 수록 좋다.
• 상대가 없음
  • 내가 원하는 방향으로만 최적 선택

• V(s) : 현재 상태 s에서 출발해서 앞으로 잘 선택했을 때 얻을 수 있는 최고의 점수

  • Terminal State에서의 value : 그냥 주어짐 \(V(s) = \max_{s' \in children(s)} V(s')\)

    • Non-terminal State : 자식 상태들 중 하나 선택 가능

Adversarial Game Trees

• 내가 가고 싶은 길만 볼 수 없다.
  • 내가 어떤 선택을 해도, 그 다음에는 상대가 나한테 불리한 쪽으로 움직일 수 있다.
• 최종 결과를 내가 혼자 결정 X
• value 계산이 max/min이 번갈아가며 올라오는 구조

1. 내 차례(Agent’s Control) \(V(s) = \max_{s' \in successors(s)} V(s')\)

• 내가 움직일 수 있는 상태라면 가능한 다음 상태들 중 가장 value가 큰 상태를 고른다.
  • 내 목표는 내 utility를 최대화하는 것이 목적

2. 상대 차례(Opponent’s control) \(V(s') = \min_{s \in successors(s')} V(s)\)

• 상대가 움직이는 상태에서는 상대는 내 utility를 최소화하려고 하므로 자식들 중 가장 작은 value를 고른다.

Minimax Search

Minimax = 상대가 최적으로 행동한다고 가정하고, 내가 확보할 수 있는 최선의 결과를 계산하는 방법

• Deterministic, Zero-sum, Turn-based 게임이라고 가정
• 나는 maximize, 상대는 minimize
• leaf 값에서 시작해서 min/max를 번갈아 적용하며 위로 올라간다.
• 시간 복잡도 : Time = O(b^m)
  • b : branching factor (자식 수)
  • m : depth (트리 길이)
• 공간 복잡도 : Space = O(bm)
  • DFS 기반

1. Max-value

def max_value(state):
    v = -∞
    for successor:
        v = max(v, min_value(successor))
    return v

• 내 차례니까 최대값 선택
• 다음은 상대 차례 -> min-value 호출

2. Min-value

def min_value(state):
    v = +∞
    for successor:
        v = min(v, max_value(successor))
    return v

• 상대 차례니까 최소값 선택
• 다음은 내 차례 -> max-value 호출

3. 전체 흐름

def value(state):
    if terminal:
        return utility

    if MAX turn:
        return max_value(state)

    if MIN turn:
        return min_value(state)

• 종료 상태이면 -> 값 반환
• 내 턴이면 -> max
• 상대 턴이면 -> min

Alpha-Beta Pruning

Minimax Pruning : 굳이 다 계산할 필요가 없다. 이미 답이 정해진 가지는 버린다.

• α (alpha) : MAX가 지금까지 확보한 최소 보장값

• β (beta) : MIN이 지금까지 확보한 최대 허용값

• Purning 조건
  • MIN 노드 : value ≤ α → STOP 이면 더 볼 필요가 없다.
  • MAX 노드 : value ≥ β → STOP 이면 더 볼 필요가 없다.
• α ≥ β 되면 → pruning 발생

max-value

def max_value(state, α, β):
    v = -∞
    for s in successors:
        v = max(v, value(s, α, β))
        if v ≥ β:
            return v   # pruning
        α = max(α, v)
    return v

min-value

def min_value(state, α, β):
    v = +∞
    for s in successors:
        v = min(v, value(s, α, β))
        if v ≤ α:
            return v   # pruning
        β = min(β, v)
    return v

Properties

• 결과는 동일 : Alpha-beta 해도 결과는 minimax와 같다.
• 중간 값은 틀릴 수 있다. (루트 값만 중요하기에 괜찮다.)
• ordering이 중요 : 좋은 순서로 탐색하면 pruning이 많이 된다.

하지만 Pruning으로는 여전히 너무 느리다.

Pruning은 조금 줄여주는 것 : 근본 해결 방법은 아니다.

Depth-limited Search

끝까지 가지 말고, 중간까지만 보자

• 기존 minimax : lear까지 가서 실제 승/패 값 사용
• 변경된 방식 : depth k까지만 탐색하고, 그 아래는 추정값을 사용

Evaluation Function

• non-terminal state의 “좋은 정도”를 추정하는 함수
• 이상적인 경우
  • Eval(s) = 실제 minimax 값
• 실제 방법
  • Eval(s) = w1 f1(s) + w2 f2(s) + ... + wn fn(s)
  • feature 기반 점수
• Evaluation Function은 항상 틀릴 수 있다.
  • 미래를 완전히 못보기 때문
  • 얕은 탐색이면 root -> eval함수에 100% 의존
• Trade-off
  • 좋은 evaluation function : 정확하지만 계산이 느리다.
  • 깊은 탐색 : 정확하지만 계산이 느리다.

언제 우리가 Minimax를 사용할까?

• 상대가 완벽한 플레이어일 때
  • 가정 : 상대는 항상 최선의 선택을 한다.
• 현실에서는
  • 사람은 완벽하지 않다. (실제보다는 보수적인 선택)

Expectimax Search

왜 결과를 정확히 모를까?

• 명시적 랜덤성 : 환경 자체가 랜덤
• 상대가 꼭 최적으로 행동하지 않는다.
  • 실수, 무작위 움직임, 예측 불가능
• 행동 자체가 noisy : 같은 action이라도 결과가 하나로 고정되지 않을 수 있다.

expectimax : 여러 결과가 확률적으로 발생

• 각각의 결과를 확률 가중 평균해서 계산한다.
• Expectimax = 내가 최적으로 행동할 때 얻는 기대 점수를 계산하는 검색
  • MAX node : 자식 중 최댓값 선택
  • CHANCE node : 자식들의 확률 가중 평균 계산
• Pseudocode
  • 전체 구조

def value(state):
    if terminal: return utility
    if MAX turn: return max-value(state)
    if EXP turn: return exp-value(state)

• terminal state : utility를 그대로 반환

• 내 차례면 : max-value (minimax의 MAX와 동일)

• 확률 노드면 : exp-value

  • exp-value 코드

  for each successor:
      p = probability(successor)
      v += p * value(successor)
  return v
  

  • successor의 value를 구한 다음에 그것에 확률을 곱해서 모두 더함.
• Expectimax의 Purning : 거의 불가능
  • 모든 자식이 평균 계산에 필요하기에 하나라도 안보면 기댓값이 틀리다.
• Depth-Limited Expectimax
  • 계산량이 너무 크다.
  • Depth 제한 + evaluation function을 사용
    • 어느 깊이까지만 탐색하고, 그 아래는 evaluation function으로 근사
• Optimism vs Pessimism
  • Dangerous Optimism (낙관)
    • 실제로는 적대적인데 랜덤이라고 가정
    • 상대가 공격적으로 나오면 망한다.
  • Dangerous Pessimism (비관)
    • 실제로는 랜덤인데 최악만 가정
    • 성능이 저하된다.

즉, 문제 환경에 맞는 모델 선택이 필요

Other Games

• Multi-player game : 각자 자기의 utility를 maximize 하는 minimax 확장

Utility

• 결과를 숫자로 바꾸는 함수
  • 같은 결과라도 사람마다 utility가 다르다.
• Maximum Expected Utility (MEU)
  • 합리적인 에이전트는 기대 utility를 최대화해야 한다.
  • U([p1, s1; ...; pn, sn]) = Σ pi * U(si)
  • 확률적 상황에서는 가장 좋은 결과가 아닌 기댓값이 가장 큰 선택을 해야 함.
• Utility는 선형이 아니다.
  • 예) 인간은 합리적인가? Allais Paradox
  • 사람은 상황에 따라 기준이 바뀜
• 인간은 rational 하지 않다.
  • 불확실성을 구조적으로 모델링이 필요 -> (Markov Decision Process)
  • MDP = 연속적인 의사결정

---

Markov Decision Processes