27_game_theory.py

Download
python 571 lines 17.4 KB 
  1"""
  2๊ฒŒ์ž„ ์ด๋ก  (Game Theory)
  3Game Theory Algorithms
  4
  5์กฐํ•ฉ ๊ฒŒ์ž„ ์ด๋ก ๊ณผ ์ตœ์  ์ „๋žต์„ ๋‹ค๋ฃจ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.
  6"""
  7
  8from typing import List, Dict, Tuple, Set, Optional
  9from functools import lru_cache
 10
 11
 12# =============================================================================
 13# 1. ๋‹˜ ๊ฒŒ์ž„ (Nim Game)
 14# =============================================================================
 15
 16def nim_xor(piles: List[int]) -> int:
 17    """
 18    ๋‹˜ ๊ฒŒ์ž„์˜ XOR ๊ฐ’ (Nim-sum)
 19    XOR != 0์ด๋ฉด ์„ ๊ณต ์Šน๋ฆฌ, XOR == 0์ด๋ฉด ํ›„๊ณต ์Šน๋ฆฌ
 20    """
 21    result = 0
 22    for pile in piles:
 23        result ^= pile
 24    return result
 25
 26
 27def nim_winning_move(piles: List[int]) -> Optional[Tuple[int, int]]:
 28    """
 29    ๋‹˜ ๊ฒŒ์ž„์—์„œ ์Šน๋ฆฌํ•˜๋Š” ์ˆ˜ ์ฐพ๊ธฐ
 30    ๋ฐ˜ํ™˜: (๋”๋ฏธ ์ธ๋ฑ์Šค, ๋‚จ๊ธธ ๊ฐœ์ˆ˜) ๋˜๋Š” None
 31    """
 32    xor = nim_xor(piles)
 33
 34    if xor == 0:
 35        return None  # ํŒจ๋ฐฐ ์ƒํƒœ, ์Šน๋ฆฌ ์ˆ˜ ์—†์Œ
 36
 37    for i, pile in enumerate(piles):
 38        target = pile ^ xor
 39        if target < pile:
 40            return (i, target)  # pile์—์„œ target๊ฐœ๋งŒ ๋‚จ๊ธฐ๊ธฐ
 41
 42    return None
 43
 44
 45def nim_game_simulation(piles: List[int], verbose: bool = False) -> int:
 46    """
 47    ๋‹˜ ๊ฒŒ์ž„ ์‹œ๋ฎฌ๋ ˆ์ด์…˜
 48    ๋ฐ˜ํ™˜: ์Šน์ž (0: ์„ ๊ณต, 1: ํ›„๊ณต)
 49    """
 50    current = 0  # ํ˜„์žฌ ํ”Œ๋ ˆ์ด์–ด
 51
 52    while max(piles) > 0:
 53        move = nim_winning_move(piles)
 54
 55        if move is None:
 56            # ํŒจ๋ฐฐ ์ƒํƒœ: ์•„๋ฌด ์ˆ˜๋‚˜
 57            for i, pile in enumerate(piles):
 58                if pile > 0:
 59                    move = (i, pile - 1)
 60                    break
 61
 62        pile_idx, new_count = move
 63        if verbose:
 64            print(f"    Player {current}: ๋”๋ฏธ {pile_idx}์—์„œ {piles[pile_idx]}โ†’{new_count}")
 65
 66        piles[pile_idx] = new_count
 67        current = 1 - current
 68
 69    return 1 - current  # ๋งˆ์ง€๋ง‰์— ๊ฐ€์ ธ๊ฐ„ ์‚ฌ๋žŒ์ด ์Šน๋ฆฌ
 70
 71
 72# =============================================================================
 73# 2. ์Šคํ”„๋ผ๊ทธ-๊ทธ๋Ÿฐ๋”” ์ •๋ฆฌ (Sprague-Grundy Theorem)
 74# =============================================================================
 75
 76def mex(s: Set[int]) -> int:
 77    """
 78    Minimum Excludant
 79    ์ง‘ํ•ฉ์— ์—†๋Š” ๊ฐ€์žฅ ์ž‘์€ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜
 80    """
 81    i = 0
 82    while i in s:
 83        i += 1
 84    return i
 85
 86
 87def calculate_grundy(position: int, moves: List[int], memo: Dict[int, int] = None) -> int:
 88    """
 89    ์Šคํ”„๋ผ๊ทธ-๊ทธ๋Ÿฐ๋”” ์ˆ˜ ๊ณ„์‚ฐ
 90    position: ํ˜„์žฌ ์ƒํƒœ (์˜ˆ: ๋Œ์˜ ๊ฐœ์ˆ˜)
 91    moves: ๊ฐ€๋Šฅํ•œ ์ด๋™๋Ÿ‰ ๋ฆฌ์ŠคํŠธ
 92    """
 93    if memo is None:
 94        memo = {}
 95
 96    if position in memo:
 97        return memo[position]
 98
 99    if position == 0:
