Mô phỏng thuật toán Trò Bash (lấy 1..K viên)

Bash Game · Nhóm: Lý thuyết trò chơi

Trò Bash: có n viên sỏi, mỗi lượt lấy 1..K viên, ai lấy viên cuối thì THẮNG; thế THUA đúng là bội của (K+1).

Ý tưởng

Tính win[s] từ nhỏ lên lớn: win[s] = true nếu tồn tại nước đi tới một thế THUA của đối thủ (win[s-m] = false).

win[0] = false (hết nước đi thì thua); kết quả cho thấy thế THUA rơi đúng vào bội của (K+1).

Vì sao đúng

Chiến lược cân bằng: nếu đối thủ lấy x viên, mình lấy (K+1)−x viên để mỗi vòng vơi đúng K+1, giữ đối thủ luôn ở bội của (K+1); ai bị đẩy vào bội của (K+1) sẽ thua.

Mã Python

def bash_game(n, K):
    win = [False] * (n + 1)      # win[0] = False: no move => lose
    for s in range(1, n + 1):
        # winning if some move reaches a losing state for the opponent
        win[s] = any(not win[s - m] for m in range(1, K + 1) if s - m >= 0)
    return win   # win[s] == False  => losing state (multiples of K+1)

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