Wiki › Thuật toán › Lý thuyết trò chơi

Lý thuyết trò chơi

huunguyen Updated Tháng sáu 2, 2026

Lý thuyết trò chơi tổ hợp (Combinatorial Game Theory) nghiên cứu các trò chơi hai người, luân phiên, thông tin hoàn hảo, không may rủi, hai bên đều chơi tối ưu. Câu hỏi điển hình: "với trạng thái ban đầu cho trước, người đi trước thắng hay thua?". Cách ngây thơ là duyệt toàn bộ cây trò chơi (số nhánh bùng nổ theo hàm mũ); lý thuyết trò chơi cho ta công cụ phân loại từng trạng thái thành thắng/thua chỉ trong $O (số trạng thái \times số nước đi)$ , và với trò chơi dạng Nim còn rút gọn xuống $O (k)$ nhờ phép XOR và số Grundy.

Trong bài này ta dùng normal play convention: người không còn nước đi để đi là người thua (biến thể "người đi cuối thua" gọi là misère, xét riêng ở mục mở rộng).

Ý tưởng / Trực giác

Trạng thái P và N

Mọi trạng thái được dán nhãn một trong hai loại:

P-position (Previous player wins): người vừa đi xong đang thắng, tức người sắp đến lượt thua.
N-position (Next player wins): người sắp đến lượt thắng.

Ba quy tắc đệ quy xác định nhãn, xuất phát từ trạng thái cuối:

Trạng thái không còn nước đi là P (người đến lượt không đi được → thua).
Một trạng thái là N nếu tồn tại ít nhất một nước đi dẫn tới một P-position. (Người đi cứ chọn nước đó, đẩy đối thủ vào thế thua.)
Một trạng thái là P nếu mọi nước đi đều dẫn tới một N-position. (Đi đâu cũng trao thế thắng cho đối thủ.)

Vì sao đúng? Đây chính là quy nạp ngược trên cây trò chơi. Trạng thái cuối là cơ sở quy nạp. Với trạng thái bất kỳ, nếu người đi có thể đẩy đối thủ vào thế thua (P) thì đương nhiên anh ta thắng; còn nếu mọi nước đi đều cho đối thủ thế thắng (N) thì anh ta thua. Hai mệnh đề này bao trùm mọi khả năng, nên nhãn được xác định duy nhất.

Số Grundy (Nimber) và phép mex

Để ghép nhiều trò chơi độc lập chơi song song, dán nhãn P/N là chưa đủ — ta cần lượng hoá "độ mạnh" của mỗi trạng thái bằng một con số. Đó là số Grundy $G (s)$ :

