Mô phỏng thuật toán Số Grundy (trò lấy sỏi)

Grundy Numbers (Subtraction Game) · Nhóm: Lý thuyết trò chơi

Gán cho mỗi thế cờ một số Grundy (số Sprague-Grundy) để biết ai thắng: thế THUA đúng khi số Grundy bằng 0.

Ý tưởng

Tính từ thế nhỏ lên thế lớn: tại thế s, xét tập số Grundy của mọi thế tới được từ s (lấy 1, 2 hoặc 3 viên).

Lấy mex của tập đó · số nguyên không âm nhỏ nhất KHÔNG có trong tập · làm số Grundy của s.

Vì sao đúng

Định lý Sprague-Grundy: một thế là thế THUA (P-position) khi và chỉ khi số Grundy bằng 0; mex đảm bảo từ thế Grundy khác 0 luôn có nước về thế Grundy 0, và từ thế Grundy 0 mọi nước đều tới thế khác 0.

Mã Python

def grundy(n, moves):
    g = [0] * (n + 1)
    for s in range(1, n + 1):
        reach = {g[s - m] for m in moves if s - m >= 0}
        mex = 0
        while mex in reach:   # smallest non-negative not in reach
            mex += 1
        g[s] = mex
    return g   # g[s] == 0  => losing state

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.