Tower Breakers · Nhóm: Lý thuyết trò chơi
Trò phá tháp: có N tháp cao M, mỗi lượt hạ một tháp xuống một chiều cao NHỎ HƠN là ước của chiều cao hiện tại; ai hết nước đi thì THUA. Kết quả rút về quy tắc chẵn lẻ.
Người 1 THUA khi và chỉ khi M == 1 (không tháp nào hạ được) HOẶC N chẵn (người 2 soi gương lại đúng nước của người 1).
N lẻ và M > 1: người 1 hạ một tháp về 1 để đưa về thế N chẵn có tháp chết rồi tự soi gương · THẮNG.
Với N chẵn, người 2 luôn bắt chước nước của người 1 ở tháp còn lại nên khôi phục đối xứng sau mỗi cặp nước và không bao giờ cạn nước trước; M == 1 chặn mọi nước ngay từ đầu; N lẻ M > 1 cho người 1 giành thế đối xứng có lợi.
def tower_breakers(N, M):
# a move reduces a tower to any smaller height that divides it
# player 1 loses iff M == 1 (no move) or N is even (mirror strategy)
if M == 1 or N % 2 == 0:
return 2 # player 2 wins
return 1 # player 1 wins (odd N, M > 1)
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.