게임 이론 (Game theory)

• 작성중

설명하기 쉽게 하기 위해서, 용어를 통일해서 쓰도록 하겠다. (통일하려고 노력해볼 것이긴 한데 잘 될지는 모르겠다..)

• 포지션: 현재 게임의 상태. 게임에서는 스테이트 대신에 포지션이 더 일반적인 것 같다.
• 승리 포지션: 현재 플레이어에게 필승 전략이 존재하는 포지션
• 패배 포지션: 무승부가 없는 게임에서, 현재 플레이어에게 필승 전략이 존재하지 않는 포지션

• 체르멜로 정리 : 2인 유한 턴제 확정 완전정보(2-person finite alternative deterministic game with complete information and alternating moves) 게임에서, 둘 중 한 명은 반드시 지지 않을 전략을 가지고 있다는 정리
• Strategy-stealing argument

• 가장 기본적인 형태의 게임이다.

• [TODO]: Subtraction game으로 용어를 바꾸자
• 기본 규칙은, 게임의 참여자들은 차례를 정해 1부터 31까지의 수를 순차적으로 부른다. 한번에 1~3개까지 수를 연달아 부를 수 있으며, 마지막 31을 부른 사람이 진다
• 승리 전략을 생각해보자
  • 내 차례에서 30을 부를수 있다면, 다음 상대방의 차례에서는 31을 부를수밖에 없으므로 상대방은 패배한다 (=내가 승리한다)
  • 내 차례에서 26을 부를수 있다면, 다음 상대방이, 1,2,3중 몇개의 수를 연달아 부르든 나는 4-{상대방이 부른 수}만큼을 연달아 불러서 30을 부를수 있다. 따라서 26을 부를수 있으면 승리한다.
  • 마찬가지로 내 차례에서 22를 부를수 있으면, 상대방이 어떻게 하든 내가 26을 부를수 있다. 따라서 내가 승리.
  • 이것을 반복하면, 4k+2 를 부르는 것을 유지하면 승리한다. 선공이 처음 시작할때 2를 부르고 이대로 유지하면 되므로 이 게임은 선공 필승 게임이다.
• 규칙을 일반화해보자. N을 부르면 이기고, 한번에 최대 M개까지의 수를 연달아 부를수 있는 게임이라고 하자. 위에서 설명한 규칙은 N을 부르면 지는 규칙이었는데, 이것은 N-1을 부르면 이기는 게임과 동일하다
  • N-(M+1)k 를 부르는 것을 반복하면 이길수 있다. 선공이 처음에 이 숫자를 부를수 있는 경우에는 승리, 그렇지 못하면 패배한다.
  • 식을 정리하면, N % (M + 1) == 0 이면 후공의 승리. 나머지는 모두 선공의 승리이다.
  • 만약, N을 부르면 지는 게임이라면 N % (M + 1) == 1이면 후공의 승리. 나머지는 모두 선공의 승리이다.
• 관련문제
  • Rozgrywka N을 부르면 이기는 배스킨라빈스 게임. N % (M + 1) == 0 인지를 체크하면 된다
  • 배스킨라빈스~N~귀엽고~깜찍하게~ N을 부르면 지는 배스킨라빈스 게임. N % (M + 1) == 1 인지를 체크하면 된다
  • 돌 게임, 돌 게임 2, 돌 게임 5: 한번에 부를 수 있는 숫자가 1개 또는 3개로 제한된 변형.
  • 21906 관찰을 통해서 배스킨라빈스 형태의 게임으로 변환 가능

• [TODO] P-포지션과 N-포지션으로 용어를 바꾸자
• 이제 배스킨라빈스에서 사용한 전략을 더 일반화해보자.
• 게임의 포지션들을 어떤 기준을 통해서 두가지 그룹으로 나눴을때, 최종 포지션중 패배 포지션들과 승리 포지션들은 다른 그룹에만 속해있다고 하자. 패배 포지션을 포함한 그룹의 포지션들을 L포지션, 승리 포지션을 포함한 그룹의 포지션들을 W포지션이라고 하자.

