Phân tích: Zillionim

Có lẽ bài này không có đến zillion lời giải, nhưng vẫn nhiều hơn những gì có thể bàn hết! Ta chỉ xét vài cách, có cách hiệu quả và có cách không. Bạn có thể chia sẻ cách riêng trong nhóm Google của Code Jam.

Chơi ngẫu nhiên

Nếu luôn chọn đều ngẫu nhiên một nước khả dụng như AI thì sao? Vì tổng số xu rất lớn so với một nước, việc đi trước hay sau không quan trọng lắm khi cả hai bên đều ngẫu nhiên, nên mỗi ván gần như tung đồng xu công bằng. Giả sử xác suất thắng là \(50\%\); theo phân phối nhị thức, xác suất thắng ít nhất \(300/500\) chỉ khoảng \(0{,}0004\%\). Cách này thậm chí không lấy được 1 điểm bộ test 1!

Chiến thuật phản chiếu

Nếu được đi trước, ta có thể bảo đảm thắng. Tưởng tượng đường tâm giữa xu thứ \(10^{12}/2\) và \((10^{12}/2)+1\). Lượt đầu lấy nhóm \(10^{10}\) xu bị đường này chia đôi, từ \(((10^{12}-10^{10})/2)+1\) đến \((10^{12}+10^{10})/2\). Sau mỗi nước đối thủ, phản chiếu nó qua tâm. Ví dụ, nếu họ lấy \(10^{10}\) xu bắt đầu ở số 2, ta lấy \(10^{10}\) xu bắt đầu từ xu áp chót rồi đi sang trái. Đối xứng bảo đảm ta luôn còn nước, nên đối thủ cuối cùng thua.

Ta không đi trước, nhưng có thể thử phản chiếu nước đối thủ. Việc này luôn được trừ khi họ cắt qua tâm. Nếu họ đi gần tâm mà không cắt qua — lấy một xu cách tâm ít hơn \(10^{10}/2\) xu — họ tự bảo đảm thất bại. Nếu họ cắt qua tâm, ta bỏ chiến thuật và đi ngẫu nhiên.

Mô phỏng cho tỷ lệ thắng khoảng \(57{,}5\%\), nhưng chỉ khoảng \(14\%\) cơ hội vượt bộ test 1. Vì nước ta phụ thuộc bộ chấm, ta khó điều chỉnh tính ngẫu nhiên của nó; chỉ kiểm soát phần nào sau một nước làm hại chiến thuật. Nhìn chung nên bỏ cách này.

Chiến thuật \(2 \times 10^{10}\)

Gọi tập ít nhất \(10^{10}\) xu còn lại liên tiếp là một “đoạn”. Với đoạn đúng \(2 \times 10^{10}\), lấy \(10^{10}\) xu đầu hoặc cuối sẽ để lại đúng một nước; lấy nhóm nào khác sẽ không để lại nước, tức “phá hủy” đoạn. Nếu AI đi trong đoạn này, gần như luôn là kiểu thứ hai; xác suất chọn đúng đầu hoặc cuối là không đáng kể.

Đoạn như vậy cho phép kiểm soát chẵn lẻ. Giả sử chỉ còn các đoạn đúng kích thước ấy và đến lượt ta. Nếu số đoạn lẻ, ta phá một đoạn, AI cũng thế, luân phiên đến khi AI hết nước. Nếu số đoạn chẵn, ta lấy nửa đầu một đoạn, để lại nửa sau thành đoạn nhỏ hơn. AI lúc đó rơi vào chính tình thế xấu “số đoạn chẵn” của ta.

Ta tạo tình thế này bằng nhiều nước sớm. Liên tục chọn đoạn lớn nhất dài ít nhất \(3 \times 10^{10}\), bắt đầu tại xu thứ \(2 \times 10^{10}+1\) từ trái, để lại đoạn đúng \(2 \times 10^{10}\) và phần dư bên phải. Với các đoạn dài trong khoảng \((2 \times 10^{10},3 \times 10^{10})\), đi ở giữa để phá chúng. Mục tiêu là loại mọi đoạn lớn trước khi AI phá hết các đoạn chuẩn. AI dễ chọn đoạn lớn hơn đoạn chuẩn cuối cùng nên thường đang giúp ta! Khi mọi đoạn không quá \(2 \times 10^{10}\) và còn ít nhất một đoạn chuẩn, ta đạt tình thế gần khóa chặt nói trên.

Chúng tôi không tính xác suất chính xác, nhưng mô phỏng thắng \(100000/100000\) ván. Xác suất thua quá một trong 500 ván gần như bằng không; kể cả điều tệ nhất xảy ra, ta phần nào kiểm soát tính ngẫu nhiên tổng thể và có thể thử lại với điều chỉnh nhỏ.

Các chiến thuật chẵn lẻ khác

Vòng 1C năm nay có Bacterial Tactics, cũng là trò chơi theo lượt. Phân tích bài ấy nhắc định lý Sprague–Grundy; liệu có thể dùng chiến thuật chẵn lẻ tương tự?

Như chiến thuật \(2 \times 10^{10}\), ta cố giữ số đoạn chẵn cho AI: nếu số đoạn chẵn thì đi giữa một đoạn, nếu không thì lấy đầu trái của một đoạn lớn khác. Thực nghiệm cho thấy cách này giải bộ test 1, và cả bộ test 2 nếu luôn chọn đoạn lớn nhất. Nó tương tự chiến thuật tốt nhất ở trên, dù không kiểm soát tinh vi bằng.

Ta thậm chí có thể giải hoàn hảo bằng cách tính vét cạn số Grundy và lưu bằng mã hóa độ dài loạt! Tuy nhiên, có thể tìm ra ý tưởng \(2 \times 10^{10}\) đủ tốt mà không biết lý thuyết này.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 3 — Zillionim.