의사 결정 - Decision Tree

Decision Tree

---

Decision Tree는 Decision Making 구현법 중 하나이다. 빠르고, 쉽게 구현 가능하고 이해하기 쉽다는 장점을 가지고 있다.

 

Decision Tree

 

위 트리에서 Leaf 노드는 실행할 액션(output)이 된다.

 

input이 어떻게 들어오느냐에 따라 매우 민감하게 output이 바뀔 수 있기 때문에 주의가 필요하다.

 

 

AND/OR

Decision Tree내에서 AND/OR을 구현하는 것은 쉽다. 아래의 그림을 보자

 

 

 

 

 

Branching

Deep Binary Decision Tree

 Flat Decision Tree

 

위 그림처럼 Decision Tree에서 3개 이상의 Branch를 사용할 수 있는데, 2개의 branch만 사용하는 구조에 비해서 더 빨리 output을 찾을 수 있다는 장점이 있다.

 

그럼에도 불구하고 보통은 2개의 브랜치만 사용한다. 그 이유는 다음과 같다.

 

1. 2개만 사용해도 작동 방식은 비슷하고 속도도 크게 차이 안 난다.
2. 학습 알고리즘들이 보통 2개의 브랜치를 사용하는 구조를 대상으로 한다.
3. 2개만 있는 더 간단히 구현 가능하고 툴을 만들기도 쉽다.

 

 

데이터 접근

보통 Decision Tree는 Global Game State에 직접 접근한다. 또한 자주 사용되지 않는 Action의 경우 버그를 찾기 힘들다는 단점이 있다. 그래서 Global Game State가 바뀌면 예상하지 못한 버그가 튀어나올 수 있다. 따라서 State에 대한 접근에 신경을 써주어야 한다.

 

 

 

Balancing

Decision Tree도 Tree이므로 Balance에 따라 성능이 갈릴 수 있다.

 

Unbalanced Decision Tree

 

Balanced Decision Tree

 

Decision Tree의 밸런싱에서 주의할 점은, 밸런스가 좋다고 해서 꼭 성능이 좋을 것이란 보장이 없다는 점이다. Decision Tree에서는 대부분의 경우 몇몇 Output에만 도달하는데 이렇게 자주 도달하는 Action이 Root 노드에 가까워야 성능이 좋다. 예를 들어 위 그림에서 대부분 Idle 상태에 있는 AI의 경우 Unbalanced 한 구조에서 더 빠르다.

 

 

Random

Decision Tree에서는 AI의 행동이 너무 단순하고 예상하기 쉽다는 단점이 있다. 이런 부분을 어느 정도 해소해주기 위해 Random 하게 분기를 타도록 할 수 있다. 이때 매 프레임마다 트리를 타게 되면 AI가 갈팡질팡 하게 되니 결정을 일정 시간동안 저장해두어서 일정 시간동안 계속 같은 분기를 타 주도록 할 수 있다.

 

 

학습

잘 쓰이지는 않지만 Decision Tree에도 학습을 적용할 수 있다. 이때 인공 신경망의 학습보다 더 이해하기 쉽다는 장점이 있다.

 

 

 

 

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [299~314p]