Algorithm: Định lý Sprague – Grundy

Trong bài viết này, chúng ta sẽ tìm hiểu một lý thuyết về trò chơi: định lý Sprague – Grundy. Đây là một định lý rất quan trọng, đặc biệt hữu ích trong các cuộc thi về lập trình, nhờ nó, chúng ta có thể viết được kẻ thắng người thua ngay cả khi trò chơi còn chưa bắt đầu.

Nhắc đến định lý Sprague – Grundy, chúng ta không thể không nói đến trò chơi Nim kinh điển. Định lý Sprague – Grundy sẽ cho chúng ta lời giải cho những game như vậy, tuy nhiên, Nim chỉ là một trường hợp nhỏ, chúng ta có thể áp dụng định lý Sprague – Grundy cho rất nhiều trò chơi khác nhau.

Nim game

Trong phần này, chúng ta sẽ tìm hiểu qua một chút về trò chơi Nim.

Có nhiều biến thể khác nhau của trò chơi, nhưng về cơ bản, nội dung của chúng sẽ như sau:

Có một vài đống đá, mỗi đống sẽ có một số lượng biết trước các viên đá. Hai người sẽ chơi với nhau, đến lượt của mình, mỗi người sẽ lấy ra một số viên đá (ít nhất là 1 viên) từ một đống đá bất kỳ. Ai là người có lượt chơi cuối cùng sẽ là người chiến thắng. (Cũng có nghĩa là ai không thể tiếp tục cuộc chơi sẽ là người thua cuộc.)

Một ví dụ cụ thể hơn, giả sử chúng ta có 2 người chơi A và B với 3 đống đá có lần lượt là 3, 4, 5 viên. Giả sử người chơi A đi bước đầu tiên.

Lý thuyết chỉ ra rằng, ngay khi nghe xong điều kiện trên, chúng ta có thể đưa ra đáp án ai sẽ là người giành chiến thắng

Nếu cả A và B đều lựa chọn cách chơi tối ưu (nghĩa là họ không mắc một sai lầm nào trong bước đi của họ), thì người chơi A sẽ giành chiến thắng nếu tổng Nim của game khác không. Ngược lại, người chơi B sẽ chiến thắng, bất kể hai người đi như thế nào.

Thử áp dụng lý thuyết xem sao. Tổng Nim của game này sẽ là 3 XOR 4 XOR 5 = 2, vậy người chơi A sẽ là người chiến thắng, bất kể người chơi B có dùng thủ đoạn gì đi chăng nữa.

Lý thuyết trên đã được chứng minh là chính xác. Không tin bạn cứ thử chơi mà xem.

Như vậy, việc thắng thua của game Nim này sẽ được quyết định bới các yếu tố sau:

• Ai là người chơi đầu tiên
• Trạng thái bắt đầu của game

Chỉ cần vậy, chúng ta đã biết chắc chắn ai là người chiến thắng, ngay cả khi không cần chơi game.

Bây giờ, mở rộng bài toán một chút, giả sử mỗi lượt người, người chơi chỉ có thể lấy ra tối đa 3 viên đá (không phải bất kỳ số đá nào). Chúng ta có thể biết được ai là người chiến thắng nữa hay không.

Câu trả lời là có, chúng ta có thể biết được dựa vào định lý Sprague-Grundy

Định lý Sprague-Grundy

Định lý Sprague-Grundy là một định lý áp dụng cho các trò chơi mở rộng hơn của trò chơi Nim kinh điển. Nội dung của định lý như sau:

Có một trò chơi tổng hợp, hợp thành từ N trò chơi nhỏ giống nhau, và có 2 người chơi A và B. Nếu cả A và B đều có lựa chọn tối ưu trong mỗi bước đi của họ (nghĩa là không ai mắc một sai lầm nào), thì người chơi đầu tiên sẽ giành chiến thắng nếu XOR của các số Grundy của từng trò chơi nhỏ cho kết quả khác 0. Ngược lại, nếu kết quả này bằng 0, người chơi đầu tiên sẽ thất bại, bất kể anh ta dùng cách gì đi nữa.

