ARTIFICIAL INTELLIGENCE

ARTIFICIAL INTELLIGENCE

본 포스팅은 Sanjay Madhav 가 집필한 Game Programming in C++ (2018) 의 내용을 정리한 글입니다
그 중에서도 4장 ARTIFICIAL INTELLIGENCE 의 내용을 다룹니다

---

Overview

본 장에서는 아래와 같은 내용을 배울 수 있다

• State Machine Behaviors
  • 개체의 상태와 행동을 정의하는 방법
• Path Finding
  • 개체 이동에 있어 경로를 탐색하는 알고리듬
• Game Trees
  • 게임의 상태에 따른 의사결정 알고리듬

---

State Machine Behaviors

개체가 가질 수 있는 상태와 상태간 전이에 대한 조건을 명시하는 방법을 다룬다

• State Machine
  • 일종의 그래프
  • 각 정점은 개체가 가질 수 있는 상태
  • 각 간선은 상태 전이 조건
  • 개체는 하나의 상태만을 가지고 전이 조건에 해당할 때마다 상태를 변경한다
    ※ 개체의 죽음 같은 특별한 경우 모든 상태에서 간선을 가질 필요가 있음
• Applying to AIState
  • 개체의 상태를 단순히 정수형으로 저장하는 것보다는 열거형으로 정의
    • 가시성 확보 및 중간 삽입 용이
  • 하지만 상태의 개수가 늘어날수록 AIComponent 에서의 분기문 작성 어려움
    • 다형성을 활용하기 위해 AIState 를 클래스로 정의
  • 각 상태마다 진입 / 유지 / 탈출 시기에 따른 행동을 정의
    • 상태를 유지할 때뿐만 아니라 전이할 때에도 특정 행동을 하도록 정의가능
• Applying to AIComponent
  • AIState 가 열거형으로 정의된 경우
    • if 또는 switch 를 사용해 각 상태에 대한 처리를 명시하기 때문에 비효율적
  • AIState 가 클래스로 정의된 경우
    • 멤버함수 호출만 명시하여 코드 분량 절감 및 확장성 확보

---

Path Finding

게임상에서 AI 개체로 하여금 어느 한 지점에서 다른 지점으로 이동시킬 때가 종종 있다
이동경로를 어떻게 정하느냐에 따라 AI 개체가 이동하는 거리에 대한 효율성이 결정된다

• Breadth First Search BFS
  • 그래프상에서 같은 단계에 있는 정점들을 순차적으로 방문하는 방법
  • 정답에 해당하는 정점이 매우 높은 단계에 존재할 경우 불필요한 연산량이 큰 편
    • 정답을 발견할 때까지 같은 단계의 모든 정점들을 방문하기 때문
  • 간선을 지나가는 비용이 모두 같다고 보기 때문에 범용적으로 사용하기 힘들다
    • 간선마다 비용이 다를 경우 BFS 가 최적경로를 준다고 보장할 수 없다
  • 정점을 키와 값으로 동시에 가지는 맵을 사용하여 이동경로를 저장
    • 자식을 키로 하며 값으로 부모를 얻게 되는 구조로 활용
    • 궁극적으로 거꾸로 뒤집어진 이동경로를 얻게 된다
• Heuristics
  • Manhattan Distance
    • 목적지와 같은 행 또는 열까지 직선으로 이동한 뒤
    • 같은 열 또는 행까지 직선으로 이동한다
    • 이 경로상 소요된 거리가 Manhattan Distance 이다
  • Euclidean Distance
    • 출발지 좌표값과 목적지 좌표값으로 벡터를 만든 뒤
    • 두 벡터를 빼고 얻은 벡터의 거리를 계산한다
    • 그 결과값이 Euclidean Distance 이다
• Greedy Best First Search GBFS
  • 매번 Heuristics 을 계산하여 정점을 차례대로 경로에 추가하는 방법
    • Heuristics 로는 주로 Manhattan Distance 이 사용된다
  • 장애물을 만났을 경우 우회할 수 있도록 설계된다
    • 당장 눈앞의 정점만을 보기 때문에 사전에 장애물을 우회하는 경로탐색은 불가능
  • Heuristics 계산을 통해 경로에 추가된 정점은 Closed Set 에 추가해 중복계산을 방지
