💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

본 논문은 불확실성이 존재하는 2 인 턴제 일반 게임 기술 언어 (GDL) 게임을 해결하기 위한 최초의 ASP 기반 접근법인 확률적 답 집합 프로그래밍 (SQASP) 을 소개하며, 이는 소규모 확률적 게임에서 전향적 탐색과 경쟁력을 보이며 엔드게임 평가에 대한 잠재력을 입증합니다.

원저자: Yifan He, Michael Thielscher

게시일 2026-05-25

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yifan He, Michael Thielscher

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터에게 보드 게임 플레이를 가르친다고 상상해 보세요. 보통 이런 게임들은 체스와 같습니다. 당신이 한 수를 두면 상대가 한 수를 두고, 보드는 예측 가능한 방식으로 변합니다. 하지만 만약 게임에 '와일드카드'가 포함된다면 어떨까요? 당신이 수를 둔 후, 마법적인 주사위 굴림이 당신의 수를 성공시킬지 결정하거나, 제 3 의 보이지 않는 플레이어 (그를 '랜덤'이라고 부르겠습니다) 가 기어에 렌치를 던지는 상황이라면요?

이 논문은 컴퓨터에게 이러한 까다롭고 예측 불가능한 게임들을 해결하는 법을 가르치는 것에 관한 것입니다. 저자 Yifan He 와 Michael Thielscher 는 운이 개입될 때 최상의 전략을 찾아내기 위한 새로운 수학 도구를 개발했습니다.

다음은 그들의 접근 방식을 간단한 비유로 설명한 내용입니다:

1. 문제: '랜덤' 플레이어

표준 게임 이론에서 컴퓨터는 똑똑한 상대에게 완벽한 수를 계산하는 데 뛰어납니다. 하지만 여기에 무작위성(주사위 굴리기나 카드 뽑기 등)을 추가하면 수학은 복잡해집니다.

옛 방법: 이전 컴퓨터 프로그램들은 두 명의 똑똑한 플레이어가 있는 게임 (체스 등) 이나 한 명의 플레이어와 무작위 요소가 있는 게임 (솔리테어 등) 을 처리할 수 있었습니다. 하지만 두 명의 똑똑한 플레이어와 무작위 요소가 동시에 존재하는 게임은 처리하지 못했습니다.
목표: 저자들은 '일반 확률적 2 인 게임 (General Stochastic Two-Player Games)'을 해결하고 싶어 했습니다. 틱택토 게임을 상상해 보세요. 당신이 X 를 두려고 할 때마다, 30% 확률로 그 칸이 O 로 변하거나, 50% 확률로 수를 두는 것이 완전히 차단되는 상황입니다.

2. 새로운 도구: SQASP ('마법 설계도')

저자들은 **확률적 답 집합 프로그래밍 (Stochastic Answer Set Programming, SQASP)**이라는 새로운 언어를 고안했습니다.

비유: 당신이 집을 설계하는 건축가라고 상상해 보세요. 당신은 설계도 (게임 규칙) 를 가지고 있습니다. 과거에는 두 가지 특정 유형의 건설업자를 위한 설계도만 만들 수 있었습니다. 하나는 천재 전략가 (상대) 이고, 다른 하나는 엄격한 규칙을 따르는 로봇입니다.
혁신: SQASP 는 천재 전략가, 로봇, 그리고 도박사가 모두 함께 일하는 건설 현장을 설명할 수 있는 새로운 유형의 설계도입니다.
- 천재(플레이어 X)는 이기고 싶어 합니다.
- 상대(플레이어 O)는 플레이어 X 가 이기는 것을 막고 싶어 합니다.
- 도박사(랜덤)는 다음에 무슨 일이 일어날지 결정하기 위해 동전을 던집니다.
SQASP 를 통해 컴퓨터는 다음과 같은 질문을 할 수 있습니다: "상대가 나를 막기 위해 완벽하게 플레이하고, 도박사는 원하는 대로 행동한다고 가정할 때, 내가 이길 수 있는 최대 확률은 얼마인가?"

3. 번역기: 설계도를 퍼즐로 변환

컴퓨터는 '설계도'를 말하지 않습니다. 그들은 '논리 퍼즐'을 말합니다.

