4차 산업 혁명 2

《Connect Four》는 $6$ 행 $7$ 열의 수직으로 세워진 직사각형 게임판에서 진행하는 게임입니다. 두 플레이어가 번갈아가며 턴을 진행하며, 각 턴에 플레이어는 아직 채워지지 않은 칸이 있는 열을 하나 골라 자신의 말을 떨어뜨립니다. 떨어뜨린 말은 채워지지 않은 가장 아래쪽 칸에 들어갑니다. 먼저 자신의 말 네 개를 가로, 세로, 또는 대각선으로 한 줄을 이루도록 하는 플레이어가 승리합니다. 편의상 먼저 말을 놓는 플레이어의 말을 빨간색, 상대편의 말을 노란색이라 하겠습니다. 또한 열 번호는 가장 왼쪽에 있는 열에서 시작하여 오른쪽으로 가면서 $1$ 번부터 $7$ 번까지 붙입니다.

여러분은 현존하는 최강의 Connect Four 인공지능을 상대로 승리해야 합니다. 여러분이 먼저 플레이합니다.

최선의 수는 다음과 같이 (게임 상태에 대해 재귀적으로) 정의합니다.

이길 수 있다면, 두 플레이어가 최선의 수를 둘 때 내가 이기면서 말을 최대한 적게 놓게 되는 수가 최선의 수입니다.
이길 수는 없지만 비길 수 있다면, 두 플레이어가 최선의 수를 둘 때 비기는 수가 최선의 수입니다.
이길 수도 없고 비길 수도 없다면, 두 플레이어가 최선의 수를 둘 때 (내가 지면서) 말을 최대한 많이 놓게 되는 수가 최선의 수입니다.

이 문제에서는 게임판을 길이가 $14$ 인 문자열로 인코딩합니다. 먼저 각 열을 다음과 같이 인코딩합니다.

$x = 1$ 로 초기화합니다.
놓여있는 말을 위에서부터 하나씩 읽습니다. 빨간색 말이라면 $2x$ 가, 노란색 말이라면 $2x+1$ 이 새로운 $x$ 가 됩니다.
모두 읽은 다음 $x$ 의 값을 $16$ 진수로 씁니다. 한 자리 수인 경우 앞에 $0$ 을 붙입니다. (ex. $x=13$ 이면 0d, $x=127$ 이면 7f)

간단하게 설명하자면, 열을 위에서부터 순서대로 읽고, 노란색 말을 $1$ , 빨간색 말을 $0$ 으로 치환한 다음, 맨 왼쪽에 $1$ 을 추가한 이진수를 $16$ 진수로 쓰면 됩니다.

다음으로 게임판의 $1$ 열부터 $7$ 열까지를 인코딩한 문자열을 순서대로 이어 붙여 하나의 문자열을 만듭니다. 이 문자열이 게임판의 상태를 인코딩한 결과입니다. 아래는 인코딩한 결과가 각각 01010102010101, 0305146a032501, 55656a6a2c5555인 게임판을 나타낸 그림입니다.

플레이어의 플레이는 말을 떨어뜨릴 열의 번호로 나타낼 수 있습니다. 예를 들어 $4$ , $5$ , $3$ , $2$ , $4$ , $4$ , $1$ , $7$ 순서로 플레이한 뒤의 게임판은 다음과 같으며, 이 게임판을 인코딩한 문자열은 0203020c030103입니다.

여러분은 아래 함수들을 구현해야 합니다.

void init()

이 함수는 단 한 번, 다른 모든 next_move() 함수가 호출되기 전에 호출됩니다.

int next_move(std::string state)

state: 위에서 설명한 방법대로 현재 판의 상태가 인코딩된 문자열
이 함수는 판의 상태에 따라 다음 플레이, 즉 말을 떨어뜨릴 열을 반환해야 합니다. 열 번호는 $1$ 부터 시작합니다.
이 함수의 반환값은 $0$ 이상 $7$ 이하여야 합니다.
반환값이 $0$ 인 경우, 해당 상태에서는 게임을 더 이상 진행하지 않고 패배합니다.
이 함수는 테스트 케이스당 최대 $21$ 번 호출됩니다.

