JSON-Bag: A generic game trajectory representation

기술 요약: JSON-Bag: 범용 게임 궤적 표현

문제 제기
게임 분석 작업, 예를 들어 에이전트 강도 최적화, 인간 플레이스타일 모델링, 자동화된 게임 설계 등을 위해서는 게임의 특징과 표현을 정의하고 이에 상응하는 거리 또는 유사도 척도를 확립하는 것이 기초가 됩니다. 전통적으로 이러한 표현들은 상당한 도메인 지식을 요구하는 수동 설계 특징이나 추가적인 특징 공학이 필요한 딥러닝 모델에 의존해 왔습니다. 유클리드 거리나 코사인 유사도와 같은 기존 거리 척도들은 종종 이러한 수동으로 정의된 벡터에 적용됩니다. 저자들은 도메인 특화 특징 공학에 의존하지 않고 게임 궤적을 범용적으로 표현하는 방법을 제안하여, 통합된 데이터 기반 접근법을 통해 다양한 보드 게임의 게임 로그를 비교할 수 있도록 합니다.

방법론
본 논문은 **JSON Bag-of-Tokens 모델 (JSON-Bag)**을 소개합니다. 이 방법은 게임 궤적을 JSON 설명을 토큰화하여 표현합니다.

• 토큰화: 게임 궤적은 개별 게임 상태의 JSON 을 연결하여 형성됩니다. 토큰은 루트에서의 경로로 식별되는 원자적 구성 요소 (사전형이나 리스트가 아닌 값) 로 정의됩니다 (예: .playerResources[0].Wood.2). 저자들은 게임의 메커니즘에 따라 순차적 및 비순차적 토큰화 모드를 실험했습니다 (예: 카드 손은 비순차적, 그리드 위치는 순차적).
• 표현: 자연어 처리 (NLP) 의 'bag-of-words'모델과 유사하게, JSON-Bag 는 토큰-발생 횟수 쌍의 집합입니다. 이러한 횟수는 합이 1 이 되도록 정규화되어, 게임 중 해당 토큰을 생성할 확률을 나타내는 토큰 빈도를 가진 게임 궤적의 확률적 모델로 해석됩니다.
• 거리 척도: 이러한 확률적 모델 간의 유사도를 측정하기 위해 저자들은 Jensen-Shannon 발산에서 유도된 대칭적이고 유계인 척도인 **Jensen-Shannon 거리 (JSD)**를 사용합니다.
• 분류 접근법:
  1. 프로토타입 기반 최근접 이웃 검색 (P-NNS): 클래스의 프로토타입은 해당 클래스의 모든 궤적에 대한 평균 JSON-Bag 로 정의됩니다. 분류는 JSD 를 사용하여 가장 가까운 프로토타입을 찾는 방식으로 수행됩니다.
  2. 랜덤 포레스트 (RF): 개별 토큰-빈도 쌍을 특징으로 간주하여 랜덤 포레스트 분류기에 입력함으로써, 수동 선택 없이 자동으로 특징을 추출할 수 있는 모델의 능력을 평가합니다.

실험 설정
이 접근법은 TAG 프레임워크에 구현된 여섯 가지 보드 게임 (7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4, Dots and boxes) 에서 평가되었습니다. 저자들은 Connect4와 Dots and boxes를 다른 게임들에 비해 고유한 게임 구성 요소가 제한적이므로 '희소 (sparse)'게임으로 분류했습니다.
각 게임에 대해 세 가지 분류 작업이 수행되었습니다:

1. 에이전트 분류: 무작위 (Random), 1 단계 미리보기 (OSLA), 그리고 몬테카를로 트리 검색 (MCTS) 의 세 가지 변형 에이전트 간을 구분합니다.
2. 매개변수 분류: 다양한 게임 매개변수 세트 (예: 그리드 크기, 카드 값) 를 식별합니다.
3. 시드 분류: 게임을 초기화하는 데 사용된 난수 생성기 시드를 식별합니다.

주요 결과

