Tổng quan
Nim là trò chơi vô tư nổi tiếng nhất trong lý thuyết trò chơi tổ hợp. Toàn bộ chiến lược của nó gói gọn trong một đại lượng nhị phân — tổng-nim.
Cách giải Trò Chơi Nim từng bước
- Tính tổng-nim: XOR của tất cả kích thước đống (3 ⊕ 4 ⊕ 5 = 2).
- Nếu khác 0 bạn có thể thắng: tìm đống mà XOR với tổng-nim nhỏ hơn chính nó.
- Giảm đống đó về giá trị ấy, làm tổng-nim bằng 0 và đẩy đối thủ vào thế thua.
Mấu chốt
Thế có tổng-nim bằng 0 là thế thua cho người đi: nước nào cũng phá cân bằng, và đối thủ luôn khôi phục được. Vậy hãy để lại tổng-nim bằng 0 sau lượt của bạn.
Biến thể & liên hệ
- Định lý Sprague–Grundy chỉ ra mọi trò chơi vô tư đều quy về một đống Nim tương đương.
- Nim ngược (lấy viên cuối là thua) chỉ cần chỉnh nhẹ ở gần cuối ván.
Câu hỏi thường gặp
Nếu đến lượt tôi mà tổng-nim đã bằng 0 thì sao?
Thì bạn đang ở thế thua nếu đối thủ chơi hoàn hảo — hy vọng duy nhất là họ sai lầm.