Định lý trên được chính minh bởi hai nhà toán học Roland Sprague (người Đức) vào năm 1935 và Patrick Michael Grundy (người Anh) vào năm 1939. Hai nhà toán học đã nghiên cứu và phát triển định lý trên một cách độc lập. Do dó, dù thời gian có cách nhau một chút, định lý vẫn được công nhận cho cả hai người.

Áp dụng định lý Sprague-Grundy khi nào?

Chúng ta có thể áp dụng định lý Sprague-Grundy cho bất cứ trò chơi tổ hợp cân bằng nào. Trò chơi cân bằng là các trò chơi phải thỏa mãn điều kiện sau:

• Mọi người chơi luôn luôn biết rõ ràng về trạng thái hiện tại của trò chơi
• Tại mỗi bước, bất cứ người chơi nào cũng đều có thể thực hiện các bước đi như nhau
• Trò chơi sẽ kết thúc sau một số hữu hạn các bước (tức là trò chơi chắc chắn sẽ kết thúc và thắng – thua chứ không lặp vô hạn)

Chú ý rằng, một số trò như cờ vua, cờ caro không phải dạng game này. Ví dụ, với môn cờ vua, mỗi người chơi chỉ có thể điều khiển các quân cờ của chính mình mà không thể di chuyển quân của đối thủ được.

Với các game tổ hợp cân bằng, chúng ta có thể áp dụng định lý Sprague-Grundy theo các bước như sau:

• Chia trò chơi lớn thành các trò chơi nhỏ giống nhau
• Tính số Grundy cho từng trò chơi nhỏ
• Tính XOR của tất cả các số Grundy tính được
• Nếu kết quả khác 0, người chơi đầu tiên sẽ thắng. Ngược lại, anh ta sẽ thua.

Số Grundy

Số Grundy là một số tự nhiên định nghĩa trạng thái của trò chơi. Số Grundy còn tên gọi khác là Nimber có thể tính toán được cho mọi trò chơi tổ hợp cân bằng (không chỉ áp dụng cho riêng Nim).

Tuy nhiên, trước khi tính toán số Grundy, chúng ta cần tìm hiểu một khái niệm khác trước, đó là Mex.

MeX

MeX (Minimum eXculdant) của một tập hợp là số tự nhiên nhỏ nhất không có mặt trong tập hợp đó. Ví dụ:

MeX(∅) = 0
Mex({1, 2, 3}) = 0
MeX({0, 2, 4}) = 1
MeX({0, 1, ..., n}) = n + 1

Tính số Grundy

Số Grundy có thể tính dựa theo định nghĩa sau:

Số Grundy/Nimber bằng 0 trong trường hợp người chơi đầu tiên thua ngay lập tức (tức là anh ta không thể đưa ra bất kỳ bước đi nào), và bằng MeX của các số Grundy của mọi bước đi có thể tiếp theo.

Nghe định nghĩa có vẻ khó hiểu nhỉ. Chúng ta sẽ xem xét một vài ví dụ cụ thể để minh họa cho việc tính toán số Grundy này.

Ví dụ 1

Trò chơi của chúng ta có một đống n viên đá, trong mỗi lượt chơi, người chơi có thể lấy đi số viên đá bất kỳ (ít nhất là 1 viên). Bây giờ chúng ta sẽ tính số Grundy của trò chơi này.

Trước hết, nếu n = 0, tức là không có viên đá nào, người chơi đầu tiên sẽ thua ngay lập tức, vậy Grundy(0) = 0.

Nếu n = 1, người chơi có thể lấy ra 1 viên đá, vậy nhưng bước đi tiếp theo (cho người chơi khác) là 0 viên. Vậy Grundy(1) = MeX({Grundy(0)}) = MeX({0}) = 1.

Tương tự, nếu n = 2, người chơi có thể lấy 1 viên đá hoặc lấy 2 viên đá. Vậy người chơi tiếp theo có thể lấy số đá tương ứng là (1, 0). Do đó Grundy(2) = MeX({Grundy(1), Grundy(0)}) = MeX({1, 0}) = 2

Tiếp tục như vậy, chúng ta sẽ đi đến kết luận Grundy(n) = n.

Ví dụ 2