과정: 저자들은 번역기 (sqasp2xssat 라는 도구) 를 개발했습니다. 이 도구는 그들의 정교한 SQASP 설계도를 **확장된 확률적 만족도 (Extended Stochastic Satisfiability, XSSAT)**라는 거대한 논리 퍼즐로 변환합니다.
은유: SQASP 를 케이크를 위한 복잡한 레시피라고 생각하세요. 번역기는 그 레시피를 거대한 다층 스도쿠 퍼즐로 바꾸는 기계입니다. 퍼즐이 해결되면, 그 답은 게임에서 이길 정확한 확률을 알려줍니다.
해결사: 그들은 기존 해결사 (SharpSSAT) 를 사용하여 이 스도쿠를 풀었습니다. 해결사가 "예, 이 퍼즐은 해결 가능하다"고 말하면, 플레이어에게 승리 전략이 있다는 뜻입니다. 만약 67% 확률을 계산해 낸다면, 그것이 최상의 결과입니다.

4. '양자 이동 (Quantifier Shifting)' 트릭

이 논문은 **양자 이동 (Quantifier Shifting)**이라는 특정 최적화 기법도 테스트했습니다.

비유: 토너먼트를 조직한다고 상상해 보세요.
- 방법 A (기준): 모든 플레이어의 수를 나열한 후, 그 수들이 합법적인지 확인한 다음 게임이 끝났는지 확인합니다.
- 방법 B (이동): 수를 나열하기 전에 수들이 합법적인지 먼저 확인합니다. 합법적이지 않은 수를 계획하는 시간을 낭비하지 않기 때문에 더 빠른 것처럼 보입니다.
결과: 두 명의 똑똑한 플레이어가 있는 게임 (결정적 게임) 에서 이 '이동' 트릭은 엄청난 속도 향상을 가져옵니다. 그러나 저자들은 '도박사'가 있는 게임 (확률적 게임) 에서는 이 트릭이 큰 차이를 만들지 않았음을 발견했습니다.
이유: 그들이 사용한 해결사 (SharpSSAT) 는 매우 똑똑합니다. 이 해결사에는 스스로 합법적이지 않은 수를 찾아내는 내장된 '탐정'(단위 전파, unit propagation) 이 있어, 지시 사항을 어떤 순서로 주든 상관없이 작동합니다. 따라서 이 특정 해결사에게는 정교한 재배열이 필요하지 않았습니다.

5. 결과: 어떻게 수행되었는가?

팀은 틱택토, 커넥트 4, **님 (Nim)**과 같은 고전 게임의 변형에 '랜덤' 플레이어를 추가하여 시스템을 테스트했습니다.

성능: 그들의 새로운 방법은 표준 '전진 탐색 (forward search)' 방법 (컴퓨터가 머릿속에서 게임이 어떻게 될지 보기 위해 게임을 수백만 번 플레이하는 것과 유사) 과 경쟁력이 있었습니다.
단점: 작은 보드 (3x3 또는 4x4 등) 에서는 잘 작동했습니다. 하지만 게임이 너무 커지면 (님 게임에서 100 개의 더미 등), 논리 퍼즐이 컴퓨터가 합리적인 시간 내에 해결하기에 너무 거대해졌습니다.
교훈: 이 방법은 **종국 평가 (endgame evaluation)**에 탁월합니다. 게임이 거의 끝났을 때, 이 시스템은 일반 게임 플레이 AI 에게 "이 수를 두면 99% 확률로 이길 수 있다"고 알려주어 최종 결정을 내리는 데 도움을 줄 수 있습니다.

요약

저자들은 운과 전략이 충돌하는 게임을 수학적으로 설명하는 새로운 방법을 고안했습니다. 그들은 이러한 설명을 컴퓨터가 해결하여 이길 수 있는 '최상의 확률'을 찾을 수 있는 논리 퍼즐로 변환했습니다. 모든 게임 크기에 만능 해결책은 아니지만, 이 방법은 논리 프로그래밍을 사용하여 복잡하고 불확실한 게임을 해결할 수 있음을 증명하며, 혼란스러운 세계에서 컴퓨터가 미래를 더 잘 생각할 수 있는 방법을 제공합니다.

그들이 주장하지 않은 것:

그들은 전체 보드를 볼 수 없는 게임 (포커나 크rieg-틱택토 등) 에 대해 이것이 작동한다고 주장하지 않았습니다. 그들은 명시적으로 이 방법이 전체 보드를 모두가 볼 수 있는 게임 (완전 정보 게임) 에 적용된다고 밝혔습니다.
그들은 이것이 즉시 모든 다른 AI 방법을 대체할 것이라고 주장하지 않았습니다. 그들은 이것이 특히 종국과 같은 특정 시나리오를 위한 대안이라고 지적했습니다.

