Chương 31 - Game Theory

Game theory trong phỏng vấn coding là bài 2 người chơi luân phiên, mỗi người chơi optimally. Pattern chung: DP minimax - tại mỗi state, người đi tìm cách max điểm mình hoặc min điểm đối thủ. Bài có chu trình → dùng BFS multi-source từ “terminal states”.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Minimax DP: tại mỗi state, người đi tìm max/min phụ thuộc turn.
  • Pattern diff(l, r): chênh lệch tối đa người hiện tại đạt được.
  • BFS từ terminal states khi state graph có chu trình.
  • Bitmask DP cho game với set state nhỏ (Can I Win).

Khi nào dùng pattern này?

  • 2 (đôi khi nhiều) người chơi luân phiên.
  • Đề bài có cụm “both play optimally”, “ai thắng”, “max score difference”.
  • State có thể enumerated → DP / memoization khả thi.

Template code 

from functools import cache

@cache
def dp(state, is_alice_turn):
    if terminal(state):
        return score(state)
    if is_alice_turn:
        return max(dp(next_state(s), False) - delta for s in moves(state))
    else:
        return min(dp(next_state(s), True) + delta for s in moves(state))

Bài tự luyện cuối chương

  • LC 294 - Flip Game II
  • LC 375 - Guess Number Higher or Lower II
  • LC 1140 - Stone Game II
  • LC 1690 - Stone Game VII (Chương 29.17)

31.1 Nim Game (LC 292)

Đề bài

Có n đá. Mỗi turn lấy 1, 2, hoặc 3 đá. Người lấy đá cuối thắng. Alice đi trước. Hỏi Alice có thắng không.

Ví dụ 

Input:  n=4
Output: False

Ràng buộc

  • 1 <= n <= 2^31-1

Clarifying questions

  • n = 0? → Alice không thắng (không có đá để lấy).

Hướng tiếp cận

Quan sát (induction): - n ∈ {1,2,3}: Alice lấy hết → thắng. - n == 4: bất kể Alice lấy 1/2/3, Bob luôn ở trạng thái {1,2,3} → Bob thắng. - Mở rộng: Alice thắng ↔︎ n % 4 != 0.

Code Python 3 

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

Phân tích độ phức tạp

  • Thời gian: O(1).
  • Bộ nhớ: O(1).

Bình luận

  • Bài 1 dòng - test bạn nhìn ra pattern game theory.

Bài tự luyện liên quan

  • LC 877 - Stone Game (bài 31.2)
  • LC 1908 - Game of Nim (variant)

31.2 Stone Game (LC 877)

Đề bài

Mảng piles (chẵn cái, sum lẻ). Alice và Bob lần lượt lấy đống ở 2 đầu. Alice đi trước. Cả 2 chơi optimal. Alice thắng?

Ví dụ 

Input:  piles = [5, 3, 4, 5]   (số pile chẵn, tổng stones lẻ; 2 đầu mới lấy được)
Output: True   (Alice luôn thắng khi cả 2 chơi tối ưu)

Ràng buộc

  • 2 <= len(piles) <= 500
  • len(piles) chẵn
  • 1 <= piles[i] <= 500
  • Sum lẻ

Clarifying questions

  • n piles lẻ? → Theo đề: n chẵn.

Hướng tiếp cận

Trick math: Vì n chẵn, Alice có thể chiến lược luôn lấy chỉ số chẵn hoặc luôn lẻ - chọn tổng lớn hơn. Vì sum lẻ, 1 trong 2 phải > sum/2.

→ Alice luôn thắng.

Code Python 3 

from typing import List

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

class SolutionDP:
    """DP version - pattern chuẩn cho biến thể."""

    def stoneGame(self, piles: List[int]) -> bool:
        from functools import cache
        n = len(piles)

        @cache
        def diff(l: int, r: int) -> int:
            if l > r: return 0
            return max(piles[l] - diff(l + 1, r), piles[r] - diff(l, r - 1))

        return diff(0, n - 1) > 0

