기술 요약: 일반 게임 시스템 내에서의 확장 가능한 보드 확장

문제 정의

Ludii와 같은 일반 게임 플레이(General Game Playing, GGP) 시스템은 다양한 종류의 게임을 통합된 프레임워크를 통해 지원하는 것을 목표로 한다. 그러나 현재의 Ludii 구현은 플레이어가 타일을 배치하며 동적으로 공간을 구축하는 '보드리스(boardless)' 테이블탑 게임(예: Carcassonne, Andantino)을 처리하는 데 어려움을 겪고 있다.

기존 Ludii 아키텍처에서 보드리스 게임은 고정된 크기의 정적 보드(예: 사각형/삼각형 타일의 경우 $41 \times 41$, 육각형 타일의 경우 $21 \times 21$)를 사용하여 시뮬레이션된다. 사용자 인터페이스는 경계선을 숨겨 무한한 공간처럼 보이게 하지만, AI 에이전트는 이 전체가 미리 할당된 그리드 전체를 대상으로 추론해야 한다. 이러한 접근 방식은 세 가지 결정적인 한계를 초래한다:

1. 메모리 및 계산 낭비: 시스템은 전체 그리드에 대해 방대한 데이터 구조(이동 및 인접성을 위한 "radial" 등)를 미리 계산하는데, 여기에는 게임 내내 비어 있는 상태로 남을 광활한 영역이 포함된다.
2. 부정확한 표현: 고정된 그리드는 보드리스 게임의 근본적인 특성과 상충되는 인위적인 경계를 부과하며, 이는 이론적으로 무한히 확장될 수 있는 게임의 본질을 저해한다.
3. 성능 저하: 거대한 상태 공간은 AI가 초당 수행할 수 있는 랜덤 플레이아웃(시뮬레이션)의 수를 줄여, 몬테카를로 트리 탐색(MCTS) 및 기타 AI 전략의 효과를 현저히 저하시킨다.

방법론

본 논문은 정적 그리드를 확장 가능한 구조로 대체하는 동적 보드 확장 메커니즘을 제안한다. 핵심 목표는 시작 타일에 충분한 최소 크기로 보드를 초기화하고, 플레이어의 행동에 따라 필요할 때만 보드를 확장하는 것이다.

본 연구는 두 가지 주요 확장 전략을 탐구하며, 각 전략은 두 가지 상태 관리 접근 방식과 함께 구현된다.

1. 확장 전략

• 주변부 전략 (Perimeter Strategy/Contour): 플레이어가 현재 보드의 가장자리에 타일을 배치하면, 시스템은 전체 주변부에 새로운 셀 레이어를 한 층 추가한다. 이는 보드가 항상 잠재적인 플레이 영역으로 둘러싸여 있도록 보장하지만, 최악의 경우 급격한 지수적 성장을 초래할 수 있다.
• 구역 전략 (Zone Strategy): 플레이어가 가장자리에 타일을 배치하면, 시스템은 해당 특정 움직임의 즉각적인 이웃(예: 사각형의 경우 8개 인접 셀, 육각형의 경우 6개)에만 새로운 셀을 추가한다. 이 접근 방식은 더 국지적이며 생성되는 타일 수를 최소화하는 것을 목표로 한다.

2. 상태 관리 접근 방식

확장 중 발생하는 구조적 변화를 처리하기 위해, 게임 상태를 업데이트하는 두 가지 방법을 개발하였다:

• 재적용 (Reapplication, RE): "실행 취소(undo)" 메커니즘에서 영감을 받아, 보드를 초기 상태로 리셋하고 새로운 크기로 조정한 뒤, 모든 이전 수들을 순차적으로 다시 실행하여 현재 상태를 재구성한다.
• 직접 매핑 (Direct Mapping, MAP): 기존 게임 상태(컨테이너, 소유권, 이동 기록)를 더 큰 새로운 보드 구조에 직접 매핑한다. 기존 셀의 인덱스를 새로운 토폴로지에 따라 재계산하고, 전체 이동 기록을 다시 재생하지 않고도 새로운 빈 세트에 새 셀을 추가한다.

3. 구현 세부 사항

구현은 Ludii의 내부 구조를 다음과 같이 조정한다:

• 그래프/토폴로지 (Graph/Topology): 셀, 정점(vertex), 간선(edge)의 그래프를 동적으로 재구성한다.
• 컨테이너 상태 (Container State): ChunkSet 비트셋(비어 있음, 점유됨, 플레이 가능 사이트 추적)을 업데이트하여 새로운 보드 크기와 셀 매핑을 반영한다.
• 소유 구조 (Owned Structure): 구성 요소의 소유권을 새로운 셀 인덱스로 재매핑한다.
• 타일 형태 (Tile Shapes): 고유한 이웃 수와 기하학적 성장 패턴을 고려하여 사각형, 육각형, 삼각형 타일에 대한 특정 알고리즘을 도출하였다.

주요 기여

1. 동적 보드 아키텍처: 임의의 크기 제한 없이 보드리스 게임을 지원할 수 있는 확장 가능한 보드 확장 메커니즘을 도입하였다.
2. 최적화된 상태 관리: 확장 중에 매번 전체 상태를 재구성하는 오버헤드 없이 게임 상태를 효율적으로 업데이트하는 PERI-MAP 및 ZONE-MAP 기법을 개발하였다.
3. 형태별 로직: 확장 시 새로운 셀 수와 인덱스 매핑을 계산하기 위한 상세한 수학적 공식을 도출하였다.
4. 경험적 평가: 여러 게임(Andantino, Bravalath, Plotto)과 타일 형태에 대해 정적 베이스라인과 새로운 동적 접근 방식을 비교하는 종합적인 벤치마크를 수행하였다.

결과

클러스터에서 사각형, 육각형, 삼각형 타일을 사용하는 네 가지 게임을 대상으로 보드 크기 성장과 랜덤 플레이아웃 성능(초당 플레이아웃 수 및 초당 이동 수)을 측정하는 실험을 진행하였다.

• 보드 크기 효율성:

  • 정적 BASE 구현은 게임 진행 상황과 관계없이 일정한 거대한 보드 크기(예: 사각형의 경우 1,681개 셀)를 유지하며, 이는 90% 이상의 미사용 타일을 발생시킨다.
  • ZONE 전략은 가장 작은 보드 크기를 유지하며, 최악의 경우에도 정적 제한보다 훨씬 낮은 수준을 유지한다.
  • PERI 전략은 최악의 경우 지수적으로 성장하지만, 최선의 경우 정적 베이스라인보다 작게 유지된다.

• 성능 (랜덤 플레이아웃):

  • PERI-MAP 전략은 가장 높은 성능을 달성하였으며, 정적 BASE 구현보다 평균적으로 약 25배 더 높은 성능을 보였다.
  • PERI-MAP과 PERI-RE는 유사한 성능을 보였으며, 일반적으로 PERI-MAP이 약간 더 우수했다.
  • 이론적 예상과는 달리, 더 적은 타일을 생성하는 ZONE 전략들이 PERI 전략들보다 성능이 낮게 나타났다. 저자들은 이를 Ludii의 내장된 정규 주변부 그리드 생성 함수와 비교했을 때, 불규칙한 그래프 구조를 동적으로 생성하는 현재 구현의 비효율성 때문이라고 분석하였다.

의의 및 주장

본 논문은 제안된 PERI-MAP 접근 방식이 GGP 시스템 내에서 보드리스 게임을 표현하는 데 있어 중요한 진전임을 주장한다. 거대한 사전 할당 정적 그리드의 필요성을 제거함으로써 시스템은 다음을 달ach한다:

• 확장성 (Scalability): 사실상 무제한적인 보드 성장이 가능한 게임을 모델링할 수 있는 능력.
• 효율성 (Efficiency): 메모리 사용량의 획기적인 감소와 시뮬레이션 속도의 향상을 통해 더욱 효과적인 AI 에이전트를 가능하게 함.
• 충실도 (Fidelity): 인위적인 경계를 제거함으로써 게임의 공간적 역동성을 더 정확하게 표현함.

저자들은 ZONE 전략이 타일 생성 측면에서는 이론적으로 더 효율적이지만, 현재 Ludii 프레임워크 내에서는 PERI-MAP 전략이 성능과 구현 성숙도 사이에서 최적의 균형을 제공한다고 결론지었다. 이 연구는 더 넓은 범위의 현대적 보드리스 게임을 구현하기 위한 토대를 마련하며, 동적 토폴로지 및 규칙 기반 확장에 관한 향후 연구를 지원한다.