$G (s) = mex {G (s^{'}) : s \to s^{'}}, mex (S) = min (ℕ_{0} ⧵ S)$

trong đó $mex$ (minimum excludant) là số tự nhiên nhỏ nhất không xuất hiện trong tập. Quy ước $mex (\emptyset) = 0$ , nên trạng thái cuối có $G = 0$ .

Liên hệ với P/N: $G (s) = 0 ⟺ s$ là P-position (thua), $G (s) > 0 ⟺$ N-position (thắng). Lý do: nếu $G (s) = 0$ thì mọi nước đi đều tới trạng thái $G > 0$ (vì mex bằng 0 nghĩa là 0 không có trong tập đích); ngược lại nếu $G (s) > 0$ thì tồn tại nước đi tới trạng thái có $G = 0$ .

Định lý Sprague–Grundy

Khi trò chơi là tổng của nhiều ván con độc lập (mỗi lượt người đi chọn đúng một ván con để đi):

$G (G_{1} + G_{2} + \dots + G_{k}) = G_{1} \oplus G_{2} \oplus \dots \oplus G_{k}$

(với $\oplus$ là XOR). Người đi trước thua khi và chỉ khi tổng XOR bằng 0. Trực giác: mỗi ván con tương đương một "đống Nim" có kích thước bằng số Grundy của nó, và trò Nim nhiều đống được giải đúng bằng XOR (xem dưới). Đây là kết quả trung tâm: nó biến một trò chơi phức tạp thành phép XOR của các số nhỏ.

Nim — viên gạch nền

Trò Nim: có $k$ đống đá, đống $i$ có $a_{i}$ viên. Mỗi lượt lấy tuỳ ý ( $\geq 1$ ) viên từ đúng một đống; ai không lấy được (mọi đống rỗng) thì thua. Một đống đơn lẻ kích thước $a$ có $G = a$ , nên theo Sprague–Grundy:

$Người đi trước thua ⟺ a_{1} \oplus a_{2} \oplus \dots \oplus a_{k} = 0$

Vì sao XOR? Nếu XOR $\neq 0$ , gọi bit cao nhất của tổng XOR là bit $b$ ; tồn tại đống có bit $b$ bật, ta giảm đống đó để biến tổng XOR thành 0 — đẩy đối thủ vào thế P. Nếu XOR $= 0$ , mọi nước đi (thay đổi đúng một đống) đều làm tổng XOR khác 0 — ta luôn nhận lại thế N. Đó chính là hai quy tắc P/N viết lại bằng XOR.

Ví dụ chạy tay

Phân loại P/N cho trò bốc sỏi

Xét trò: một đống $n$ viên, mỗi lượt lấy 1, 3 hoặc 4 viên, ai không lấy được thì thua. Tính $G (n)$ bằng mex, từ đó suy ra P/N:

n :  0   1   2   3   4   5   6   7   8   9
        moves tới: n-1, n-3, n-4
-----------------------------------------------
G(0) = mex{}                       = 0   (P)
G(1) = mex{G0}      = mex{0}       = 1   (N)
G(2) = mex{G1}      = mex{1}       = 0   (P)   <-- thua!
G(3) = mex{G2,G0}   = mex{0,0}     = 1   (N)
G(4) = mex{G3,G1,G0}= mex{1,1,0}   = 2   (N)
G(5) = mex{G4,G2,G1}= mex{2,0,1}   = 3   (N)
G(6) = mex{G5,G3,G2}= mex{3,1,0}   = 2   (N)
G(7) = mex{G6,G4,G3}= mex{2,2,1}   = 0   (P)   <-- thua!

Đọc kết quả: tại $n = 2$ và $n = 7$ , người đi trước thua ( $G = 0$ ). Thử $n = 2$ : lấy 1 viên → còn 1 viên, đối thủ lấy nốt → ta hết nước → thua. (Không thể lấy 3 hoặc 4 vì chỉ có 2 viên.) Đúng như nhãn P.

Tổng hai ván độc lập (Sprague–Grundy)

Giả sử chơi đồng thời hai đống của trò trên: đống A có $n_{A} = 4$ , đống B có $n_{B} = 6$ . Mỗi lượt chọn một đống để bốc.

G(A) = G(4) = 2          (nhị phân 10)
G(B) = G(6) = 2          (nhị phân 10)
Tổng XOR = 2 ^ 2 = 0  --> P-position --> NGƯỜI ĐI TRƯỚC THUA

Hai ván "mạnh ngang nhau" triệt tiêu lẫn nhau qua XOR: bất cứ nước đi nào ở một đống cũng phá thế cân bằng, đối thủ luôn cân bằng lại được — đúng tinh thần "chiến lược gương".

Cài đặt

Nim cơ bản

// Trả về true nếu người đi trước THẮNG
bool nimWinner(const vector<int>& piles) {
    int xorSum = 0;
    for (int p : piles) xorSum ^= p;   // XOR toàn bộ đống
    return xorSum != 0;                // != 0: đi trước thắng; == 0: thua
}

Bảng Grundy cho trò bốc sỏi tổng quát (subtraction game)

// moves: tập số viên được phép lấy mỗi lượt.
// Trả về mảng G[0..maxN], với G[n] là số Grundy của đống n viên.
vector<int> grundy(int maxN, const vector<int>& moves) {
    vector<int> G(maxN + 1, 0);
    for (int n = 1; n <= maxN; n++) {
        // Tập các số Grundy đạt tới được từ trạng thái n
        set<int> reachable;
        for (int m : moves)
            if (n >= m) reachable.insert(G[n - m]);
        // mex = số tự nhiên nhỏ nhất không có trong reachable
        int mex = 0;
        while (reachable.count(mex)) mex++;
        G[n] = mex;
    }
    return G;
}
// Nhiều đống độc lập: XOR các G[a_i]; kết quả 0 => đi trước thua.

Game DP (minimax) — khi không quy về Nim được

Nhiều bài "trò chơi tối ưu" không phải Nim mà là tối ưu giá trị (điểm số), giải bằng quy hoạch động minimax. Mẫu điển hình: hai người lần lượt lấy ở hai đầu dãy, tối đa hoá điểm của mình.

// a[]: dãy giá trị; dp[i][j] = chênh lệch điểm tốt nhất của NGƯỜI ĐANG ĐI
//                              trên đoạn [i..j].
int n;
long long a[N];
long long dp[N][N];

long long solve(int i, int j) {
    if (i > j) return 0;
    long long &res = dp[i][j];
    if (res != LLONG_MIN) return res;
    // Lấy đầu trái hoặc đầu phải; phần còn lại đối thủ chơi => trừ đi
    long long takeLeft  = a[i] - solve(i + 1, j);
    long long takeRight = a[j] - solve(i, j - 1);
    return res = max(takeLeft, takeRight);   // người đang đi tối đa hoá chênh lệch
}
// dp[0][n-1] > 0  => người đi trước có điểm cao hơn.

Độ phức tạp

Bài toán	Thời gian	Bộ nhớ	Lý do
Nim cơ bản	$O (k)$	$O (1)$	Một lần duyệt XOR qua $k$ đống.
Bảng Grundy (subtraction)	$O (N \cdot \| M \|)$	$O (N)$	Với mỗi trong $N$ trạng thái, thử $\| M \|$ nước đi; mex tính trong $O (\| M \|)$ nhờ tập kích thước $\leq \| M \|$ .
Game DP đoạn	$O (N^{2})$	$O (N^{2})$	Có $O (N^{2})$ trạng thái $(i, j)$ , mỗi trạng thái xử lý $O (1)$ chuyển.

Lưu ý: nếu dùng set để tính mex, mỗi trạng thái tốn thêm hệ số $\log$ ; thay bằng mảng đánh dấu kích thước $| M | + 1$ để giữ $O (| M |)$ thật sự. Với Nim, không cần xây bảng — chỉ XOR, nên bộ nhớ là hằng số.

⚠️ Lỗi thường gặp

Nhầm normal play với misère. Quy tắc "XOR $\neq 0$ thì thắng" chỉ đúng cho normal play (đi cuối thắng / không đi được thì thua). Với misère Nim (lấy viên cuối thua), công thức khác hẳn (xem mục mở rộng). Đọc kỹ đề "ai thua".
Quên trạng thái cuối là $G = 0$ (P-position). Khởi tạo sai cơ sở quy nạp khiến toàn bộ bảng Grundy lệch. Trạng thái không còn nước đi luôn là thua cho người đến lượt.
Tính mex sai. mex là số tự nhiên nhỏ nhất vắng mặt, tính từ 0 — không phải "giá trị nhỏ nhất/lớn nhất trong tập", cũng không phải số phần tử. $mex {0, 1, 3} = 2$ , không phải 4.
Lấy số Grundy của trạng thái hiện tại thay vì của các trạng thái đích. mex được tính trên tập ${G (s^{'}) : s \to s^{'}}$ , tức Grundy của các nước đi tới, không bao gồm $G (s)$ .
XOR nhầm thành cộng/||. Để ghép các ván độc lập phải dùng XOR (^). Dùng + hay logic OR/|| cho ra kết quả sai hoàn toàn.
Tràn số trong game DP giá trị. Chênh lệch điểm tích luỹ có thể vượt int (tổng tới $N \times max a_{i}$ ); dùng long long. Đồng thời khởi tạo dp bằng giá trị "chưa tính" (vd LLONG_MIN) chứ không phải 0, vì 0 là một kết quả hợp lệ.
Tưởng tổng nhiều trò luôn quy về Nim. Sprague–Grundy chỉ áp dụng khi các ván độc lập và mỗi lượt đi đúng một ván. Trò có ràng buộc chéo (vd phải đi theo thứ tự, hay nước đi này ảnh hưởng ván khác) thì phải dùng game DP/minimax, không XOR Grundy được.
Bảng Grundy quá lớn để xây trực tiếp. Khi $a_{i}$ tới $10^{9}$ , không thể tạo mảng $G [0 . . a_{i}]$ . Phải tìm quy luật/chu kỳ của dãy Grundy (rất hay tuần hoàn) bằng cách in vài chục giá trị đầu rồi khái quát hoá.

Biến thể / Mở rộng

Misère Nim (lấy viên cuối thua): Nếu mọi đống $\leq 1$ , người đi trước thắng khi số đống (kích thước 1) là chẵn. Ngược lại (có ít nhất một đống $\geq 2$ ), luật giống Nim thường: thắng khi tổng XOR $\neq 0$ .
Staircase Nim (Nim bậc thang): di chuyển sỏi từ bậc $i$ xuống bậc $i - 1$ . Chỉ tổng XOR của các bậc lẻ mới quyết định: đi trước thắng $⟺ a_{1} \oplus a_{3} \oplus a_{5} \oplus \dots \neq 0$ (sỏi ở bậc chẵn coi như "trung tính").
Tìm chu kỳ Grundy: dãy số Grundy của subtraction game luôn tuần hoàn cuối cùng (eventually periodic). In $G [0 . .200]$ , dò chu kỳ, rồi tra cứu $G [n] = G [n mod chu kỳ]$ cho $n$ rất lớn.
Trò chơi không phải Nim: rất nhiều bài là minimax DP thuần (tối ưu điểm số, không có cấu trúc XOR). Khi đó dùng kỹ thuật ở Quy hoạch động, đặc biệt là DP khoảng.

Bài tập luyện

Trò Chơi Palindrome (palingam) — (Sơ cấp) Subtraction game với nước đi là số palindrome; tìm quy luật P/N đơn giản trên đống một chiều, làm quen khái niệm thắng/thua.
Trò Chơi Bi (moorbles) — (Nâng cao) Mỗi lượt bỏ một cặp bi cùng màu; bài luyện lập luận chẵn/lẻ tổng số nước đi thay vì XOR, một dạng phân tích P/N kinh điển.
Chuồng Bò Tròn (circbarn) — (Trung cấp) Mỗi phòng là một ván con (trừ 1 hoặc một số nguyên tố); ghép kết quả các ván độc lập theo lượt — luyện tư duy phân rã trò chơi thành nhiều thành phần.
WANDDUEL Đấu Đũa Phép (wandduel) — (Nâng cao) Trò chơi tối ưu giá trị trên đoạn, giải bằng minimax interval DP; ví dụ điển hình cho trò chơi không quy về Nim.