solver.c

黑白棋终局解算程序

	return move->n;
}

/*!
 * \brief Update a board.
 *
 * Update a board by flipping its discs and updating every other data,
 * according to the 'move' description.
 * \param board : the board to modify
 * \param move  : A Move structure describing the modification.
 */
void board_update_move(Board *board, const Move *move)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	SquareList *empties;

	BOARD_UPDATE_SQUARE(board, move);
	BOARD_UPDATE_PLAYER(board);
	BOARD_UPDATE_DISCS(board, move->n);
	BOARD_UPDATE_INTERNAL_NODES();
	BOARD_UPDATE_HASH_CODE(board, move->hash_code);
	BOARD_UPDATE_PARITY(board, *move->position);
	BOARD_UPDATE_EMPTIES(board, empties, *move->position);
}

/*!
 * \brief Restore a board.
 *
 * Restore a board by un-flipping its discs and restoring every other data,
 * according to the 'move' description, in order to cancel a board_update_move.
 * \param board : board to restore.
 * \param move  : a Move structure describing the modification.
 */
void board_restore_move(Board *board, const Move *move)
{
	const char o = board->player;
	const char p = OPPONENT(o);
	SquareList *empties;

	BOARD_RESTORE_SQUARE(board, move);
	BOARD_RESTORE_PLAYER(board);
	BOARD_RESTORE_DISCS(board, move->n);
	BOARD_RESTORE_HASH_CODE(board, move->hash_code);
	BOARD_RESTORE_PARITY(board, *move->position);
	BOARD_RESTORE_EMPTIES(board, empties, *move->position);
}

/*!
 * \brief Passing move
 *
 * Modify a board by passing player's turn.
 * \param board : board to update.
 */
void board_update_pass(Board *board)
{
	const char o = OPPONENT(board->player);
	BOARD_UPDATE_PLAYER(board);
	BOARD_UPDATE_INTERNAL_NODES();
	BOARD_UPDATE_HASH_CODE(board, hash_code_swap_player);
}

/*!
 * \brief Un-passing
 *
 * Restore a board by un-passing player's turn.
 * \param board : board to restore.
 */
void board_restore_pass(Board *board)
{
	const char p = OPPONENT(board->player);
	BOARD_RESTORE_PLAYER(board);
	BOARD_RESTORE_HASH_CODE(board, hash_code_swap_player);
}

/*!
 * \brief Get a list of legal moves.
 *
 * Compute the complete list of legal moves and store it into a simple linked
 * list, to fasten ulterior move sorting.
 * \param board : the board to check
 * \param start : start point of the linked-list that will received the legal
 *                moves.
 */
void board_get_movelist(const Board *board, MoveList *start)
{
	MoveList *list = start + 1, *previous = start;
	SquareList *empties;

	for (empties = board->empties->next; empties->position != NOMOVE; empties = empties->next) {
		if (board_get_move(board, empties->position, &(list->move))) {
			previous = previous->next = list;
			list++;
		}
	}
	previous->next = NULL;
}

/*!
 * \brief Estimate the mobility.
 *
 * Count a number of legal moves for a player. The mobility is an
 * important concept in Othello, used here for move sorting.
 * \param board : the board to test.
 * \param player : the player to test.
 * \return : the number of legal moves.
 */
int board_get_mobility(const Board *board, int player)
{
	SquareList *empties;
	int n_moves = 0;

	for (empties = board->empties->next; empties->position != NOMOVE; empties = empties->next) {
		if (board_check_move(board, empties->position, player))
			n_moves++;
	}

	return n_moves;
}

/*!
 * \brief Estimate corner stability.
 *
 * Count the number of stable discs around the corner. Limiting the count
 * to the corner keep the function fast but still get this information,
 * particularly important at Othello. Corner stability will be used for
 * move sorting.
 * \param board : the board.
 * \param player : the player.
 * \return : the number of stable discs around the corner.
 */
int board_get_corner_stability(Board *board, int player)
{
	const char *square = board->square;
	const char p = player;
	int n_stables = 0;

	if (square[A1] == p) {
		n_stables++;
		if (square[B1] == p) n_stables++;
		if (square[A2] == p) n_stables++;
	}
	if (square[A8] == p) {
		n_stables++;
		if (square[B8] == p) n_stables++;
		if (square[A7] == p) n_stables++;
	}
	if (square[H1] == p) {
		n_stables++;
		if (square[G1] == p) n_stables++;
		if (square[H2] == p) n_stables++;
	}
	if (square[H8] == p) {
		n_stables++;
		if (square[G8] == p) n_stables++;
		if (square[H7] == p) n_stables++;
	}

	return n_stables;
}

