solver.c

黑白棋终局解算程序

		F1, F2, F3, F4, F5, F6, F7, F8,
		G1, G2, G3, G4, G5, G6, G7, G8,
		H1, H2, H3, H4, H5, H6, H7, H8
	};
#endif

	for (i=0; i < BOARD_SIZE; i++) board->square[i] = OFF_SIDE;
	board->n_discs[BLACK] = board->n_discs[WHITE] = board->n_empties = 0;
	for (i = A1; i <= H8; i += 9)
	for (j = i; j < i + 8; j++) {
		if (*string == '\0') break;
		switch (tolower(*string)) {
		case 'b':
		case 'x':
		case '*':
			board->square[j] = BLACK;
			board->n_discs[BLACK]++;
			break;
		case 'o':
		case 'w':
			board->square[j] = WHITE;
			board->n_discs[WHITE]++;
			break;
		case '-':
		case '.':
			board->square[j] = EMPTY;
			board->n_empties++;
			break;
		default:
			j--;
			break;
		}
		string++;
	}

	board->player = EMPTY;
	for (;*string != '\0' && board->player == EMPTY; string++) {
		switch (tolower(*string)) {
		case 'b':
		case 'x':
		case '*':
			board->player = BLACK;
			break;
		case 'o':
		case 'w':
			board->player = WHITE;
			break;
		default:
			break;
		}
	}
	if (board->player == EMPTY) {
		fprintf(stderr, "board_set: incorrect player value '%c'\n", *string);
		exit(EXIT_FAILURE);
	}

	/* init Empties */
	empties = board->empties;
	empties->position = NOMOVE; /* sentinel */
	empties->previous = NULL;
	empties->next = empties + 1;
	empties = empties->next;
	for (i = 0; i < 60; i++) {    /* add empty squares */
		if (board->square[presorted_position[i]] == EMPTY) {
			empties->position = presorted_position[i];
			empties->previous = empties - 1;
			empties->next = empties + 1;
			board->position_to_empties[presorted_position[i]] = empties;
			empties = empties->next;
		}
	}
	empties->position = NOMOVE; /* sentinel */
	empties->previous = empties - 1;
	empties->next = NULL;

	/* set hash_code */
	board->hash_code[0] = board->hash_code[1] = 0;
	if ((board->player == WHITE) ^ ((board->n_empties & 1) == 1)) {
		board->hash_code[0] ^= hash_code_swap_player[0];
		board->hash_code[1] ^= hash_code_swap_player[1];
	}
	for (i = A1; i <= H8; i += 9)
	for (j = i; j < i + 8; j++) {
		board->hash_code[0] ^= hash_code_set_disc[j][(int)board->square[j]][0];
		board->hash_code[1] ^= hash_code_set_disc[j][(int)board->square[j]][1];
	}

	/* init parity */
	board->parity[0] = board->parity[1] = board->parity[2] = board->parity[3] = 0;
	for (empties = board->empties->next; empties->position != NOMOVE; empties = empties->next) {
		board->parity[QUADRANT_ID[empties->position]] ^= 1;
	}

	/* nodes */
	board->n_nodes = 0;
}

/*!
 * \brief Check move validity.
 *
 * Check if a legal move exists on square 'x' for 'player'
 * \param board   board to test
 * \param x       square on which to move.
 * \param player  player to move.
 * \return        1 if a legal move exists, 0 otherwise.
 */
int board_check_move(const Board *board, int x, int player)
{
	const char p = player;
	const char o = OPPONENT(p);
	const char *square = board->square + x;

	switch (FLIPPING_DIRECTION_ID[x]) {
	case 1:
		return  (BOARD_CHECK_MOVE_6(SE) ||
				 BOARD_CHECK_MOVE_6(S ) ||
				 BOARD_CHECK_MOVE_6( E));
	case 3:
		return  (BOARD_CHECK_MOVE_6(SW) ||
				 BOARD_CHECK_MOVE_6( W) ||
				 BOARD_CHECK_MOVE_6(S ));
	case 7:
		return  (BOARD_CHECK_MOVE_6(NE) ||
				 BOARD_CHECK_MOVE_6(N ) ||
				 BOARD_CHECK_MOVE_6( E));
	case 9:
		return  (BOARD_CHECK_MOVE_6(NW) ||
				 BOARD_CHECK_MOVE_6(N ) ||
				 BOARD_CHECK_MOVE_6( W));
	case 2:
		return  (BOARD_CHECK_MOVE_6(S ) ||
				 BOARD_CHECK_MOVE_4(SE) ||
				 BOARD_CHECK_MOVE_4(SW) ||
				 BOARD_CHECK_MOVE_4( E) ||
				 BOARD_CHECK_MOVE_4( W));
	case 4:
		return  (BOARD_CHECK_MOVE_6( E) ||
				 BOARD_CHECK_MOVE_4(NE) ||
				 BOARD_CHECK_MOVE_4(SE) ||
				 BOARD_CHECK_MOVE_4(N ) ||
				 BOARD_CHECK_MOVE_4(S ));
	case 6:
		return  (BOARD_CHECK_MOVE_6( W) ||
				 BOARD_CHECK_MOVE_4(NW) ||
				 BOARD_CHECK_MOVE_4(SW) ||
				 BOARD_CHECK_MOVE_4(S ) ||
				 BOARD_CHECK_MOVE_4(N ));
	case 8:
		return  (BOARD_CHECK_MOVE_6(N ) ||
				 BOARD_CHECK_MOVE_4(NE) ||
				 BOARD_CHECK_MOVE_4(NW) ||
				 BOARD_CHECK_MOVE_4( E) ||
				 BOARD_CHECK_MOVE_4( W));
	case 5:
		return  (BOARD_CHECK_MOVE_4(N ) ||
				 BOARD_CHECK_MOVE_4( E) ||
				 BOARD_CHECK_MOVE_4(S ) ||
				 BOARD_CHECK_MOVE_4( W) ||
				 BOARD_CHECK_MOVE_4(NE) ||
				 BOARD_CHECK_MOVE_4(SE) ||
				 BOARD_CHECK_MOVE_4(NW) ||
				 BOARD_CHECK_MOVE_4(SW));
	}
	return 0;
}

