프로모션 체스

이 게임은 $5 \times 5$ 체스판에서 시민을 배치하고 프로모션하여 상대 킹을 체크메이트하는 변형 체스입니다.

체스판은 왼쪽부터 a열에서 e열, 하얀색 진영 쪽부터 검은색 진영 쪽으로 1행에서 5행까지의 좌표를 사용합니다. 열과 행을 이어 쓴 a1, c4와 같은 문자열로 한 칸을 나타냅니다. 하얀색의 홈 랭크는 1행이고 검은색의 홈 랭크는 5행입니다.

선공은 하얀색, 후공은 검은색을 맡습니다. 처음에는 하얀색 킹이 c1, 검은색 킹이 c5에 놓이며 나머지 칸은 모두 비어 있습니다. 하얀색 플레이어부터 시작하여 두 플레이어가 번갈아 행동합니다.

시민을 제외한 기물의 이동, 공격과 포획 규칙은 일반 체스와 같습니다. 캐슬링과 앙파상은 사용할 수 없습니다.

시민은 이동하거나 공격할 수 없습니다. 각 턴이 시작되면 현재 플레이어가 소유한 모든 시민의 레벨이 $1$ 증가하며, 레벨은 $9$보다 커지지 않습니다.

자신의 턴에는 다음 세 행동 중 하나를 수행합니다.

• 시민 배치: 비어 있는 자기 홈 랭크의 칸 하나에 레벨 $0$인 시민을 배치합니다.
• 시민 프로모션: 자기 시민 하나를 현재 레벨로 선택할 수 있는 일반 기물 하나로 바꿉니다.
• 기물 이동: 자기 기물 하나를 그 기물의 이동 규칙에 따라 이동합니다. 도착 칸에 상대 기물이 있으면 잡습니다.

시민은 현재 레벨이 다음 표의 최소 레벨 이상인 기물로 프로모션할 수 있습니다.

폰이 상대편의 마지막 랭크에 도착하면 같은 행동에서 나이트, 비숍, 룩, 퀸 중 하나로 프로모션해야 합니다.

다음 행동은 잘못된 행동입니다.

• 출력 형식에 맞지 않는 문자열이나 체스판 범위 밖의 좌표를 출력하는 경우
• 자기 기물이 아닌 칸을 시작점으로 선택하거나 기물의 이동 규칙에 맞지 않는 행동을 하는 경우
• 자기 홈 랭크가 아닌 칸이나 이미 기물이 있는 칸에 시민을 배치하는 경우
• 레벨이 부족한 시민을 프로모션하거나 허용되지 않은 기물을 선택하는 경우
• 폰이 마지막 랭크에 도착하면서 프로모션 기물을 선택하지 않거나 허용되지 않은 기물을 선택하는 경우
• 행동 뒤 자신의 킹을 체크 상태에 남기는 경우

잘못된 행동을 한 플레이어는 즉시 패배하며, 해당 행동은 체스판에 반영되지 않습니다. 제한 시간 안에 응답하지 못하거나 프로그램 실행 중 오류가 발생한 경우에도 해당 플레이어가 즉시 패배합니다.

각 플레이어에게는 게임 전체에서 사용할 수 있는 총 $10{,}000\text{ms}$가 주어집니다. 게임 준비와 자신의 모든 턴에 사용한 응답 시간이 누적 차감되며, 다음 턴이 되어도 남은 시간은 늘어나지 않습니다.

수락된 행동 하나를 $1$ ply로 계산합니다. 게임은 행동을 적용한 뒤 다음 순서로 종료 여부를 판정합니다.

1. 다음 플레이어에게 합법적인 행동이 없고 킹이 체크 상태이면 체크메이트입니다.
2. 다음 플레이어에게 합법적인 행동이 없지만 킹이 체크 상태가 아니면 스테일메이트로 무승부입니다.
3. 1번과 2번 조건을 만족하지 않았더라도 $200$ ply에 도달하면 무승부입니다.

