Mô phỏng thuật toán Trò chơi Wythoff

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

Trò Wythoff: hai đống, mỗi lượt lấy tuỳ ý từ MỘT đống hoặc lấy CÙNG số lượng từ CẢ HAI đống; tìm các thế THUA bằng luật tham lam mex.

Ý tưởng

Với k = 0, 1, 2, ...: đặt a = mex (toạ độ nhỏ nhất chưa bị chiếm), b = a + k; cặp (a, b) và ảnh gương (b, a) là thế THUA.

Chiếm hai toạ độ a và b rồi tăng k; khoảng cách b − a tăng đều theo k.

Vì sao đúng

Các thế THUA có dạng (⌊kφ⌋, ⌊kφ²⌋) với φ là tỉ lệ vàng (dãy Beatty); luật mex sinh đúng dãy này vì mỗi toạ độ số nguyên xuất hiện đúng một lần giữa hai dãy Beatty bù nhau.

Mã Python

def cold_positions(n):
    P = [[False] * n for _ in range(n)]   # P[a][b] = losing position
    used = [False] * (2 * n)              # coordinate already claimed
    k = 0
    while True:                           # k = 0, 1, 2, ...
        a = next(i for i in range(2 * n) if not used[i])   # mex
        b = a + k                         # Beatty gap grows by k
        if a >= n:                        # out of the n x n board
            break
        if b < n:
            P[a][b] = P[b][a] = True      # losing position + mirror
        used[a] = used[b] = True          # claim both coordinates
        k += 1
    return P

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