알고리즘/수학
2021. 3. 13.
스프라그–그런디 정리
게임 이론에 대해 알아봅시다. 하나의 게임은 몇 명의 참가자와 참가자들이 할 수 있는 행동, 그리고 이 행동 조합에 따라 받게 되는 보상으로 구성됩니다. 이러한 게임 중 여기에서 다루고자 하는 게임은 다음과 같은 조건을 만족하는 게임입니다. 1. 두 명의 참가자가 진행합니다. 2. 두 사람이 차례를 가지고 번갈아가며 진행합니다. (순차적 게임) 3. 모든 참가자가 게임에 대한 모든 정보를 공유합니다. (완전 정보 게임) 4. 자신의 차례에 할 수 있는 행동이 하나도 없으면 패배합니다. (일반 게임) 5. 게임이 무한히 진행되지 않습니다. 이런 복잡한 조건들을 만족하는 게임이 대체 뭐가 있냐고 생각하실 수 있지만, 이를 만족하는 간단한 게임이 있습니다. 바로 "베스킨라빈스 31"이라는 게임입니다. 두 명이..