¶ Lý thuyết trò chơi
Người viết: Nguyễn Nhật Minh Khôi
Reviewer chính: Trần Quang Lộc, Hồ Ngọc Vĩnh Phát
Trong thực tế, có rất nhiều loại trò chơi khác nhau, tuy nhiên trong bài viết này, chúng ta sẽ chỉ giới hạn trong các trò chơi tổ hợp cân bằng vì độ phổ biến của nó trong lập trình thi đấu.
¶ Giới thiệu: trò chơi bốc sỏi
Trước khi đi vào các định nghĩa, chúng ta sẽ đi qua một ví dụ để hiểu được vấn đề mà lý thuyết trò chơi với trò chơi tổ hợp cân bằng giải quyết.
¶ Phát biểu trò chơi
Hai bạn An và Bình đang chơi bốc sỏi, trò chơi được phát biểu như sau: cho một đống sỏi có viên sỏi, hai bạn sẽ luân phiên bốc sỏi từ đống sỏi, mỗi lượt chỉ được bốc , hoặc viên sỏi, người lấy được viên sỏi cuối cùng sẽ là người chiến thắng. Biết rằng An đi trước, Bình đi sau. Hãy tìm một chiến thuật để An có thể chiến thắng trò chơi.
¶ Cách giải
Ta sẽ tiếp cận bài toán bằng cách giải những trường hợp đơn giản trước, sau đó rút ra quy luật chung cho trường hợp tổng quát.
Với hoặc , An luôn chiến thắng bằng cách lấy hết sỏi trong lượt bốc đầu tiên.
Với , An không thể lấy hết sỏi trong lần bốc đầu tiên vì số sỏi được lấy tối đa mỗi lần chỉ là . Nếu Bình là một người thông minh và luôn biết được những nước đi tối ưu, An sẽ luôn thua do:
- Nếu An chọn lấy viên, số sỏi còn lại là , lúc đó Bình có thể dùng chiến thuật của An ở trên, đó là lấy hết sỏi để chiến thắng.
- Tương tự, nếu An chọn lấy hoặc viên thì bạn cũng sẽ thua.
Do đó, trong trường hợp này An nên cố gắng kéo dài trò chơi bằng cách chỉ bốc viên sỏi và hi vọng Bình sẽ phạm sai lầm. Tuy nhiên như đã nói, nếu Bình là một người chơi có chiến thuật tối ưu thì An sẽ luôn thua. Từ trường hợp này, ta thấy trường hợp là một trường hợp "xấu" do nó đặt người ở lượt đi hiện tại vào thế bất lợi.
Từ nhận xét trên, ta thấy nếu , An luôn có thể thắng bằng cách lấy sỏi sao cho số sỏi còn lại là , mục đích là để ép Bình vào trường hợp bất lợi (cũng là có lợi cho An).
Ta rút ra được một quy luật của trò chơi: nếu ở lượt của ai mà số sỏi là hay nói cách khác chia hết cho thì người đó sẽ ở vị trí bất lợi.
Vậy chiến thuật tối ưu của An dựa trên số sỏi hiện tại sẽ là:
- Nếu thì An sẽ bốc viên sỏi để ép Bình vào trường hợp bất lợi .
- Nếu thì An sẽ bốc viên sỏi để kéo dài trò chơi và chờ sai lầm của Bình.
với là phép lấy phần dư.
¶ Trò chơi tổ hợp cân bằng
Trò chơi ở trên chính là một ví dụ điển hình cho trò chơi tổ hợp cân bằng. Trong phần này, chúng ta sẽ tổng quát hóa bài toán này thành định nghĩa trò chơi tổ hợp cân bằng để thể giải được một lớp bài toán lớn hơn.
¶ Định nghĩa
Trò chơi tổ hợp là trò chơi gồm: hai người chơi (ở đây gọi người chơi trước là và người chơi sau là ), một tập hữu hạn các trạng thái (viết tắt của State) có thể đạt được của trò chơi. Mỗi người chơi có một tập các bước di chuyển hợp lệ để di chuyển từ trạng thái này sang trạng thái khác (gọi là luật chơi) và một tập các trạng thái kết thúc gọi là (viết tắt của Terminal). Hai người chơi sẽ luân phiên di chuyển từ trạng thái này sang trạng thái khác. Người đến được trạng thái kết thúc trước sẽ là người chiến thắng.
Trong trò chơi ví dụ, giả sử thì mỗi trạng thái sẽ là số sỏi còn lại hiện tại của trò chơi. Do đó tập trạng thái của trò chơi là (hình dưới).
Giả sử đang ở trạng thái , ta có thể di chuyển hợp lệ đến trạng thái (lấy ra viên sỏi), (lấy ra viên sỏi) hoặc (lấy ra viên sỏi). Do đó ta có các phần tử thuộc tập di chuyển hợp lệ (hình dưới).
Từ đó, ta nhận xét được tập các bước di chuyển hợp lệ của cả hai người chơi sẽ là tất cả những cặp số nguyên () sao cho (từ trạng thái có số sỏi chỉ có thể lấy ra , , hoặc viên sỏi) và (số sỏi lấy ra không được phép lớn hơn số sỏi đang có).
Trò chơi kết thúc khi không còn viên sỏi nào để bốc, do đó tập trạng thái kết thúc của cả hai người chơi là . Khi đó người bốc viên sỏi cuối cùng sẽ là người thắng.
Khi hai người chơi có tập các bước di chuyển hợp lệ và tập trạng thái kết thúc giống nhau thì trò chơi được gọi là trò chơi tổ hợp cân bằng. Nói cách khác, hai người chơi chỉ khác nhau ở đúng một điểm là người này được đi trước, người kia đi sau.
Trò chơi bốc sỏi ở ví dụ chính là một trò chơi tổ hợp cân bằng, do cả An và Bình đều chỉ được cho phép bốc , , hoặc viên sỏi một lần và đều thắng khi bốc được viên sỏi cuối cùng.
¶ Chiến thuật thắng
Mục tiêu của chúng ta khi giải các bài toán với trò chơi tổ hợp cân bằng là tìm ra chiến thuật mà ở đó một trong hai người chơi luôn có thể ép người còn lại thua. Chiến thuật như vậy gọi là một chiến thuật thắng.
Rõ ràng khi phân tích trò chơi bốc sỏi, ta thấy rằng nếu cả An và Bình đều chơi tối ưu thì chỉ cần biết được trạng thái ban đầu của trò chơi, ta có thể xác định được người đi trước (An) sẽ thắng hay thua. Nếu số sỏi ban đầu là chia hết cho , Bình chắc chắn sẽ thắng do bạn sẽ luôn ép An đi tới trạng thái có chia hết cho và cuối cùng là (cũng chia hết cho ). Lập luận tương tự, nếu không chia hết cho thì chắc chắn An sẽ thắng.
Vậy từ đây, ta thấy với một trò chơi tổ hợp cân bằng, chỉ cần biết trạng thái ban đầu, ta có thể suy ra được ai sẽ là người chiến thắng. Để phục vụ cho việc đưa ra chiến thuật thắng, người ta phân loại các trạng thái cùa trò chơi thành 2 tập và :
- : tập các trạng thái sao cho nếu trạng thái ban đầu của trò chơi là thì người chơi trước luôn chiến thắng.
- : tập các trạng thái sao cho nếu trạng thái ban đầu của trò chơi là thì người chơi sau luôn chiến thắng.
Trong trò chơi ví dụ, nếu số sỏi ban đầu là thì
Từ định nghĩa trên, và sẽ thỏa ba tính chất sau:
- Tập phải chứa toàn bộ trạng thái kết thúc.
- Với mỗi trạng thái thuộc tập , tồn tại ít nhất một trạng thái đến được từ mà thuộc tập .
- Với mỗi trạng thái thuộc tập , tất cả các trạng thái đến được từ phải thuộc tập .
Tới đây, có thể bạn sẽ đặt ra câu hỏi: Liệu mọi trạng thái của trò chơi đều thuộc một trong hai tập hay ? Ta có thể chứng minh dễ dàng bằng quy nạp mạnh theo số bước tối đa để đạt tới trạng thái kết thúc. Nếu muốn, bạn đọc có thể tham khảo thêm ở phần 1.1. Impartial game - Game Theory, Alive.
Ràng buộc đầu tiên xác định trường hợp cơ bản nhất. Hai ràng buộc sau sẽ giúp chúng ta liên tục đệ quy từ trường hợp cơ bản để xây dựng được tập và hoàn chỉnh. Ta sẽ thấy rõ điều này ở phần Thuật toán xác định tập và .
Khi xây dựng được tập và theo các ràng buộc trên, ta có thể dễ dàng xây dựng chiến thuật thắng cho người chơi như sau (do đây là trò chơi tổ hợp cân bằng nên chiến thuật thắng của cũng sẽ tương tự):
- Nếu bắt đầu ở trạng thái thuộc , luôn đi tới trạng thái thuộc để ép đi vào trạng thái thuộc . Do người thắng là người đi vào trạng thái kết thúc, mà trạng thái kết thúc lại thuộc nên chắc chắn sẽ thắng.
- Nếu bắt đầu ở trạng thái thuộc , chỉ có thể kéo dài ván đấu và đợi sơ hở của ( đi vào vị trí thuộc ) và dùng chiến thuật thắng ở trường hợp đầu. Tuy nhiên nếu cũng chơi tối ưu thì chắc chắn sẽ thua.
Qua đó, ta thấy được ý nghĩa của việc đặt tên tập và . là viết tắt của positive, đặt tên như vậy vì người nào đi đến trạng thái này sẽ có lợi, đó là lý do tại sao các trạng thái kết thúc lại thuộc , vì người chơi nào đi tới được trạng thái kết thúc sẽ có lợi (thắng trò chơi). Tương tự, là viết tắt của negative, đặt tên như vậy vì người nào đi đến trạng thái thuộc tập sẽ bị bất lợi (vì người kia sẽ luôn tìm cách đi được vào trạng thái thuộc ).
¶ Thuật toán xác định tập P và N
Ta có ý tưởng thuật toán để tìm tập và như sau:
// Hàm kiểm tra một trạng thái thuộc P (true) hay N (false)
bool isInP(State u) {
if (u in T) // nếu u là trạng thái kết thúc thì u thuộc P
return true;
// duyệt qua tất cả các trạng thái v trong tập hợp S
for (State v in S)
if (u, v) in Q and isInP(v)
return false; // nếu có v thuộc P thì u thuộc N
return true; // nếu không thì u thuộc P
}
Ý tưởng ở đây chính là đệ quy:
- Nếu trạng thái đang xét là trạng thái kết thúc thì thêm vào tập . Đây chính là trường hợp cơ bản của quá trình đệ quy.
- Nếu không là trạng thái kết thúc thì đệ quy đến những trạng thái mà từ có thể di chuyển trực tiếp đến. Nếu có bất kỳ nào thuộc tập thì thuộc tập , ngược lại (tất cả đều thuộc ) thì thuộc .
Ở đây có một chú ý về cách cài đặt trên, đó là kiểu dữ liệu State là một kiểu dữ liệu tượng trưng để lưu một trạng thái của trò chơi. Trong thực tế, trạng thái hay được biểu diễn bằng một số nguyên int, tuy nhiên nhiều trường hợp trạng thái của chúng ta không ở dạng số nguyên, khi đó có một số cách các bạn có thể xem xét để lưu trạng thái như: bitmask, hashmap (unordered_map trong c++).
Tuy nhiên, thuật toán này có một nhược điểm, đó là gọi lại cùng một giá trị quá nhiều lần do không lưu lại kết quả trong quá trình đệ quy. Cách giải quyết chính là quy hoạch động top-down (hay còn gọi là đệ quy có nhớ), trong đó ta có một mảng lưu lại kết quả của những trạng thái đã từng xét. Để hiểu thêm, bạn hãy xem cài đặt tìm trò chơi bốc sỏi ở phần ví dụ sau.
¶ Ví dụ cài đặt thuật toán cho trò chơi bốc sỏi
Đầu tiên, ta cần thêm các thư viện cần thiết, cũng như khai báo mảng để nhớ kết quả của những trạng thái đã đệ quy.
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 100000; // số trạng thái tối đa
int dp[MAX_N];
Sau đó, ta viết hàm xác định xem trạng thái có thuộc không như sau
bool isInP(int u) {
if (dp[u] != -1) // nếu u đã được tính trước đó thì
return dp[u];
if (u == 0) { // u = 0 là trạng thái kết thúc nên thuộc P
dp[u] = 1;
return 1;
}
// Từ u chỉ có thể đi tới các v hợp lệ
for (int v = u - 1; v >= max(u - 3, 0); v--)
if (isInP(v)) {
dp[u] = 0;
return false;
}
// u không đi được trạng thái nào thuộc P
dp[u] = 1;
return true;
}
Ở đây quy ước giá trị của mảng như sau:
- nghĩa là trạng thái đã xét và không thuộc , hay nói cách khác thuộc .
- nghĩa là trạng thái đã xét và thuộc .
- nghĩa là trạng thái chưa xét.
Sở dĩ ta quy ước như vậy vì c++ có cơ chế implicit casting. Nói đơn giản, khi trả về trong hàm isInP(u), sẽ được tự động ép kiểu về bool với quy tắc: là , các giá trị khác là .
Cài đặt này tối ưu thời gian đệ quy bằng hai ý sau:
- Khi tính xong, trước khi trả về giá trị thì ta lưu giá trị lại vào một mảng và ở đầu hàm
- Ta trả về nếu (tức đã được tính trước đó).
Cuối cùng, ta viết hàm main để nhập xuất và kết luận nghiệm. Lưu ý trước khi thực hiện quá trình tìm tập và ta phải khởi tạo mảng thành toàn bằng hàm fill do thư viện chuẩn của c++ cung cấp.
int main() {
int n;
cin >> n;
fill(dp, dp + n + 1, -1);
if (!isInP(n)) cout << "A win";
else cout << "B win";
return 0;
}
¶ Trò chơi Nim chuẩn
Sau khi đã tìm hiểu lý thuyết trò chơi tổ hợp cân bằng tổng quát, phần tiếp theo ta sẽ áp dụng lý thuyết đó vào một bài toán kinh điển trong lý thuyết trò chơi - trò chơi Nim - đại diện tiêu biểu cho trò chơi tổ hợp cân bằng.
¶ Phát biểu trò chơi
Có đống sỏi, và mỗi đống lần lượt có sỏi, trong đó mỗi số là một số nguyên không âm. Mỗi trạng thái trò chơi tương ứng với mỗi bộ cho biết số sỏi của từng đống này.
Có hai người chơi thay phiên nhau bỏ sỏi. Người chơi trong lượt hiện tại có thể loại bỏ bao nhiêu sỏi tùy thích, miễn là tất cả các sỏi đều cùng một đống. Hình thức hơn, người chơi sẽ chọn một đống sỏi và số lượng sỏi để loại bỏ khỏi đống (), sau đó thay bằng . Chú ý rằng người chơi không thể bỏ qua lượt của mình mà không bỏ viên sỏi nào cả. Sau đó, đến lượt người chơi kia loại bỏ sỏi, lần lượt như vậy tới khi trò chơi kết thúc.
Trò chơi kết thúc khi không còn sỏi trên bàn chơi. Người chiến thắng là người lấy được viên sỏi cuối cùng. Nói cách khác, người thua cuộc là người đầu tiên không thể lấy sỏi trong lượt của mình.
Trò bốc sỏi ở ví dụ trên chính là biến thể của trò chơi Nim chuẩn, khác hai chỗ là ở đây chỉ có một đống sỏi () và số sỏi lấy ra tối đa ở mỗi đống là .
¶ Giá trị Nim
Mục tiêu lớn nhất của chúng ta vẫn là xác định xem ai là người thắng nếu cả hai người chơi tối ưu, hay nói cách khác là xác định được chiến thuật thắng.
Tuy nhiên, khi bắt tay vào làm, bạn sẽ gặp ngay một rào cản, đó là trạng thái của trò chơi đang được biểu diễn dưới dạng một bộ các số nguyên chứ không phải một số nguyên, điều đó gây khó khăn cho chúng ta khi tổng quát hóa lời giải và lập trình, một khó khăn rất dễ thấy đó là nếu chúng ta xài mảng nhiều chiều để lưu trạng thái đã tính thì có khả năng khi thay đổi đoạn code cũ sẽ không dùng được nữa do số chiều của mảng đã thay đổi. Theo suy nghĩ tự nhiên, chúng ta sẽ cố gắng tìm cách kết hợp thông tin của bộ trạng thái số lại thành một số nguyên duy nhất. Một cách khả thi để làm điều này chính là giá trị Nim, ký hiệu là .
Đầu tiên, hãy giải quyết trường hợp đơn giản nhất - chỉ có một đống sỏi duy nhất với viên sỏi.
- Theo trực giác, vì thông tin duy nhất ta có là số lượng sỏi trong đống, ta có thể giả sử rằng giá trị Nim của trường hợp này là một số nguyên cho biết số sỏi còn lại.
- Chúng ta thấy rằng nếu thì trạng thái trò chơi hiện tại thuộc , ngược lại nếu thì trạng thái trò chơi hiện tại thuộc . Điều này có thể giải thích bằng việc nếu số sỏi là số dương, người đi trước luôn có thể lấy hết sỏi nên người đi sau luôn thua. Từ trường hợp đơn giản này, ta mường tượng được điều mà giá trị Nim phản ánh: trạng thái trò chơi hiện tại thuộc khi giá trị Nim dương và thuộc khi giá trị Nim bằng .
Tiếp theo, chúng ta sẽ tìm cách ghép các đống sỏi đơn lại thành một trò chơi hoàn chỉnh gồm đống sỏi. Cụ thể hơn, ta sẽ tìm ra một phép toán để biết được giá trị Nim của trò chơi mới khi kết hợp hai trò chơi có giá trị Nim lần lượt là và lại. Ta sẽ liệt kê một số tính chất cần có của phép toán này để có thể gộp các giá trị của cột lại:
- , và , nghĩa là có tính chất kết hợp và giao hoán. Tính chất này có thể giải thích bằng lập luận rằng thứ tự các cọc không thực sự quan trọng nên khi đổi thứ tự kết hợp thì giá trị Nim không thay đổi.
- , nghĩa là, phần tử trung hòa của toán tử này là . Điều này rất hiển nhiên vì nếu bạn thêm một đống sỏi trống vào trò chơi, thì trò chơi vẫn không thay đổi, do đó giá trị Nim vẫn như cũ.
- , nghĩa là phần tử đối của mỗi trạng thái trò chơi là chính nó. Tại sao điều này lại đúng? Giả sử chúng ta có hai đống sỏi giống nhau, mỗi đống có viên sỏi. Lúc đó, người đi sau luôn có một chiến lược chiến thắng, đó là chỉ sao chép bước đi của người đi trước! Điều tương tự xảy ra với trường hợp tổng quát. Do đó, người đi trước sẽ luôn là người thua, tức trạng thái trò chơi thuộc , như ta đã lập luận ở ví dụ trước, trạng thái thuộc tương ứng với , do đó .
Ba thuộc tính này, đặc biệt nhất là tính chất giúp chúng ta tìm ra một ứng cử viên tìm năng, đó là phép bitwise XOR. Và quả thật phép toán này cũng chính là đáp án chúng ta cần tìm, định lý Bouton được trình bày ở phía dưới sẽ chứng minh tính đúng đắn của việc này.
Thực chất, phép bitwise XOR chỉ là phép cộng modulo trên từng bit, do đó chúng ta hay gọi giá trị Nim là tổng Nim. Tổng Nim của một trò chơi có trạng thái thu được bằng cách thực hiện phép XOR các lại với nhau.
Ví dụ: với trò chơi Nim có ba đống sỏi với số sỏi lần lượt là , , thì tổng Nim là .
¶ Định lý Bouton
Tuy nhiên, trong phần trình bày ở phía trên có một giả thuyết rất quan trọng mà ta chỉ mới thừa nhận chứ chưa chứng minh, đó là trạng thái trò chơi hiện tại thuộc khi giá trị Nim dương và thuộc khi giá trị Nim bằng . Thực ra, nhận xét đó là một định lý đã được chứng minh, gọi là định lý Bouton. Phần này khuyến khích bạn đọc hiểu về các tính chất của phép toán bitwise XOR.
Định lý Bouton: trạng thái của trò chơi Nim thuộc khi và chỉ khi tổng Nim của nó bằng .
Chứng minh
Gọi là tập gồm các trạng thái có tổng Nim bằng và là tập gồm các trạng thái có tổng Nim lớn hơn . Ta nhận xét hai tập này có các tính chất sau:
Đầu tiên, trạng thái kết thúc là thuộc do có tổng Nim là
Thứ hai, với một trạng thái thuộc (), ta luôn có thể đi tới một trạng thái thuộc (). Để chứng minh, chọn một đống sỏi thứ có sỏi và biến nó thành sao cho , ta có được tổng Nim mới như sau:
Lưu ý rằng phép XOR không giống phép cộng thông thường. Ở phép cộng hai số nguyên dương, kết quả luôn lớn hơn các toán hạng ban đầu. Tuy nhiên, trong phép XOR điều này không xảy ra, kết quả có thể lớn hơn hoặc nhỏ hơn các toán hạng ban đầu. Do đó việc ta có thể đảm bảo luôn tồn tại đống sỏi thỏa mãn yêu cầu không phải là điều hiển nhiên và cần được chứng minh.
Vì nên biểu diễn nhị phân của luôn tồn tại bit trái nhất bằng (tạm gọi là ).Khi đó, xét bit thứ của tất cả các cột , ta có số lượng có bit thứ bằng phải lẻ (theo tính chất của phép XOR), do đó luôn tồn tại một đống sỏi có bit thứ bằng . Chọn đống sỏi có bit thứ bằng đó để thực hiện bốc sỏi, ta thấy bởi vì khi XOR bit tại vị trí bằng , do đó luôn mất một bit tại vị trí so với .
Ví dụ, nếu trò chơi Nim hiện tại có cột có số sỏi lần lượt là , , , , thì thao tác tính tổng Nim và chọn cột để lấy sỏi ra sẽ diễn ra như hình dưới
Cuối cùng, với một trạng thái thuộc (tức ), mọi cách đi đều dẫn tới trạng thái thuộc (tức ). Ta có thể chứng minh dễ dàng bằng phương pháp phản chứng. Giả sử trạng thái trò chơi hiện tại là có tổng Nim và tồn tại một đống sỏi sao cho khi lấy bớt sỏi từ ra trạng thái trò chơi mới có tổng Nim . Khi đó
Điều này có nghĩa là ta không bốc viên sỏi nào từ đống ra cả, mà theo giả thuyết ta phải bốc ít nhất một viên (), vì vậy không thể tồn tại đống sỏi nào thỏa mãn yêu cầu.
Ví dụ, nếu trò chơi Nim hiện tại có đống có số sỏi lần lượt là , , , thì tổng Nim . Xét bit đầu tiên từ phải qua, ta thấy được số lượng bit được bật tại vị trí này là số chẵn (, tương ứng với bit đầu tiên của và ). Tương tự, số lượng các bit được bật tại các vị trị khác đều có tính chất này. Điều này không phải là trùng hợp mà do tính chất của phép XOR, nếu muốn bit thứ trong kết quả bằng thì số lượng bit thứ được bật trong các toán hạng phải là số chẵn. Từ đây ta nhận thấy, việc bỏ sỏi ở một đống sỏi chỉ có thể làm thay đổi số lượng bit được bật tại mỗi vị trí lên hoặc xuống 1 đơn vị, do đó dù cho lấy sỏi ở cột nào đi nữa thì vẫn sẽ xuất hiện một vị trí có số bit được bật là lẻ.
Rõ ràng và thỏa mãn ba điều kiện theo định nghĩa của tập và trong trò chơi tổng quát, vì vậy và .
Qua định lý Bouton, chúng ta có một cách xác định tập và dựa trên tổng Nim, hơn thế nữa với việc chứng minh định lý Bouton, ta không chỉ biết được trạng thái thắng/thua của trò chơi mà còn có thể xây dựng được một chiến thuật thắng cụ thể.
¶ Cài đặt
Hàm isInP trong trường hợp này rất đơn giản, nếu lưu số lượng sỏi mỗi đống vào vector số nguyên thì thuật toán chỉ đơn giản là XOR của các phần tử với nhau, độ phức tạp thuật toán là .
bool isInP(vector<int> v) {
int g = 0;
for (auto p: v)
g ^= p;
return (g == 0);
}
¶ Misère Nim
Ngoài trò chơi Nim chuẩn, có rất nhiều biến thể của trò chơi Nim. Một trong số đó là misère Nim, cách chơi giống như trò chơi Nim bình thường, tuy nhiên thay vì người lấy viên sỏi cuối cùng sẽ thắng, trong Misère Nim thì người lấy viên sỏi cuối cùng sẽ thua.
Khi đó, dựa vào trạng thái bắt đầu, ta có thể xác định việc thắng thua như sau:
- Nếu tất cả đống sỏi đều có số sỏi nhỏ hơn hơn (tức chỉ gồm các đống sỏi có và viên): nếu số lượng đống sỏi còn sỏi là lẻ (tức giá trị Nim ) thì người chơi đầu tiên sẽ thua, ngược lại (tức ) thì người chơi đầu tiên sẽ thắng.
- Các trường hợp còn lại: Người chơi đầu tiên sẽ thắng nếu giá trị Nim hiện tại , ngược lại sẽ thua. Chiến thuật để giành chiến thắng là chơi theo chiến lược Nim thông thường, trừ khi bước di chuyển tiếp theo làm các đống sỏi đều có nhỏ hơn viên, lúc đó người chơi thực hiện nước đi hiện tại sẽ đặt số lượng đống có viên sỏi là số lẻ để ép người kia phải bốc viên cuối cùng. Ta có thể chứng minh được nếu một người đang ở trạng thái có giá trị Nim , anh ta luôn có thể quyết định số lượng đống sỏi là chẵn hay lẻ và do đó luôn là người chiến thắng.
¶ Định lý Sprague-Grundy
¶ Đồ thị của trò chơi
Nếu xem mỗi trạng thái trong tập trạng thái là một đỉnh, mỗi cạnh có hướng thể hiện cho việc từ trạng có thể di chuyển đến trạng thái (tức là một phần tử thuộc tập các bước di chuyển di chuyển hợp lệ ) thì ta có thể xây dựng một đồ thị có hướng với tập đỉnh và tập cạnh tương ứng với tập trạng thái và tập các bước di chuyển như đã nói. Ở đây có một quan sát quan trọng rằng ta tất cả các trạng thái kết thúc sẽ ứng với những đỉnh những đỉnh có bậc ra bằng (tức từ đỉnh này không đi tới được bất kỳ đỉnh nào khác)
Ví dụ: trong trò chơi bốc sỏi ở phần đầu, giả sử ta chỉ có một đống sỏi viên, thì đồ thị của trò chơi sẽ như hình dưới, trạng thái kết thúc có bậc ra bằng .
Cũng cần chú ý rằng các trò chơi được xem xét trong phần định lý Sprague-Grundy có một tính chất quan trọng, đó là chúng sẽ kết thúc trong hữu hạn bước. Khi đó, hiển nhiên đồ thị trò chơi phải không tồn tại chu trình, vì nếu tồn tại chu trình, sẽ tồn tại trường hợp người chơi cố tình đi theo chu trình đó và sẽ không bao giờ đến được đỉnh kết thúc, nghĩa là khi đó trò chơi sẽ lặp vĩnh viễn. Loại đồ thị có hướng không có chu trình như trên còn có thể gọi tắt là DAG (Directed Acyclic Graph).
¶ Trò chơi tổng
Để có thể kết hợp nhiều trò chơi đơn lẻ với nhau, ta đặt ra khái niệm trò chơi tổng.
Trò chơi tổng: Cho trò chơi và với là tập trạng thái, tập các bước di chuyển hợp lệ và tập trạng thái kết thúc ứng với trò chơi và , trò chơi tổng là trò chơi có:
- Tập trạng thái , tức trạng thái của trò chơi tổng là các cặp trạng thái với là trạng thái thuộc và là trạng thái thuộc .
- Tập các bước di chuyển hợp lệ , nghĩa là một bước di chuyển hợp lệ trong trò chơi tổng sẽ tương ứng với việc thực hiện một bước di chuyển hợp lệ trong trò chơi con hoặc và giữ nguyên trạng thái trò chơi còn lại.
- Tập các trạng thái kết thúc $$T = { (x_1, x_2) : x_1 \in T_1 \wedge x_2 \in T_2 }$$, nghĩa là trạng thái kết thúc của trò chơi tổng là trạng thái mà cả hai trò chơi và đều kết thúc.
Ví dụ: trò chơi Nim có đống sỏi có thể xem như trò chơi tổng của ba trò chơi , và , với là trò chơi chỉ bốc ở đống sỏi thứ , là trò chơi chỉ bốc ở đống sỏi thứ , là trò chơi chỉ bốc ở đống sỏi thứ .
¶ Mở rộng trò chơi Nim
Định lý Bouton đã cho chúng ta một cách giải rất đẹp cho trò chơi Nim chuẩn, nhưng trong thực tế, hầu hết các bài lý thuyết trò chơi trong lập trình thi đấu sẽ không là trò chơi Nim chuẩn mà sẽ được thay đổi luật chơi ở một số điểm. Lúc ấy, định lý Bouton sẽ không thể giải quyết các dạng bài này. Trong phần này, ta sẽ trình bày hai định lý quan trọng để giải quyết các trò chơi cân bằng kết thúc trong hữu hạn bước. Tuy nhiên ta sẽ chỉ trình bày về động lực hình thành và định nghĩa của hai định lý. Để hiểu rõ hơn, bạn đọc hãy đọc phần Phụ lục để hiểu được chứng minh.
Để giải quyết, ta quay lại chiến lược ban đầu của mình - phân tách trạng thái trò chơi thành nhiều trò chơi con có cùng cấu trúc, tìm một số tính chất đặc biệt của mỗi trò chơi con, sau đó kết hợp chúng lại với nhau để có câu trả lời cho trò chơi gốc.
Hãy lấy ví dụ với một biến thể của trò chơi Nim chuẩn, trong đó chúng ta có đống sỏi, luật chơi vẫn như cũ, chỉ khác là số sỏi phải bốc ở mỗi lượt phải là số chính phương ().
Đầu tiên, ta cũng xét trò chơi ở dạng đơn giản nhất: chỉ có một đống sỏi duy nhất với viên. Vậy làm thế nào để bạn biết đó là trạng thái thuộc hay trạng thái thuộc ?
Hãy nhìn trò chơi dưới góc độ đồ thị. Đồ thị này có đỉnh có nhãn lần lượt là các số nguyên từ đến . Mỗi đỉnh đồ thị tương ứng với một trạng thái trò chơi, trong đó nhãn của nó cho biết có bao nhiêu sỏi còn lại trong đống hiện tại. Hình dưới là ví dụ trò chơi với một đống sỏi có số sỏi .
Rõ ràng đỉnh là đỉnh kết thúc, do đó nó là đỉnh thuộc . Các đỉnh tiếp theo có thể xác định là thuộc hay như hình dưới
Tuy nhiên, cách làm ở trên chỉ cho ta trạng thái định tính của từng trạng thái, để phục vụ cho việc ghép các trò chơi lại, ta cần một hàm định lượng. Hàm mà chúng ta sẽ dùng có tên là hàm Sprague-Grundy, với một trạng thái thì giá trị Sprague-Grundy được định nghĩa như sau:
Trong định nghĩa trên có dùng hàm mex (minimum excludant), hàm này sẽ nhận vào một tập hợp và trả về số nguyên không âm nhỏ nhất sao cho không nằm trong tập hợp, ví dụ . Ngoài ra, quy ước . Từ đó, ta có thể phát biểu bằng lời rằng giá trị Sprague-Grundy của một đỉnh sẽ là mex của tập hợp các giá trị Sprague-Grundy của sao cho từ có thể di chuyển trực tiếp đến .
Câu hỏi đặt ra là: tại sao lại là hàm Sprague-Grundy? Hàm này có ý nghĩa gì trong việc giải các trò chơi tổ hợp cân bằng?
Để thấy rõ hơn ý nghĩa của hàm Sprague-Grundy, ta có thể ví dụ biến thể của trò chơi Nim ở trên.
Quan sát ví dụ ở trên, ta có nhận xét rằng các trạng thái thuộc đều có và các trạng thái thuộc đều có . Điều này làm ta nhận ra sự tương đồng của giá trị Sprague-Grundy với một đại lượng ở phần trước - giá trị Nim. Đó là cảm nhận ban đầu để có định lý sau.
Định lý 1: Trong một trò chơi tổ hợp cân bằng, trạng thái thuộc khi và chỉ khi giá trị Sprague-Grundy .
Vậy với hàm Sprague-Grundy, ta đã giải quyết được trò chơi đơn giản nhất, vấn đề tiếp theo là giải trò chơi tổng. Ta cũng sẽ tìm một phép toán để tìm ra giá trị Sprague-Grundy của trò chơi tổng từ hai trò chơi thành phần. Cũng như trò chơi Nim, ta sẽ thấy phép toán này có các tính chất kết hợp, giao hoán, phần tử trung hòa là và phần tử đối của một trò chơi là chính nó. Do đó, ta sẽ lại thấy phép bitwise XOR là phép toán mà chúng ta cần tìm. Tính đúng đắn của phép toán bitwise XOR được khẳng định bằng định lý sau
Định lý 2: với trò chơi tổng và lần lượt là các trạng thái của trò chơi thành phần , khi đó:
Với lần lượt là hàm Sprague-Grundy của trò chơi .
Ví dụ: với trò chơi Nim biến thể với luật bốc các số chính phương như trên, nhưng bây giờ ta có đống sỏi lần lượt có viên sỏi. Khi đó ta có thể coi mỗi đống sỏi là một trò chơi thành phần, vì vậy giá trị Sprague-Grundy của trò chơi tổng là , vậy đây là trạng thái mà người chơi đi đầu tiên sẽ giành chiến thắng.
Hai định lý 1 và 2 trong phần này có ý nghĩa rất quan trọng, nó cho ta cách giải bất cứ trò chơi tổ hợp cân bằng nào, miễn là trò chơi đó luôn kết thúc trong hữu hạn bước, hay nói cách khác đồ thị của trò chơi là một DAG. Định lý 2 giúp chúng ta phân rã trò chơi phức tạp ra thành những trò chơi thành phần đơn giản hơn và định lý 1 giúp chúng ta giải quyết những trò chơi thành phần đơn giản đó.
Như vậy, ta thấy rằng thực ra cách giải trò chơi Nim cũng chỉ là một trường hợp riêng của cách giải với giá trị Sprague-Grundy này, trong đó giá trị Nim của trò chơi Nim chỉ có một đống viên sỏi tương đương với giá trị Sprague-Grundy
Ví dụ với trò chơi Nim chỉ có một đống viên sỏi
và định lý Bouton tương đương định lý 2.
¶ Định lý Sprague-Grundy
Định lý Sprague-Grundy phát biểu rằng: mọi trò chơi tổ hợp cân bằng kết thúc trong hữu hạn bước đều tương đương với trò chơi Nim một cột, trong đó trạng thái của trò chơi hiện tại tương ứng với trạng thái trò chơi Nim một cột có viên sỏi, trong đó là giá trị Sprague-Grundy của .
Sở dĩ có nhận xét này là vì ở trạng thái có giá trị Sprague-Grundy , hàm mex cho chúng ta một "lời hứa", lời hứa đó là: từ với giá trị Sprague-Grundy , ta có thể đi đến tất cả các trạng thái có giá trị Sprague-Grundy từ đến . Điều này có sự tương đồng với việc trong trò chơi Nim một cột, từ trạng thái có thể đi đến tất cả trạng thái từ đến .
Tuy nhiên, luật chơi trò chơi Nim một cột này không giống với bình thường, vì trong trò chơi bình thường từ trạng thái ta chỉ có thể đi tới các trạng thái có giá trị nhỏ hơn . Tuy nhiên, từ một trạng thái có giá trị Sprague-Grundy là ta lại có thể đi đến một trạng thái có giá trị Sprague-Grundy , tương ứng với việc thêm viên sỏi vào trò chơi Nim một cột. Mặc dù vậy, người kia có thể trung hòa thao tác thêm sỏi, làm cho trạng thái của trò chơi quay về trạng thái bằng cách lấy đi viên sỏi trong lượt tiếp theo. Hơn nữa, vì điều kiện trò chơi sẽ kết thúc trong hữu hạn bước, chắc chắn sẽ có một lúc người chơi không thể thêm sỏi vào nữa và sẽ phải chơi như trò chơi Nim thông thường. Do vậy, ta kết luận trò chơi Nim với phép thêm sỏi không làm kết quả của trò chơi Nim thay đổi so với luật chơi thông thường.
Định lý Sprague-Grundy cho ta sự liên tưởng giữa một trò chơi tổ hợp cân bằng với trò chơi Nim một cột - một trò chơi tổ hợp cân bằng đơn giản, cung cấp cho ta một cách nhìn trực quan hơn về trò chơi tổ hợp cân bằng. Tuy bản thân định lý không có nhiều ứng dụng, nhưng các định lý phụ trợ cho việc chứng minh định lý này lại là nền móng quan trọng cho việc giải các trò chơi tổ hợp cân bằng, chính là các định lý 1 và 2 ở phần trước. Để tránh bài viết quá dài dòng, ở đây sẽ không trình bày lại chứng minh của định lý này, bạn đọc có thể tham khảo thêm về cách chứng minh định lý Sprague-Grundy bằng khái niệm trò chơi tương đương được đề cập đến trong wiki.
¶ Ví dụ
Ta sẽ ví dụ với trò chơi sau
Cho bàn cờ với quân mã trên đó. Không giống như quân mã trong cờ vua truyền thống, những quân mã này chỉ có thể di chuyển như thể hiện trong hình bên dưới (vì vậy tọa độ của các con sẽ chỉ bị giảm chứ không tăng, đảm bảo trò chơi kết thúc trong hữu hạn bước). Cùng một lúc có thể có nhiều quân ở cùng một ô của bàn cờ. Hai người chơi thay phiên nhau di chuyển. Khi tới lượt, người chơi chọn một trong các quân mã và di chuyển nó. Người chơi không thể thực hiện nước đi ở lượt của mình là người thua.
Đầu tiên, vì luật chơi cho phép có nhiều quân mã trên cùng ô nên các quân mã có thể di chuyển độc lập với nhau, như vậy ta có thể coi trò chơi có quân mã là trò chơi tổng của trò chơi thành phần, trong đó trò chơi thành phần thứ chỉ có quân mã thứ trên bàn cờ.
Ta sẽ giải trò chơi với một quân mã trước. Rõ ràng kết quả của trò chơi khi này chỉ phụ thuộc vào vị trí của quân mã, do đó một trạng thái của trò chơi tương ứng với một cặp số nguyên cho biệt vị trí của quân mã. Khi đó ta sẽ tính giá trị Sprague-Grundy của từng vị trí bằng hàm sau
// khai báo các thông tin của trò chơi
const int MAXN = 100;
int N;
int g[MAXN + 1][MAXN + 1];
int di[] = {-2, -2, -1, 1};
int dj[] = {1, -1, -2, -2};
// hàm tính mex của một vector U
int mex(vector<int>& U) {
int res = 0;
sort(U.begin(), U.end());
for (int x: U)
if (res == x)
++res;
return res;
}
int calculateGValue(int i, int j) {
if (g[i][j] != -1)
return g[i][j];
int res = 0;
vector<int> U;
// lấy giá trị SP của các trạng thái mà (i,j) có thể đi tới
for (int k = 0; k < 4; ++k) {
int x = i + di[k];
int y = j + dj[k];
if (1 <= x && x <= N && 1 <= y && y <= N)
U.push_back(calculateGValue(x, y));
}
// tính mex và trả về giá trị
res = mex(U);
g[i][j] = res;
return res;
}
Ý tưởng của hàm trên chỉ đơn giản là tại mỗi vị trí ta tính mex bằng công thức đệ quy như định nghĩa. Để di chuyển đến các vị trí hợp lệ, ta có hai mảng hằng số di và dj kích thước tương ứng với bốn bước di chuyển như đề bài miêu tả, với mỗi vị trí ta xét xem vị trí có nằm trên bàn cờ không, nếu có thì mới thêm thêm giá trị Grundy tại vị trí đó vào vector U. Lưu ý là ở đây để tối ưu thời gian chạy thì ta sẽ dùng kỹ thuật đệ quy có nhớ đã trình bày ở phần Trò chơi tổ hợp cân bằng, do đó trước khi gọi tính giá trị Sprague-Grundy của từng ô trong bảng thì phải khởi tạo tất cả giá trị của mảng bằng .
Trước tiên, ta định nghĩa cấu trúc dữ liệu để lưu trữ thông tin của một quân mã, đó một struct gồm hai thông tin tương ứng là tọa độ dòng và cột của quân mã.
struct Cell {
int row, col;
};
Khi đã có giá trị Grundy của tất cả các ô từ đến , để tính giá trị Sprague-Grundy của trò chơi có quân mã ta chỉ cần áp dụng định lý 2, đó là XOR giá trị Sprague-Grundy của quân mã lại. Thuật toán sẽ như sau:
bool isFirstWin(vector<Cell> Q) {
int res = 0;
for (Cell x: Q)
res ^= g[x.row][x.col];
return (res > 0);
}
Độ phức tạp thời gian của thao tác tính giá trị Sprague-Grundy của trò chơi thành phần là do ta phải duyệt tất cả các ô trong bàn cờ, nhưng do dùng đệ quy có nhớ nên ta không phải tính một ô nào quá lần. Độ phức tạp thời gian của thao tác XOR giá trị Sprague-Grundy là , mà , do đó độ phức tạp thời gian của toàn bộ thuật toán là .
¶ Bài tập luyện tập
¶ Phụ lục
Phần này sẽ chứng minh cơ sở toán học cho hai định lý và ở phần Định lý Sprague-Grundy, để hiểu rõ hơn tại sao lại có hai định lý trên, bạn đọc hãy đọc phần này.
Định lý 1: Trong một trò chơi tổ hợp cân bằng, trạng thái thuộc khi và chỉ khi giá trị Sprague-Grundy .
Chứng minh:
Tương tự phần trước, ta sẽ gọi là tập các trạng thái có và là tập các trạng thái có và cố gắng chứng minh điều sau:
Thứ nhất, các trạng thái kết thúc chắc chắn sẽ thuộc do .
Thứ hai, với một trạng thái thuộc , khi đó , điều đó có nghĩa là trong các trạng thái đến được từ luôn tồn tại một trạng thái có , tức thuộc . Ta có thể chứng minh dễ dàng bằng phản chứng rằng nếu tất cả các trạng thái đến được từ có thì rõ ràng phần tử nhỏ nhất không nằm trong tập là , tức khi đó trái với giả thuyết ban đầu là .
Thứ ba, với mọi trạng thái thuộc mà không phải trạng thái kết thúc, khi đó với mọi trạng thái đến được từ thì , tức mọi cách đi từ luôn dẫn đến trạng thái . Ta cũng sẽ chứng minh phát biểu này bằng phản chứng, giả sử tồn tại một trong các trạng thái đến được từ có , lúc đó rõ ràng , trái với giả thuyết ban đầu là .
Từ ba tính chất vừa chứng minh, ta thấy rõ ràng tập và tương đương với tập và theo định nghĩa của hai tập này.
Định lý 2: với trò chơi tổng và lần lượt là các trạng thái của trò chơi thành phần , khi đó:
Với lần lượt là hàm Sprague-Grundy của trò chơi .
Chứng minh:
Do là một trò chơi tổ hợp cân bằng, do đó theo định lý 1 thì