• W포지션에서 어떤 액션을 취하든 L포지션으로 이동되고, L포지션에서 어떤 액션을 취하든 W포지션으로 이동되는 경우이다.
• 이 경우는 매우 간단하다. W포지션들은 모두 승리 포지션이고, L포지션들은 모두 패배 포지션이다.
• 여기서는 승리 전략이랄것도 없다. 자기턴에 승리 포지션이었다면, 어떤 액션을 취하든 이길 수밖에 없다. 지는것이 오히려 불가능하다.
• 17783을 예로 들어보자.
  • 길이가 x1, x2, …, xn인 나뭇가지들이 있을때, 부러트릴수 있는 남은 횟수는 (x1-1)+(x2-1)+…+(xn-1)이다.
  • 어떤 나뭇가지의 어떤 위치에서 부러트리든, 부러트리고 나면 부러트릴수 있는 남은 횟수가 1만큼 줄어든다.
  • 포지션들을 부러트릴수 있는 남은 횟수가 홀수인 그룹과, 짝수인 그룹으로 분류하면, 어떤 액션을 취하든 현재 포지션을 다른 그룹의 포지션으로 변환하게 된다.
  • 남은 횟수가 0일때가 패배포지션이므로, 남은 횟수가 짝수일때는 모두 패배포지션, 홀수일때는 모두 승리포지션이 된다.
• 한개 더, 돌무더기 게임 1을 생각해보자.
  • 여기에서는 어떤 액션을 취하든 돌무더기 세개의 홀짝성을 바꾸게 된다. 포지션들을 돌이 홀수개 남아있는 돌무더기의 갯수를 기준으로 분류해보자, 갯수가 홀수인 무더기가 0개 또는 1개인 그룹과, 갯수가 홀수인 무더기가 1개 또는 2개인 그룹으로 나누면, 모든 액션은 현재 포지션을 다른 그룹의 포지션으로 바꾸게 된다.
    • 홀홀홀 ↔ 짝짝짝, 홀홀짝 ↔ 짝짝홀
  • 이 게임에서의 승리 포지션은 더이상 취할수 있는 액션이 없는 상태이다. 즉 돌이 0,0,X개 또는 0,0,0개인 상태이고. 이 상태들은 모두 갯수가 홀수인 무더기가 0개 또는 1개인 그룹에 속한다.
  • 따라서 간단하게, 갯수가 홀수인 무더기가 0개 또는 1개인 상태는 모두 승리 포지션, 그렇지 않은 상태는 패배 포지션이라는 것을 알수 있다.

• 이제 조금 더 조건이 완화된 경우이다. L포지션에서 어떤 액션을 취하든 W포지션으로 이동되어야 하는것은 같지만, W포지션에서는 L포지션으로 이동시킬 방법이 적어도 한가지 있는 경우이다
• 이때도 결론은 동일하다. W포지션들은 모두 승리 포지션이고, L포지션들은 모두 패배 포지션이다.
• 배스킨라빈스도 이 경우이다. 4로 나눈 나머지가 2인 포지션들(L포지션)과 나머지 포지션들(W포지션)의 두 그룹으로 나눌수가 있고, L포지션에서 1,2,3중 어느것을 불러도 W포지션으로 가게 된다. 그리고 W포지션에서는 L포지션으로 이동할 방법이 있다.
• 좀더 복잡하지만 님 게임도 여기에 해당한다. 스프라그-그런디 정리를 쓰지 않고도 분석이 가능하다. xor합이 0인 포지션들과 나머지 포지션들로 나눌수 있다. 어떤 파일에서 몇개를 제거하더라도 xor합은 변하게 되므로, xor합이 0인 포지션(L포지션)에서는 항상 다른 포지션(W포지션)으로 가게 된다. 그리고 현재 xor합이 얼마이든, 돌을 제거해서 xor합을 0으로 바꾸는 것은 항상 가능하다. 현재의 xor합에서 최상위 비트를 찾고, 거기에 그 비트가 켜져있는 수를 갖는 파일을 찾아서 그 파일에서 xor합이 0이 되도록 돌을 제거해주면 된다.
• 관련 문제 : 팰린드롬 게임

