블록게임

조합게임의 예제로 나온 문제. 모두가 최선을 다했을 때 이길 수 있는 경우에 대한 것은 앞에서 설명했으니 넘어가고 블록과 보드게임의 상태를 비트 연산을 이용해 어떻게 깔끔히 표현했는지에 주목하자.

 
void precalc() {
	for(int y = 0; y < 4; y++)
		for (int x = 0; x < 4; x++) {
			vector<int> cells;
			for (int dy = 0; dy < 2; dy++)
				for (int dx = 0; dx < 2; dx++)
					cells.push_back(cell(y + dy, x + dx));
			int square = cells[0] + cells[1] + cells[2] + cells[3];

			for (int i = 0; i < 4; i++)
				moves.push_back(square - cells[i]);
		}

	for(int i=0; i<5; i++)
		for (int j = 0; j < 4; j++) {
			moves.push_back(cell(i, j) + cell(i, j+1));
			moves.push_back(cell(j, i) + cell(j+1, i));
		}
}

char play(int board) {
	char& ret = cache[board];

	if (ret != -1)
		return ret;

	ret = 0;

	for(int i=0; i<moves.size(); i++)
		if((moves[i] & board) == 0)
			if (!play(board | moves[i])) {
				ret = 1;
				break;
			}

	return ret;
}

먼저 5*5 board판인 점을 이용해서 비트를 이용해 각각의 상태를 표현한다는 접근법부터 놀랍다. 나라면 또 board의 상태에 따라서 행렬을 그리고 이중포인터 사용하고 지저분해졌을것 같은데 저자는 board의 상태를 비트로 표현해 int변수 만으로 표현해줄 수 있었다.

또한 precalc()는 모든 위치에서 블록을 둘 수 있는 경우의 수들을 저장해둔것인데 모든 위치에 대해 둘 수 있는 블록의 경우의 수를 미리 계산한 것도 멋지고 또다시 주목할만한 부분은 L모양의 블록을 비트로 표현할 때 square값에다가 각각의 cell값을 빼준 것이다. 생각하는 방식이 나와 다른 것 같다.

play함수 내에서 블럭을 놓을 수 있는지를 간단히 AND 연산으로 처리했고 블럭을 놓는 경우는 OR연산으로 처리했다. 고수들만이 이런 경지에 오르는 것이 아닐까 싶다.