Phân tích độ phức tạp

  • Thời gian: O(1) math; O(n²) DP version.
  • Bộ nhớ: O(n²) cho memo.

Bình luận

  • diff(l, r) = chênh lệch tối đa người hiện tại có thể đạt được trên piles[l..r].

Bài tự luyện liên quan

  • LC 1140 - Stone Game II.
  • LC 1690 - Stone Game VII (Chương 29).

31.3 Predict the Winner (LC 486)

Đề bài

Như Stone Game, nhưng n bất kỳ (có thể lẻ), sum bất kỳ. Alice thắng nếu score(Alice) ≥ score(Bob).

Ví dụ 

Input:  nums = [1, 5, 2]   (2 player luân phiên lấy 1 đầu mảng)
Output: False   (Player 1 không thể thắng khi cả 2 chơi tối ưu)

Ràng buộc

  • 1 <= len(nums) <= 20
  • 0 <= nums[i] <= 10^7

Clarifying questions

  • nums có duplicate? → Có; pattern không đổi.

Hướng tiếp cận

DP diff(l, r) y hệt 31.2.

Code Python 3 

from functools import cache
from typing import List

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:

        @cache
        def diff(l: int, r: int) -> int:
            if l == r: return nums[l]
            return max(nums[l] - diff(l + 1, r), nums[r] - diff(l, r - 1))

        return diff(0, len(nums) - 1) >= 0

Phân tích độ phức tạp

  • Thời gian: O(n²).
  • Bộ nhớ: O(n²) cho memo.

Bình luận

  • Bẫy: chuyển từ “thắng” sang “chênh lệch ≥ 0” - luôn dùng diff dễ hơn.
  • Follow-up: LC 877 case n chẵn → trivially True.

Bài tự luyện liên quan

  • LC 877 - Stone Game.

31.4 Stone Game II (LC 1140)

Đề bài

Piles. Alice trước. Mỗi turn lấy X pile đầu tiên với 1 <= X <= 2*M (M ban đầu 1, sau mỗi turn M = max(M, X)). Tối đa số đá Alice lấy được.

Ví dụ 

Input:  piles = [2, 7, 9, 4, 4]   (M ban đầu = 1; người chơi lấy X piles với 1 ≤ X ≤ 2M, sau đó M = max(M, X))
Output: 10   (số stones tối đa Alice lấy được)

Ràng buộc

  • 1 <= len(piles) <= 100
  • 1 <= piles[i] <= 10^4

Clarifying questions

  • M ban đầu khác 1? → Theo đề: M = 1.
  • n = 1? → Alice lấy hết.

Hướng tiếp cận

DP dfs(i, M) = số đá người hiện tại có thể lấy được từ piles[i:] với M hiện tại. Maximize của các X.

Code Python 3 

from functools import cache
from typing import List

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]

        @cache
        def dfs(i: int, M: int) -> int:
            if i + 2 * M >= n:
                return suffix[i]
            return suffix[i] - min(dfs(i + x, max(M, x)) for x in range(1, 2 * M + 1))

        return dfs(0, 1)

Phân tích độ phức tạp

  • Thời gian: O(n²).
  • Bộ nhớ: O(n²) cho memo.

Bình luận

  • suffix[i] - min(...): tổng còn lại trừ đi cái đối thủ tối ưu hoá lấy = phần Alice giữ được.

Bài tự luyện liên quan

  • LC 877 - Stone Game (bài 31.2)
  • LC 1690 - Stone Game VII (Chương 29.17)

31.5 Cat and Mouse (LC 913)

Đề bài

Input: graph: List[List[int]] - adjacency list của một graph vô hướng, graph[i] là danh sách các node kề node i. Đỉnh đánh số 0..n-1.

Luật chơi: - Mouse bắt đầu ở node 1, Cat bắt đầu ở node 2, hole là node 0. - Lượt 1: chuột đi, lượt 2: mèo đi (mỗi lượt mỗi con buộc phải đi sang 1 neighbor). - Mèo không được vào hole (node 0). - Mouse thắng khi đến hole; Cat thắng khi cùng ô với Mouse; hoà nếu lặp state.