/*!
 * \brief Initialize the local parity counters.
 *
 * Approximate the local parity by computing it on each board quadrant. This
 * will be used at the very end of game for move sorting.
 * \param board : the board.
 */
/*#if PLAY_ODD_SQUARE_FIRST
void board_init_parity(Board *board)
{
	unsigned char *parity = board->parity;
	SquareList *empties;

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

/*!
 * \brief Print out the board.
 *
 * Print an ASCII representation of the board to an output stream.
 * \param board : board to print.
 * \param f     : output stream.
 */
void board_print(Board *board, FILE *f)
{
	int i, j, square, x;
	char *color = "*O-.?";

	fputs("  A B C D E F G H\n", f);
	for (i = 1; i <= 8; i++) {
		fputc(i + '0', f);
		fputc(' ', f);
		for (j = 1; j <= 8; j++) {
			x = i * 9 + j;
			square = (int)board->square[x];
			if (square == EMPTY && board_check_move(board, x, board->player))
				square++;
			fputc(color[square], f);
			fputc(' ', f);
		}
		fputc(i+'0', f);
		if (i == 2)
			fprintf(f, " %c to move", color[(int)board->player]);
		else if (i == 4)
			fprintf(f, " *: discs = %2d    moves = %2d",
				board->n_discs[BLACK], board_get_mobility(board, BLACK));
		else if (i == 5)
			fprintf(f, " O: discs = %2d    moves = %2d",
				board->n_discs[WHITE], board_get_mobility(board, WHITE));
		else if (i == 6)
			fprintf(f, "  empties = %2d      ply = %2d",
				board->n_empties, 61-board->n_empties);
		fputc('\n', f);
	}
	fputs("  A B C D E F G H\n", f);
}

/*@}*/
/*!
 * \defgroup move Move module
 * Functions to print a move or a list of moves and to sort list of moves.
 */
/*@{*/

/*!
 * \brief Print out a move
 *
 * Print the move, using letter case to distinguish player's color,
 * to an output stream.
 * \param x      square coordinate to print.
 * \param player player color.
 * \param f      output stream.
 */
void move_print(int x, int player, FILE *f)
{
	int s[2];

	if (x == NOMOVE) {
		s[0] = ' ';
		s[1] = ' ';
	} else if (x == PASS) {
		s[0] = 'p';
		s[1] = 's';
	} else if (x >= A1 && x <= H8 && x % 9 > 0) {
		s[0] = x % 9 + 'a' - 1;
		s[1] = x / 9 + '1' - 1;
	} else {
		s[0] = '?';
		s[1] = '?';
	}

	if (player == BLACK) {
		s[0] = toupper(s[0]);
		s[1] = toupper(s[1]);
	}
	fputc(s[0], f);
	fputc(s[1], f);
}

/*!
 * \brief Print a PV.
 *
 * Get the Principal Variation (best move sequence) from the hash table,
 * and print it to the output stream.
 * \param board      starting position.
 * \param hash_table hash table where to retrieve the moves.
 * \param depth      maximum number of moves to print.
 * \param f          output stream.
 */
void line_print(Board *board, HashTable *hash_table, int depth, FILE *f)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	Hash *hash = hash_get(hash_table, board);
	Move move[1];

	if (depth <= 0) return;
	if (hash != NULL) {
		move_print(hash->move, board->player, f);
		fputc(' ',f);
		if (board_get_move(board, hash->move, move)) {
			BOARD_UPDATE_SQUARE(board, move);
			BOARD_UPDATE_PLAYER(board);
			BOARD_UPDATE_HASH_CODE(board, move->hash_code);
			line_print(board, hash_table, depth - 1, f);
			BOARD_RESTORE_SQUARE(board, move);
			BOARD_RESTORE_PLAYER(board);
			BOARD_RESTORE_HASH_CODE(board, move->hash_code);
		} else if (hash->move == PASS) {
			BOARD_UPDATE_PLAYER(board);
			BOARD_UPDATE_HASH_CODE(board, hash_code_swap_player);
			line_print(board, hash_table, depth - 1, f);
			BOARD_RESTORE_PLAYER(board);
			BOARD_RESTORE_HASH_CODE(board, hash_code_swap_player);
		} else {
			line_print(board, hash_table, depth - 1, f);
		}
	} else {
		fputs("-- ", f);
		line_print(board, hash_table, depth - 1, f);
	}
}

