Phân tích: Google Royale

Google Royale có lẽ là bài khó tiếp cận nhất mà Google Code Jam từng ra. Trước khi xử lý được dữ liệu lớn, ta phải hiểu rất nhiều, bởi quan hệ giữa xác suất thắng và số tiền ban đầu khá phức tạp và không thể duyệt đủ \(10^{16}\) trạng thái. Dù tình huống có vẻ giống bài Millionaire trước đây, lượng tính toán dùng ở bài đó là không khả thi ở đây.

Trước hết hãy hiểu một vòng cược. Gọi tiền cược ban đầu là \(y\). Nếu thua \(k\) lần rồi thắng, tổng lợi nhuận là \(y2^{k-1}-y2^{k-2}-y2^{k-3}-\cdots-y\), luôn bằng \(y\) bất kể \(k\). Nếu thua cả vòng, lợi nhuận âm và giá trị chính xác phụ thuộc vào số lần đã gấp đôi.

Mấu chốt của toàn bài là kỳ vọng lợi nhuận của một vòng cược luôn đúng bằng 0, bất kể tiền cược ban đầu và số lần sẵn sàng gấp đôi. (Kỳ vọng lợi nhuận là lợi nhuận “trung bình”; chính thức là \(\sum p_i i\), với \(p_i\) là xác suất thắng đúng \(i\) đô la.) Kỳ vọng bằng 0 vì tại mỗi bước, xác suất thắng một khoản tiền và thua đúng khoản ấy đều là 50%. Lợi nhuận trung bình của từng bước là 0, nên của toàn bộ quá trình cũng là 0.

Nói chung có nhiều chiến lược cùng tối đa hóa xác suất thắng. Trước mắt ta chỉ tìm một chiến lược; việc tìm mức cược tối đa sẽ được quay lại sau.

Quan sát 1: Nếu có \(x\) đô la, không có lý do gì bắt đầu một vòng với tiền cược lớn hơn \(V-x\).

Lý do: Cược hơn \(V-x\) thì thắng luôn đưa ta vượt \(V\). Giảm cược một chút vẫn tốt như cũ khi thắng, còn khi thua thì không tệ hơn. Vì vậy cứ cược ít hơn. Từ đây ta chỉ xét chiến lược tuân theo quan sát này, nên dù may hay rủi cũng không bao giờ có hơn \(V\) đô la.

Quan sát 2: Cố định một chiến lược. Gọi \(P\) là xác suất đạt \(V\), và \(L\) là kỳ vọng số tiền cuối cùng với điều kiện thua. Khi đó

Vì \(V,A\) cố định, tối đa hóa \(P\) tương đương tối thiểu hóa \(L\).

Lý do: Sau bất kỳ số vòng cược nào, kỳ vọng lợi nhuận vẫn là 0, tức kỳ vọng tổng tiền vẫn là \(A\). Khi kết thúc, ta thắng với xác suất \(P\) và có đúng \(V\) theo Quan sát 1; hoặc thua với xác suất \(1-P\) và có kỳ vọng \(L\). Do đó

Bài toán giờ là làm \(L\) nhỏ nhất có thể.

Quan sát 3: Nếu có \(x\) đô la, ta chỉ cần làm một trong hai việc: (1) cược đúng \(x\) và tiếp tục gấp đôi cho tới khi thắng hoặc không thể gấp đôi; hoặc (2) cược đúng 1 và không gấp đôi dù thua.

Lý do: Một chiến lược tối ưu nào đó cược \(y\) và gấp đôi tối đa \(k\) lần. Nếu một bước thắng, cuối cùng ta có \(x+y\); nếu không, ta có \(x-z\). Kỳ vọng vẫn là \(x\). Ta sẽ thay chiến lược này bằng một chiến lược tuân theo hai dạng trên (có thể qua nhiều vòng) mà khả năng đạt \(x+y\) không kém.

Trường hợp 1: \(x-z\ge0\). Thay vì cược \(y\), liên tục cược 1 và không gấp đôi; chỉ dừng khi tiền tăng đến \(x+y\) hoặc giảm đến \(x-z\). Vì \(x-z\ge0\), việc tiếp tục cho đến một trong hai kết quả là hợp lệ. Chiến lược mới có đúng hai kết quả như cũ và kỳ vọng cuối vẫn là \(x\). Theo Quan sát 2, hai chiến lược có cùng kết quả thắng, kết quả thua và kỳ vọng thì có cùng xác suất đạt kết quả tốt hơn. Do đó hai chiến lược tương đương.

Trường hợp 2: \(x-z<0\). Liên tục cược 1, không gấp đôi, và chỉ dừng khi tiền tăng đến \(x+y\) hoặc giảm đến \(y\). Nếu đến \(y\), cược \(y\) rồi gấp đôi cho tới khi thắng hoặc phá sản. Nếu thắng, quay lại bước đầu, tiếp tục cược 1 đến khi đạt \(x+y\) hoặc trở lại \(y\); nếu lại đến \(y\), lại cược \(y\) và lặp. Giống chiến lược cũ, cuối cùng ta có đúng \(x+y\) hoặc phá sản. Nhưng dễ kiểm tra rằng \(L\) ở đây nhỏ hơn nghiêm ngặt so với chiến lược cũ, trong khi kỳ vọng vẫn là \(x\). Quan sát 2 bảo đảm chiến lược mới tốt hơn nghiêm ngặt.

Vậy mọi chiến lược đều có thể chuyển sang cược 1 hoặc cược \(x\) mà không tệ hơn, chứng minh Quan sát 3.

