Zillionim

Zillionim은 두 명의 플레이어가 번갈아 가며 하는 턴제 게임이다. 처음에 $10^{12}$개의 동전이 왼쪽에서 오른쪽으로 한 줄에 끝과 끝이 맞닿아 놓여 있으며, 왼쪽에서부터 1번부터 $10^{12}$번까지 번호가 붙어 있다. 각 턴에 플레이어는 연속된 $10^{10}$개의 동전을 골라 반드시 제거해야 한다. 원래 연속되어 있지 않던 두 동전은, 그 사이의 동전이 모두 제거되더라도 연속된 동전이 되지 않는다.

플레이어는 자기 차례에 유효한 수를 둘 수 있으면 반드시 두고, 그 다음은 상대의 차례가 된다. 자기 차례에 유효한 수를 둘 수 없으면 그 플레이어가 지고 상대가 이긴다.

우리 엔지니어들은 Zillionim을 플레이하도록 기계 학습 모델을 아직 훈련 중이라, 무작위로 수를 두는 간단한 AI를 만들었다. AI가 항상 먼저 둔다. AI는 자기 차례마다 가능한 유효한 수를 모두 찾은 뒤, 그중 하나를 균등한 확률로 무작위 선택한다.

이 AI를 이길 수 있겠는가? 적어도 대부분의 경우에는 이길 수 있겠는가?

• $T = 500$.
• $-3 \le P \le 10^{12} - 10^{10} + 1$.
• $P \neq 0$.
• $P$는 위에서 설명한 대로 유효한 플레이 또는 게임 상태에 대한 유효한 정보를 나타낸다.