Trò Chơi Nim và Định Lý Sprague-Grundy Trong Lý Thuyết Trò Chơi
Trong các kỳ thi lập trình thi đấu như Olympic Tin học, ACM-ICPC hay Codeforces, những bài toán đối kháng hai người chơi (Game Theory) luôn mang lại cảm giác vô cùng kích thích và kịch tính. Đề bài thường mô tả một trò chơi bốc sỏi, di chuyển quân cờ trên bàn cờ hoặc chia cắt đồ thị, rồi đặt ra câu hỏi quen thuộc: "Nếu cả hai người chơi đều chơi tối ưu (optimal play), ai sẽ là người chiến thắng: người đi trước (First) hay người đi sau (Second)?"
Nhiều thí sinh khi mới tiếp cận thường cố gắng dùng thuật toán tìm kiếm Minimax hoặc quy hoạch động vét cạn mọi nhánh cây trò chơi. Tuy nhiên, khi không gian trạng thái lên tới hàng triệu đỉnh, phương pháp vét cạn hoàn toàn bế tắc.
Thế nhưng, trong lớp trò chơi tổ hợp công bằng (Impartial Combinatorial Games), toán học đã ban tặng cho chúng ta một vũ khí tối thượng: Trò chơi Nim của Bouton và Định lý Sprague-Grundy. Định lý này khẳng định rằng: Mọi trò chơi tổ hợp công bằng độc lập, dù luật chơi có phức tạp đến đâu, đều tương đương với một đống sỏi Nim duy nhất!
Khái niệm trò chơi tổ hợp công bằng và vị trí N - P
Một trò chơi được xếp vào nhóm trò chơi tổ hợp công bằng (Impartial Game) khi thỏa mãn đầy đủ các tính chất:
- Có hai người chơi luân phiên thực hiện các nước đi.
- Thông tin hoàn hảo (Perfect Information): Cả hai người đều nhìn thấy toàn bộ trạng thái của trò chơi (không có thông tin ẩn, không có xúc xắc hay yếu tố ngẫu nhiên may rủi).
- Tính công bằng (Impartiality): Tại cùng một trạng thái của bàn cờ, tập hợp các nước đi hợp lệ của người chơi 1 và người chơi 2 là hoàn toàn giống hệt nhau (khác với Cờ vua hay Cờ tướng, nơi người chơi chỉ được đi quân của mình).
- Trò chơi hữu hạn: Trò chơi phải kết thúc sau một số lượng nước đi hữu hạn (đồ thị trạng thái là một DAG - Directed Acyclic Graph, không có chu trình lặp vô hạn).
- Quy ước chơi chuẩn (Normal Play Convention): Người chơi không thể thực hiện được nước đi hợp lệ nào nữa là người thua cuộc (người đi nước cuối cùng là người chiến thắng).
Phân loại vị trí: N-position và P-position
Trong lý thuyết trò chơi, mọi trạng thái của trò chơi đều được phân loại duy nhất vào một trong hai nhóm:
- P-position (Previous player winning position): Vị trí mà người vừa đi nước trước đó sẽ chiến thắng (nghĩa là người đang đến lượt đi ở vị trí này sẽ bị thua nếu đối thủ chơi chuẩn).
- N-position (Next player winning position): Vị trí mà người chuẩn bị đi nước kế tiếp sẽ chiến thắng (người đang đến lượt có chiến thuật chắc chắn thắng).
Quy tắc chuyển dịch trạng thái kinh điển:
- Tất cả các trạng thái kết thúc (Terminal states - không còn nước đi nào) đều là P-position.
- Một trạng thái là N-position khi và chỉ khi: từ nó tồn tại ít nhất một nước đi dẫn tới một P-position. (Người chơi chỉ cần đi vào nước đó để đẩy đối thủ vào thế thua).
- Một trạng thái là P-position khi và chỉ khi: MỌI nước đi hợp lệ từ nó đều dẫn tới một N-position. (Dù người chơi có đi nước nào đi nữa cũng đều mang lại cơ hội chiến thắng cho đối thủ).
Trò chơi Nim kinh điển và định lý Bouton
Năm 1901, giáo sư toán học Charles L. Bouton tại Đại học Harvard đã công bố lời giải hoàn chỉnh cho Trò chơi Nim — viên đá tảng của lý thuyết trò chơi tổ hợp.
Luật chơi Nim
- Cho \(K\) đống sỏi, đống thứ \(i\) có số lượng sỏi là \(a_i \ge 0\).
- Hai người chơi luân phiên nhau. Tại mỗi lượt, người chơi chọn duy nhất một đống sỏi và bốc đi một số lượng sỏi tùy ý (ít nhất 1 viên, và có thể bốc hết toàn bộ viên sỏi trong đống đó).
- Người bốc viên sỏi cuối cùng là người chiến thắng.
Định lý Bouton: Sức mạnh của tổng Nim-sum (XOR)
Bouton đã chỉ ra rằng trạng thái của trò chơi Nim được quyết định hoàn toàn bởi tổng Nim-sum, ký hiệu là phép toán XOR bitwise giữa số lượng sỏi của tất cả các đống:
\[S = a_1 \oplus a_2 \oplus \dots \oplus a_K\]
Định lý Bouton (1901): Trạng thái \((a_1, a_2, \dots, a_K)\) là một P-position (người đi trước thua) khi và chỉ khi: \[S = a_1 \oplus a_2 \oplus \dots \oplus a_K = 0\] Ngược lại, nếu \(S \ne 0\), trạng thái đó là một N-position (người đi trước chắc chắn thắng)!
Chiến thuật thắng cụ thể
Khi bạn đang đứng ở vị trí có tổng XOR \(S \ne 0\):
- Tìm bit \(1\) cao nhất (Most Significant Bit - MSB) của \(S\), giả sử là bit thứ \(d\).
- Chắc chắn tồn tại ít nhất một đống sỏi \(a_k\) mà bit thứ \(d\) của nó bằng \(1\) (vì phép XOR ra bit 1 nghĩa là có số lượng lẻ các số có bit 1 ở vị trí đó).
- Đặt \(a'_k = a_k \oplus S\). Vì bit \(d\) của \(a_k\) là \(1\) và bit \(d\) của \(S\) cũng là \(1\), nên trong \(a'_k\), bit \(d\) bị triệt tiêu về \(0\). Do đó chắc chắn \(a'_k \lt a_k\)!
- Nước đi tối ưu: Bạn chỉ việc bốc đống thứ \(k\) từ \(a_k\) viên xuống còn đúng \(a'_k\) viên sỏi.
- Tổng XOR mới sẽ trở thành: \[S' = S \oplus a_k \oplus a'_k = S \oplus a_k \oplus (a_k \oplus S) = 0\] Đối thủ bị đẩy vào trạng thái có tổng XOR bằng 0 (P-position). Dù đối thủ có bốc bất kỳ viên nào ở bất kỳ đống nào, tổng XOR mới chắc chắn sẽ khác 0. Bạn lại tiếp tục lặp lại chiến thuật trên cho đến khi bốc viên sỏi cuối cùng để giành chiến thắng tuyệt đối!
Hàm MEX và Giá trị Grundy (Sprague-Grundy Function)
Làm thế nào để áp dụng kết quả của Nim cho các trò chơi có luật đi khác (ví dụ: chỉ được bốc 1, 2 hoặc 3 viên, hoặc chỉ được bốc số lượng sỏi là số nguyên tố)?
Nhà toán học Roland Sprague (1935) và Patrick Michael Grundy (1939) đã độc lập phát minh ra Giá trị Grundy (Nim-value).
Định nghĩa hàm MEX (Minimum Excluded Value)
Cho một tập hợp các số nguyên không âm \(S \subset \mathbb{N}\). Hàm \(\text{mex}(S)\) trả về số nguyên không âm nhỏ nhất KHÔNG thuộc tập \(S\):
\[\text{mex}(S) = \min \{ x \in \{0, 1, 2, \dots\} \mid x \notin S \}\]
Ví dụ:
- \(\text{mex}(\emptyset) = 0\)
- \(\text{mex}(\{1, 2, 3\}) = 0\) (vì số 0 chưa có)
- \(\text{mex}(\{0, 1, 3\}) = 2\) (vì số 2 chưa có)
- \(\text{mex}(\{0, 1, 2, 3\}) = 4\)
Định nghĩa giá trị Grundy của một trạng thái
Mỗi trò chơi tổ hợp công bằng có thể biểu diễn như một đồ thị có hướng không chu trình (DAG), trong đó mỗi đỉnh \(u\) là một trạng thái, và mỗi cung \(u \to v\) là một nước đi hợp lệ chuyển từ trạng thái \(u\) sang \(v\).
Giá trị Grundy \(G(u)\) của trạng thái \(u\) được định nghĩa đệ quy: \[G(u) = \text{mex}(\{ G(v) \mid u \to v \})\]
Quy tắc:
- Nếu \(u\) là trạng thái kết thúc (không còn nước đi hợp lệ nào nữa): tập chuyển tiếp là rỗng \(\implies G(u) = \text{mex}(\emptyset) = 0\).
- Một trạng thái \(u\) là P-position (thua) \(\iff G(u) = 0\).
- Một trạng thái \(u\) là N-position (thắng) \(\iff G(u) \gt 0\).
Định lý Sprague-Grundy gộp các trò chơi con độc lập
Trong thực tế, một ván chơi thường bao gồm nhiều trò chơi con độc lập diễn ra đồng thời (ví dụ: có nhiều đống sỏi, mỗi lượt người chơi chỉ được chọn 1 đống để đi theo luật riêng).
Định lý Sprague-Grundy: Bất kỳ trò chơi tổ hợp công bằng nào ở trạng thái \(u\) đều tương đương tuyệt đối với một đống sỏi Nim có kích thước đúng bằng \(G(u)\).
Nếu trò chơi \(G\) là tổng của \(m\) trò chơi con độc lập \(G_1, G_2, \dots, G_m\) ở các trạng thái tương ứng \(u_1, u_2, \dots, u_m\): Giá trị Grundy của toàn bộ trò chơi tổng chính là tổng Nim-sum (XOR) của các giá trị Grundy thành phần: \[G(u) = G_1(u_1) \oplus G_2(u_2) \oplus \dots \oplus G_m(u_m)\] Người đi trước chiến thắng \(\iff G(u) \ne 0\)!
Ví dụ chạy tay: Trò chơi bốc sỏi bị chặn số lượng
Xét một trò chơi bốc sỏi với một đống \(x\) viên. Tại mỗi lượt, người chơi chỉ được bốc \(1, 2\) hoặc \(3\) viên (\(S = \{1, 2, 3\}\)). Hãy tính giá trị Grundy \(G(x)\) từ \(0\) đến \(8\):
- \(G(0) = \text{mex}(\emptyset) = 0\)
- \(G(1) = \text{mex}(\{G(0)\}) = \text{mex}(\{0\}) = 1\)
- \(G(2) = \text{mex}(\{G(1), G(0)\}) = \text{mex}(\{1, 0\}) = 2\)
- \(G(3) = \text{mex}(\{G(2), G(1), G(0)\}) = \text{mex}(\{2, 1, 0\}) = 3\)
- \(G(4) = \text{mex}(\{G(3), G(2), G(1)\}) = \text{mex}(\{3, 2, 1\}) = 0\)
- \(G(5) = \text{mex}(\{G(4), G(3), G(2)\}) = \text{mex}(\{0, 3, 2\}) = 1\)
- \(G(6) = \text{mex}(\{G(5), G(4), G(3)\}) = \text{mex}(\{1, 0, 3\}) = 2\)
- \(G(7) = \text{mex}(\{G(6), G(5), G(4)\}) = \text{mex}(\{2, 1, 0\}) = 3\)
- \(G(8) = \text{mex}(\{G(7), G(6), G(5)\}) = \text{mex}(\{3, 2, 1\}) = 0\)
Nhận xét: Giá trị Grundy có chu kỳ hoàn hảo: \[G(x) = x \pmod 4\] Nếu bàn chơi có 3 đống sỏi với kích thước \((4, 5, 7)\): \[G_{\text{tổng}} = G(4) \oplus G(5) \oplus G(7) = 0 \oplus 1 \oplus 3 = 2 \ne 0\] Vì \(G_{\text{tổng}} \ne 0\), Người đi trước (First) chắc chắn thắng!
Cài đặt chuẩn C++17 và Python 3
Dưới đây là lời giải mẫu hoàn chỉnh được kiểm thử kỹ lưỡng, tối ưu I/O và sẵn sàng nộp trên hệ thống:
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
// Cấu trúc giải trò chơi tổ hợp công bằng bằng Định lý Sprague-Grundy
// Tính hàm MEX và tổng XOR (Nim-sum) trên các trò chơi con độc lập
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m; // Số lượng nước đi hợp lệ
if (!(cin >> m)) return 0;
vector<int> moves(m);
for (int i = 0; i < m; i++) {
cin >> moves[i];
}
int t; // Số lượng test case ván chơi
if (!(cin >> t)) return 0;
vector<vector<int>> test_piles(t);
int max_val = 0;
for (int i = 0; i < t; i++) {
int n; // Số đống sỏi
cin >> n;
test_piles[i].resize(n);
for (int j = 0; j < n; j++) {
cin >> test_piles[i][j];
max_val = max(max_val, test_piles[i][j]);
}
}
// Tiền xử lý giá trị Grundy cho mọi trạng thái từ 0 đến max_val
vector<int> g(max_val + 1, 0);
vector<int> vis(max_val + 2, -1);
for (int x = 1; x <= max_val; x++) {
for (int step : moves) {
if (x >= step) {
vis[g[x - step]] = x;
}
}
int mex = 0;
while (vis[mex] == x) {
mex++;
}
g[x] = mex;
}
// Trả lời từng ván chơi bằng tổng XOR các giá trị Grundy
for (int i = 0; i < t; i++) {
int total_xor = 0;
for (int p : test_piles[i]) {
total_xor ^= g[p];
}
if (total_xor != 0) {
cout << "FIRST\n";
} else {
cout << "SECOND\n";
}
}
return 0;
}
import sys
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
m = int(input_data[0])
moves = [int(x) for x in input_data[1:m + 1]]
idx = m + 1
t = int(input_data[idx])
idx += 1
test_piles = []
max_val = 0
for _ in range(t):
n = int(input_data[idx])
idx += 1
piles = [int(input_data[idx + i]) for i in range(n)]
idx += n
test_piles.append(piles)
for p in piles:
if p > max_val:
max_val = p
g = [0] * (max_val + 1)
vis = [-1] * (max_val + 2)
for x in range(1, max_val + 1):
for step in moves:
if x >= step:
vis[g[x - step]] = x
mex = 0
while vis[mex] == x:
mex += 1
g[x] = mex
results = []
for piles in test_piles:
total_xor = 0
for p in piles:
total_xor ^= g[p]
if total_xor != 0:
results.append("FIRST")
else:
results.append("SECOND")
sys.stdout.write("\n".join(results) + "\n")
if __name__ == '__main__':
main()
Các biến thể kinh điển trong đề thi Tin học
- Trò chơi Misère Nim (Bốc viên cuối cùng là THUA):
- Nếu có ít nhất một đống có \(\ge 2\) viên sỏi: Chiến thuật giống hệt Nim thông thường (\(S \ne 0\) thì thắng).
- Nếu tất cả các đống đều chỉ có đúng 1 viên sỏi: Người đi trước thắng khi và chỉ khi tổng số đống là số chẵn!
- Trò chơi chia tách đống (Splitting Games):
- Một nước đi có thể chia 1 đống thành 2 đống nhỏ hơn \(a \to (b, c)\) với \(b + c = a\), \(b, c \ge 1\) và \(b \ne c\) (trò chơi Grundy).
- Khi đó, trạng thái mới là hợp của hai đống sỏi độc lập, nên giá trị Grundy của nước đi này là: \[G(b) \oplus G(c)\] \[G(a) = \text{mex}(\{ G(b) \oplus G(c) \mid b + c = a, b \ne c \})\]
- Trò chơi trên đồ thị có hướng:
- Đặt một quân tốt tại đỉnh \(u\). Hai người chơi luân phiên di chuyển quân tốt theo cung có hướng. Ai không đi tiếp được là thua.
- Trò chơi này trực tiếp áp dụng \(G(u) = \text{mex}(\{G(v) \mid u \to v\})\) bằng thuật toán sắp xếp tô pô hoặc DFS có nhớ.
Luyện ngay trên Big-O Coding
Để củng cố kiến thức và kiểm tra trực tiếp độ chính xác của chương trình, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:
Vì sao hàm MEX lại đảm bảo tính tương đương giữa trạng thái game và đống sỏi Nim?
Trong trò chơi Nim, một đống sỏi kích thước \(k\) cho phép người chơi bốc để chuyển về bất kỳ đống sỏi có kích thước nào trong tập \(\{0, 1, 2, \dots, k - 1\}\). Hàm \(\text{mex}\) được định nghĩa chính xác để thỏa mãn hai tính chất này:
- Từ trạng thái \(u\) có \(G(u) = k\), bạn luôn có thể chuyển tới các trạng thái có giá trị Grundy là bất kỳ số nguyên nào từ \(0\) đến \(k - 1\).
- Từ trạng thái \(u\), bạn không bao giờ có thể chuyển trực tiếp tới một trạng thái khác cũng có giá trị Grundy bằng \(k\). Hai tính chất này biến trạng thái \(u\) hành xử hoàn toàn đồng nhất với một đống sỏi Nim kích thước \(k\)!
Trò chơi có chu trình (vòng lặp vô hạn) có giải bằng Sprague-Grundy được không?
Định lý Sprague-Grundy tiêu chuẩn chỉ áp dụng cho đồ thị phi chu trình (DAG - không có trạng thái lặp lại). Nếu trò chơi cho phép đi vòng tròn vô hạn dẫn tới hòa cờ (Draw), ta phải chuyển sang sử dụng thuật toán lan truyền trạng thái trên đồ thị có chu trình (Game on general directed graphs) bằng phương pháp khử bậc vào (Degree reduction / BFS ngược từ các đỉnh kết thúc).
Nếu max_val lên tới 10^9 thì tính hàm Grundy như thế nào?
Khi giới hạn trạng thái quá lớn (\(10^9\)), ta không thể dùng mảng để tính quy hoạch động từng bước. Cách xử lý thực chiến:
- Hãy viết code chạy tay tính \(G(x)\) cho 50 đến 100 giá trị nhỏ đầu tiên.
- Quan sát quy luật: Hầu hết các trò chơi tổ hợp đều có giá trị Grundy tuần hoàn (chu kỳ \(T\)) hoặc có công thức đóng dạng bitwise!
- Dùng công thức đóng hoặc modulo chu kỳ để tìm \(G(x)\) trong \(O(1)\).
Nguồn tham khảo
- CP-Algorithms - Sprague-Grundy theorem. Nim - Toàn cảnh lý thuyết trò chơi tổ hợp và chứng minh định lý Sprague-Grundy.
- VNOI Wiki - Trò chơi Nim & Định lý Sprague-Grundy - Trò chơi Nim, định lý Bouton, hàm MEX và định lý Sprague-Grundy, viết bằng tiếng Việt.
- USACO Guide - Game Theory - Trò chơi Nim, giá trị Grundy và bài tập áp dụng.
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