• 24553
• 26973

• 2차원 보드. 점대칭 위치에 두기
  • 16884
  • 26074
  • Постройка дороги

• 여기서 설명할 방법들은 앞에서 설명한 방법과는 조금 다른데, 승리하는 전략이 존재한다는 것을 찾아낼 수는 있지만, 승리하는 전략이 뭔지는 알아내지 못한다는 것이다.
  • 실질적으로는, 모든 포지션에 대해서 승리 포지션인지 여부를 찾을 수 있다면, 승리 전략은 바로 도출된다. 이 방법을 특정 포지션뿐 아니라 모든 포지션에 적용할수 있다면, 승리 전략도 알수 있다.

• 선턴 플레이어가 선후공을 고를수 있는 방법이 있다고 하자. 예를 들자면 아무 액션도 취하지 않는 '패스'라는 액션을 맨 첫턴에만 선택할수 있다고 하자. 그러면 선턴 플레이어는 '패스'라는 액션을 취함으로서 실질적으로는 후공을 선택한것과 같은 효과를 내게 된다.
• 이런 게임이 있다면, 선턴 플레이어는 항상 승리할수 있다. 선공에게 필승법이 있다면 선공을 선택하고, 후공에게 필승법이 있다면 후공을 선택하면 된다.
• 이런 게임의 예제는 약수 지우기 게임 1 이다.
  • 1~N 까지의 카드가 주어지는 초기 상태에서, 선플레이어는 '1'만 가져가든가 '1'과 다른 숫자들을 가져가거나 하는 두가지 선택을 할 수 있다. 뭘 하든 '1'은 항상 가져가게 되고, 후턴 플레이어에 차례에는 '1'이 남지 않는다.
  • 2~N 까지의 카드를 갖고 시작하는 게임을 생각해보자. 이 게임에서 선공에게 필승법이 있고 그 방법이 카드 x,y,z를 가져가는 것이라면, 선공은 처음에 1과 x,y,z를 가져간 뒤에 그 필승법에 따라서 움직이면 된다. 2~N 게임에서 후공에게 필승법이 있다면, 선공은 처음에 '1'만 가져가고, 2~N 게임의 후공의 역할로 플레이하면 이길수 있다.
• 예제
  • 4342
  • 게임이론

• 간단한 논리를 통해서 답이 잘 안나온다면, 컴퓨터의 계산능력을 이용해서 문제를 푸는것이 PS에 임하는 사람으로써의 올바른 자세이다.
  • 그냥 딱 보고 규칙이 안떠오르면, 괜히 더 고민하지 말고 바로 컴퓨터로 일일히 구해보는 것이 차라리 효율적인 경우가 많다. 실제로 규칙성이 존재하는 문제이고, 생각을 충분히 하면 논리적으로 그 규칙을 찾는 것이 가능했을지라도, 그것보다 그냥 빠르게 컴퓨터로 계산해보고 그 결과로부터 패턴을 분석해서 규칙을 찾는 것이 더 효율적인 경우가 많다.
• 일일히 결과를 계산해보는 것은 많은 경우에는 DP를 이용해서 효율적으로 처리가 가능하다. 대부분 경우, 어떤 포지션에서 이동 가능한 포지션들을 연결했을때 DAG를 이루게 되고, 따라서 DP를 이용해서 효율적으로 구할수 있다.
  • 아주 드물게 포지션 공간이 너무 스파스하게 많고, 최종 포지션까지의 이동 경로가 매우 긴 경우도 있기는 하다. 그래서 그냥 백트래킹을 써야 하는 경우도 있다.