Giờ đây, chúng ta sẽ nâng độ khó lên một chút. Giả sử cũng có một đống với n viên đá, nhưng mỗi người chởi chỉ có thể lấy tối đa 3 viên đá. Chúng ta cần tính số Grundy của trò này.

Tương tự như trường hợp trước, nếu n = 0, người chơi đầu tiên sẽ thua ngay lập tức. Grundy(0) = 0.

Nếu n = 1, người chơi có thể lấy 1 viên đá và người chơi tiếp theo có lựa chọn duy nhất là 0. Vậy Grundy(1) = MeX({Grundy(0)}) = MeX({0}) = 1.

Nếu n = 2 hoặc n = 3, cũng tương tự như ví dụ trước, chúng ta sẽ tính được Grundy(2) = 2, Grundy(3) = 3.

Giờ mọi việc sẽ phức tạp hơn khi n = 4. Nếu có 4 viên đá, người chơi chỉ có thể lấy 1, 2, hoặc 3 viên từ đống đá đó. Và người chơi tiếp theo sẽ có những lựa chọn tương ứng là 3, 2, 1 viên. Do đó, Grundy(4) = MeX({Grundy(3), Grundy(2), Grundy(1)})

Với n > 4, chúng ta sẽ có công thức truy hồi là Grundy(n) = Mex({Grundy (n-1), Grundy (n-2), Grundy (n-3)})

Thông thường trong lập trình, số Grundy vẫn được tính bằng cách sử dụng các hàm đệ quy.

Áp dụng định lý Sprague – Grundy

Chúng ta sẽ xem xét việc áp dụng định lý Sprague – Grundy với một ví dụ cụ thể như sau:

Có 3 đống đá lần lượt có 3, 4 và 5 viên đá. Có 2 người chơi, trong mỗi lượt, người chơi có thể lấy ra tối đa 3 viên đá từ 1 đống bất kỳ. Người chơi cuối cùng là người chiến thằng. Chúng ta có thể biết ai là người chiến thắng hay không nếu mọi người chơi đều đưa ra lựa chọn tối ưu trong lượt chơi của mình.

Trước hết, chúng ta nhận định rằng đây là một trò chơi tổ hợp cân bằng. Chúng ta có thể chia trò chơi này thành các trò nhỏ hơn như sau:

Dễ dàng nhận ra rằng, mỗi đống đá trong trò chơi này sẽ được xử lý độc lập và không liên quan gì đến nhau. Vậy chúng ta sẽ chia trò chơi thành các trò nhỏ hơn, mỗi trò tương ứng với một đống đá.

Chúng ta sẽ tính Grundy cho từng trò nhỏ này

Grundy(3) = 3
Grundy(4) = 0
Grundy(5) = 1

Tiếp theo là XOR của các số Grundy mà chúng ta đã tính được:

3 XOR 4 XOR 5 = 2

Với kết quả trên, chúng ta sẽ biết chắc chắn rằng, người chơi đầu tiên sẽ là người chiến thắng.

Nếu chúng ta trong một cuộc thi lập trình, số viên đá trong mỗi đống và đưa ra output là người giành chiến thắng trong trò chơi đó, chúng ta có thể sử dụng dụng định lý Sprague – Grundy với code như sau:

def mex(a_set):
    m = 0
    while m in a_set:
        m += 1
    return m


def grundy(n, grundies):
    grundies[0] = 0
    grundies[1] = 1
    grundies[2] = 2
    grundies[3] = 3

    if grundies[n] > 0:
        return grundies[n]
    a_set = set()
    for i in range(1, 4):
        a_set.add(grundy(n - i, grundies))
    grundies[n] = mex(a_set)
    return grundies[n]

def winner(piles, grundies, n):
    xor_val = grundies[piles[0]]

    for i in range(1, n):
        xor_val ^= grundies[piles[i]]
    print("Player %d will win." % (xor_val != 0 and 1 or 2))

if __name__ == '__main__':
    num_piles = int(input("number of piles: "))
    piles = list(map(int, input('stones in each pile: ').split()))
    grundies = [-1] * (max(piles) + 1)
    for i in range(max(piles)):
        grundy(i, grundies)
    winner(piles, grundies, num_piles)