Trả về 1 trong 3 giá trị: 1 = MOUSE_WIN, 2 = CAT_WIN, 0 = DRAW.

Ví dụ 

Input:  graph = [[2,5], [3], [0,4,5], [1,4,5], [2,3], [0,2,3]]
        (adjacency list của graph vô hướng; graph[i] = các node kề node i)
        Graph trên có 6 node 0..5; node 0 là hole.
Output: 0
        (0 = DRAW, 1 = MOUSE_WIN, 2 = CAT_WIN)

Ràng buộc

  • 3 <= len(graph) <= 50
  • 0 ∈ graph (hole)

Clarifying questions

  • Graph có cycle giữa mouse và cat? → Có (vì undirected).
  • Hole node không connect đến node nào? → Mouse không tới được hole → Cat thắng.

Hướng tiếp cận

BFS từ terminal states (retrograde analysis). Pattern này khác DP vì state graph có chu trình (mèo & chuột có thể đi tới đi lui) ⇒ memoization top-down không terminate.

State = (mouse, cat, turn) với turn ∈ {0=mouse, 1=cat}. Tổng O(n²) states.

Terminal: - mouse == 0 (chuột vào hole) ⇒ MOUSE_WIN. - mouse == cat (cùng ô, mèo bắt) ⇒ CAT_WIN.

Outcome propagation (retrograde): với mỗi state đã biết outcome, đi ngược (xét các parent state có thể dẫn đến state này) và suy: - Nếu đến lượt người chiến thắng ở parent (vd parent là lượt chuột và state hiện tại là MOUSE_WIN) ⇒ parent cũng WIN (chỉ cần 1 nước thắng). - Nếu đến lượt người thua ở parent ⇒ chỉ ghi parent thua khi tất cả nước đi của họ đều dẫn về thua (đếm bằng degree).

State/outcome diagram (rút gọn):

Terminal layer:
  (0, *, *)        ─────────────► MOUSE_WIN
  (k, k, *)  k>0   ─────────────► CAT_WIN

Retrograde propagation (BFS):

  state S đã biết outcome = X
       │
       ▼ for each parent P of S (đảo lượt):
       │
       ├── lượt(P) là "người thắng X" ?  YES → P = X (push)
       │
       └── lượt(P) là "người thua X" ?
              degree[P] -= 1
              if degree[P] == 0:
                  P = X (push)     ← mọi nước đều thua

  state còn lại sau khi BFS kết thúc → DRAW.

Đây là bài Hard có độ khó cao trên LeetCode; chương này tập trung giới thiệu pattern (retrograde BFS), phần cài đặt đầy đủ ngay bên dưới.

Code Python 3 

from collections import deque
from typing import List

MOUSE_WIN, CAT_WIN, DRAW = 1, 2, 0

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)
        # state: (mouse, cat, turn) - turn 0=mouse, 1=cat
        color = {}
        degree = {}
        for m in range(n):
            for c in range(n):
                degree[(m, c, 0)] = len(graph[m])
                degree[(m, c, 1)] = len(graph[c]) - (0 in graph[c])

        q = deque()
        for c in range(n):
            for t in range(2):
                color[(0, c, t)] = MOUSE_WIN
                q.append((0, c, t, MOUSE_WIN))
            color[(c, c, 0)] = color[(c, c, 1)] = CAT_WIN if c != 0 else MOUSE_WIN
            for t in range(2):
                q.append((c, c, t, color[(c, c, t)]))

        def parents(m: int, c: int, t: int):
            prev_turn = 1 - t
            if prev_turn == 0:           # mouse just moved
                for prev_m in graph[m]:
                    yield (prev_m, c, prev_turn)
            else:
                for prev_c in graph[c]:
                    if prev_c == 0: continue
                    yield (m, prev_c, prev_turn)

        while q:
            m, c, t, col = q.popleft()
            for pm, pc, pt in parents(m, c, t):
                if (pm, pc, pt) in color: continue
                if (pt == 0 and col == MOUSE_WIN) or (pt == 1 and col == CAT_WIN):
                    color[(pm, pc, pt)] = col
                    q.append((pm, pc, pt, col))
                else:
                    degree[(pm, pc, pt)] -= 1
                    if degree[(pm, pc, pt)] == 0:
                        color[(pm, pc, pt)] = col
                        q.append((pm, pc, pt, col))
        return color.get((1, 2, 0), DRAW)

