Lý thuyết trò chơi

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 15:31

Lý thuyết trò chơi tổ hợp (Combinatorial Game Theory) nghiên cứu các trò chơi hai người, thông tin hoàn hảo, không có yếu tố may rủi, và người không đi được coi là thua (normal play convention).

Khái niệm cơ bản

Trạng thái P (Previous player wins): Người vừa đi thắng — tức là người đang đến lượt thua. Đây là trạng thái thua.
Trạng thái N (Next player wins): Người đến lượt thắng.

Quy tắc xác định:

Trạng thái cuối (không còn nước đi) là trạng thái P (thua).
Trạng thái N nếu tồn tại ít nhất một nước đi đến trạng thái P.
Trạng thái P nếu mọi nước đi đều dẫn đến trạng thái N.

Nim

Trò chơi Nim: có $k$ đống đá, mỗi đống $a_{i}$ viên. Hai người thay nhau lấy bất kỳ số viên nào từ một đống. Người lấy viên cuối cùng thắng.

Định lý Sprague-Grundy cho Nim: Người đi trước thua khi và chỉ khi:

a_{1} \oplus a_{2} \oplus \dots \oplus a_{k} = 0

int nim_winner(vector<int>& piles) {
    int xor_sum = 0;
    for (int p : piles) xor_sum ^= p;
    return xor_sum != 0;   // true: người đi trước thắng
}

Chiến lược thắng: Tìm đống $i$ sao cho $a_{i} \oplus xor_sum < a_{i}$ , lấy từ đống $i$ xuống còn $a_{i} \oplus xor_sum$ viên.

Grundy Number (Nimber)

Grundy number $G (s)$ của trạng thái $s$ là mex (minimum excludant) của tập Grundy number của các trạng thái kế tiếp:

G (s) = mex {G (s^{'}) : s \to s^{'}}

mex (S) = min (ℕ_{0} ⧵ S)

// Tính Grundy number cho trò chơi đơn giản
// moves: tập nước đi hợp lệ từ trạng thái n (ví dụ: {1, 3, 4} cho Nim 1 đống)
vector<int> grundy(int max_n, vector<int>& moves) {
    vector<int> G(max_n + 1, 0);
    for (int n = 1; n <= max_n; n++) {
        set<int> reachable;
        for (int m : moves)
            if (n >= m) reachable.insert(G[n - m]);
        int mex = 0;
        while (reachable.count(mex)) mex++;
        G[n] = mex;
    }
    return G;
}

Ý nghĩa: $G (s) = 0$ là trạng thái thua (P-position). $G (s) > 0$ là trạng thái thắng (N-position).

Định lý Sprague-Grundy

Khi chơi đồng thời nhiều trò chơi độc lập (sum of games), Grundy number của tổng bằng XOR của các Grundy number thành phần:

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

// Ví dụ: nhiều đống, mỗi đống có quy tắc lấy riêng
// G_total = XOR của G(a_i) với G tính theo quy tắc lấy của mỗi đống
int total_grundy = 0;
for (int pile : piles)
    total_grundy ^= G[pile];   // G tính sẵn theo quy tắc
// total_grundy == 0: người đi trước thua

Nim biến thể

Misère Nim (người lấy viên cuối thua):

Nếu mọi đống $\leq 1$ : thắng khi số đống lẻ là chẵn.
Nếu có đống $> 1$ : thắng khi XOR $\neq 0$ (ngược lại Nim thường).

Staircase Nim: Có $k$ bậc thang, mỗi bậc $a_{i}$ viên. Người đi lấy bất kỳ số viên từ bậc $i > 0$ và chuyển xuống bậc $0$ . Chỉ xét XOR của các bậc lẻ: thắng khi $a_{1} \oplus a_{3} \oplus a_{5} \oplus \dots \neq 0$ .

Các trang con

Nim và Grundy Number — chi tiết trong trang này

Bình luận

Không có bình luận tại thời điểm này.