/*!
 * \brief Count flippable discs.
 *
 * Count how many discs can be flipped (without flipping them).
 * \param board  board to test
 * \param x      square on which to move.
 * \param player player to move.
 * \return       the number of disc(s) flipped.
 */
int board_count_flips(const Board *board, int x, int player)
{
	const char p = player;
	const char o = OPPONENT(p);
	const char *square = board->square + x;
	int n_flips = 0;

	switch (FLIPPING_DIRECTION_ID[x]) {
	case 1:
		BOARD_COUNT_FLIPS_6( E);
		BOARD_COUNT_FLIPS_6(S );
		BOARD_COUNT_FLIPS_6(SE);
		break;
	case 3:
		BOARD_COUNT_FLIPS_6( W);
		BOARD_COUNT_FLIPS_6(SW);
		BOARD_COUNT_FLIPS_6(S );
		break;
	case 7:
		BOARD_COUNT_FLIPS_6(N );
		BOARD_COUNT_FLIPS_6(NE);
		BOARD_COUNT_FLIPS_6( E);
		break;
	case 9:
		BOARD_COUNT_FLIPS_6(NW);
		BOARD_COUNT_FLIPS_6(N );
		BOARD_COUNT_FLIPS_6( W);
		break;
	case 2:
		BOARD_COUNT_FLIPS_6(S );
		BOARD_COUNT_FLIPS_4( W);
		BOARD_COUNT_FLIPS_4( E);
		BOARD_COUNT_FLIPS_4(SW);
		BOARD_COUNT_FLIPS_4(SE);
		break;
	case 4:
		BOARD_COUNT_FLIPS_6( E);
		BOARD_COUNT_FLIPS_4(N );
		BOARD_COUNT_FLIPS_4(NE);
		BOARD_COUNT_FLIPS_4(S );
		BOARD_COUNT_FLIPS_4(SE);
		break;
	case 6:
		BOARD_COUNT_FLIPS_6( W);
		BOARD_COUNT_FLIPS_4(NW);
		BOARD_COUNT_FLIPS_4(N );
		BOARD_COUNT_FLIPS_4(SW);
		BOARD_COUNT_FLIPS_4(S );
		break;
	case 8:
		BOARD_COUNT_FLIPS_6(N );
		BOARD_COUNT_FLIPS_4(NW);
		BOARD_COUNT_FLIPS_4(NE);
		BOARD_COUNT_FLIPS_4( W);
		BOARD_COUNT_FLIPS_4( E);
		break;
	case 5:
		BOARD_COUNT_FLIPS_4(NW);
		BOARD_COUNT_FLIPS_4(N );
		BOARD_COUNT_FLIPS_4(NE);
		BOARD_COUNT_FLIPS_4( W);
		BOARD_COUNT_FLIPS_4( E);
		BOARD_COUNT_FLIPS_4(SW);
		BOARD_COUNT_FLIPS_4(S );
		BOARD_COUNT_FLIPS_4(SE);
		break;
	}
	return n_flips;
}

/*!
 * \brief Flip discs on the board.
 *
 * Modify a board by flipping its discs. Only the square[] and player members
 * are modified.
 * \param board board to modify
 * \param x     square on which to move.
 * \param move  a Move structure remembering the modification.
 * \return      the number of disc(s) flipped.
 */
