Mô phỏng thuật toán Nim nhiều đống (nim-sum)

Multi-pile Nim (XOR) · Nhóm: Lý thuyết trò chơi

Nim nhiều đống: mỗi lượt lấy tuỳ ý quân từ đúng một đống, ai lấy quân cuối thì THẮNG; đánh giá thế cờ bằng nim-sum (XOR mọi kích thước đống).

Ý tưởng

Tính nim-sum = XOR mọi kích thước đống; nim-sum = 0 là thế THUA cho người sắp đi, khác 0 là thế THẮNG.

Nước thắng: tìm đống p có (p XOR nim-sum) < p, giảm đống đó về (p XOR nim-sum) để đưa nim-sum về 0.

Vì sao đúng

Định lý Bouton: thế THẮNG khi và chỉ khi nim-sum khác 0; từ thế nim-sum khác 0 luôn có nước đưa nim-sum về 0, còn từ thế nim-sum 0 mọi nước đều phá thế 0, nên người luôn khôi phục nim-sum 0 sẽ thắng.

Mã Python

def nim_winner(piles):
    nim_sum = 0
    for p in piles:            # XOR all pile sizes
        nim_sum ^= p
    if nim_sum == 0:
        return "second player wins"   # losing position for mover
    for i, p in enumerate(piles):     # find a winning move
        target = p ^ nim_sum
        if target < p:                # reduce pile i to target
            return (i, target)        # this move makes nim_sum 0

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