기술적 요약: 일반 확률적 2 인 게임을 해결하기 위한 ASP 기반 접근법

문제 정의

일반 게임 플레이 (GGP) 시스템은 규칙에 대한 사전 지식 없이 런타임 설명에 기반하여 전략적 게임을 플레이하는 것을 목표로 합니다. 게임 기술 언어 (GDL) 와 그 확장인 GDL-II 는 이러한 게임을 지정하기 위한 표준 형식이며, GDL-II 는 무작위성 (확률성) 과 부분 관측성을 지원합니다. 답변 집합 프로그래밍 (ASP) 이 결정론적 1 인 및 2 인 GDL 게임 해결에 성공적으로 적용되어 왔지만, 기존 ASP 프레임워크는 동시에 적대적 (최소 - 최대) 행동과 확률적 행동을 표현할 수 있는 기능이 부족합니다. 따라서 불확실성이 포함된 2 인 턴제 GDL 게임을 해결하기 위해 ASP 기반 방법을 사용하는 데에는 간극이 존재합니다.

방법론

저자들은 새로운 언어와 번역 기반 솔버를 도입함으로써 2 인 확률적 GDL 게임을 해결하는 새로운 접근법을 제안합니다.

1. 확률적 양화 답변 집합 프로그래밍 (SQASP)

ASP 와 확률적 게임 해결 사이의 간극을 메우기 위해, 본 논문은 확률 양자를 추가하여 QASP(Quantified ASP) 를 확장한 SQASP를 소개합니다.

구문: SQASP 프로그램은 $Q_1.x_1 \dots Q_n.x_n \ P$ 형태를 띠며, 여기서 $P$ 는 일반 논리 프로그램이고 양자 $Q_i$ 는 존재 양자 ( $\exists$ ), 전칭 양자 ( $\forall$ ), 또는 확률 양자 ( $\mathcal{R}_{p}$ ) 일 수 있습니다.
의미론: SQASP 프로그램을 만족시키는 최대 확률은 재귀적으로 정의됩니다. 확률 양자 $\mathcal{R}_{p}$ 는 변수가 참일 확률 $p$ 를 할당하여 하위 공식들의 확률에 기반한 기댓값을 계산합니다.
번역: 저자들은 SQASP 프로그램을 확장 확률 만족도 (XSSAT) 공식으로 변환하는 도구인 sqasp2xssat를 구현했습니다. XSSAT 는 확률 양자를 추가하여 양화 부울 공식 (QBF) 을 확장한 것입니다. 이 번역은 논리 프로그램 $P$ 를 CNF 공식 $\psi$ 로 변환하는 기존 도구 (예: lp2sat) 를 활용하며, 이 $\psi$ 의 모델은 $P$ 의 안정 모델에 해당합니다.

2. GDL 게임을 SQASP 로 인코딩

핵심 기여는 플레이어 $x$ 가 $n$ 단계 내에서 승리할 확률 ( $P_x^w(S_0, n)$ ) 과 SQASP 프로그램 $\Psi$ 의 최대 만족도 확률이 같도록 SQASP 프로그램 $\Psi$ 를 구성하는 것입니다. 인코딩은 두 가지 주요 단계로 진행됩니다.

협력적 기준선: 먼저, 모든 플레이어 (상대방 $o$ 와 무작위 플레이어 $r$ 포함) 가 $x$ 가 승리하는 종단 상태에 도달하도록 협력한다고 가정하여 논리 프로그램 $P_c$ 를 구성합니다. 이는 유효한 게임 진행, $n$ 단계 내 종료, 그리고 목표 상태 달성을 보장합니다.
적대적 및 확률적 모델링: 그 후 상대방과 환경의 특정 행동을 포착하도록 프로그램을 확장합니다.
- 적대적 플레이어 ( $o$ ): 결정 변수 (dec_o) 에 대한 전칭 양화 ( $\forall$ ) 를 사용하여 모델링합니다. 이는 솔버가 상대방이 $x$ 의 승리 확률을 최소화하는 최악의 시나리오를 고려하도록 강제합니다. 인코딩은 규칙 수를 줄이기 위해 행동을 로그 표현으로 사용합니다.
- 확률적 플레이어 ( $r$ ): 확률 양자 ( $\mathcal{R}_{1/i}$ ) 를 사용하여 모델링합니다. 인코딩은 게임이 종료되지 않은 경우 무작위 플레이어가 사용 가능한 합법적인 이동 중 정확히 하나의 합법적인 행동을 균일하게 선택하도록 보장합니다. 이는 합법적인 행동을 세고 결정 변수 (dec_r) 에 확률 제약을 적용함으로써 달성됩니다.

