Game Theory (2) 썸네일형 리스트형 63. Nim Game & Sprague-Grundy Theorem 님 게임(Nim Game)은 간단하면서도 게임 이론에서 중요한 역할을 하는 게임으로, 여기서 사용된 전략을 다른 많은 게임에 응용해서 적용할 수 있다. 님 게임은 $0$개 이상의 돌이 있는 $n$개의 더미에서 번갈아 가면서 돌을 가져가는 방식으로 차례를 진행한다. 가져가는 돌의 개수에는 제한이 없지만 한 차례에는 하나의 더미에서만 돌을 가져갈 수 있다. 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 지게 된다. 님 게임에서 각각의 더미에 남아 있는 돌의 개수를 $[x_1, x_2, \ldots x_n]$이라고 하면 이 게임의 상태를 님 합(Nim Sum)으로 분류할 수 있다. 님 합 $s = x_1 \oplus x_2 \oplus \ldots \oplus x_n$이며, $\oplus$는 XOR 연산을 .. 62. Game Theory 게임 이론(Game Theory)은 상호 의존적이고 이성적인 의사 결정을 다루는 이론이다. 게임(Game)은 각각의 행위자들이 일정한 전략을 가지고 최고의 보상을 얻기 위해 벌이는 행위를 말하며, 알고리즘 문제에 적용할 경우 게임에서 승리하거나 최대한 좋은 결과를 얻기 위해 적절한 전략을 가지고 플레이하는 것을 의미한다고 할 수 있다. 게임 이론에서 모든 참가자는 최선의 선택을 하며 다른 참가자들 역시 최선의 선택을 할 것이라는 사실을 알고 있다고 간주한다. 또한 다음과 같은 사항이 존재한다. 모든 참가자는 정보를 가지고 있다. 게임의 초기 상태가 존재한다. 게임의 순서와 정해진 규칙이 존재한다. 참가자는 가능한 선택 중 어떤 것이든지 할 수 있다. 대부분의 게임은 다음과 같은 추가적인 제한을 갖는다. .. 이전 1 다음