/*!
 * \brief Sort a move as best.
 *
 * Put a move at the head of the list.
 * \param movelist   list of moves to sort.
 * \param move       best move to to set first.
 */
void movelist_sort_bestmove(MoveList *movelist, int move)
{
	MoveList *iter, *previous;

	for (iter = (previous = movelist)->next; iter != NULL; iter = (previous = iter)->next) {
		if (*iter->move.position == move) {
			previous->next = iter->next;
			iter->next = movelist->next;
			movelist->next = iter;
			break;
		}
	}
}

/*!
 * \brief Sort a list of move, fastest-first.
 *
 * Sort a list to accelerate the alphabeta research. The moves that minimize
 * opponent mobility and increase player's relative stability will be played
 * first.
 * \param movelist   : list of moves to sort.
 * \param board      : board on which the moves applied.
 */
void movelist_sort_fastfirst(MoveList *movelist, Board *board)
{
	MoveList *iter, *best, *previous_best, *previous;
	SquareList *empties;
	const char p = board->player;
	const char o = OPPONENT(p);

	for (iter = movelist->next; iter != NULL; iter = iter->next) {
		BOARD_UPDATE_SQUARE(board, &(iter->move));
		BOARD_LAST_UPDATE_EMPTIES(board, empties, *iter->move.position);
		BOARD_UPDATE_ALL_NODES();
#if PLAY_STABLEST_SUBTREE
		iter->move.score = (board_get_mobility(board, o) << 4) - board_get_corner_stability(board, p);
#else
		iter->move.score = board_get_mobility(board, o);
#endif
		BOARD_RESTORE_SQUARE(board, &(iter->move));
		BOARD_LAST_RESTORE_EMPTIES(board, empties, *iter->move.position);
	}
	for (iter = movelist; iter->next != NULL; iter = iter->next) {
		previous_best = iter;
		for (previous = previous_best->next; previous->next != NULL;
			previous = previous->next) {
			if (previous_best->next->move.score >  previous->next->move.score) {
				previous_best = previous;
			}
		}
		if (previous_best != iter) {
			best = previous_best->next;
			previous_best->next = best->next;
			best->next = iter->next;
			iter->next = best;
		}
	}
}

/*@}*/
/*!
 * \defgroup search Search module
 * Functions that evaluate a board with different methods depending on the
 * position in the tree search and/or that finds the best move of a given
 * board.
 *
 * At the end of the game, some trivial functions are used to compute the score.
 * Optimization here is reached by maintaining a disc number record that is
 * updated each time a move is made. At the end of the game, computing the score
 * consists only to a simple substraction. For further optimization, the last
 * move is not made and only the number of flipped discs is evaluated. Special
 * and optimized functions are used when one or two empty squares remain on the
 * board, in order to speed up the search.
 *
 * The search of the best move is driven with the Principal Variation Search
 * algorithm (PVS) [1], an enhanced variation of the alphabeta algorithm. The
 * alphabeta algorithm is known to visit less nodes when the alphabeta window is
 * reduced. PVS takes this property into account. From a set of sibling nodes,
 * the first node is searched using a plain alpha beta window. Then the sibling
 * nodes are only searched with minimal windows (where beta = alpha + 1), just
 * to refute the best (first) score. In rare cases the first move is actually
 * refuted, then the current move is re-searched a second time in order to
 * determinate its score more accurately. On highly ordered tree, very few
 * re-searches will be done. Moreover, thanks to the hash table, a second search
 * is usually faster than a first search. So the seldom and fast re-searches
 * will not impact too much the benefit of using minimal windows. Aspiration
 * windows have been added as another improvement, so that even the first
 * search is done with a reduced window.
 * During the 1990s, several re-re-search algorithm based on null-window
 * alphabeta have been proposed : SSS*ab [2], Dual*ab[2], NegaC*[3], MDT[2],
 * negascout[4]. Some (unpublished) experimental tests I made with them did not
 * show any significant improvement compare to the PVS algorithm with
 * aspiration-windows used here.