• DP를 이용해서 규칙을 찾을 때에는 매우 정형화된 형태의 코드로 처리가 가능하다.
  • 다만, 상황에 따라서는 bottom-up 대신 top-down으로 구현하는 것이 더 효율적인 경우도 있고, bottom-up의 경우에도, 다음 포지션들의 값으로부터 현재 포지션을 업데이트 하는 방식 대신에, 현재 포지션의 결과로부터 다음 포지션들의 값을 업데이트 하는 방식이 더 효율적인 경우도 있다.

• 기본적인 bottom-up DP의 구현은 아래처럼 된다.
  • 이 방법은 포지션들에 대한 값을 채워나갈때, 최종포지션을 가장 먼저 채우고, 그 이전 포지션들을 차례대로 계산해 나가서, 마지막으로 시작포지션에서의 승패여부를 계산한다. 최종포지션에서 시작포지션까지 DAG에서의 위상순서대로 이터레이션하는 것이 간단하게 가능할때 사용하면 된다. ordered_positions 에는 그 순서대로 정렬된 포지션들을 넘겨주면 된다. 말이 복잡하지만, 돌 제거하는 게임을 예로 들면, 돌이 n개에서 시작해서 점점 줄어들다가 0개가 되면 끝나므로, ordered_positions에서는 그냥 [0, 1, …, n] 또는 range(n+1)을 주면 된다.

  • def compute_game(ordered_positions, get_next_positions, is_win_pos=None):
        is_win_pos = is_win_pos or {}
        for pos in ordered_positions:
            is_win_pos[pos] = any(
                not is_win_pos[next_pos] for next_pos in get_next_positions(pos)
            )
        return is_win_pos

• 돌 게임 4을 이 함수를 이용해서 구현해보면 이런 식이 된다.
  • 마지막 돌을 가져가면 진다는 것은, 내 차례에 돌이 하나도 없는 상태로 이동하면 상대방이 이긴다는 뜻이다. 즉 돌이 0개 있는 포지션을 승리 포지션이라고 생각하면 된다. 돌이 0개 있을때는 승리라는 것을 알고 있으니, 돌이 1개~N개일 때를 DP로 구해주면 된다.

  • def get_next_positions(pos):
        if pos >= 1:
            yield pos - 1
        if pos >= 3:
            yield pos - 3
        if pos >= 4:
            yield pos - 4
            
    def main():
        N = int(input())
        is_win_pos = compute_game(range(1, N + 1), get_next_positions, {0: True})
        print('SK' if is_win_pos[N] else 'CY')

• 하지만 물론 dp 테이블을 채우는 함수 자체가 매우 단순하기 때문에, 굳이 이것을 compute_game 함수로 뽑아서 쓰는것은 비효율적이다. 이렇게는 개념적으로만 이해하고, 실제로는 그냥 메인 로직에 합쳐서 써도 가독성을 해치지 않고 더 효율적이다.
  • 돌 게임 4 을 이렇게 다시 구현하면 다음처럼 된다.

  • def main():
        N = int(input())
        is_win_pos = [True]
        for i in range(1, N + 1):
            is_win_pos.append(
                any(not is_win_pos[i - x] for x in (1, 3, 4) if i - x >= 0)
            )
        print('SK' if is_win_pos[N] else 'CY')

• 한줄 요약: 이전 포지션을 구하는 것이 용이하다면, 이전 포지션을 이용해서 DP를 작성하자.
• 내가 DP를 풀 때 점화식을 쓰는 원칙은 동적 계획법에서도 언급했던것처럼, 더 작은 상태들의 값들로부터 현재 상태의 값을 업데이트하는 형태로 쓰는 것이다.
  • 이것의 반대는 현재 상태의 값으로부터 더 큰 상태들의 값을 업데이트 하는 방식이다.
  • 예를 들면, dp[i] = f(dp[i-1]) 으로 쓰도록 하고, dp[i+1] = f(dp[i]) 으로 쓰지 않는 것을 원칙으로 한다는 말이다