이 문제에는 $10$ 개의 테스트 케이스가 있습니다. 각 테스트 케이스마다 여러분은 항상 최선의 수 중 하나를 두는 인공지능과 대결합니다. 채점기는 다음과 같이 동작합니다.

처음 게임판을 인코딩한 문자열인 "01010101010101"을 next_move() 함수의 state 인자로 넘겨줍니다.
next_move() 함수의 반환값을 확인합니다. 만약 반환값이 state에 대한 최선의 수가 아니거나 $0$ 이라면 게임을 더 이상 진행하지 않습니다. 그렇지 않다면 반환값과 state를 바탕으로 새로운 게임판을 만듭니다.
만약 새로운 게임판에서 당신의 말 네 개가 가로, 세로, 또는 대각선으로 한 줄을 이루고 있다면 당신의 승리로 프로그램을 종료합니다. 그렇지 않다면 그 상태에서 인공지능이 최선의 수를 둔 후의 게임판을 인코딩한 문자열을 다시 next_move() 함수의 state 인자로 넘겨줍니다.

하나의 테스트 케이스에서 채점기는 항상 정해진 대로 동작합니다. 다시 말해서, 3번 과정에서 만약 최선의 수가 여러 개일 때 인공지능이 선택하는 최선의 수는, 해당 테스트 케이스의 채점 과정에서 도달할 수 있는 모든 게임판에 대해 정해져 있습니다. 인공지능의 선택은 각 테스트 케이스마다 다를 수 있습니다.

각 테스트 케이스마다, 만약 당신이 게임을 이겼다면 $2790$ 점을 받습니다. 그렇지 않고 만약 당신의 next_move() 함수가 $0$ 이상 $7$ 이하의 정수가 아닌 값을 반환했다면 $0$ 점을 받습니다. 그렇지 않다면 당신의 next_move() 함수가 최선의 수를 반환한 횟수를 $n$ 이라 할 때, 이 테스트 케이스에 대한 여러분의 점수는 다음 표와 같습니다.


조건	점수
$n = 0$	$0$
$1 \le n \le 9$	$2^{n-1}$
$n = 10$	$343$
$n = 11$	$486$
$n = 12$	$512$
$n = 13$	$666$
$n = 14$	$1024$
$n = 15$	$1248$
$n = 16$	$1557$
$n = 17$	$1717$
$n = 18$	$2023$
$n = 19$	$2320$
$n = 20$	$2780$

모든 테스트 케이스에서 채점 프로그램이 시간 내에 정상적으로 종료했을 경우에 한해, 각 테스트 케이스의 점수의 합이 여러분의 점수가 됩니다. 예를 들어, 모든 테스트 케이스에서 $n = 3$ 인 경우 $40$ 점을 받습니다.

Sample grader는 인터랙티브하게 동작합니다. Sample grader의 동작을 위해서는 당신의 next_move() 함수의 반환값이 최선의 수인지 판단하고, 인공지능이 선택할 최선의 수를 직접 입력해야 합니다.

만약 next_move() 함수의 반환값대로 게임을 진행했을 때 게임이 끝났다면 $0$ 을 입력해야 합니다.
만약 next_move() 함수의 반환값이 최선의 수가 아니라면 $-1$ 을 입력해야 합니다.
이외의 경우 인공지능이 선택할 최선의 수를 입력해야 합니다.

다음은 Sample grader의 동작 예시입니다.


`next_move()` 함수		input	이전 `state`	새로운 `state`
call	return
`next_move("01010101010101")`	4		`"01010101010101"`	`"01010102010101"`
		4	`"01010102010101"`	`"01010106010101"`
`next_move("01010106010101")`	3		`"01010106010101"`	`"01010206010101"`
		-1	최선의 수가 아니라고 판단, 게임 종료
`next_move()` 함수가 최선의 수를 반환한 횟수: $1$ , 점수: $1$

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있습니다. 또한, 위 예시의 input은 실제 인공지능의 최선의 수가 아닐 수 있습니다.

sample_grader.cpp