3. 양화 전략

본 논문은 결과 XSSAT 공식에 대한 두 가지 양화 전략을 조사합니다.

기준선 방법 ( $Q_b$ ): 모든 비-선택 원자 (예: legal, terminal) 는 선택 원자의 엄격한 시간적 순서를 따르며 가장 안쪽의 존재 양자 블록에 배치됩니다.
의존성 기반 방법 ( $Q_d$ ): 결정론적 게임을 위한 기법에 영감을 받아, 이 방법은 의존하는 선택 원자 직후에 나타날 수 있도록 비-선택 원자를 양화 접두사에서 가능한 한 일찍 이동시킵니다. 이는 does에 분기하기 전에 legal과 같은 값을 고정함으로써 검색 공간을 줄이는 것을 목표로 합니다.

주요 기여

확률적 GDL 을 위한 최초의 ASP 기반 솔버: 본 논문은 ASP 를 사용하여 2 인, 확률적, 턴제 GDL 게임을 해결하는 최초의 접근법을 제시합니다.
SQASP 언어: 논리 프로그래밍 프레임워크 내에서 적대적 추론과 확률적 추론을 통합한 확률적 양화 답변 집합 프로그래밍의 도입.
번역 기반 솔버: SQASP 프로그램을 XSSAT 공식으로 변환하여 기존 XSSAT 솔버 (특히 SharpSSAT) 를 게임 해결에 사용할 수 있게 하는 sqasp2xssat의 개발.
이론적 정확성: 저자들은 GDL 게임에서의 최대 승리 확률과 생성된 SQASP/XSSAT 공식의 최대 만족도 확률 사이의 동등성을 확립하는 공식 증명 (정리 2 및 3) 을 제공합니다.

실험 결과

저자들은 Tic-Tac-Toe, Connect-4, Nim 의 확률적 변형에 대해 접근법을 평가했으며, SQASP 기반 방법 (두 가지 양화 $Q_b$ 및 $Q_d$ 모두 사용) 을 순방향 탐색 기대 최소 - 최대 (EMM) 솔버와 비교했습니다.

성능: ASP 기반 접근법은 작은 확률적 게임에서 순방향 탐색과 경쟁력 있는 성능을 보입니다. 많은 경우 (예: Tic-Tac-Toe, Connect-3) 에서 ASP 솔버는 EMM 과 유사한 승리 확률을 계산하며, 종종 유사한 시간 범위 내에 수행됩니다.
양자 이동: 놀랍게도 SharpSSAT 솔버를 사용할 때 의존성 기반 양화 ( $Q_d$ ) 는 기준선 ( $Q_b$ ) 대비 유의미한 성능 향상을 보이지 않았습니다. 저자들은 이는 SharpSSAT 의 내부 단위 전파 메커니즘이 양자 순서에 관계없이 원자 (예: legal) 의 값을 유도할 수 있어 명시적 이동의 필요성을 효과적으로 완화하기 때문이라고 귀결합니다.
확장성 한계: 이 접근법은 큰 더미 크기를 가진 확률적 Nim 과 같은 더 큰 상태 공간에서는 어려움을 겪습니다. 결과 XSSAT 공식은 현재 솔버가 효율적으로 처리하기에는 너무 커집니다 (100 만 개 이상의 절). 반면 EMM 은 동적 프로그래밍과 전이 테이블로 인해 잘 확장됩니다.

중요성과 주장

본 논문은 제안된 ASP 기반 접근법이 일반 게임 플레이 시스템에서 엔드게임 평가를 위한 실현 가능한 대안을 제공한다고 주장합니다. 결정론적 게임에 대한 ASP 의 성공적인 적용을 확률적 영역으로 확장함으로써, 이 작업은 논리 프로그래밍이 불확실성과 적대적 추론을 효과적으로 처리할 수 있음을 보여줍니다.

저자들은 겸손하게도 이 접근법이 모든 경우 (특히 매우 큰 상태 공간이나 Nim 과 같은 특정 구조를 가진 게임) 에 순방향 탐색을 압도하지는 않지만, 결정론적 게임에 대한 이전 결과를 확률적 게임으로 성공적으로 일반화했다고 지적합니다. 그들은 완전 정보 게임에 국한된 현재 방법의 한계를 인정하면서, 부분 관측성 (예: 포커, 크리그 틱택토) 으로 확장하는 것을 향후 연구의 중요한 방향으로 식별합니다.