리버시

$8 \times 8$ 크기의 게임판 위에서 두 플레이어가 번갈아 돌을 놓고 상대의 돌을 뒤집는 게임을 진행합니다.

게임판은 $1 \times 1$ 크기의 칸이 $8$행 $8$열로 배열된 형태입니다. 행 번호는 위에서 아래로 $1$행부터 $8$행, 열 번호는 왼쪽에서 오른쪽으로 $1$열부터 $8$열까지이며, $r$행 $c$열의 칸을 $(r,c)$로 표기합니다.

각 칸은 빈칸 ., 흑돌 B, 백돌 W 중 하나의 상태를 가집니다. 게임을 시작할 때에는 $(4,4)$와 $(5,5)$에 백돌이, $(4,5)$와 $(5,4)$에 흑돌이 놓이며, 나머지 칸은 비어 있습니다.

게임은 흑돌을 사용하는 선공부터 시작하여 두 플레이어가 번갈아 턴을 진행합니다. 자신의 턴에는 빈칸 $(r,c)$ 하나를 선택하여 자신의 색 돌을 놓습니다.

돌을 놓으려는 칸은 다음 조건을 만족해야 합니다.

• 해당 칸에서 가로, 세로, 대각선의 여덟 방향 중 적어도 한 방향으로 상대의 돌이 하나 이상 연속해 있어야 합니다.
• 그 연속한 상대의 돌 바로 다음 칸에는 자신의 돌이 있어야 합니다. 중간에 빈칸이나 자신의 돌이 있으면 그 너머의 상대 돌은 포함하지 않습니다.

플레이어가 돌을 놓으면 다음 과정이 순서대로 진행됩니다.

• 선택한 빈칸에 현재 플레이어의 돌을 놓습니다.
• 새로 놓은 돌에서 여덟 방향을 확인하여, 위 조건을 만족하는 방향에 끼인 상대의 돌을 모두 찾습니다.
• 해당 돌을 모두 현재 플레이어의 색으로 뒤집습니다. 여러 방향에서 조건을 만족하면 해당 방향의 돌을 모두 뒤집습니다.

돌을 뒤집은 결과 다른 방향에서 상대의 돌이 끼이더라도 추가로 뒤집지는 않습니다. 새로 놓은 돌에서 직접 이어지는 방향만 확인합니다.

예를 들어 첫 턴에 흑이 $(3,4)$에 돌을 놓으면 $(4,4)$의 백돌이 흑돌로 뒤집힙니다. 처음 흑이 선택할 수 있는 칸은 $(3,4)$, $(4,3)$, $(5,6)$, $(6,5)$입니다.

자신의 턴에 돌을 놓을 수 있는 칸이 없다면 차례를 넘깁니다. 돌을 놓을 수 있는 칸이 하나라도 있다면 차례를 넘길 수 없습니다. 이미 돌이 있는 칸이나 상대의 돌을 뒤집을 수 없는 칸을 선택할 수 없습니다.

두 플레이어 모두 돌을 놓을 수 없으면, 게임판에 빈칸이 남아 있더라도 게임이 종료됩니다.

게임이 종료되었을 때 자신의 색 돌이 더 많은 플레이어가 승리하며, 두 플레이어의 돌 개수가 같다면 무승부입니다.

상대의 돌을 뒤집고 더 많은 돌을 차지하여 최종 승자가 되기 위한 AI를 설계해주세요!

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

• turn, r, c는 정수입니다.
• turn은 두 플레이어의 행동을 모두 세는 턴 번호이며 $1$부터 시작합니다. 차례를 넘긴 경우에도 $1$ 증가합니다.
• board는 길이가 $64$인 문자열입니다. $1$행 $1$열부터 각 행을 왼쪽에서 오른쪽으로 나열한 뒤, 위 행부터 아래 행까지 이어 붙인 형태입니다.
• board의 각 문자는 빈칸 ., 흑돌 B, 백돌 W 중 하나입니다. $(r,c)$의 상태는 문자열의 앞에서 $8(r-1)+c$번째 문자입니다.
• r, c는 $1$ 이상 $8$ 이하이며, 각각 위에서부터 센 행과 왼쪽에서부터 센 열을 의미합니다.
• 채점기는 자신의 턴마다 현재 게임판 전체를 입력합니다. 상대의 직전 행동도 이 게임판에 반영되며, 상대의 턴에는 입력이 주어지지 않습니다.
• 두 플레이어에게는 게임 전체에서 사용할 수 있는 총 $5{,}000\text{ms}$가 각각 주어지며, READY와 자신의 모든 TURN 응답 시간이 차감됩니다. 상대의 응답을 기다리는 시간은 차감되지 않습니다.
• 남은 시간은 입력에 별도 값으로 주어지지 않습니다. 매 턴 새로운 시간 제한이 주어지는 방식이 아닙니다.
• 프로그램 전체의 CPU 사용 시간에도 별도로 $5{,}000\text{ms}$ 제한이 적용됩니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다. 각 요청에는 정해진 토큰으로 이루어진 한 줄만 응답해야 합니다.
• 남은 총 시간 안에 응답하지 못하거나 프로그램이 비정상 종료되면 즉시 패배합니다.
• 출력 형식에 맞지 않는 문자열이나 합법적이지 않은 좌표를 출력하면 즉시 패배합니다. 돌을 놓을 수 있는 칸이 있는데 PASS를 출력한 경우에도 즉시 패배합니다.
• 게임이 끝나면 채점기는 추가 명령을 보내지 않고 플레이어의 프로그램을 종료합니다.

다음은 초기 게임판에서 두 플레이어와 채점기가 통신하는 예시입니다.

선공이 $(3,4)$에 돌을 놓으면 $(4,4)$의 백돌이 흑돌로 뒤집힙니다. 이어서 후공이 $(3,3)$에 돌을 놓으면 $(4,4)$의 흑돌이 백돌로 뒤집힙니다. 다음 선공이 $(3,2)$에 돌을 놓으면 $(3,3)$의 백돌이 흑돌로 뒤집힙니다.

자신의 턴에 돌을 놓을 수 있는 칸이 없다면 MOVE r c 대신 PASS를 출력합니다. 게임이 종료되면 더 이상 입력이 주어지지 않습니다.

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