Mô phỏng thuật toán Nim ngược (misère)

Misère Nim · Nhóm: Lý thuyết trò chơi

Nim ngược (misère): giống Nim nhưng ai lấy quân CUỐI thì THUA; luật thắng phụ thuộc thế cờ đã tới tàn cuộc hay chưa.

Ý tưởng

Nếu MỌI đống đều <= 1 (tàn cuộc): người sắp đi THẮNG khi và chỉ khi SỐ ĐỐNG là CHẴN.

Nếu còn ít nhất một đống >= 2: dùng đúng luật Nim thường · thế THẮNG khi nim-sum khác 0, nước thắng đưa nim-sum về 0.

Vì sao đúng

Khi còn đống lớn, việc lật ngược điều kiện thắng ở quân cuối chưa ảnh hưởng nên nim-sum vẫn đúng; chỉ đến tàn cuộc (mọi đống <= 1) misère mới lật ngược Nim thường, và khi đó chỉ còn đếm chẵn·lẻ số đống còn quân.

Mã Python

def misere_nim_winner(piles):
    nim_sum = 0
    for p in piles:                 # XOR all pile sizes
        nim_sum ^= p
    all_small = all(p <= 1 for p in piles)
    if all_small:                   # endgame: only piles of size 0 or 1
        return "first player wins" if len(piles) % 2 == 0 else "first player loses"
    if nim_sum == 0:                # some pile >= 2: normal-Nim rule
        return "first player loses"
    for i, p in enumerate(piles):   # find a winning move
        target = p ^ nim_sum
        if target < p:              # reduce pile i to target -> nim_sum becomes 0
            return (i, target)

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