8. AI

지금까지

• 게임 세계를 그려주고, 진동을 만드는 부분
• 애니메이션 업데이트, 전략 업데이트
• Input 등에 대해 배웠다
• Input을 처리하기 위한 Collision Detection을 배웠다
• 이제 장기적인 업데이트를 위한 AI를 배워보자

AI

• 게임 내의 캐릭터나 상대방이 어떤 행동을 취할지를 정한다
• 전통적인 인공지능에 가장 가깝다. Action에 관련된 부분이 적용됨
• 지능적인 행위를 컴퓨터가 시뮬레이션 한다!
  • 지능적인 행위란 ? 내가 예측하지 못한 일을 했을 때
  • 사람이 하는 것보다 빠르게, 또는 정확하게 처리하는 것

게임에서의 AI

• 상황 (Status)를 이해해서 Plan을 세우고, Action을 취하여 Update한다
• 게임에서는 Performance가 추가된다. 매우 빠르게 처리되어야 한다
  • 초당 60프레임정도 빠르게 업데이트 업데이트가 되어야 한다
  • 게임에서는 정확성보다는 눈으로 봤을 때 그럴듯해야한다!

💡 AI의 종류

• agent
  • 캐릭터 하나의 상황을 파악한다. 월드 전체를 알 필요 X
  • 필요한 요소
    • Sensor : 주변에 뭐가 있는지 알기 위함
    • Memory : 주변 상황이 이전과 얼마나 변화했는지 알기 위한 메모리
    • Reasoning Core : Plan을 짜기 위함
    • Action System : Plan을 기반으로 행동하기 위함
  • AI마다 개별적인 컨트롤러를 가진다
• strategy
  • 스포츠나 그룹 안에서의 전체를 파악하고 전략을 세워야 한다.
  • 그룹이나 월드 전체의 상황을 파악하는 것이 필요하다.
  • Abstract Controller : 그룹을 대상으로 큰 전략을 짜고, 세부적인 Agent 가 컨트롤하도록 한다

💡 AI 시스템 컴포넌트

• sensor
  • 목적 : 전체 시스템을 인지한다.
  • 개별 컨트롤러에서는 현재 위치에서 무엇이 보이는지, 어디서 소리가 났는지. 나와 어떤 대상과의 거리 등을 알아야 한다
  • Abstract 컨트롤러에서는 전장 전체를 알고, 유닛이 어디어디에 있다 등을 알아야 한다. 전체적인 상황을 만들어야 한다 → 전체 맵의 상황 Map을 계산하고 만들어낸다. 여기서 시간이 많이 든다 → 물리적으로 실제 전략을 만드는건 힘드므로, 어느정도 안다고 생각하고 만든다
    
• memory
  • 현재 데이터를 저장해서, 미래에 goal 에 대해 알아야 한다
  • 캐릭터의 상태, 월대의 상태를 저장한다
  • 캐릭터의 상태변수, 장기적인 goal, 단기적인 goal 을 저장한다
  • 디자인 패턴에서 동일한 상황에서 취할 수있는 케이스처럼 구현한다
• Reasoning Core
  • 센싱된 데이터를 기반으로 결정한다
  • 예시 : 체스 - 몇 수 뒤의 값 중 가장 승률이 높은 값을 사용한다
  • AI의 핵심 코어이며, 가장 오랜 시간이 필요하다
  • 이 과정을 쉽게 계산하기 위해 seonsor, memory를 가장 좋은 방법을 채택해야 한다
• Action System
  • Reasoning Core에서 나온 결과를 실제 Action으로 보여줘야 한다
  • 예시 : 슈퍼마리오처럼 AI가 같은 동작이더라도 조금씩 다르게 보여주면 더 완성도 높아보인다!

---

가장 어려운 Reasoning Core를 좀더 자세히 알아보자

Reasoning

• 센서와 메모리의 정보로부터 주변 상황에 대한 것을 파악하고, 파악한 것을 기반으로 Action을 계획해야 한다
• 여러 방법들이 있다

자주 쓰이는 Reasoning 알고리즘

1) Login Programming : 이런 행동을 취했으니까 다음 행동은 이걸 해야해!

2) Optimiazion / Searching : A* search. 오목, 체스처럼 여러 케이스를 해보고 그 중 가장 최적화된 방법을 찾기

3) Classifiers : 어떤 상황에 포함되는지, 공격할 상황인지를 판정하기

4) Non-deterministic reasoning : 계획대로 흘러가지 않기 때문에. 상황에 대해 항상 똑같이 행동하지 않고 이전의 상황에 의해 변화된 행동을 보여준다.

