Dhyang's method (1) 그런디 말입니다...

그런디 말입니다...
좀 더 알아봐야겠습니다.

이 글에서는 제가 발견한, Sprague-Grundy theorem을 조금 더 다양한 상황에서 exploit할 수 있게 하는 방법을 다룹니다.

 

Sprague-Grundy theorem

Sprague-Grundy theorem은 impartial game에서 효과적으로 두 개의 게임을 하나의 게임으로 취급할 수 있게 합니다.

Impartial game의 조건은 다음과 같습니다.

• 각각의 플레이어는 게임이 끝날 때까지 턴을 가져야 하고, 턴을 가지지 못하는 상태를 패배한 상태로 합니다. (misere는 일반 nim으로 바꿀 수 있으므로 이 글에서는 다루지 않겠습니다.)
• 게임은 유한해야 합니다. 이 때문에 루프가 있는 게임이거나 비길 수 있는 게임은 Sprague-Grundy theorem으로 다룰 수 없습니다.
• 두 플레이어의 무브셋 (취할 수 있는 동작의 종류) 는 같아야 합니다.
• 모든 정보가 공개되어야 합니다. 즉, 공개되지 않은 정보를 가정한 전략이 존재해서는 안 됩니다.

위와 같은 조건이 있기 때문에, Sprague-Grundy theorem은 선형적 게임, 한 쪽에 무조건 필승법이 있는 게임들에서만 사용될 수 있습니다.

 

하지만, 비선형적 게임에서 과연 Sprague-Grundy theorem을 사용할 수 없을까요?

 

Dhyang24's method의 기본 설명

dhyang's method는 Sprague-Grundy theorem을 변형시킴으로서 무한 루프가 있는 게임에서 Sprague-Grundy theorem의 아이디어를 사용할 수 있게 만듦니다.

우선, Sprague-Grundy theorem의 Grundy-index부터 생각해 봅시다. 이 index는 어떠한 Game-state에서 다른 Game-state로 갈 수 있는 선택지의 수들을 나타내며, 이에 따라 Grundy-index 가 0이면 후공이 승리하고, 그 외의 상황에서는 선공이 승리하는 특징을 가지고 있습니다.

 

index는 공기입니다.

 

저는 이것을 D-index라는 것으로 확장시켰습니다. (D는 Deoreoun(더러운)의 약자입니다.)

우선 D-index는 0과 자연수만을 포함한 중복이 없는 셋으로 나타낼 수 있으며, Grundy-index와 비슷한 전파성을 지닙니다.(자세한 설명은 나중에) 또한, 루프가 있는 게임에서는 무한 루프로 인하여 비기는 경우가 존재할 수 있으므로, D-index에 0이 있는 상태에서는 선공에게 필승법이 없고(후공이 비기거나 이긴다.), D-index에 0이 아닌 숫자가 있는 상태에서는 후공에게 필승법이 없음(선공이 비기거나 이긴다)의 성질로 바뀝니다.

 

전파성의 자세한 설명

D-index는 셋의 형태로 나타나기 때문에, Grundy-index와 같은 방법으로 단순히 갈 수 있는 모든 상태에서의 mex값으로 정리할 수 없습니다.

따라서, D-index 전용의 D-전파 를 정의할 필요가 있습니다. D-전파는 매우 더럽습니다. 

D-전파는 우선 갈 수 있는 모든 Game-state의 D-index를 구한 다음, 각 D-index에서 원소를 하나 고르는 것의 combination을 모두 봐, 그 combination의 mex값을 현재 D-index에 추가하는 것을 반복합니다.

따라서, 현재 D-index의 최댓값이 갈 수 있는 모든 상태의 최댓값보다 최대 1 큼을 알 수 있으며, 원소의 개수 또한 갈 수 있는 모든 상태의 최댓값+1 보다 크지 않음은 자명합니다.

 

아무것도 할 수 없는 상태를 {0} 이라고 하면, 모든 Gamestate의 D-index를 재귀적으로 구할 수 있고, 모든 D-index가 비어있지 않은 집합이라는 것을 증명할 수 있습니다.

 

과연 이러한, 계산하는 데에도 나이브하게는 O(M^N) (N은 갈 수 있는 상황의 개수, M은 각 상황의 D-index의 크기)이 걸리는 더러운 index로 무엇을 할 수 있을까요?

 

 

피곤한 관계로 다음 시간에~

😈😈😈😈😈😈😈