• 위에서도 이 방식으로 점화식을 세웠다. 이동가능한 다음 포지션들의 값으로부터 현재 포지션의 값을 업데이트 하는 방식이다.
• 하지만 만약, 현재 포지션으로 이동할수 있는 이전 포지션들을 구하는 것이 간단하다면, 반대방향으로 점화식을 구현하는 것이 더 효율적이다. 현재 포지션이 패배포지션이라면, 현재 포지션으로 이동할수 있는 모든 포지션들은 승리포지션이 된다.
• 코드로 표현하면 이런 방식이 된다.

  • def compute_game(ordered_positions, get_prev_positions, is_win_pos=None):
        is_win_pos = is_win_pos or {}
        for pos in ordered_positions:
            if not is_win_pos[pos]: 
                for prev_pos in get_prev_positions(pos):
                    is_win_pos[prev_pos] = True
        return is_win_pos

• 앞에서의 compute_game 함수와 비교하면, 앞에서는 항상 내부 루프를 돌아야 했는데, 여기에서는 is_win_pos[pos] 가 False 인 경우에만 내부 루프를 돌게 된다.
• 내부 루프의 크기가 큰 문제 (=어떤 포지션에서 취할수 있는 액션이 많은 게임) 에서는, 두가지 방식이 꽤 큰 성능차이를 보이기도 한다.
• 16888은 현재 포지션이 n일때, 취할수 있는 액션은 n 이하의 제곱수를 빼는 것이다. 액션의 갯수가 O(sqrt(n))개로 총 시간복잡도가 O(n*sqrt(n))이 되는 문제이다. 이 문제를 두가지 방법으로 구현하면 이렇게 된다.
  • 다음 포지션으로부터 현재 포지션을 업데이트

    • is_win_pos = [False] * (max_n + 1)
      sq_nums = [j * j for j in range(1, math.isqrt(max_n) + 1)]
      for i in range(1, max_n + 1):
          for sq in sq_nums:
              if sq > i:
                  break
              if not is_win_pos[i - sq]:
                  is_win_pos[i] = True
                  break

  • 현재 포지션으로부터 이전 포지션을 업데이트

    • is_win_pos = [False] * (max_n + 1)
      sq_nums = [j * j for j in range(1, math.isqrt(max_n) + 1)]
      for i in range(max_n + 1):
          if not is_win_pos[i]:
              for sq in sq_nums:
                  if i + sq > max_n:
                      break
                  is_win_pos[i + sq] = True

  • 두 코드는 비슷하지만, 후자쪽이 훨씬 빠르다. python 3.11 기준으로 후자는 880ms 에 통과되었고, 전자는 4초를 초과해서 시간초과가 났다. (pypy로는 통과함)

• 16571
• 16888
  • prev state를 계산 가능하면 이쪽을 쓰는게 더 빠르다.
• 15877
  • prev state를 계산 가능하면 이쪽을 쓰는게 더 빠르다.

• 돌 게임 6 은 결

• 스프라그-그런디
• 스프라그 그런디를 쓰러면 게임이 normal play여야 한다.

• nim
• 스프라그-그런디 정리를 적용하기에 최적화된 게임..
• 원래 많이 플레이되는 버전은 마지막에 막대를 가져가면 패배하는 misère nim이지만, 게임이론에서 분석할때에는 마지막에 막대를 가져가면 승리하는 normal nim을 기본으로 이야기한다
• 관련 문제: 님 게임 2