시민을 프로모션할 시점과 일반 기물의 움직임을 함께 계획하여 상대 킹을 체크메이트하고 최종 승자가 되기 위한 AI를 설계해주세요!

표준 초기 상태에는 하얀색 킹이 c1, 검은색 킹이 c5에 있고 나머지 칸은 모두 비어 있습니다. 플레이어는 이 상태에서 시작하여 자신이 출력한 행동과 OPP로 받은 상대 행동을 차례대로 적용해 현재 상태를 관리해야 합니다.

채점기는 다음의 한 줄 단위로 플레이어와 통신합니다.

• role은 FIRST 또는 SECOND입니다. FIRST는 하얀색인 선공, SECOND는 검은색인 후공입니다.
• remainingMs는 현재 응답 전에 해당 플레이어에게 남아 있는 총 시간의 밀리초 단위 정수입니다. 값은 $1$ 이상 $10{,}000$ 이하입니다. 남은 시간이 $0$이 되면 다음 TURN 없이 시간 초과로 패배합니다.
• 칸 좌표 square, from, to는 a1부터 e5까지이며 정규식 [a-e][1-5]와 일치합니다.
• 기물 이름 piece는 PAWN, KNIGHT, BISHOP, ROOK, QUEEN 중 하나입니다.
• 모든 명령어와 기물 이름은 표에 적힌 대문자를 사용합니다.

TURN에 출력할 수 있는 행동은 다음과 같습니다.

게임 시작 시 채점기는 두 플레이어에게 차례대로 READY를 보내고 OK를 확인합니다. 두 플레이어가 모두 준비되면 하얀색 플레이어에게 첫 TURN을 보냅니다.

자신의 행동이 합법이고 게임이 계속되면 채점기는 상대에게 같은 행동을 OPP action...으로 먼저 보낸 뒤 그 상대에게 TURN을 보냅니다. 플레이어는 자신이 출력한 행동을 별도 확인 입력 없이 적용해야 합니다.

수락된 행동이 체크메이트나 무승부를 만들면 그 행동을 상대에게 OPP로 보내지 않고 양쪽에 FINISH를 보냅니다. 잘못된 출력이나 불법 행동도 상대에게 전달하지 않습니다.

두 플레이어에게는 게임 전체에서 사용할 수 있는 $10{,}000$밀리초가 각각 주어집니다. READY와 자신의 모든 TURN 응답 시간이 같은 총 시간에서 누적 차감되며, 다음 턴이 되어도 늘어나지 않습니다. 한 플레이어의 시간 사용은 상대의 시간에 영향을 주지 않습니다.

플레이어가 출력하는 한 줄은 마지막 LF를 포함하여 최대 $64$바이트입니다. 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다. 디버그 메시지는 표준 오류에만 출력해야 하며, 요청받지 않은 시점이나 표준 출력에 정해진 응답 외의 문자열을 출력하면 안 됩니다.

제한 시간 안에 응답하지 못하거나, FINISH 전에 프로그램이 종료되거나, 출력 형식이 잘못되거나, 게임 규칙상 불법인 행동을 출력하면 해당 플레이어가 즉시 패배합니다. 실패한 행동은 게임 상태에 반영되지 않고 상대에게 전달되지 않습니다.

한 경기에서 다음과 같이 통신할 수 있습니다. 빈 칸은 해당 플레이어에게 입력이나 출력이 없는 시점을 의미하며, 시간 값은 설명을 위한 예시입니다.

양쪽 프로그램은 자신이 출력한 행동과 OPP로 받은 상대 행동을 자기 보드에 적용합니다. 수락된 마지막 행동이 경기를 끝냈다면 그 행동은 상대에게 OPP로 전달되지 않고 다음 입력은 FINISH가 됩니다.

• CPP20 : main.cpp
• PYTHON3, PYPY3 : main.py