[인공지능 : AI, Artificial Intelligence] Lecture 9 : Adversarial Search 1

Lecture 9

'Problem Solving, PS란 무엇인가?'에 대한 답변

• Problem Solving이란 무엇인가? = initial state에서 goal state까지 찾아가는 과정 혹은 순서(sequence of action)를 찾는 것.

  • State, Action, Goal로 구성되어있으며, Action을 통해서 Goal에 도달하는 방법을 찾는 것을 Problem Solving이라고 한다.
  • AI Agent가 reach a goal하는 것을 Problem Solving이라고 한다.
  • 다만 Local Search는 path가 아니라 optimal Goal만을 찾을 뿐인 것이다.

• Problem

  • 현재상태 to 목표상태까지의 gap이 있는 것

• Problem solving solution

  • 목표상태까지 가는 a sequence of action (path)
  • solution in a given situation

• Search

  • 일반적으로 컴퓨터과학에서 말하는 PS는 원하는 Goal에 도달하거나, solution을 찾는 것을 의미한다.
    • 주로 인공지능 분야. algorithm, heuristic, root casue analysis등을 통해서 해낸다.
    • to a single problem, many solution or heuristic
    • PS를 하는 알고리즘을 Search Algorithm이라고 하는 것이다.

• PS의 순서

  • define problem
  • possible solution 확인
  • optimal solution choosing
  • implementation

• path를 찾는 것도 local로 적용가능하다.

  • 각 node를 state가 아니라 path로 둔다면, 최적의 path를 찾을 수 있다.

• 인공지능에서의 Problem Solving은 결국 goal based agent를 둔 상태로 진행되며, 이는 두가지로 나뉜다.

  • problem solving agent
  • planning agent

Adversarial Search

uninformed and informed search

• goal까지 가는 경로를 빠르게 찾는 것.
• 문제해결을 Search로 시도.
• sequence of action을 찾는다.
• Heuristic function을 쓴다. A*가 대표적이다.

local search

• optimization 문제를 search로 해결하려고 시도.
• optimal goal state를 찾는 것이 목적이다.
• objective function을 둔다.
• hill Climbing, Stochastic Annealing, Genetic Algorithm, Local Beam Search 등이 있다.

Adversarial Search(Game Search)

• Agent가 서로 경쟁할 때, 즉, MultiAgent 일 때, 그리고 상대 Agent를 제어할 수 없는 상황에 사용한다.
• search problem으로 모델링한다.
• optimal solution이 seq of action이 아니라, policy(strategy)이다.
• uncertainty가 있다.
• utility를 사용한다. (heuristic한)evaluation score라는 추정치를 사용할 수도 있다.
• MinMax, 몬테칼로, 강화학습 등이 있다.

언제 adversarial search를 사용하는가?

현재의 state에서 전방으로 몇칸 더 나가서 어떤 action이 더 유리한 지 확인할 수도 있다... 그러려고 하는데 문제는 상대방이 어디에 두는지 알 수가 없다는 것이다. 또한, 게임에 따라서 발생하는 랜덤성이 존재할 때 또 문제다. 이건 예측 불가한 문제이다.

이런 경우가 adversarial search를 하는 상황이다.

해결법 두가지

1. 상대방이 어디에 둘지 모르니깐, 상대방도 나랑 같다고 가정. 같은 heuristic, strategy : minmax
2. 상대방이 진짜 랜덤이라면... non deteministic

Game에 대한 Typical한 정의

Game의 종류를 다음과 같이 분류한다.

• 2명이 교대로 행동한다.
• zero sum. 한 명의 손해가 다른 한명에게는 이득이ㅏ.
• perfect information : State에 대한 정보가 두 명에게 모두 공유되어야한다.
• No Chance : 확률적인 것은 없다.

Zero Sum Game

Agent는 outcome에 대해서 각기 다른 value를 지닌다. 한 Agent가 하나의 value를 최대화하면, 다른 Agent가 그 value를 최소화한다.
Agent의 각 move는 ply라고 정의한다.

Embedded Thinking (Backward Reasoning)

두 Agent가 서로에 대해서 어떤 행동을 하고 이를 어떻게 대응할지 몇 수 앞을 내다보는 것을 의미.

Formalization

여러 formalization이 있지만, 대표적으로 이런 방법이 있다.

• States: S (start at s0)
  • initial State
• Players: P={1...N} (usually take turns)
• Actions: A (may depend on player / state)
• Transition Function: SxA -> S
• Terminal Test: S -> {t,f}
• Utilities: SxP -> R, 이기면 1, 지면 -1, 비기면 0. 혹은 1, -1, 1/2로 쓸 수도 있다.
  Solution for a player is a policy: S-> A

예시 : NIM게임

더 이상 나눠질 때가 없을 떄까지 계속해서 나누는 게임
같은 숫자 안됨
전체 트리는 아래와 같다.

각 leaf에서 +1 -1 적는다.
내 것은 max, 상대는 min으로 만들려고 하는 것이 목적이다.

여기서 terminal node를 보고, 이를 기준으로 root방향으로 두 Agent의 차례에 맞게 max 혹은 min으로 올리면, 다음 그림과 같다.