• 미제르 님
  • 대부분의 경우에 승리포지션은 노멀 님과 동일하다. 단, 모든 파일에 막대기가 1개씩만 남았을 경우에만 노멀 님과 반대가 된다. 모든 파일에 막대기가 1개씩만 남았을 경우, 노멀 님에서는 파일의 갯수가 짝수개일때가 승리포지션이지만, 미제르 님에서는 파일의 갯수가 홀수개일때가 승리포지션이 된다.
  • 미제르 님에서의 필승 전략은, 노멀 님에서의 승리포지션을 유지하다가, 마지막 무브에서만 모든 파일에 막대기가 1개씩만 있고 파일의 갯수가 홀수개인 상태로 만들어주는 것이다
  • 승리포지션을 여부를 확인하는 것도, 모든 파일에 막대기가 1개씩만 있을때에만 파일의 갯수에 따라서 결정하고, 나머지 포지션은 똑같이 grundy 수를 계산해서 0이 아닌지를 확인하면 된다
  • 관련 문제: 님 게임

• 돌 추가가 가능한 님
  • 파일 한개에서 돌을 제거하는 행동 외에도, 돌을 추가하는 행동도 가능한 버전.
  • 상대가 x개의 돌을 추가하면 나는 다음턴에 그대로 x개의 돌을 제거해서 원래 포지션으로 돌려놓을수 있다. 결국 돌 추가 행동은 게임에 영향을 주지 않고, 일반 님에서의 승리/패배 포지션 공식이 그대로 유지된다
  • 돌 추가를 무한하게 반복해서 게임이 종료되지 않는 것을 방지하기 위해, 돌 추가 행동의 시행 횟수에는 제한이 있어야 한다.

• staircase nim
  • 돌의 갯수가 같은 파일 K개에서 돌을 1개씩만 제거할수 있다.
  • 파일이 한개면 그냥 홀짝성으로 승패가 결정된다.
  • 돌의 갯수가 짝수인 파일들에서 돌을 1개씩 제거하는 것은, 다음턴에 상대가 다시 그 파일들에서 돌을 제거할수 있게 만든다. 결국, 짝수인 파일들에서 돌을 제거하는 행동은 의미가 없고, 나아가면 돌의 갯수가 짝수인 파일들은 그냥 돌이 없다고 치고 게임을 생각해도 상관없다.
  • 그러면, 돌의 갯수가 홀수인 파일들만 생각하자. n개의 파일이 같은 갯수의 돌을 갖고 있다. 이중에서 k개의 파일에서 돌 한개씩을 제거하면 k개의 파일은 그냥 없어진다고 생각해도 된다. 관점을 바꾸면, n개의 돌이 있는 파일에서 k개의 돌을 제거한다고 생각할수 있고, 이러면 그냥 노멀 님 게임으로 변환이 가능하다.
  • 예를 들어서 돌의 갯수가 [1,1,1,1,2,2,2,3,3,4] 이런 식의 staircase nim 이라면, 홀수개 파일은 제거하고 짝수개 파일은 2가 3개 4가 1개이므로 [3,1] 의 일반 nim 게임이라 생각할수 있다.

• 배스킨라빈스
  • N에서 출발해서 1~M까지의 수만큼 줄여나가서, 0을 부르는 사람이 이기는 게임
  • 이 게임의 그런디 수는 N%(M+1) 이다

• 2600
• 11683 파일마다 그런디 따로 계산

• staircase nim
• 8170

• 위에서 보던 게임들은 어떤 플레이어가 특정 포지션에 도달하면 게임이 종료되고, 그 플레이어가 승리 또는 패배하는 문제였다.
• 내가 스코어링 게임이라고 이름 붙인 게임 유형은, 선공은 점수를 높이는 쪽으로 행동하고, 후공은 점수를 낮추는 쪽으로 행동한 뒤에, 게임이 종료되었을때 얻을수 있는 가장 높은 점수를 구하는 문제이다.
  • 이때 게임이 종료되는 조건은, 특정 포지션에 도달했을때일수도 있고, 단순히 N턴이 지났을때일수도 있고 다양하다.
• 승리시에는 1점, 패배시에는 -1점을 얻는다고 생각하면 위에서 보던 게임들도 스코어링 게임에 포함되긴 한다.
• minimax DP를 사용해서 구현해야 한다
• 기본 형태는 이렇게 된다
  • …