Phân tích độ phức tạp

  • Thời gian: O(n³) (state (m, c, t)).
  • Bộ nhớ: O(n²).

Bình luận

  • Pattern “BFS từ terminal” quan trọng khi DP top-down bị chu trình.

Bài tự luyện liên quan

  • LC 1728 - Cat and Mouse II
  • LC 913 - Cat and Mouse (bài này)

31.6 Can I Win (LC 464)

Đề bài

Có 1..maxChoosable. Mỗi turn người chơi chọn 1 số chưa chọn. Người đầu tiên làm tổng các số đã chọn ≥ desiredTotal thắng. Alice trước. Alice thắng?

Ví dụ 

Input:  maxChoosable=10, desiredTotal=11
Output: False

Ràng buộc

  • 1 <= maxChoosable <= 20
  • 0 <= desiredTotal <= 300

Clarifying questions

  • desiredTotal ≤ maxChoosable? → Alice lấy maxChoosable → thắng ngay nếu ≥ desiredTotal.

Hướng tiếp cận

Bitmask DP - state = set các số đã chọn (bitmask) + current sum. @cache memoize.

Code Python 3 

from functools import cache

class Solution:
    def canIWin(self, maxChoosable: int, desiredTotal: int) -> bool:
        if (1 + maxChoosable) * maxChoosable // 2 < desiredTotal:
            return False

        @cache
        def dfs(mask: int, remaining: int) -> bool:
            for i in range(1, maxChoosable + 1):
                bit = 1 << i
                if mask & bit:
                    continue
                if i >= remaining:
                    return True
                if not dfs(mask | bit, remaining - i):
                    return True             # đối thủ thua → ta thắng
            return False

        return dfs(0, desiredTotal)

Phân tích độ phức tạp

  • Thời gian: O(2^n · n).
  • Bộ nhớ: O(2^n) cho memo.

Bình luận

  • Pattern Bitmask DP - Chương 40 sẽ đào sâu.

Bài tự luyện liên quan

  • LC 698 - Partition to K Equal Sum Subsets (Chương 40).

Tóm tắt chương & Quyết định

Game taxonomy

Loại Đặc trưng Bài
Math trick Phân tích parity / sum / “always wins” LC 877 (Stone Game I), LC 292 Nim
Minimax DP dp[state] = giá trị tối ưu cho người đến lượt LC 486, 1140
Memoized state graph State rời rạc, transitions phức tạp LC 464 (Can I Win)
Retrograde BFS Truyền outcome từ trạng thái terminal lùi LC 913 (Cat and Mouse)

Stone Game (LC 877) - vì sao Alice luôn thắng

  • n chẵn ⇒ Alice có thể chọn toàn bộ pile chẵn-index hoặc toàn bộ pile lẻ-index (chia màu xanh/đỏ). Tổng even ≠ odd (vì even + odd = total lẻ tổng cộng các pile) ⇒ Alice chọn nhóm tổng lớn hơn.
  • DP vẫn cần học vì pattern “minimax 2 đầu” tổng quát cho LC 486.

Can I Win (LC 464) - bitmask state

  • State = bitmask các số đã dùng (≤ 20 → mask ≤ 2²⁰).
  • memo[mask] = True nếu người đến lượt có nước thắng.
  • Bridge sang Chương 40 (Bitmask DP).

Cat and Mouse (LC 913) - retrograde

  • State = (mouse_pos, cat_pos, turn). Terminal: mouse ở hole → mouse win; cat == mouse → cat win.
  • BFS lùi: nếu tất cả moves của người đến lượt dẫn về state thua → state hiện tại cũng thua.