• A Star Search
  • GBFS 의 개량판
    • 목적지까지의 경로상에 장애물이 있어도 최적경로를 제공한다
  • GBFS 와 다르게 Heuristics 뿐만 아니라 출발지와의 거리 또한 고려한다
    • Heuristics 값과 출발지와의 거리 값의 합이 최소인 정점을 선택한다
      ※ 출발지와의 거리 는 현재까지 구해진 경로를 따라갔을 때의 거리이다
  • 어떤 정점이 Closed Set 에 포함되기 전에 다음의 절차를 수행한다
    • Closed Set 에 포함되지않은 주변 정점들에 대해 출발지와의 거리 를 갱신한다
    • 출발지와의 거리 값을 이전값과 비교하여 증가했다면 포함시키지 않는다
• Dijkstra's Algorithm
  • 지금까지 알아본 경로탐색 알고리듬은 복수의 정답이 있을 경우에 대해 최적경로를 보장하지않는다
  • 반대로 Dijkstra 의 경우 복수의 정답에 대한 각각의 최적경로를 탐색할 수 있다
  • 하지만 탐색해야할 정점의 개수가 매우 많아 게임 프로그래밍에서 많이 사용되지는 않는다
• Other Methods
  • Path Nodes
    • 맵상에서 개체가 위치할 수 있는 정점을 사전에 정의하는 방식이다
    • 개체가 이동해야할 범위를 제한함으로써 경로계산에 필요한 연산량을 절감
    • 개체가 정점과 간선상에서만 움직일 수 있다는 단점이 존재한다
  • Navigation Mesh
    • 맵을 여러 개의 덩어리로 나누고 각 덩어리를 정점으로 보는 방식이다
    • Path Nodes 처럼 경로계산에 필요한 연산량을 절감할 수 있다
    • 각 덩어리 내에서 움직이는 방법에 대한 연산이 별도로 필요한 단점이 존재한다

---

Game Trees

틱택토와 같은 게임들은 부모 상황에 대해 이 다음으로 가능한 여러 가지 자식 상황들이 존재한다
처음 상황에서부터 특정 단계의 상황까지를 트리로 표현할 수 있는데 이를 게임트리라 한다

※ 아래의 최적 게임트리 선택 알고리듬들은 게임트리가 생성되어 있다는 가정을 가진다

• Minimax
  • 턴제 게임이며 게임을 진행하는 플레이어가 2명일 경우 사용할 수 있다
  • 게임트리를 탐색하면서 다음의 절차를 수행한다
    • 자신의 턴일 경우 자신의 이득을 극대화하는 경우의 수를 선택한다
    • 상대의 턴일 경우 자신의 이득을 최소화하는 경우의 수를 선택한다
      ※ 상대가 자신의 이득을 최소화하는 선택을 할 것이라고 가정한다
  • 모든 게임트리를 탐색한 경우
    • 상대가 자신의 이득을 최소화하려고 시도를 하는 환경에서의
    • 자신에게 제일 이득이 되는 경우의 수를 찾았음을 보장할 수 있다
      ※ 예컨대 승리를 할 수 있는 경우의 수
  • 게임트리의 탐색단계가 높아질수록 검사하는 경우의 수가 기하급수적으로 많아진다
    • 내다보는 턴의 수를 제한하여 연산량을 절감하는 것이 좋다
• Alpha Beta Pruning
  • Minimax 를 최적화해 연산량을 줄인 알고리듬이다
  • 동일한 단계의 게임트리에서 이득의 상한선을 가지는 정점만 선택한다
  • 버려진 정점들에 대해 탐색하지않아 연산량을 대폭 절감할 수 있다
• Iterative Deepening
  • 게임 초반에는 경우의 수가 매우 많기 때문에 내다볼 수 있는 턴의 수가 많지않다
  • 하지만 진행에 따라 경우의 수가 줄고 동일한 연산량으로 내다볼 수 있는 턴 수가 증가
  • 진행에 따라 내다보는 턴 수를 늘리는 것이 추천되고 이를 Iterative Deepening 이라 한다

---

Exercise

예제 풀이는 https://github.com/BaeMinCheon/game-programming-in-cpp 의 commits 참고