나는 게임이론 문제 풀 때 스프라그-그런디 정리 생각 안하고
게임 자체를 브루트포스로 구현하고
작은 n에서 규칙성을 찾고
그 규칙성을 O(1) 또는 O(n)으로 조건문으로 구현하는 식으로 풀거든?
근데 그러기조차 어려운 문제들이 간혹 있더라고
사실 생각해보면 게임 이론 문제는 대부분 님 게임의 확장 아님?
그러면 대부분 여러 조건 분기랑 xor연산으로 풀리는 게 아닐까 궁금하네
게임 자체를 브루트포스로 구현하고
작은 n에서 규칙성을 찾고
그 규칙성을 O(1) 또는 O(n)으로 조건문으로 구현하는 식으로 풀거든?
근데 그러기조차 어려운 문제들이 간혹 있더라고
사실 생각해보면 게임 이론 문제는 대부분 님 게임의 확장 아님?
그러면 대부분 여러 조건 분기랑 xor연산으로 풀리는 게 아닐까 궁금하네
Grundy Number가 만능은 아니에요. XOR과 MEX라는 굉장히 비직관적인 연산들을 쓰는지라 Grundy Number의 규칙성 찾기가 굉장히 까다로운 편이고, NIM GAME을 작은 NIM GAME으로 쪼개서 Grundy Number를 XOR하는 경우, 그 작은 NIM GAME들로 어떻게 쪼개지는지 찾는것도 일입니다. 그래서 규칙성 찾기 너무 어려워서 작은 n에 대해서 시뮬레이션 하면서 Grundy Number가 이런 공식으로 써지지 않을까? 추측하는 경우도 많습니다. 그리고 Grundy Number 말고 Tree DP 같은 경우로 Win/Lose만 판단하는 경우도 많고요
https://www.acmicpc.net/problem/28407
이런 문제처럼 아주 높은 난이도로 가면 NIM GAME 이외의 게임문제가 나와서 Grundy Number로 접근할 수 없는 문제도 나오긴 합니다. (Combinatorial Game Theory 혹은 Hot/Cold Game 참고)
자세한 답변 감사합니다