100        memo[position] = 0
101        return 0
102
103    reachable = set()
104    for move in moves:
105        if position >= move:
106            reachable.add(calculate_grundy(position - move, moves, memo))
107
108    result = mex(reachable)
109    memo[position] = result
110    return result
111
112
113def multi_pile_grundy(piles: List[int], moves: List[int]) -> int:
114    """
115    ์—ฌ๋Ÿฌ ๋”๋ฏธ ๊ฒŒ์ž„์˜ ์ „์ฒด ๊ทธ๋Ÿฐ๋”” ์ˆ˜
116    ๊ฐ ๋”๋ฏธ์˜ ๊ทธ๋Ÿฐ๋”” ์ˆ˜๋ฅผ XOR
117    """
118    memo = {}
119    total_grundy = 0
120
121    for pile in piles:
122        grundy = calculate_grundy(pile, moves, memo)
123        total_grundy ^= grundy
124
125    return total_grundy
126
127
128# =============================================================================
129# 3. ๋ณ€ํ˜• ๋‹˜ ๊ฒŒ์ž„
130# =============================================================================
131
132def staircase_nim(stairs: List[int]) -> int:
133    """
134    ๊ณ„๋‹จ ๋‹˜ (Staircase Nim)
135    ํ™€์ˆ˜ ๋ฒˆ์งธ ๊ณ„๋‹จ์˜ XOR = ๊ทธ๋Ÿฐ๋”” ์ˆ˜
136    """
137    xor = 0
138    for i in range(0, len(stairs), 2):  # ํ™€์ˆ˜ ์ธ๋ฑ์Šค (0-indexed์˜ ์ง์ˆ˜)
139        xor ^= stairs[i]
140    return xor
141
142
143def misere_nim(piles: List[int]) -> bool:
144    """
145    ๋ฏธ์ œ๋ฅด ๋‹˜ (๋งˆ์ง€๋ง‰ ๊ฐ€์ ธ๊ฐ€๋Š” ์‚ฌ๋žŒ์ด ํŒจ๋ฐฐ)
146    ๋ฐ˜ํ™˜: True๋ฉด ์„ ๊ณต ์Šน๋ฆฌ
147    """
148    xor = nim_xor(piles)
149    all_one_or_zero = all(p <= 1 for p in piles)
150
151    if all_one_or_zero:
152        # 1์ธ ๋”๋ฏธ์˜ ๊ฐœ์ˆ˜๊ฐ€ ํ™€์ˆ˜๋ฉด ํ›„๊ณต ์Šน๋ฆฌ
153        ones = sum(1 for p in piles if p == 1)
154        return ones % 2 == 0
155    else:
156        return xor != 0
157
158
159def poker_nim(piles: List[int], k: int) -> bool:
160    """
161    ํฌ์ปค ๋‹˜: ๋”๋ฏธ์— ๋Œ์„ ์ถ”๊ฐ€ํ•  ์ˆ˜๋„ ์žˆ์Œ (์ตœ๋Œ€ k๊ฐœ)
162    ๋ฐ˜ํ™˜: True๋ฉด ์„ ๊ณต ์Šน๋ฆฌ
163    ๊ทœ์น™: ์ผ๋ฐ˜ ๋‹˜๊ณผ ๋™์ผ (XOR != 0์ด๋ฉด ์„ ๊ณต ์Šน๋ฆฌ)
164    """
165    return nim_xor(piles) != 0
166
167
168# =============================================================================
169# 4. ๋ฏธ๋‹ˆ๋งฅ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Minimax)
170# =============================================================================
171
172def minimax(position, depth: int, is_maximizing: bool,
173            evaluate, get_moves, is_terminal) -> int:
174    """
175    ๋ฏธ๋‹ˆ๋งฅ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜
176    position: ํ˜„์žฌ ๊ฒŒ์ž„ ์ƒํƒœ
177    depth: ํƒ์ƒ‰ ๊นŠ์ด
178    is_maximizing: ์ตœ๋Œ€ํ™” ํ”Œ๋ ˆ์ด์–ด์˜ ํ„ด์ธ์ง€
179    evaluate: ์ƒํƒœ ํ‰๊ฐ€ ํ•จ์ˆ˜
180    get_moves: ๊ฐ€๋Šฅํ•œ ์ˆ˜ ๋ฐ˜ํ™˜ ํ•จ์ˆ˜
181    is_terminal: ์ข…๋ฃŒ ์ƒํƒœ ํ™•์ธ ํ•จ์ˆ˜
182    """
183    if depth == 0 or is_terminal(position):
184        return evaluate(position)
185
186    moves = get_moves(position)
187
188    if is_maximizing:
189        max_eval = float('-inf')
190        for move in moves:
191            new_position = apply_move(position, move)
192            eval_score = minimax(new_position, depth - 1, False,
193                                evaluate, get_moves, is_terminal)
194            max_eval = max(max_eval, eval_score)
195        return max_eval
196    else:
197        min_eval = float('inf')
198        for move in moves:
199            new_position = apply_move(position, move)
200            eval_score = minimax(new_position, depth - 1, True,
201                                evaluate, get_moves, is_terminal)
202            min_eval = min(min_eval, eval_score)
203        return min_eval
204
205
206def apply_move(position, move):
207    """์ˆ˜๋ฅผ ์ ์šฉํ•œ ์ƒˆ ์ƒํƒœ ๋ฐ˜ํ™˜ (์ถ”์ƒ ํ•จ์ˆ˜)"""
208    # ๊ตฌํ˜„์€ ๊ฒŒ์ž„์— ๋”ฐ๋ผ ๋‹ค๋ฆ„
209    pass
210
211
212# =============================================================================
213# 5. ์•ŒํŒŒ-๋ฒ ํƒ€ ๊ฐ€์ง€์น˜๊ธฐ (Alpha-Beta Pruning)
214# =============================================================================
215
216def alpha_beta(position, depth: int, alpha: float, beta: float,
217               is_maximizing: bool, evaluate, get_moves, is_terminal) -> int:
218    """
219    ์•ŒํŒŒ-๋ฒ ํƒ€ ๊ฐ€์ง€์น˜๊ธฐ
220    alpha: ์ตœ๋Œ€ํ™” ํ”Œ๋ ˆ์ด์–ด์˜ ์ตœ์„ ์˜ ๋ณด์žฅ๊ฐ’
221    beta: ์ตœ์†Œํ™” ํ”Œ๋ ˆ์ด์–ด์˜ ์ตœ์„ ์˜ ๋ณด์žฅ๊ฐ’
222    """
223    if depth == 0 or is_terminal(position):
224        return evaluate(position)
225
226    moves = get_moves(position)
227
228    if is_maximizing:
229        max_eval = float('-inf')
230        for move in moves:
231            new_position = apply_move(position, move)
232            eval_score = alpha_beta(new_position, depth - 1, alpha, beta,
233                                   False, evaluate, get_moves, is_terminal)
234            max_eval = max(max_eval, eval_score)
235            alpha = max(alpha, eval_score)
236            if beta <= alpha:
237                break  # ๊ฐ€์ง€์น˜๊ธฐ
238        return max_eval
239    else:
240        min_eval = float('inf')
241        for move in moves:
242            new_position = apply_move(position, move)
243            eval_score = alpha_beta(new_position, depth - 1, alpha, beta,
244                                   True, evaluate, get_moves, is_terminal)
245            min_eval = min(min_eval, eval_score)
246            beta = min(beta, eval_score)
247            if beta <= alpha:
248                break  # ๊ฐ€์ง€์น˜๊ธฐ
249        return min_eval
250
251
252# =============================================================================
253# 6. ํ‹ฑํƒํ†  (Tic-Tac-Toe) ๊ตฌํ˜„
254# =============================================================================
255
256class TicTacToe:
257    """ํ‹ฑํƒํ†  ๊ฒŒ์ž„"""
258
259    def __init__(self):
260        self.board = [[' '] * 3 for _ in range(3)]
261        self.current_player = 'X'
262
263    def get_moves(self) -> List[Tuple[int, int]]:
264        """๊ฐ€๋Šฅํ•œ ์ˆ˜ ๋ฐ˜ํ™˜"""
265        moves = []
266        for i in range(3):
267            for j in range(3):
268                if self.board[i][j] == ' ':
269                    moves.append((i, j))
270        return moves
271
272    def make_move(self, row: int, col: int) -> bool:
273        """์ˆ˜ ๋‘๊ธฐ"""
274        if self.board[row][col] != ' ':
275            return False
276        self.board[row][col] = self.current_player
277        self.current_player = 'O' if self.current_player == 'X' else 'X'
278        return True
279
280    def undo_move(self, row: int, col: int):
281        """์ˆ˜ ๋˜๋Œ๋ฆฌ๊ธฐ"""
282        self.board[row][col] = ' '
283        self.current_player = 'O' if self.current_player == 'X' else 'X'
284
285    def check_winner(self) -> Optional[str]:
286        """์Šน์ž ํ™•์ธ"""
287        # ํ–‰
288        for row in self.board:
289            if row[0] == row[1] == row[2] != ' ':
290                return row[0]
291        # ์—ด
292        for col in range(3):
293            if self.board[0][col] == self.board[1][col] == self.board[2][col] != ' ':
294                return self.board[0][col]
295        # ๋Œ€๊ฐ์„ 
296        if self.board[0][0] == self.board[1][1] == self.board[2][2] != ' ':
297            return self.board[0][0]
298        if self.board[0][2] == self.board[1][1] == self.board[2][0] != ' ':
299            return self.board[0][2]
300        return None
301
302    def is_terminal(self) -> bool:
303        """๊ฒŒ์ž„ ์ข…๋ฃŒ ํ™•์ธ"""
304        return self.check_winner() is not None or len(self.get_moves()) == 0
305
306    def evaluate(self) -> int:
307        """์ƒํƒœ ํ‰๊ฐ€ (X ๊ด€์ )"""
308        winner = self.check_winner()
309        if winner == 'X':
310            return 10
311        elif winner == 'O':
312            return -10
313        return 0
314
315    def minimax(self, is_maximizing: bool) -> int:
316        """๋ฏธ๋‹ˆ๋งฅ์Šค"""
317        if self.is_terminal():
318            return self.evaluate()
319
320        if is_maximizing:
321            max_eval = float('-inf')
322            for row, col in self.get_moves():
323                self.make_move(row, col)
324                eval_score = self.minimax(False)
325                self.undo_move(row, col)
326                max_eval = max(max_eval, eval_score)
327            return max_eval
328        else:
329            min_eval = float('inf')
330            for row, col in self.get_moves():
331                self.make_move(row, col)
332                eval_score = self.minimax(True)
333                self.undo_move(row, col)
334                min_eval = min(min_eval, eval_score)
335            return min_eval
336
337    def best_move(self) -> Tuple[int, int]:
338        """์ตœ์„ ์˜ ์ˆ˜ ์ฐพ๊ธฐ"""
339        best_score = float('-inf') if self.current_player == 'X' else float('inf')
340        best_move = None
341
342        for row, col in self.get_moves():
343            self.make_move(row, col)
344            score = self.minimax(self.current_player == 'X')
345            self.undo_move(row, col)
346
347            if self.current_player == 'X':
348                if score > best_score:
349                    best_score = score
350                    best_move = (row, col)
351            else:
352                if score < best_score:
353                    best_score = score
354                    best_move = (row, col)
355
356        return best_move
357
358    def display(self):
359        """๋ณด๋“œ ์ถœ๋ ฅ"""
360        for i, row in enumerate(self.board):
361            print("    " + " | ".join(row))
362            if i < 2:
363                print("    " + "-" * 9)
364
365
366# =============================================================================
367# 7. ๋Œ ๊ฒŒ์ž„ (Stone Game)
368# =============================================================================
369
370@lru_cache(maxsize=None)
371def stone_game_dp(piles: Tuple[int, ...], left: int, right: int) -> int:
372    """
373    ๋Œ ๊ฒŒ์ž„: ์–‘ ๋์—์„œ๋งŒ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ์Œ
374    ์„ ๊ณต์ด ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ ์ˆ˜ ์ฐจ์ด ๋ฐ˜ํ™˜
375    """
376    if left > right:
377        return 0
378
379    # ์„ ๊ณต์ด ์™ผ์ชฝ ์„ ํƒ
380    pick_left = piles[left] - stone_game_dp(piles, left + 1, right)
381    # ์„ ๊ณต์ด ์˜ค๋ฅธ์ชฝ ์„ ํƒ
382    pick_right = piles[right] - stone_game_dp(piles, left, right - 1)
383
384    return max(pick_left, pick_right)
385
386
387def stone_game(piles: List[int]) -> bool:
388    """
389    ๋Œ ๊ฒŒ์ž„: ์„ ๊ณต์ด ์ด๊ธฐ๋ฉด True
390    """
391    n = len(piles)
392    diff = stone_game_dp(tuple(piles), 0, n - 1)
393    return diff > 0
394
395
396# =============================================================================
397# 8. ๋ฐ”์‹œ ๊ฒŒ์ž„ (Bash Game)
398# =============================================================================
399
400def bash_game(n: int, k: int) -> bool:
401    """
402    ๋ฐ”์‹œ ๊ฒŒ์ž„: n๊ฐœ ๋Œ์—์„œ ์ตœ๋Œ€ k๊ฐœ์”ฉ ๊ฐ€์ ธ๊ฐ
403    ๋งˆ์ง€๋ง‰ ๋Œ์„ ๊ฐ€์ ธ๊ฐ€๋Š” ์‚ฌ๋žŒ์ด ์Šน๋ฆฌ
404    ๋ฐ˜ํ™˜: ์„ ๊ณต์ด ์ด๊ธฐ๋ฉด True
405    """
406    return n % (k + 1) != 0
407
408
409def bash_game_optimal_move(n: int, k: int) -> int:
410    """๋ฐ”์‹œ ๊ฒŒ์ž„์—์„œ ์ตœ์ ์˜ ์ˆ˜ (๊ฐ€์ ธ๊ฐˆ ๋Œ์˜ ๊ฐœ์ˆ˜)"""
411    if n % (k + 1) == 0:
412        return 1  # ํŒจ๋ฐฐ ์ƒํƒœ, ์•„๋ฌด ์ˆ˜๋‚˜
413    return n % (k + 1)
414
415
416# =============================================================================
417# 9. ์œ„๋”ํ”„ ๊ฒŒ์ž„ (Wythoff's Game)
418# =============================================================================
419
420def wythoff_game(a: int, b: int) -> bool:
421    """
422    ์œ„๋”ํ”„ ๊ฒŒ์ž„: ๋‘ ๋”๋ฏธ์—์„œ ๊ฐ™์€ ๊ฐœ์ˆ˜ ๋˜๋Š” ํ•œ ๋”๋ฏธ์—์„œ ์ž„์˜ ๊ฐœ์ˆ˜
423    ๋งˆ์ง€๋ง‰ ๋Œ์„ ๊ฐ€์ ธ๊ฐ€๋Š” ์‚ฌ๋žŒ์ด ์Šน๋ฆฌ
424    ๋ฐ˜ํ™˜: ์„ ๊ณต์ด ์ด๊ธฐ๋ฉด True
425    """
426    phi = (1 + 5 ** 0.5) / 2  # ํ™ฉ๊ธˆ๋น„
427
428    if a > b:
429        a, b = b, a
430
431    k = b - a
432    ak = int(k * phi)
433
434    return a != ak
435
436
437# =============================================================================
438# 10. ์œ ํด๋ฆฌ๋“œ ๊ฒŒ์ž„ (Euclid's Game)
439# =============================================================================
440
441def euclid_game(a: int, b: int) -> bool:
442    """
443    ์œ ํด๋ฆฌ๋“œ ๊ฒŒ์ž„: ํฐ ์ˆ˜์—์„œ ์ž‘์€ ์ˆ˜์˜ ๋ฐฐ์ˆ˜๋ฅผ ๋บŒ
444    0์„ ๋งŒ๋“œ๋Š” ์‚ฌ๋žŒ์ด ์Šน๋ฆฌ
445    ๋ฐ˜ํ™˜: ์„ ๊ณต์ด ์ด๊ธฐ๋ฉด True
446    """
447    if a < b:
448        a, b = b, a
449
450    if b == 0:
451        return False  # ์ด๋ฏธ ๋๋‚จ
452
453    # ์žฌ๊ท€์  ๋ถ„์„
454    turn = True  # True: ์„ ๊ณต์˜ ํ„ด
455    while b > 0:
456        if a >= 2 * b or a == b:
457            return turn
458        a, b = b, a - b
459        turn = not turn
460
461    return not turn
462
463
464# =============================================================================
465# ํ…Œ์ŠคํŠธ
466# =============================================================================
467
468def main():
469    print("=" * 60)
470    print("๊ฒŒ์ž„ ์ด๋ก  (Game Theory) ์˜ˆ์ œ")
471    print("=" * 60)
472
473    # 1. ๋‹˜ ๊ฒŒ์ž„
474    print("\n[1] ๋‹˜ ๊ฒŒ์ž„ (Nim Game)")
475    piles = [3, 4, 5]
476    xor = nim_xor(piles)
477    move = nim_winning_move(piles)
478    print(f"    ๋”๋ฏธ: {piles}")
479    print(f"    XOR: {xor} ({'์„ ๊ณต ์Šน๋ฆฌ' if xor != 0 else 'ํ›„๊ณต ์Šน๋ฆฌ'})")
480    if move:
481        print(f"    ์Šน๋ฆฌ ์ˆ˜: ๋”๋ฏธ {move[0]}์—์„œ {move[1]}๊ฐœ๋กœ")
482
483    # ์‹œ๋ฎฌ๋ ˆ์ด์…˜
484    print("\n    ๊ฒŒ์ž„ ์‹œ๋ฎฌ๋ ˆ์ด์…˜:")
485    piles_copy = [3, 4, 5]
486    winner = nim_game_simulation(piles_copy, verbose=True)
487    print(f"    ์Šน์ž: Player {winner}")
488
489    # 2. ์Šคํ”„๋ผ๊ทธ-๊ทธ๋Ÿฐ๋””
490    print("\n[2] ์Šคํ”„๋ผ๊ทธ-๊ทธ๋Ÿฐ๋”” ์ •๋ฆฌ")
491    moves = [1, 3, 4]  # ํ•œ ๋ฒˆ์— 1, 3, 4๊ฐœ ๊ฐ€์ ธ๊ฐˆ ์ˆ˜ ์žˆ์Œ
492    memo = {}
493    for n in range(10):
494        g = calculate_grundy(n, moves, memo)
495        print(f"    G({n}) = {g}", end="  ")
496    print()
497
498    # ์—ฌ๋Ÿฌ ๋”๋ฏธ
499    piles = [7, 5]
500    total_g = multi_pile_grundy(piles, moves)
501    print(f"    ๋”๋ฏธ {piles}, ์ด๋™ {moves}")
502    print(f"    ์ „์ฒด ๊ทธ๋Ÿฐ๋””: {total_g} ({'์„ ๊ณต ์Šน๋ฆฌ' if total_g != 0 else 'ํ›„๊ณต ์Šน๋ฆฌ'})")
503
504    # 3. ๋ณ€ํ˜• ๋‹˜
505    print("\n[3] ๋ณ€ํ˜• ๋‹˜ ๊ฒŒ์ž„")
506    # ๋ฏธ์ œ๋ฅด ๋‹˜
507    piles_misere = [1, 2, 3]
508    print(f"    ๋ฏธ์ œ๋ฅด ๋‹˜ {piles_misere}: ์„ ๊ณต {'์Šน๋ฆฌ' if misere_nim(piles_misere) else 'ํŒจ๋ฐฐ'}")
509
510    # ๊ณ„๋‹จ ๋‹˜
511    stairs = [3, 1, 2, 4]  # ๊ณ„๋‹จ 1, 2, 3, 4
512    print(f"    ๊ณ„๋‹จ ๋‹˜ {stairs}: ๊ทธ๋Ÿฐ๋”” = {staircase_nim(stairs)}")
513
514    # 4. ํ‹ฑํƒํ† 
515    print("\n[4] ํ‹ฑํƒํ†  ๋ฏธ๋‹ˆ๋งฅ์Šค")
516    game = TicTacToe()
517    game.board = [['X', 'O', 'X'],
518                  [' ', 'O', ' '],
519                  [' ', ' ', ' ']]
520    game.current_player = 'X'
521    print("    ํ˜„์žฌ ์ƒํƒœ:")
522    game.display()
523    best = game.best_move()
524    print(f"    X์˜ ์ตœ์„ ์˜ ์ˆ˜: {best}")
525
526    # 5. ๋Œ ๊ฒŒ์ž„
527    print("\n[5] ๋Œ ๊ฒŒ์ž„")
528    piles = [5, 3, 4, 5]
529    print(f"    ๋”๋ฏธ: {piles}")
530    result = stone_game(piles)
531    diff = stone_game_dp(tuple(piles), 0, len(piles) - 1)
532    print(f"    ์„ ๊ณต {'์Šน๋ฆฌ' if result else 'ํŒจ๋ฐฐ'} (์ ์ˆ˜ ์ฐจ์ด: {diff})")
533
534    # 6. ๋ฐ”์‹œ ๊ฒŒ์ž„
535    print("\n[6] ๋ฐ”์‹œ ๊ฒŒ์ž„")
536    n, k = 10, 3
537    print(f"    n={n}, k={k}")
538    print(f"    ์„ ๊ณต {'์Šน๋ฆฌ' if bash_game(n, k) else 'ํŒจ๋ฐฐ'}")
539    if bash_game(n, k):
540        print(f"    ์ตœ์ ์˜ ์ˆ˜: {bash_game_optimal_move(n, k)}๊ฐœ ๊ฐ€์ ธ๊ฐ€๊ธฐ")
541
542    # 7. ์œ„๋”ํ”„ ๊ฒŒ์ž„
543    print("\n[7] ์œ„๋”ํ”„ ๊ฒŒ์ž„")
544    test_cases = [(1, 2), (3, 5), (4, 7), (5, 8)]
545    for a, b in test_cases:
546        result = wythoff_game(a, b)
547        print(f"    ({a}, {b}): ์„ ๊ณต {'์Šน๋ฆฌ' if result else 'ํŒจ๋ฐฐ'}")
548
549    # 8. ์œ ํด๋ฆฌ๋“œ ๊ฒŒ์ž„
550    print("\n[8] ์œ ํด๋ฆฌ๋“œ ๊ฒŒ์ž„")
551    test_cases = [(25, 7), (24, 10), (100, 45)]
552    for a, b in test_cases:
553        result = euclid_game(a, b)
554        print(f"    ({a}, {b}): ์„ ๊ณต {'์Šน๋ฆฌ' if result else 'ํŒจ๋ฐฐ'}")
555
556    # 9. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์š”์•ฝ
557    print("\n[9] ๊ฒŒ์ž„ ์ด๋ก  ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์š”์•ฝ")
558    print("    | ๊ฒŒ์ž„           | ์Šน๋ฆฌ ์กฐ๊ฑด                    |")
559    print("    |----------------|------------------------------|")
560    print("    | ๋‹˜ ๊ฒŒ์ž„        | XOR != 0                     |")
561    print("    | ๋ฏธ์ œ๋ฅด ๋‹˜      | ๋ณต์žกํ•œ ์กฐ๊ฑด                  |")
562    print("    | ๋ฐ”์‹œ ๊ฒŒ์ž„      | n % (k+1) != 0               |")
563    print("    | ์œ„๋”ํ”„ ๊ฒŒ์ž„    | ํ™ฉ๊ธˆ๋น„ ๊ธฐ๋ฐ˜ ํŒจ๋ฐฐ ์œ„์น˜        |")
564    print("    | ์ผ๋ฐ˜ ๊ฒŒ์ž„      | ์Šคํ”„๋ผ๊ทธ-๊ทธ๋Ÿฐ๋”” ์ •๋ฆฌ         |")
565
566    print("\n" + "=" * 60)
567
568
569if __name__ == "__main__":
570    main()