• P-NNS 성능: JSD 를 사용한 JSON-Bag 는 대부분의 작업에서 수동 설계 특징과 유클리드 거리를 사용한 베이스라인보다 우수한 성능을 보였습니다. 대부분의 게임에서 OSLA 및 무작위 에이전트를 MCTS 변형과 성공적으로 구분했습니다. 그러나 Connect4와 Dots and boxes와 같은 '희소'게임과 Dominion시드 분류와 같은 특정 작업에서는 성능이 저하되었는데, 이는 희소 JSON 설명의 제한된 정보 내용이나 Dominion에서의 높은 무작위성 역할 때문일 가능성이 있습니다.
• 샘플 효율성: N-shot 분류 실험에서 JSON-Bag 프로토타입은 높은 샘플 효율성을 보여주었습니다. '쉬운'작업 (클래스 간에 명백한 차이가 있는 경우) 의 경우, 클래스당 5 개의 샘플만으로 정확한 분류가 달성되었습니다.
• 랜덤 포레스트 개선: JSON-Bag 토큰을 특징으로 사용하여 랜덤 포레스트 분류기를 적용했을 때, P-NNS 가 부진했던 작업, 특히 희소 게임과 복잡한 매개변수 분류에서 정확도가 크게 향상되었습니다. 이는 JSON-Bag 가 복잡한 상호작용을 학습할 수 있는 모델이 활용할 수 있는 특징을 효과적으로 포착함을 시사합니다.
• 정책 거리와의 상관관계: 서로 다른 에이전트 클래스의 JSON-Bag 프로토타입 간의 JSD 는 해당 에이전트 간의 실제 정책 거리와 높은 상관관계 (피어슨 계수 0.62~0.97) 를 보이는 것으로 나타났습니다. 이는 수동 설계 특징 없이 행동 차이를 위한 대리 지표로서 해당 척도의 유효성을 입증합니다.
• JSON-Char: JSON 문자열의 개별 문자를 토큰화하는 제거 실험 (JSON-Char) 은 놀랍도록 경쟁력 있는 결과를 낳았으며, 이는 JSON 자체의 의미 구조가 상당한 신호를 담고 있음을 시사합니다.

의의 및 기여
본 논문은 네 가지 주요 기여를 주장합니다:

1. 범용 표현: 표준 JSON 변환 이상의 수동 특징 공학이나 게임 특화 직렬화 로직 없이 JSON 설명만으로 게임 궤적을 표현하는 도메인 중립적 방법을 제공합니다.
2. 확률적 유사성: JSON-Bag 의 확률적 해석과 정보 이론적 JSD 척도를 결합하여 게임 궤적 유사성을 효과적으로 평가할 수 있음을 보여줍니다.
3. 샘플 효율성 및 특징 추출: JSON-Bag 프로토타입이 궤적 클래스를 표현하는 데 있어 샘플 효율적이며, 랜덤 포레스트와 같은 머신러닝 알고리즘에 적합한 특징을 추출하는 고유한 능력을 가지고 있음을 보여줍니다.
4. 행동 상관관계: JSON-Bag 프로토타입의 JSD 와 에이전트 간의 실제 정책 거리 사이에 강한 상관관계를 확립하여, 도메인 특화 척도에 의존하지 않고 플레이스타일 클러스터링과 신규성 탐색에 대한 유용성을 입증합니다.

한계점
저자들은 직렬화된 상태 데이터가 정보성 있는 고유 구성 요소를欠하거나 공간적 관계 (예: 그리드 좌표) 가 중요한 '희소'게임의 경우 JSON-Bag 가 어려움을 겪는다고 인정합니다. 이러한 경우, 토큰화 방법은 서로 다른 턴 수와 같이 서로 다르지만 의미적으로 유사한 값을 완전히 다른 토큰으로 처리하여 정보를 잃을 수 있습니다. 논문은 좌표 짝짓기나 수치 값 구간화 (binning) 와 같은 토큰화 전략을 정교화함으로써 이러한 한계를 해결할 수 있다고 제안합니다.