다음 노드를 선택할 때, 나는 평가함수가 최대(max)인쪽으로 선택하려 할 것이며, 상대방은 나의 평가함수가 최소(min)인쪽으로 선택하려 할 것이다.
따라서 path 를 선택할 때에는 이러한 Min 과 Max 를 번갈아 가며 진행하게 된다.
위의 그림에서 각 level 별로 min 과 max 를 정하여 놓고, 목표점(즉, 내가 이기는 leaf node)에서부터 위로 올라가면서 min 혹은 max 에 따라 올라가서 path 를 정하게 되며, 이 path 가 목표점으로 가는 제일 좋은 path 라고 결정하는 것이다.
위의 그림에서 굵은 선으로 표시된 path 가 내가 이길 수 있는 path, 즉 2-2-1-1-1 을 상대방에게 제시하게 되는 path 가 된다. 점선표시는 내가 지게 되는 path 를 나타낸다.

위의 방법론의 문제점

하지만 이 방법에는 문제가 있다.
state가 너무 많으면 못그린다.
전체 tree를 다 그려야해서 그렇다.

그래서 local Tree와같은 방법을 채택한다. subtree의 terminal node의 값을 추정을 한다.
물론 이런 방법을 선택하면 complete나 optimal은 안된다.
전체 tree를 그려야 compete optimal이 가능하다.

상대턴이 끝날 때마다 새로운 tree를 만들어서 다음 state를 분석한다.

예시 : 틱택토 게임에서의 full tree MinMax

subtree의 추정치에 대해서도 같은 원리로 계산한다.

즉, 다음과 같은 방식으로 Maximum Utility를 구한다는 것이다.

• 게임 트리에 대해서 DFS
• optimal leaf node는 어떠한 depth에서도 발생 가능하다.
• MinMax principle : 두 Agent가 모두 optimal하게 play한다는 가정
• terminal node가 발견되면, 다시 위로 propagate해서 Maximum policy를 찾는다.
  • Compute Each node's minimax value : optimal한 상대를 두고 최대의 utility를 얻는다.

MinMax는 다음과 같이 구현할 수 있다.

pseudo code를 이렇게 쓰기도 한다.

전체 트리가 없을 때 최선의 방법 고르는 법

full size Tree는 complexity때문에 못만든다.
틱택토만해도 장난 아니다.
방식이 DFS니깐 DFS time space로 계산하게 되기 때문에 시간복잡도가 매우 커진다.

Optimal, Complete
시간복잡도 : O(b^m)
공간복잡도 : O(bm)

전체 utility를 알 수는 없으니까, utility를 추정하는 방법을 evaluation function이라고 한다.

앞서말한 것 처럼 subtree를 만들어서 DFS를 통해서 evaluation function으로 Adversarial Search를 한다.
이런 방식의 DFS를 Depth limited search라고도 한다.

1. replace utitity with evaluation function
2. IDS(iterative deepening search)사용 : partial search라고도 한다.
3. pruning : large part of the tree 제거

틱택토의 경우, 다음과 같이 evalutation을 정의한다.

이 그림에서 나는 X 이고 상대방은 O 이다. 평가함수는 나의 winning line 이 가장 크고, 상대방의 winning line 이 가장 적게 하고자 하는 것이 목표이다. 위의 그림에서처럼 E(n)=M(n)-O(n)으로 정의를 하면, 나는 E(n)값이 max 가 되게, 상대방은 min 이 되게 진행을 할 것이다.

이렇게 해서 만들어진 partial tree 와 그 partial tree 의 terminal nodes 가 evaluation function에 의해 추정된 utility values 를 가지고 있다.

아래 그림과 같이 추상적으로 partial tree를 만들어서 evaluation function을 각 node 별로 매기고, 이에 대해 minmax 알고리즘을 적용하면, root에서는 3을 따라가는 결과가 나온다.

내다보는 수가 많으면 많을수록, 이길 확률이 높아지게 되는 것은 당연할 것이다. 처음에 이야기 했던 NIM 게임의 전체 tree 처럼, complete 한 full tree 를 만들어서 minmax tree 를 만든다면 이길 확률이 매우 높아지게 된다. 하지만, full tree 를 만들어 그 모든 경우를 계산하는 것은, 게임의 search space 가 조금만 커지게 되어도 computational complexity 가 높아지게 되어 정해진 시간 안에 계산을 마치는 것이 불가능 하게 될 수가 있다.

위 그림과 같이 n-ply를 여러번 반복하여 optimal solution을 추정할 수도 있다.

---

Heuristic function과는 다르게 evaluation 함수는 주로 상대방과 나의 차이를 이용해서 정의한다.
이런 특성 때문에 Adversarial이라고 하는 것이다.
이렇게 정의하는 이유는 utility값을 추정해야하기 때문이다. (utility는 zero-sum이니까)

예시 : 체스_딥블루

체스같은 경우, evaluation function을 다음과 같이 정의 할 수 있다.

feature가 6000개.
이런 feature는 heuristic을 기반으로 만들었다.

다음 시간은 Alpha Beta Pruning.