Quan sát này rất mạnh, nhưng vẫn chưa đủ: với \(10^{16}\) số tiền khả dĩ, ta không thể thử cả hai lựa chọn ở mọi trạng thái. Cần thêm một ý tưởng để giảm mạnh không gian tìm kiếm.

Quan sát 4: Với mỗi số nguyên không âm \(i\), gọi \(M_i\) là số nguyên lớn nhất thỏa \(M_i2^i\le M\). Gọi chúng là các “điểm uốn”. Ta không bao giờ nên cược toàn bộ tiền trừ khi số tiền hiện có là một điểm uốn.

Lý do: Xét chiến lược tất tay ở \(x\) với \(M_i<x<M_{i-1}\). Đặt \(y=\lceil x/2\rceil\). Ta có \(2y\le x+1\le M_{i-1}\), nên nếu cược \(y\) thì có thể gấp đôi \(i\) lần.

Chiến lược hiện tại hoặc cho \(2x\), hoặc cho \(x(1-1-2-\cdots-2^{i-1})=-2x(2^{i-1}-1)\). Nhưng \(y/x\ge1/2>(2^{i-1}-1)/(2^i-1)\). Vì vậy số tiền khi thua của chiến lược này lớn hơn \(-2y(2^i-1)\).

Xét chiến lược thay thế: thay vì tất tay tại \(x\), liên tục cược 1, không gấp đôi, và chỉ dừng khi tiền tăng đến \(2x\) hoặc giảm đến \(y\). Ở trường hợp sau, tất tay và gấp đôi tối đa \(i\) lần hoặc đến khi thắng. Như trên, tiền cược không bao giờ vượt \(M\), nên hợp lệ. Nếu thắng, bắt đầu lại từ đầu. Giống chiến lược cũ, cuối cùng ta có \(2x\) hoặc phá sản. Khi phá sản, số tiền là \(y(1-1-2-\cdots-2^i)=-2y(2^i-1)\). Giá trị thua này nhỏ hơn của chiến lược cũ, nên theo Quan sát 2, chiến lược mới có xác suất đạt \(2x\) cao hơn. Do đó chiến lược cũ không thể tối ưu.

Khi nào nên tất tay

Gọi một số tiền là “điểm tất tay” nếu ta nên cược toàn bộ khi có số tiền ấy. Quan sát 4 bảo đảm các điểm tất tay là tập con của các điểm uốn, nhưng không phải mọi điểm uốn đều là điểm tất tay.

Xét các điểm uốn theo thứ tự tăng. Điểm nhỏ nhất là 1 và chắc chắn là điểm tất tay. Với điểm uốn nhỏ thứ hai, vì mục tiêu theo Quan sát 2 là giảm \(L\), ta tính số tiền nhận được nếu tất tay tại đó rồi thua. Nếu đây là tổng thấp nhất từ trước đến nay, ta nên tất tay tại đó; nếu không, tốt hơn là cược 1 cho đến điểm uốn thấp hơn. Lập luận tương tự áp dụng cho điểm thứ ba, thứ tư, v.v.; nhờ đó có thể nhanh chóng tính một chiến lược tối ưu tại mọi số tiền.

Có hai trường hợp khó cần chú ý:

• Theo Quan sát 1, chỉ xét điểm uốn không quá \(V/2\).
• Tất tay tại \(x\) có thể hiệu quả đúng bằng cược 1 và chờ đến điểm tất tay kế tiếp. Khi đó gọi \(x\) là “điểm tất tay tùy chọn”; các điểm tất tay còn lại là “điểm tất tay nghiêm ngặt”.

Tính xác suất thắng

Gọi \(P_x\) là xác suất đạt \(V\) khi đang có \(x\). Nếu \(x\) không phải điểm tất tay nghiêm ngặt, một chiến lược tối ưu là cược 1 đến khi chạm điểm tất tay nghiêm ngặt ngay trên hoặc dưới \(x\), hoặc chạm chính \(V\). Với mọi \(x\) giữa các điểm ấy,

tức \(P_x-P_{x-1}=P_{x+1}-P_x\). Vì vậy \(P_x\) tuyến tính trong khoảng và tính được khi biết hai đầu mút.

Ta tính \(P\) từ điểm tất tay lớn nhất rồi đi xuống. Giả sử điểm lớn nhất là \(y\), xác suất thua ngay khi tất tay là \(1-p\). Khi đó \(P_y=pP_{2y}\). Theo tính tuyến tính,

Ta biết \(p,V,y\), nên dễ tính \(P_y\). Sau đó dùng cùng thủ thuật cho điểm tất tay lớn thứ hai, thứ ba, v.v. cho đến khi có mọi xác suất.

Tính mức cược tối ưu lớn nhất

Nếu \(A\) là điểm tất tay, dù nghiêm ngặt hay tùy chọn, chắc chắn ta có thể và nên cược \(A\).

Nếu không, xét số tiền \(x\). Khi \(x\) không phải điểm tất tay nghiêm ngặt, ta đã có \(P_x-P_{x-1}=P_{x+1}-P_x\), nên \(P_x\) hoàn toàn tuyến tính giữa các điểm tất tay nghiêm ngặt. Vì vậy chắc chắn có thể tăng tiền cược cho tới khi kết quả thắng hoặc thua đưa ta đến một điểm tất tay nghiêm ngặt ở mỗi phía. Nếu \(x\) chính là điểm tất tay nghiêm ngặt, cược 1 không tối ưu và

tức \(P_x-P_{x-1}>P_{x+1}-P_x\). Đặc biệt, tăng cược thêm sẽ gây bất lợi. Do đó mức cược lớn nhất có thể là khoảng cách giữa \(A\) và điểm tất tay nghiêm ngặt gần nhất.