• 선공과 후공이 각자의 점수를 올리고, 게임 종료 후에 점수가 높은 플레이어가 이기는 형태의 게임이다.
• 이것을 각 포지션마다 선공의 점수와 후공의 점수를 모두 유지하면서 계산하려고 하면 조금 번거롭다. 다음과 방법으로 좀더 간단하게 처리할수 있다.

• 두 사람이 얻는 점수의 총합이 정해져있는 경우는 간단하게 선공의 점수만 갖고 계산하면 된다. 게임이 종료된 뒤에, 선공의 점수가 점수총합의 절반 이상인지를 따져서 승패를 확인할 수 있다
  • 특히 이 경우에는 코드가 매우 간단해진다. 현재 포지션에서 얻을 수 있는 점수의 총합을 구해두면, 현재 포지션에서 취하는 액션에 따라 얻는 점수를 계산하지 않고서도, 선공의 최대 점수를 다음처럼 구할수 있다.
    • max_score[pos] = remaining_score[pos] - min(max_score[next_pos])
• negamax 알고리즘?? 이거랑은 좀 다른거 같기도 한데..
• 관련문제:
  • 동전 게임
  • 기부왕의 님게임

• 점수의 총합이 정해져있지 않은 경우에는, 점수를 {선공점수 - 후공점수} 의 하나의 점수로 생각해서 계산할 수 있다. 선공은 이 점수를 높이는 쪽으로, 후공은 이 점수를 낮추는 쪽으로 행동할것이고, 게임종료 후에 이 점수가 0보다 크면 선공의 승리, 0보다 작으면 후공의 승리, 0이면 무승부가 된다.
  • 다음처럼 식이 세워진다
    • max_score[pos] = max(score_gain(pos, next_pos) - max_score[next_pos])
• 소수 징글벨 을 예로 들어 두 방법을 비교해보자. 문제에서 주어진 게임은 1부터 시작해서 두 플레이어가 번갈아가면서 최대 a개의 다음 수들을 가져가고, 그중에 포함된 소수의 갯수만큼 점수를 얻는다. b까지 가져가면 게임이 끝난다.
• 두 플레이어의 점수의 총합은 b이하의 소수의 갯수가 된다. 지금 n까지 가져간 상태라면, 이제부터 얻을수 있는 점수의 총합은 [n+1,b] 범위의 소수의 갯수이다.
• 이것을 바탕으로 선공의 최대 점수를 찾는 방식으로 구현한 코드는 이런식이다

  • max_score = [None] * (b + 1)
    max_score[b] = 0
    remaining_score = 0
    for i in reversed(range(b)):
        if i + 1 in primes:
            remaining_score += 1
            max_score[i] = remaining_score - min(
                max_score[j] for j in range(i + 1, min(i + a, b) + 1)
            )
    
    first_score = max_score[0]
    second_score = remaining_score - first_score

• 만약 두 플레이어의 점수의 총합이 일정하다는 점을 활용하지 못하고, {선공점수 - 후공점수} 를 최대화하는 방식으로 구현한다면 다음처럼 된다

  • max_score = [-INF] * (b + 1)
    max_score[b] = 0
    for i in reversed(range(b)):
        score_gain = 0
        for j in range(i + 1, min(i + a, b) + 1):
            if j in primes:
                score_gain += 1
            max_score[i] = max(max_score[i], score_gain - max_score[j])
    
    score_diff = max_score[0]

• 실제로 소수 징글벨에 제출했을때에는 1136ms vs 4444ms 로 전자가 훨씬 빨랐다

• bottom-up dp
  • 3032 - 원형에서 구간dp
  • 2040 - 기본 dp. 여기에 dp 최적화를 할수있다
• top-down dp
  • 25949
    • bottom-up으로 하면 4차원 dp 테이블을 채워야 해서 불편하다..
