chiến lược tối ưu cho một trò chơi 2 người chơi

Question

• 2 người chơi Một & B đang chơi một trò chơi liên quan đến một số n
• Người chơi A làm cho di chuyển đầu tiên & cả hai cầu thủ chơi luân phiên.
• Trong mỗi di chuyển cầu thủ có số n, chọn một số i mà 2^i < n và thay thế n với k = n - 2^i iff số 1s trong biểu diễn nhị phân của k là lớn hơn hoặc bằng số lượng 1s trong biểu diễn nhị phân của n
• trò chơi kết thúc khi không có cầu thủ có thể làm cho một di chuyển, tức là có không tồn tại như một i

Ví dụ:

n = 13 = b1101 

Chỉ có thể i = 1

k = n - 2^i = 11 = b1011 

Một lần nữa, chỉ có thể i = 2

k = n - 2^i = 7 = b111 

Kể từ khi chơi A không thể thực hiện bất kỳ động thái hơn, Một Người Chơi B thắng

Tôi đã suy luận d ở bất kỳ bước nào, chúng ta chỉ có thể chọn một i, sao cho có 0 ở vị trí tương ứng trong biểu diễn nhị phân của n. Ví dụ: nếu n = 1010010, thì tôi chỉ có thể là {0,2,3,5}.

Nhưng tôi không thể di chuyển bất kỳ further.A thuật toán minimax isnt chính xác nổi bật tôi.Tôi sẽ đánh giá cao bất kỳ help.Thanks trước

Answer 1

Giả sử n là không quá lớn, chúng ta có thể sử dụng quy hoạch động để giải quyết vấn đề này. Xác định một mảng A [1: n], trong đó A [i] biểu thị liệu người chơi tôi có thắng được trên i không. Hãy sử dụng việc giải thích:

A[i] = 1, if A wins on input i, 
    A[i] = 0, if A loses on input i. 

Bây giờ A có thể được tính từ dưới lên như sau:

A[1] = 0, A[2] = 1. 
For j=3:n { 
     Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
           (number of 1's in i >= number of 1's in j) 
     Otherwise Assign A[j] = 0 
}