27_game_theory.c - Examples

  1/*
  2 * 게임 이론 (Game Theory)
  3 * Nim 게임, Sprague-Grundy, Minimax
  4 *
  5 * 2인 게임의 최적 전략을 찾는 알고리즘입니다.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11#include <stdbool.h>
 12#include <limits.h>
 13
 14#define MAX_N 1001
 15
 16/* =============================================================================
 17 * 1. Nim 게임
 18 * ============================================================================= */
 19
 20/* Nim 게임: 여러 더미에서 돌을 가져가는 게임
 21 * 마지막 돌을 가져가는 사람이 승리
 22 * XOR이 0이면 현재 플레이어 패배, 아니면 승리 */
 23bool nim_game(int piles[], int n) {
 24    int xor_sum = 0;
 25    for (int i = 0; i < n; i++) {
 26        xor_sum ^= piles[i];
 27    }
 28    return xor_sum != 0;
 29}
 30
 31/* 승리 전략: XOR을 0으로 만드는 수 찾기 */
 32void nim_winning_move(int piles[], int n, int* pile_idx, int* take) {
 33    int xor_sum = 0;
 34    for (int i = 0; i < n; i++) {
 35        xor_sum ^= piles[i];
 36    }
 37
 38    if (xor_sum == 0) {
 39        *pile_idx = -1;
 40        *take = -1;
 41        return;
 42    }
 43
 44    for (int i = 0; i < n; i++) {
 45        int target = piles[i] ^ xor_sum;
 46        if (target < piles[i]) {
 47            *pile_idx = i;
 48            *take = piles[i] - target;
 49            return;
 50        }
 51    }
 52}
 53
 54/* =============================================================================
 55 * 2. Sprague-Grundy 정리
 56 * ============================================================================= */
 57
 58/* Grundy 수 (Nimber) 계산
 59 * mex: minimum excludant (집합에 없는 최소 비음수 정수) */
 60int mex(int set[], int n) {
 61    bool* exists = calloc(n + 1, sizeof(bool));
 62    for (int i = 0; i < n; i++) {
 63        if (set[i] <= n) exists[set[i]] = true;
 64    }
 65    int result = 0;
 66    while (exists[result]) result++;
 67    free(exists);
 68    return result;
 69}
 70
 71/* 간단한 게임의 Grundy 수 (1~3개 가져갈 수 있는 게임) */
 72int* grundy_simple(int max_n) {
 73    int* grundy = calloc(max_n + 1, sizeof(int));
 74    grundy[0] = 0;
 75
 76    for (int i = 1; i <= max_n; i++) {
 77        int moves[3];
 78        int move_count = 0;
 79
 80        for (int take = 1; take <= 3 && take <= i; take++) {
 81            moves[move_count++] = grundy[i - take];
 82        }
 83
 84        grundy[i] = mex(moves, move_count);
 85    }
 86
 87    return grundy;
 88}
 89
 90/* 일반적인 Grundy 수 계산 (가져갈 수 있는 양 배열 주어짐) */
 91int* grundy_general(int max_n, int allowed[], int allowed_count) {
 92    int* grundy = calloc(max_n + 1, sizeof(int));
 93
 94    for (int i = 1; i <= max_n; i++) {
 95        int* moves = malloc(allowed_count * sizeof(int));
 96        int move_count = 0;
 97
 98        for (int j = 0; j < allowed_count; j++) {
 99            if (allowed[j] <= i) {
100                moves[move_count++] = grundy[i - allowed[j]];
101            }
102        }
103
104        grundy[i] = mex(moves, move_count);
105        free(moves);
106    }
107
108    return grundy;
109}
110
111/* 복합 게임의 Grundy 수 (XOR 연산) */
112int combined_grundy(int grundy_values[], int n) {
113    int result = 0;
114    for (int i = 0; i < n; i++) {
115        result ^= grundy_values[i];
116    }
117    return result;
118}
119
120/* =============================================================================
121 * 3. Minimax 알고리즘
122 * ============================================================================= */
123
124#define BOARD_SIZE 3
125
126typedef struct {
127    int board[BOARD_SIZE][BOARD_SIZE];
128    int current_player;  /* 1: X, -1: O */
129} TicTacToe;
130
131void ttt_init(TicTacToe* game) {
132    memset(game->board, 0, sizeof(game->board));
133    game->current_player = 1;
134}
135
136int ttt_check_winner(TicTacToe* game) {
137    /* 행 검사 */
138    for (int i = 0; i < 3; i++) {
139        int sum = game->board[i][0] + game->board[i][1] + game->board[i][2];
140        if (sum == 3) return 1;
141        if (sum == -3) return -1;
142    }
143
144    /* 열 검사 */
145    for (int j = 0; j < 3; j++) {
146        int sum = game->board[0][j] + game->board[1][j] + game->board[2][j];
147        if (sum == 3) return 1;
148        if (sum == -3) return -1;
149    }
150
151    /* 대각선 검사 */
152    int diag1 = game->board[0][0] + game->board[1][1] + game->board[2][2];
153    int diag2 = game->board[0][2] + game->board[1][1] + game->board[2][0];
154    if (diag1 == 3 || diag2 == 3) return 1;
155    if (diag1 == -3 || diag2 == -3) return -1;
156
157    return 0;
158}
159
160bool ttt_is_full(TicTacToe* game) {
161    for (int i = 0; i < 3; i++) {
162        for (int j = 0; j < 3; j++) {
163            if (game->board[i][j] == 0) return false;
164        }
165    }
166    return true;
167}
168
169/* Minimax with Alpha-Beta Pruning */
170int minimax(TicTacToe* game, int depth, int alpha, int beta, bool is_maximizing) {
171    int winner = ttt_check_winner(game);
172    if (winner != 0) return winner * 10;
173    if (ttt_is_full(game)) return 0;
174
175    if (is_maximizing) {
176        int max_eval = INT_MIN;
177        for (int i = 0; i < 3; i++) {
178            for (int j = 0; j < 3; j++) {
179                if (game->board[i][j] == 0) {
180                    game->board[i][j] = 1;
181                    int eval = minimax(game, depth + 1, alpha, beta, false);
182                    game->board[i][j] = 0;
183                    if (eval > max_eval) max_eval = eval;
184                    if (eval > alpha) alpha = eval;
185                    if (beta <= alpha) return max_eval;
186                }
187            }
188        }
189        return max_eval;
190    } else {
191        int min_eval = INT_MAX;
192        for (int i = 0; i < 3; i++) {
193            for (int j = 0; j < 3; j++) {
194                if (game->board[i][j] == 0) {
195                    game->board[i][j] = -1;
196                    int eval = minimax(game, depth + 1, alpha, beta, true);
197                    game->board[i][j] = 0;
198                    if (eval < min_eval) min_eval = eval;
199                    if (eval < beta) beta = eval;
200                    if (beta <= alpha) return min_eval;
201                }
202            }
203        }
204        return min_eval;
205    }
206}
207
208/* 최적의 수 찾기 */
209void find_best_move(TicTacToe* game, int* best_row, int* best_col) {
210    int best_val = INT_MIN;
211    *best_row = -1;
212    *best_col = -1;
213
214    for (int i = 0; i < 3; i++) {
215        for (int j = 0; j < 3; j++) {
216            if (game->board[i][j] == 0) {
217                game->board[i][j] = 1;
218                int move_val = minimax(game, 0, INT_MIN, INT_MAX, false);
219                game->board[i][j] = 0;
220
221                if (move_val > best_val) {
222                    *best_row = i;
223                    *best_col = j;
224                    best_val = move_val;
225                }
226            }
227        }
228    }
229}
230
231/* =============================================================================
232 * 4. 기타 유명한 게임들
233 * ============================================================================= */
234
235/* Bash 게임: n개 돌에서 1~k개 가져갈 수 있음 */
236bool bash_game(int n, int k) {
237    return (n % (k + 1)) != 0;
238}
239
240/* Wythoff 게임: 두 더미에서 같은 수 또는 한 더미에서만 가져갈 수 있음 */
241bool wythoff_game(int a, int b) {
242    if (a > b) { int t = a; a = b; b = t; }
243    double phi = (1.0 + sqrt(5.0)) / 2.0;
244    int k = b - a;
245    int cold_a = (int)(k * phi);
246    return !(a == cold_a);
247}
248
249/* Euclid 게임: gcd 게임 */
250bool euclid_game(int a, int b) {
251    if (a < b) { int t = a; a = b; b = t; }
252    if (b == 0) return false;
253
254    int moves = 0;
255    while (b > 0) {
256        if (a >= 2 * b) return (moves % 2 == 0);
257        a = a - b;
258        if (a < b) { int t = a; a = b; b = t; }
259        moves++;
260    }
261    return (moves % 2 == 1);
262}
263
264/* 돌 게임 (Stone Game) - DP 기반 */
265int stone_game(int piles[], int n) {
266    int** dp = malloc(n * sizeof(int*));
267    for (int i = 0; i < n; i++) {
268        dp[i] = calloc(n, sizeof(int));
269        dp[i][i] = piles[i];
270    }
271
272    for (int len = 2; len <= n; len++) {
273        for (int i = 0; i <= n - len; i++) {
274            int j = i + len - 1;
275            int take_left = piles[i] - dp[i + 1][j];
276            int take_right = piles[j] - dp[i][j - 1];
277            dp[i][j] = (take_left > take_right) ? take_left : take_right;
278        }
279    }
280
281    int result = dp[0][n - 1];
282    for (int i = 0; i < n; i++) free(dp[i]);
283    free(dp);
284    return result;
285}
286
287/* =============================================================================
288 * 테스트
289 * ============================================================================= */
290
291void print_board(TicTacToe* game) {
292    char symbols[] = {'O', '.', 'X'};
293    for (int i = 0; i < 3; i++) {
294        printf("      ");
295        for (int j = 0; j < 3; j++) {
296            printf("%c ", symbols[game->board[i][j] + 1]);
297        }
298        printf("\n");
299    }
300}
301
302int main(void) {
303    printf("============================================================\n");
304    printf("게임 이론 예제\n");
305    printf("============================================================\n");
306
307    /* 1. Nim 게임 */
308    printf("\n[1] Nim 게임\n");
309    int piles1[] = {3, 4, 5};
310    printf("    더미: [3, 4, 5]\n");
311    printf("    XOR: %d ^ %d ^ %d = %d\n", 3, 4, 5, 3 ^ 4 ^ 5);
312    printf("    선공 승리: %s\n", nim_game(piles1, 3) ? "예" : "아니오");
313
314    int pile_idx, take;
315    nim_winning_move(piles1, 3, &pile_idx, &take);
316    if (pile_idx >= 0) {
317        printf("    승리 전략: 더미 %d에서 %d개 가져가기\n", pile_idx, take);
318    }
319
320    int piles2[] = {1, 2, 3};
321    printf("    더미: [1, 2, 3]\n");
322    printf("    XOR: %d ^ %d ^ %d = %d\n", 1, 2, 3, 1 ^ 2 ^ 3);
323    printf("    선공 승리: %s\n", nim_game(piles2, 3) ? "예" : "아니오");
324
325    /* 2. Sprague-Grundy */
326    printf("\n[2] Sprague-Grundy 정리\n");
327    int* grundy = grundy_simple(15);
328    printf("    게임: 1~3개 가져갈 수 있음\n");
329    printf("    Grundy 수: ");
330    for (int i = 0; i <= 10; i++) {
331        printf("G(%d)=%d ", i, grundy[i]);
332    }
333    printf("\n");
334    printf("    패턴: 0, 1, 2, 3, 0, 1, 2, 3, ... (주기 4)\n");
335    free(grundy);
336
337    /* 커스텀 게임 */
338    int allowed[] = {1, 3, 4};
339    grundy = grundy_general(15, allowed, 3);
340    printf("    게임: 1, 3, 4개 가져갈 수 있음\n");
341    printf("    Grundy 수: ");
342    for (int i = 0; i <= 10; i++) {
343        printf("G(%d)=%d ", i, grundy[i]);
344    }
345    printf("\n");
346    free(grundy);
347
348    /* 3. Minimax (틱택토) */
349    printf("\n[3] Minimax 알고리즘 (틱택토)\n");
350    TicTacToe game;
351    ttt_init(&game);
352
353    int row, col;
354    find_best_move(&game, &row, &col);
355    printf("    빈 보드에서 최적의 첫 수: (%d, %d)\n", row, col);
356
357    /* 상황 설정 */
358    game.board[0][0] = 1;   /* X */
359    game.board[1][1] = -1;  /* O */
360    game.board[2][2] = 1;   /* X */
361
362    printf("    현재 상태:\n");
363    print_board(&game);
364
365    find_best_move(&game, &row, &col);
366    printf("    X의 최적 수: (%d, %d)\n", row, col);
367
368    /* 4. 기타 게임 */
369    printf("\n[4] 기타 유명한 게임\n");
370
371    printf("    Bash 게임 (n=10, k=3): %s\n",
372           bash_game(10, 3) ? "선공 승리" : "후공 승리");
373    printf("    Bash 게임 (n=12, k=3): %s\n",
374           bash_game(12, 3) ? "선공 승리" : "후공 승리");
375
376    printf("    Wythoff 게임 (3, 5): %s\n",
377           wythoff_game(3, 5) ? "선공 승리" : "후공 승리");
378
379    printf("    Euclid 게임 (10, 6): %s\n",
380           euclid_game(10, 6) ? "선공 승리" : "후공 승리");
381
382    /* 5. Stone Game */
383    printf("\n[5] Stone Game (DP)\n");
384    int stones[] = {5, 3, 4, 5};
385    printf("    돌 배열: [5, 3, 4, 5]\n");
386    int diff = stone_game(stones, 4);
387    printf("    선공-후공 점수 차: %d\n", diff);
388    printf("    선공 %s\n", diff > 0 ? "승리" : (diff < 0 ? "패배" : "무승부"));
389
390    /* 6. 복잡도 */
391    printf("\n[6] 복잡도\n");
392    printf("    | 알고리즘          | 시간복잡도    |\n");
393    printf("    |-------------------|---------------|\n");
394    printf("    | Nim XOR          | O(n)          |\n");
395    printf("    | Grundy 계산      | O(n × k)      |\n");
396    printf("    | Minimax          | O(b^d)        |\n");
397    printf("    | Alpha-Beta       | O(b^(d/2))    |\n");
398    printf("    | Stone Game DP    | O(n²)         |\n");
399    printf("    b: 분기 계수, d: 깊이, k: 가능한 이동 수\n");
400
401    printf("\n============================================================\n");
402
403    return 0;
404}