5) Genetic Algorithms (유전) : 알고리즘이 진화하는 것. 알고리즘이 좋은지 판단하고 더 좋은 알고리즘을 사용하며 진화한다

💡 Finite State Machine (FSM)

• 오토마타. state, transition, action으로 행동을 표현한다

• 예시
  • 문이 열려있는 스테이트 → 문을 여는 action → 문이 열려있는 state.
  • 문 열린 스테이트 → 문 닫힌 스테이트로 이동하기 위해서는 트랜지션이 발생해야 한다
• 어떤 조건이 만족하면 스테이트가 바뀐다
• 디자인 단계
  • Specification : 내가 할 수 있는 행위 자체를 나열한다. 몬스터가 취할 수 있는 액션은~~~
  • Layout : 행위들을 State 형태로 표현한다. agent의 모드(공격,달리기), agent의 위치 등
  • Coding : 여러 state를 정의해서 코딩하면 된다. 상태를 바꾸고 행동하고, 조건을 확인하는 코드 구조로 만든다

→ 이제 behavior를 프로그램으로 만들 수 있다 !

→ 걷는 state , 총을 쏘는 state가 있을 때 공통으로 들어가는 흐름이 생기면 모든 tree에 하나씩 추가해줘야 한다

→ Parallel automata 를 사용해 해결한다!

Parallel Automata

• 여러 개의 automata를 만들고, 그 오토마타들이 병렬적으로 동작할 수 있도록 한다
  • 어떻게 코딩할까? Sequential processing 으로, 어떤 오토마타가 먼저 실행될지 정해서 순서대로 실행해주면 된다

→ 이제 하나의 agent는 컨트롤할 수 있다

→ 여러 개의 에이전트를 동작하려면 어떻게 해야할까?

• 동기화 방법 : 여러 에이전트가 있을 때, 이제 공격을 시작하자! 라고 말하려면?
  • 메시지를 전달한다
  • 공통된 목표에 대한 공유 메모리를 사용한다

→ 모든 캐릭터가 똑같이 동작하게 된다. behavior 단계에서 각 동작을 다르게 하도록 만들 수도 있지만 Reasoning 과정에서 해결하려면?

→ Nondeterministic Automata

Nondeterministic Automata

• 전략 단계에서 캐릭터에 각각 다른 전략을 주기 위한 방법
• 행동 값을 확률로 표현해서, unexpected한 행동을 보이도록 한다
• 확률에 의해 상태 변화가 발생하게 된다
  • 장점 : 현실에 가까운, 예측하지 못한 일이 발생하게 된다
  • 단점 : 확률을 제대로 잡지 못하면 AI가 제 기능을 못하게 될 수 있다.

FSM이 좋은 경우

• 행위가 state로 지역적인 상황에 의해 결정되는 경우에 좋다
• 순차적으로 행위가 발생하는 경우

→ 행위가 여러 조건에 의해 결정되거나, 순서가 없는 경우 FSM에 의해 하기엔 복잡해진다

→ 병렬 오토마타를 써도 충돌이 너무 많이 발생한다!

→ 좀더 단순하게 표현할 수 없을까?

💡Rule Systems

• 어떤 조건에 의해 Action이 발생하는 것이 결정되는 케이스
• 표현이 쉽게 되지만, 상호간의 충돌이 발생할 수 있다 → 충돌을 어떻게 해소할까?
  
• 실행 과정
  • 조건이 만족되는지 하나씩 확인한다 → 조건을 만족하면 action을 실행한다 → 충돌이 발생할 수 있다! 우선순위를 준다
    
  • Decision Tree를 사용한다 → 해당 조건을 만족하는 경우 하위 노드로 내려가도록 한다. 충돌이 해결되지는 않는다
    

💡Structured Rule System

• 충돌이 발생하지 않도록 만든 룰 시스템
• 어떤 것이 먼저 실행되더라도 같은 결과를 보여준다 = 시간에 독립적인 결과를 보여준다
• Rete Algorithm
  • 컨디션이 항상 모두 체크될 수 있도록 한다

• 간단한 룰이 복잡해지긴 하지만 규칙에 기반해서 쉽게 디자인 가능함

Rule System vs FSM

• Rule System은 좀더 넓은 범위에서 쓸 수 있다
• FSM은 순차적인 행동을 표현하기 좋다
• Prioritized rules : 룰 중에서 중요도를 줘서 만들 수 있다 (FSM, 병렬도 우선순위 줄 수 있다)

💡State Space Search

• tic tac toe
  • 아무것도 없는 상태에서 어디에 놓을지를 정한다
  • 하나를 뒀을 때 그 다음을 어디에 둘지를 트리 형태로 가능한 경우들을 찾고, 가장 좋은 값을 채택한다
  • A* algorithm