NIM GAME (님 게임)

1. 님 게임의 규칙

 

님(Nim)은 수학적 전략 보드 게임이다. 몇개의 줄에 숫자나 자연수개의 돌을 두고 순서대로 돌아가면서 한 줄에서 정해진 수의 숫자를 제거한다. 가져오는 숫자에는 상한이 있으며 무조건 1개는 가져와야 한다. 마지막 돌을 가져오는 사람이 이긴다.

 

2. 님 게임의 필승 전략

 

일단 박스에 담겨져 있는 구슬을 2진수화 한다.

예를 들어 박스 2개에 구슬이 각각 3, 2개가 들어 있다면

0 1 1        : 3개

0 1 0        : 2개

 

이때 각 열(column)의 1의 개수가 짝수라면 (0도 짝수에 포함) 이를 상태 A라 하자. 짝수가 아닌게 적어도 하나가 있다면 상태 ~A 라 하자.

위 예제는 상태 ~A이다.

따라서 필승전략을 하려면 다음 두가지 조건을 증명해야한다.

 

1. 상태 A에서 아무 박스에서 아무 개수의 돌을 꺼내오면 무조건 상태 ~A가 된다 (역은 성립하지 않음.)

2. 상태 A~에서 A로 갈 수 있는 방법이 무조건 존재한다.

 

이 두가지를 증명해야 항상 이길 수 있는 필승전략이 증명된다고 할 수 있다. ( 여기서 증명하지는 않겠다. )

그 이유는 다음과 같다.

상대 턴에는 항상 상태 A가 나와야 하고, 상대 턴이 끝나고 상태 ~A가 된다.

이때 나의 턴에 상태 A로 만들게 된다면, 턴을 주고 받으면서 구슬 개수가 줄어들다가 결국 마지막에는 박스 안에 아무것도 남지 않는 상태가 되기 때문이다. (아무것도 없는 것은 상태 A)

 

3. 님 게임 프로그램

 

다음 프로그램은 bot과 님게임을 하는 프로그램이다. bot은 항상 필승전략에 따라 게임한다.

항상 내가 첫턴이고 봇은 다음턴이다.

만약 상태 A로 박스와 구슬이 주어진다면 봇은 항상 필승하게 된다.

 

게임 방법

 

1. 박스 수를 입력한다.

2. 각 박스에 담겨있는 구슬 수를 입력한다.

3. 턴마다 자신이 선택할 박스 번호명과 그 안에서 꺼낼 구슬 수를 입력한다.

4. 마지막 구슬을 꺼내는 사람이 이긴다.

 

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

#include <stdio.h>   void bot(int *box, int status, int *bot_box, int *bot_amount, int n); void set_status(int amount, int *status);   int main() {     int n;     int i;     int box[101];                        //box 제한 수 100개 그 안의 코인 제한 수 2억     int total_amount = 0;     int player_box, player_amount;     int bot_box, bot_amount;     int status = 0;       printf("Please Input the number of box : ");     scanf("%d", &n);       printf("Please Input the number of coin in each boxes : ");     for (i = 1; i <= n; i++)     {         scanf("%d", &box[i]);         total_amount += box[i];         set_status(box[i], &status);     }       while (1)     {         printf("Your turn (box and amount) : ");         scanf("%d %d", &player_box, &player_amount);         if (!(player_box <= n && 1 <= player_box && player_amount <= box[player_box] && 1 <= player_amount))         {             printf("Please Input correct box or amount!\n");             continue;         }         printf("You take %d coin(s) in box %d\n",player_amount, player_box);           set_status(box[player_box] ^ (box[player_box] - player_amount), &status);         box[player_box] -= player_amount;         total_amount -= player_amount;           printf("Box : ");         for (i = 1; i <= n; i++)             printf("%d ", box[i]);           if (!total_amount)         {             printf("\nGame End. You Win!\n");             return 0;         }           bot(box, status, &bot_box, &bot_amount, n);           printf("\nBot take %d coin(s) in box %d\n", bot_amount, bot_box);           set_status(box[bot_box] ^ (box[bot_box] - bot_amount), &status);         box[bot_box] -= bot_amount;         total_amount -= bot_amount;           printf("\nBox : ");         for (i = 1; i <= n; i++)             printf("%d ", box[i]);           if (!total_amount)         {             printf("\nGame End. Bot Win!\n");             return 0;         }       }            return 0; }   void bot(int *box, int status, int *bot_box, int *bot_amount, int n) {     int i;     int temp;       if (status != 0)     {         for (i = 1; i <= n; i++)         {             if ((temp = status ^ box[i]) < box[i])             {                 *bot_box = i;                 *bot_amount = box[i] - temp;                 return;             }         }     }     else     {         for (i = 1; i <= n; i++)         {             if (box[i])             {                 *bot_box = i;                 *bot_amount = 1;                 return;             }         }     } }   void set_status(int amount, int *status) {     *status = *status ^ amount; }