서론
게임이론중 하나로, 단 두명의 플레이어로 이루어질때, 두 플레이어 모두 필승법을 알고있으면 누가 이길것인가? 를 다루는 이론이다.
조건
- 두명의 참가자만 진행
- 두 참가자가 차례를 번갈아 진행
- 두 참가자가 게임에 대한 모든 정보를 공유, 필승법을 인지 하고있음
- 자신의 차례에 할 수 있는 행동이 단 하나도 없다면 패배
- 유한한 게임 진행
알고리즘
스프라그 그런디 정리란, 현재 게임판의 상태를 자연수(그런디 수)로 치환가능 하다는 이론이다.
이때 아무것도 할 수 없는 게임판의 그런디수는 0,
어떤 게임판 상태x에서 다른 게임판의 상태로 나아갈수 있을때
이런 게임판의 상태들의 그런디수의 집합을 Y로 두면,
해당 게임판의 그런디 수G는 mex(Y) 가 된다.
(mex(Y) : Minimum Excluded number, 집합Y에 속하지않은 정수중 가장 작은수)
(오타 : 집합중이아닌 집합에 속하지않은.)
두 게임판의 그런디수가 동일하다면 같은 상태임으로 정의 할 수 있다.
이때 그런디수가 0 이면 더이상 아무것도 할 수 없는. 선공이 패배(후공이 이긴 상태)하는 상태이고,
0 보다 큰 모든 경우는 한번의 행동으로 무조건 그런디수를 0 으로
만들 수 있으므로 선공이 승리할 수 있는 게임 상태이다.
이제 이 그런디수를 어떻게 활용할지 알아보자.
현재 n개의 게임판이 있고 각 게임판의 그런디 수가 Gn 라 할때,
이 게임판이 모두 동시에 진행되는. 이어진다면 전체 게임판의 그런디수 값은
모든 게임판의 상태를 순차적으로 XOR연산한 G1 ⊕ G2 ⊕ ''' ⊕ Gn 이 된다.
하나의 게임판을 볼때랑 마찬가지로, 이 값이 0이면 후공이 이기고, 0이 아니면 선공이 이기는거이다.
아래의 백준 온라인 문제은행의 11868번 문제를 보며 이해를 해보자.
관련 문제
https://velog.io/@cldhfleks2/11871 (님 게임 홀짝 풀이)
가장중요한 그런디수를 구할때 집합개념을 어떻게 사용하는지, 놓치면 안되는 중요한점을 상세히 풀어놓았다.
실제 알고리즘을 어떻게 구현할지에 필요한 점화식을 세우는 과정을 설명해놨다.
https://www.acmicpc.net/problem/11868 (님 게임2)
점화식이 필요없는 간단한 스플라그그런디알고리즘을 사용하는 문제.
n개의 돌무더기에 각각 P1, P2, P3... Pn개의 돌이 쌓아져 있을때
두 플레이어가 번갈아가며 하나의 돌무더기만 선택하여 그중 원하는 1개이상의 돌을 없애고,
최종적으로 모든 돌무더기의 맨 마지막 돌을 빼는 사람이 이기는 문제이다.
위에 설명한대로 n개의 게임판. n개의 돌무더기가 있고
하나의 돌무더기에서 돌의 갯수를 그런디수로 두면,
각각에서의 그런디수 모두 xor 연산하면 현재 이루어지는 전체게임의 그런디수가 정의된다.
왜 G = g1 ⊕ g2 ⊕ ''' ⊕ gn 일까?
필자의 생각이지만, 두 플레이어가 같은 필승법을 공유한다할때.
선공플레이어가 했던 필승법대로 후공플레이어도 알기에. 따라 한다치면은
결과적으로 두 플레이어가 같은 방법으로 진행시, 후공플레이어가 이기니까
따라서 같은 방법으로 하면 후공플레이어가 이기는 F가 되고,
둘이 다른 방법으로 진행시 선공플레이어가 이기는 T가되는
xor 연산을 사용하지않았나... 하는 직관적인 생각이다.
외부에 좋은 포스트가 있어서 링크를 남긴다..
https://casterian.net/algo/sprague-grundy.html
필자보다 더 자세히 설명해둬서 한번 정독 하면 좋겠다.