• 최적화
  • 8196

• Wythoff's game
• 체스판의 왼쪽 위 코너에서 오른쪽, 아래쪽, 오른아래 대각선 중 한가지 방향으로 번갈아가면서 퀸을 이동시켜서 이동못하는 사람이 지는 게임
• 님처럼 바꾸면, 두개의 파일이 주어지고, 번갈아가면서 한쪽 파일에서 돌을 제거하거나, 두개 파일에서 동시에 같은 갯수만큼 돌을 제거.
• 패배 포지션은 아래에 해당되는 $(n_{k}, m_{k})$이다. $ \phi$는 황금비이다
  • $ n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\ $
  • $ m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\ $
• 이 공식을 이용하면, 주어진 포지션이 승리 포지션인지는 아래처럼 계산 가능

def is_win_pos_in_wythoff_game(x, y):
    x, y = sorted((x, y))
    k = math.ceil(x / PHI)
    return (int(k * PHI), int(k * PHI_SQ)) != (x, y)

• 관련문제
  • Cow Checkers

• 23974 - 승리조건이 따로 있는 문제. dp로 결과값을 출력해보면서 패턴을 찾는다.
• 24656 - b^k 개를 제거할수 있는 게임. 논리로 그런디수의 패턴을 찾을수 있다
• 5386 - 24656과 동일한게임인데. 그런디까지는 필요없고, 그냥 승패 + 승리전략의 첫수.
• 5945 - 스코어링 게임을 dp로 푸는 기본적인 예..인데, 토글링을 안해주면 메모리초과가 난다. 11062와 똑같은 문제
• 18540 - 간단한 논리로 아주 단순한 공식을 찾을수 있다
• 16142 - '현 위치에서 돌을 제거한뒤 위치를 이동시키는' 게임. 선턴 플레이어가 실질적으로 선후공을 고를 수 있는 경우.
• 3358 - DP로 승패를 계산하는 기본문제. 돌무더기 한개에서 1,K 또는 L개를 제거할수 있는 님.
• 16443 - Wythoff game에서 grundy수를 dp로 계산하는 문제
• 1542 - 16443과 동일한 문제
• 11757 - DP로 풀수 없는 스코어링게임. 이분탐색을 사용한다
• 27528 - negamax를 쓰기 까다로운 스코어링게임. min과 max를 모두 유지하는 식으로 dp를 풀어야 하고, 포지션을 정의하는 것도 트리비얼하지는 않다
• 19954 - 게임이론과는 거리가 멀어보이는 문제. 태그는 잘못 붙은듯 하다.
• 6120 - DP로 승패를 계산하는 기본문제. 딱봐도 패턴이 없을것같은 문제이다. 1519와 유사한 문제
• 10363 - 기본적인 스프라그 그런디. 포지션 트랜지션이 아예 트리형태로 주어진다,

• 23066 - '현 위치에서 돌을 제거한뒤 위치를 이동시키는' 게임. 1개만 남기고 다 제거해서 선택지를 주지 않는 기본 전략. 인터랙티브
• 4148 - DP로 승패를 계산하는 임파셜게임. 남은 카드별 갯수들로 포지션이 정의되기 때문에 tuple로 표현해야 한다. top-down dp.
• 8817(실4) - 그냥 기본적인 배스킨라빈스 게임.
• 25179(실4) - 그냥 기본적인 배스킨라빈스 게임.
• 11307(골1) - 1차원 배열에서, 양 끝중 하나에서 번갈아가며 원소를 제거하는 게임. 19504와도 같은 규칙이지만 목표는 다르다. 재미있는 성질이 많은 게임이라 나중에 발견한 점들을 한번 정리해볼수도.
• 3754(플2) - 기본적인 미제르님. 11694와 동일
• Splitting Pairs(플5) - 논리로 규칙을 찾는 임파셜게임. 님게임의 변형 룰이지만 스프라그-그런디는 필요없다.