27_game_theory.cpp

Download
cpp 379 lines 11.8 KB 
  1/*
  2 * ๊ฒŒ์ž„ ์ด๋ก  (Game Theory)
  3 * Nim, Sprague-Grundy, Minimax, Alpha-Beta Pruning
  4 *
  5 * ๊ฒŒ์ž„์—์„œ ์ตœ์  ์ „๋žต์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11#include <unordered_set>
 12#include <functional>
 13#include <climits>
 14
 15using namespace std;
 16
 17// =============================================================================
 18// 1. Nim Game
 19// =============================================================================
 20
 21// ๋ชจ๋“  ๋”๋ฏธ์˜ XOR์ด 0์ด๋ฉด ํ›„๊ณต ์Šน๋ฆฌ, ์•„๋‹ˆ๋ฉด ์„ ๊ณต ์Šน๋ฆฌ
 22bool canWinNim(const vector<int>& piles) {
 23    int xorSum = 0;
 24    for (int pile : piles) {
 25        xorSum ^= pile;
 26    }
 27    return xorSum != 0;
 28}
 29
 30// ์Šน๋ฆฌ๋ฅผ ์œ„ํ•œ ์ฒซ ์ˆ˜ ์ฐพ๊ธฐ
 31pair<int, int> findNimMove(const vector<int>& piles) {
 32    int xorSum = 0;
 33    for (int pile : piles) {
 34        xorSum ^= pile;
 35    }
 36
 37    if (xorSum == 0) {
 38        return {-1, -1};  // ์ด๊ธธ ์ˆ˜ ์—†์Œ
 39    }
 40
 41    for (int i = 0; i < (int)piles.size(); i++) {
 42        int target = piles[i] ^ xorSum;
 43        if (target < piles[i]) {
 44            return {i, piles[i] - target};  // i๋ฒˆ ๋”๋ฏธ์—์„œ ์ด๋งŒํผ ์ œ๊ฑฐ
 45        }
 46    }
 47
 48    return {-1, -1};
 49}
 50
 51// =============================================================================
 52// 2. Sprague-Grundy ์ •๋ฆฌ
 53// =============================================================================
 54
 55// ๊ทธ๋Ÿฐ๋”” ์ˆ˜ ๊ณ„์‚ฐ
 56int grundyNumber(int n, function<vector<int>(int)> getMoves, vector<int>& memo) {
 57    if (memo[n] != -1) return memo[n];
 58
 59    unordered_set<int> reachable;
 60    for (int next : getMoves(n)) {
 61        reachable.insert(grundyNumber(next, getMoves, memo));
 62    }
 63
 64    // MEX (Minimum Excludant) ๊ณ„์‚ฐ
 65    int mex = 0;
 66    while (reachable.count(mex)) mex++;
 67
 68    return memo[n] = mex;
 69}
 70
 71// ์—ฌ๋Ÿฌ ๊ฒŒ์ž„์˜ ๊ทธ๋Ÿฐ๋”” ์ˆ˜๋Š” XOR
 72int multiGameGrundy(const vector<int>& grundyNumbers) {
 73    int result = 0;
 74    for (int g : grundyNumbers) {
 75        result ^= g;
 76    }
 77    return result;
 78}
 79
 80// =============================================================================
 81// 3. Minimax
 82// =============================================================================
 83
 84class TicTacToe {
 85private:
 86    vector<vector<int>> board;  // 0: ๋นˆ์นธ, 1: X, 2: O
 87    const int EMPTY = 0, X = 1, O = 2;
 88
 89    int checkWin() {
 90        // ๊ฐ€๋กœ
 91        for (int i = 0; i < 3; i++) {
 92            if (board[i][0] != EMPTY &&
 93                board[i][0] == board[i][1] && board[i][1] == board[i][2]) {
 94                return board[i][0];
 95            }
 96        }
 97        // ์„ธ๋กœ
 98        for (int j = 0; j < 3; j++) {
 99            if (board[0][j] != EMPTY &&
100                board[0][j] == board[1][j] && board[1][j] == board[2][j]) {
101                return board[0][j];
102            }
103        }
104        // ๋Œ€๊ฐ์„ 
105        if (board[0][0] != EMPTY &&
106            board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
107            return board[0][0];
108        }
109        if (board[0][2] != EMPTY &&
110            board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
111            return board[0][2];
112        }
113        return 0;
114    }
115
116    bool isFull() {
117        for (int i = 0; i < 3; i++) {
118            for (int j = 0; j < 3; j++) {
119                if (board[i][j] == EMPTY) return false;
120            }
121        }
122        return true;
123    }
124
125public:
126    TicTacToe() : board(3, vector<int>(3, 0)) {}
127
128    // Minimax: ์ตœ์  ์ˆ˜ ์ฐพ๊ธฐ
129    int minimax(bool isMaximizing) {
130        int winner = checkWin();
131        if (winner == X) return 1;
132        if (winner == O) return -1;
133        if (isFull()) return 0;
134
135        if (isMaximizing) {
136            int bestScore = INT_MIN;
137            for (int i = 0; i < 3; i++) {
138                for (int j = 0; j < 3; j++) {
139                    if (board[i][j] == EMPTY) {
140                        board[i][j] = X;
141                        bestScore = max(bestScore, minimax(false));
142                        board[i][j] = EMPTY;
143                    }
144                }
145            }
146            return bestScore;
147        } else {
148            int bestScore = INT_MAX;
149            for (int i = 0; i < 3; i++) {
150                for (int j = 0; j < 3; j++) {
151                    if (board[i][j] == EMPTY) {
152                        board[i][j] = O;
153                        bestScore = min(bestScore, minimax(true));
154                        board[i][j] = EMPTY;
155                    }
156                }
157            }
158            return bestScore;
159        }
160    }
161
162    pair<int, int> findBestMove(int player) {
163        int bestScore = (player == X) ? INT_MIN : INT_MAX;
164        pair<int, int> bestMove = {-1, -1};
165
166        for (int i = 0; i < 3; i++) {
167            for (int j = 0; j < 3; j++) {
168                if (board[i][j] == EMPTY) {
169                    board[i][j] = player;
170                    int score = minimax(player == O);
171                    board[i][j] = EMPTY;
172
173                    if (player == X && score > bestScore) {
174                        bestScore = score;
175                        bestMove = {i, j};
176                    } else if (player == O && score < bestScore) {
177                        bestScore = score;
178                        bestMove = {i, j};
179                    }
180                }
181            }
182        }
183
184        return bestMove;
185    }
186
187    void makeMove(int row, int col, int player) {
188        board[row][col] = player;
189    }
190
191    void print() {
192        for (int i = 0; i < 3; i++) {
193            cout << "      ";
194            for (int j = 0; j < 3; j++) {
195                char c = board[i][j] == EMPTY ? '.' : (board[i][j] == X ? 'X' : 'O');
196                cout << c << " ";
197            }
198            cout << endl;
199        }
200    }
201};
202
203// =============================================================================
204// 4. Alpha-Beta Pruning
205// =============================================================================
206
207int alphabeta(vector<vector<int>>& board, int depth, int alpha, int beta,
208              bool isMax, function<int(const vector<vector<int>>&)> evaluate,
209              function<vector<pair<int,int>>(const vector<vector<int>>&, int)> getMoves,
210              int player) {
211
212    if (depth == 0) {
213        return evaluate(board);
214    }
215
216    auto moves = getMoves(board, player);
217    if (moves.empty()) {
218        return evaluate(board);
219    }
220
221    if (isMax) {
222        int maxEval = INT_MIN;
223        for (auto [r, c] : moves) {
224            board[r][c] = player;
225            int eval = alphabeta(board, depth - 1, alpha, beta, false,
226                                 evaluate, getMoves, 3 - player);
227            board[r][c] = 0;
228            maxEval = max(maxEval, eval);
229            alpha = max(alpha, eval);
230            if (beta <= alpha) break;  // ๊ฐ€์ง€์น˜๊ธฐ
231        }
232        return maxEval;
233    } else {
234        int minEval = INT_MAX;
235        for (auto [r, c] : moves) {
236            board[r][c] = player;
237            int eval = alphabeta(board, depth - 1, alpha, beta, true,
238                                 evaluate, getMoves, 3 - player);
239            board[r][c] = 0;
240            minEval = min(minEval, eval);
241            beta = min(beta, eval);
242            if (beta <= alpha) break;  // ๊ฐ€์ง€์น˜๊ธฐ
243        }
244        return minEval;
245    }
246}
247
248// =============================================================================
249// 5. ๋Œ ๊ฒŒ์ž„ ๋ณ€ํ˜•
250// =============================================================================
251
252// 1, 2, 3๊ฐœ์”ฉ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋Œ ๊ฒŒ์ž„
253bool stoneGame123(int n) {
254    // n์ด 4์˜ ๋ฐฐ์ˆ˜์ด๋ฉด ํ›„๊ณต ์Šน๋ฆฌ
255    return n % 4 != 0;
256}
257
258// 2์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ ๊ฐœ์”ฉ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋Œ ๊ฒŒ์ž„
259bool stoneGamePowerOf2(int n) {
260    vector<int> grundy(n + 1, 0);
261
262    for (int i = 1; i <= n; i++) {
263        unordered_set<int> reachable;
264        for (int p = 1; p <= i; p *= 2) {
265            reachable.insert(grundy[i - p]);
266        }
267        int mex = 0;
268        while (reachable.count(mex)) mex++;
269        grundy[i] = mex;
270    }
271
272    return grundy[n] != 0;
273}
274
275// =============================================================================
276// 6. Bash Game
277// =============================================================================
278
279// ์ตœ๋Œ€ k๊ฐœ์”ฉ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋Œ ๊ฒŒ์ž„
280bool bashGame(int n, int k) {
281    return n % (k + 1) != 0;
282}
283
284// =============================================================================
285// 7. Wythoff's Game
286// =============================================================================
287
288// ๋‘ ๋”๋ฏธ, ํ•œ ๋”๋ฏธ์—์„œ ๊ฐ€์ ธ๊ฐ€๊ฑฐ๋‚˜ ์–‘์ชฝ์—์„œ ๊ฐ™์€ ์ˆ˜ ๊ฐ€์ ธ๊ฐ€๊ธฐ
289bool wythoffGame(int a, int b) {
290    if (a > b) swap(a, b);
291
292    const double phi = (1 + sqrt(5)) / 2;
293    int coldA = (int)(phi * (b - a));
294
295    return a != coldA;
296}
297
298// =============================================================================
299// ํ…Œ์ŠคํŠธ
300// =============================================================================
301
302int main() {
303    cout << "============================================================" << endl;
304    cout << "๊ฒŒ์ž„ ์ด๋ก  ์˜ˆ์ œ" << endl;
305    cout << "============================================================" << endl;
306
307    // 1. Nim Game
308    cout << "\n[1] Nim Game" << endl;
309    vector<int> piles = {3, 4, 5};
310    cout << "    ๋”๋ฏธ: [3, 4, 5]" << endl;
311    cout << "    XOR: " << (3 ^ 4 ^ 5) << endl;
312    cout << "    ์„ ๊ณต ์Šน๋ฆฌ: " << (canWinNim(piles) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
313
314    auto [pileIdx, removeCount] = findNimMove(piles);
315    if (pileIdx != -1) {
316        cout << "    ์ตœ์  ์ˆ˜: ๋”๋ฏธ " << pileIdx << "์—์„œ " << removeCount << "๊ฐœ ์ œ๊ฑฐ" << endl;
317    }
318
319    // 2. Sprague-Grundy
320    cout << "\n[2] Sprague-Grundy" << endl;
321    // 1, 2, 3๊ฐœ์”ฉ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ฒŒ์ž„์˜ ๊ทธ๋Ÿฐ๋”” ์ˆ˜
322    auto moves123 = [](int n) -> vector<int> {
323        vector<int> result;
324        if (n >= 1) result.push_back(n - 1);
325        if (n >= 2) result.push_back(n - 2);
326        if (n >= 3) result.push_back(n - 3);
327        return result;
328    };
329
330    vector<int> memo(20, -1);
331    memo[0] = 0;
332    cout << "    ๋Œ ๊ฒŒ์ž„ (1,2,3๊ฐœ) ๊ทธ๋Ÿฐ๋”” ์ˆ˜:" << endl;
333    cout << "    ";
334    for (int i = 0; i < 10; i++) {
335        cout << "G(" << i << ")=" << grundyNumber(i, moves123, memo) << " ";
336    }
337    cout << endl;
338
339    // 3. Minimax (Tic-Tac-Toe)
340    cout << "\n[3] Tic-Tac-Toe Minimax" << endl;
341    TicTacToe game;
342    game.makeMove(0, 0, 1);  // X
343    game.makeMove(1, 1, 2);  // O
344    cout << "    ํ˜„์žฌ ์ƒํƒœ:" << endl;
345    game.print();
346
347    auto [bestRow, bestCol] = game.findBestMove(1);  // X์˜ ์ตœ์  ์ˆ˜
348    cout << "    X์˜ ์ตœ์  ์ˆ˜: (" << bestRow << ", " << bestCol << ")" << endl;
349
350    // 4. ๋Œ ๊ฒŒ์ž„ ๋ณ€ํ˜•
351    cout << "\n[4] ๋Œ ๊ฒŒ์ž„ ๋ณ€ํ˜•" << endl;
352    cout << "    ๋Œ 10๊ฐœ (1,2,3๊ฐœ ๊ฐ€๋Šฅ): " << (stoneGame123(10) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
353    cout << "    ๋Œ 12๊ฐœ (1,2,3๊ฐœ ๊ฐ€๋Šฅ): " << (stoneGame123(12) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
354
355    // 5. Bash Game
356    cout << "\n[5] Bash Game" << endl;
357    cout << "    ๋Œ 10๊ฐœ, ์ตœ๋Œ€ 3๊ฐœ: " << (bashGame(10, 3) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
358    cout << "    ๋Œ 12๊ฐœ, ์ตœ๋Œ€ 3๊ฐœ: " << (bashGame(12, 3) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
359
360    // 6. Wythoff's Game
361    cout << "\n[6] Wythoff's Game" << endl;
362    cout << "    ๋”๋ฏธ (3, 5): " << (wythoffGame(3, 5) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
363    cout << "    ๋”๋ฏธ (1, 2): " << (wythoffGame(1, 2) ? "์„ ๊ณต ์Šน" : "ํ›„๊ณต ์Šน") << endl;
364
365    // 7. ๊ฒŒ์ž„ ์ด๋ก  ์š”์•ฝ
366    cout << "\n[7] ๊ฒŒ์ž„ ์ด๋ก  ์š”์•ฝ" << endl;
367    cout << "    | ๊ฒŒ์ž„          | ์Šน๋ฆฌ ์กฐ๊ฑด              |" << endl;
368    cout << "    |---------------|------------------------|" << endl;
369    cout << "    | Nim           | XOR != 0               |" << endl;
370    cout << "    | Bash (k)      | n % (k+1) != 0         |" << endl;
371    cout << "    | 1,2,3 ๋Œ      | n % 4 != 0             |" << endl;
372    cout << "    | Wythoff       | a != floor(phi*(b-a))  |" << endl;
373    cout << "    | ์ผ๋ฐ˜ ๊ฒŒ์ž„     | Grundy != 0            |" << endl;
374
375    cout << "\n============================================================" << endl;
376
377    return 0;
378}