int board_do_flip(Board *board, int x, Move *move)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	char *square = board->square + x;

	move->n = 0;
	switch (FLIPPING_DIRECTION_ID[x]) {
	case 1:
		BOARD_FLIP(E , 6);
		BOARD_FLIP( S, 6);
		BOARD_FLIP(SE, 6);
		break;
	case 3:
		BOARD_FLIP( W, 6);
		BOARD_FLIP(SW, 6);
		BOARD_FLIP(S , 6);
		break;
	case 7:
		BOARD_FLIP(N , 6);
		BOARD_FLIP(NE, 6);
		BOARD_FLIP( E, 6);
		break;
	case 9:
		BOARD_FLIP(NW, 6);
		BOARD_FLIP(N , 6);
		BOARD_FLIP( W, 6);
		break;
	case 2:
		BOARD_FLIP(S , 6);
		BOARD_FLIP( W, 4);
		BOARD_FLIP( E, 4);
		BOARD_FLIP(SW, 4);
		BOARD_FLIP(SE, 4);
		break;
	case 4:
		BOARD_FLIP(N , 4);
		BOARD_FLIP(NE, 4);
		BOARD_FLIP( E, 6);
		BOARD_FLIP(S , 4);
		BOARD_FLIP(SE, 4);
		break;
	case 6:
		BOARD_FLIP(NW, 4);
		BOARD_FLIP(N , 4);
		BOARD_FLIP( W, 6);
		BOARD_FLIP(SW, 4);
		BOARD_FLIP(S , 4);
		break;
	case 8:
		BOARD_FLIP(NW, 4);
		BOARD_FLIP(N , 6);
		BOARD_FLIP(NE, 4);
		BOARD_FLIP( W, 4);
		BOARD_FLIP( E, 4);
		break;
	case 5:
		BOARD_FLIP(NW, 4);
		BOARD_FLIP(N , 4);
		BOARD_FLIP(NE, 4);
		BOARD_FLIP( W, 4);
		BOARD_FLIP( E, 4);
		BOARD_FLIP(SW, 4);
		BOARD_FLIP(S , 4);
		BOARD_FLIP(SE, 4);
		break;
	}
	if (move->n > 0) {
		*move->position = x;
		*square = p;
		BOARD_UPDATE_PLAYER(board);
		BOARD_UPDATE_INTERNAL_NODES();
	}
	return move->n;
}

/*!
 * \brief Compute a move.
 *
 * Compute how the board will be modified by a move without playing it.
 * \param board board
 * \param x     square on which to move.
 * \param move  a Move structure remembering the modification.
 * \return      the number of disc(s) flipped.
 */
int board_get_move(const Board *board, int x, Move *move)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	const char *square = board->square + x;

	move->n = 0;
	move->hash_code[0] = hash_code_set_disc[x][(int)p][0];
	move->hash_code[1] = hash_code_set_disc[x][(int)p][1];
	switch (FLIPPING_DIRECTION_ID[x]) {
	case 1:
		BOARD_GET_MOVE( E, 6);
		BOARD_GET_MOVE(S , 6);
		BOARD_GET_MOVE(SE, 6);
		break;
	case 3:
		BOARD_GET_MOVE( W, 6);
		BOARD_GET_MOVE(SW, 6);
		BOARD_GET_MOVE(S , 6);
		break;
	case 7:
		BOARD_GET_MOVE(N , 6);
		BOARD_GET_MOVE(NE, 6);
		BOARD_GET_MOVE( E, 6);
		break;
	case 9:
		BOARD_GET_MOVE(NW, 6);
		BOARD_GET_MOVE(N , 6);
		BOARD_GET_MOVE( W, 6);
		break;
	case 2:
		BOARD_GET_MOVE( W, 4);
		BOARD_GET_MOVE( E, 4);
		BOARD_GET_MOVE(SW, 4);
		BOARD_GET_MOVE(S , 6);
		BOARD_GET_MOVE(SE, 4);
		break;
	case 4:
		BOARD_GET_MOVE(N , 4);
		BOARD_GET_MOVE(NE, 4);
		BOARD_GET_MOVE( E, 6);
		BOARD_GET_MOVE(S , 4);
		BOARD_GET_MOVE(SE, 4);
		break;
	case 6:
		BOARD_GET_MOVE(NW, 4);
		BOARD_GET_MOVE(N , 4);
		BOARD_GET_MOVE( W, 6);
		BOARD_GET_MOVE(SW, 4);
		BOARD_GET_MOVE(S , 4);
		break;
	case 8:
		BOARD_GET_MOVE(NW, 4);
		BOARD_GET_MOVE(N , 6);
		BOARD_GET_MOVE(NE, 4);
		BOARD_GET_MOVE( W, 4);
		BOARD_GET_MOVE( E, 4);
		break;
	case 5:
		BOARD_GET_MOVE(NW, 4);
		BOARD_GET_MOVE(N , 4);
		BOARD_GET_MOVE(NE, 4);
		BOARD_GET_MOVE( W, 4);
		BOARD_GET_MOVE( E, 4);
		BOARD_GET_MOVE(SW, 4);
		BOARD_GET_MOVE(S , 4);
		BOARD_GET_MOVE(SE, 4);
		break;
	}
	if (move->n>0) {
		*move->position = x;
	}