solver.c

黑白棋终局解算程序

 *
 * To be efficient PVS need highly ordered tree. The following ordering have
 * been made :
 *       - fixed square ordering : square usually leading to a good move are
 * visited first, ie from corner squares to X and C squares.
 *       - most stable ordering : a crude evaluation of stability at the corner
 * (corner, X and C squares) to order the moves.
 *       - fast first ordering : the moves leading to the most reduced mobility
 * for the opponent are played first.
 *       - best move previously found : If the position have been previously
 * searched, the best move that was found is replayed as the first move.
 *
 * -# Campbell MS & Marsland TA (1983) A Comparison of Minimax Trees Search
 *    Algorithms. Artificial Intelligence, 20, pp. 347-367.
 * -# Plaat A. et al. (1996) Best-First Fixed Depth Minimax Algorithms. Artificial
      Intelligence, 84, pp. 255-293.
 * -# Weill JC. (1992) Experiments With The NegaC* Search. An alternative for Othello
 *    Endgame Search. ICCA journal, 15(1), pp. 3-7.
 * -# Reinsfeld A. (1983) An Improvement Of the Scout Tree-Search Algorithm. ICCA
      journal, 6(4), pp. 4-14.
 */
/*@{*/

/*!
 * \brief Get the final score.
 *
 * Get the final score, when no move can be made.
 * \param board  board.
 * \return       the final score, as a disc difference.
 */
int board_get_final_score(const Board *board)
{
	const int p = board->player;
	const int o = OPPONENT(p);
	int score = board->n_discs[p] - board->n_discs[o];

	if (score < 0) score -= board->n_empties;
	else if (score > 0) score += board->n_empties;

	return score;
}

/*!
 * \brief Get the final score.
 *
 * Get the final score, when the board is full.
 * \param board   board.
 * \return        the final score, as a disc difference.
 */
int board_get_final_score_0(const Board *board)
{
	const int p = board->player;
	const int o = OPPONENT(p);
	int score = board->n_discs[p] - board->n_discs[o];

	return score;
}

/*!
 * \brief Get the final score.
 *
 * Get the final score, when 1 empty square remains.
 * \param board   board.
 * \return        the final score, as a disc difference.
 */
int board_get_final_score_1(Board *board)
{
	const int p = board->player;
	const int o = OPPONENT(p);
	int score = board->n_discs[p] - board->n_discs[o];
	int n_flips;
	const int x = board->empties->next->position;

	if ((n_flips = board_count_flips(board, x, p)) > 0) {
		score += 2 * n_flips + 1;
		BOARD_UPDATE_TERMINAL_NODES();
	} else if ((n_flips = board_count_flips(board, x, o)) > 0) {
		score -= 2 * n_flips + 1;
		BOARD_UPDATE_TERMINAL_NODES();
	} else if (score < 0) score--;
	else if (score > 0) score++;

	return score;
}

/*!
 * \brief Get the final score.
 *
 * Get the final score, when 2 empty squares remain.
 * \param board  the board to evaluate.
 * \param alpha  upper score value.
 * \param beta   lower score value.
 * \param passed  a flag indicating if previous move was a pass.
 * \return       the final score, as a disc difference.
 */
int board_get_final_score_2(Board *board, int alpha, int beta, int passed)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	SquareList *empties = board->empties->next;
	int x1 = empties->position;
	int x2 = empties->next->position;
	int score, bestscore, n1_flips, n2_flips, diff_discs;
	Move move;

	diff_discs = board->n_discs[(int)p] - board->n_discs[(int)o];
	bestscore = -INF_SCORE;

	/* try to play on the first available square */
	if ((n1_flips = board_do_flip(board, x1, &move)) > 0) {
		if ((n2_flips = board_count_flips(board, x2, o)) > 0) {
			bestscore = diff_discs + 2 * (n1_flips - n2_flips);
			BOARD_UPDATE_TERMINAL_NODES();
		} else if ((n2_flips = board_count_flips(board, x2, p)) > 0) {
			bestscore = diff_discs + 2 * (n1_flips + n2_flips) + 2;
			BOARD_UPDATE_TERMINAL_NODES();
		} else {
			bestscore = diff_discs + 2 * n1_flips + 1;
			if (bestscore > 0) bestscore++;
			else if (bestscore < 0) bestscore--;
		}
		BOARD_RESTORE_SQUARE(board, &move);
		BOARD_RESTORE_PLAYER(board);
	}
	/* if needed, try to play on the second & last available square */
	if (bestscore < beta && (n1_flips = board_do_flip(board, x2, &move)) > 0) {
		if ((n2_flips = board_count_flips(board, x1, o)) > 0) {
			score = diff_discs + 2 * (n1_flips - n2_flips);
			BOARD_UPDATE_TERMINAL_NODES();
		} else if ((n2_flips = board_count_flips(board, x1, p)) > 0) {
			score = diff_discs + 2 * (n1_flips + n2_flips) + 2;
			BOARD_UPDATE_TERMINAL_NODES();
		} else {
			score = diff_discs + 2 * n1_flips + 1;
			if (score > 0) score++;
			else if (score < 0) score--;
		}
		BOARD_RESTORE_SQUARE(board, &move);
		BOARD_RESTORE_PLAYER(board);
		if (score > bestscore) bestscore = score;
	}
	/* if no move were available */
	if (bestscore == -INF_SCORE) {
		if (passed) { /* game is over */
			BOARD_CORRECT_TERMINAL_NODES();
			bestscore = diff_discs;
			if (bestscore > 0) bestscore += 2;
			else if (bestscore < 0) bestscore -= 2;
		} else { /* pass... */
			BOARD_UPDATE_PLAYER(board);
			BOARD_UPDATE_INTERNAL_NODES();
			bestscore = -board_get_final_score_2(board, -beta, -alpha, 1);
			BOARD_RESTORE_PLAYER(board);
		}
	}

	return bestscore;
}

/*!
 * \brief  Evaluate a position using a shallow Alphabeta.
 *
 * This function is used when there are few empty squares on the board. Here,
 * optimizations are in favour of speed instead of efficiency. A simple
 * alphabeta is used because of the low branching factor that makes PVS less
 * efficient.
 * \param board   board.
 * \param alpha   lower bound.
 * \param beta    upper bound.
 * \param passed  a flag indicating if previous move was a pass.
 * \return        the final score, as a disc difference.
 */
int alphabeta_shallow(Board *board, int alpha, int beta, int passed)
{
	const char p = board->player;
	const char o = OPPONENT(p);
	int score, bestscore = -INF_SCORE;
	SquareList *empties;
	Move move;

#if PLAY_ODD_SQUARE_FIRST
	int parity;
	for (parity = 1; parity >= 0; parity--) {
		for (empties = board->empties->next; empties->position != NOMOVE; empties = empties->next) {
			if (board->parity[QUADRANT_ID[empties->position]] == parity
			 && board_do_flip(board, empties->position, &move)) {
#else
		{
		for (empties = board->empties->next; empties->position != NOMOVE; empties = empties->next) {
			if (board_do_flip(board, empties->position, &move)) {
#endif
				BOARD_UPDATE_PLAYER(board);
				BOARD_UPDATE_DISCS(board, move.n);
				BOARD_UPDATE_PARITY(board, *move.position);
				BOARD_UPDATE_EMPTIES(board, empties, *move.position);
				if (board->n_empties == 2) {
					score = -board_get_final_score_2(board, -beta, -alpha, 0);
				} else {
					score = -alphabeta_shallow(board, -beta, -alpha, 0);
				}
				BOARD_RESTORE_SQUARE(board, &move);
				BOARD_RESTORE_PLAYER(board);
				BOARD_RESTORE_DISCS(board, move.n);
				BOARD_RESTORE_PARITY(board, *move.position);
				BOARD_RESTORE_EMPTIES(board, empties, *move.position);
				if (score > bestscore) {
					bestscore = score;
					if (bestscore > alpha) {
						alpha = bestscore;
						if (alpha >= beta) return bestscore;
					}
				}
			}
		}
	}

	/* no move */
	if (bestscore == -INF_SCORE) {
		if (passed) { /* game over */
			BOARD_CORRECT_TERMINAL_NODES();
			bestscore = board_get_final_score(board);
		} else { /* pass */
			BOARD_UPDATE_PLAYER(board);
			BOARD_UPDATE_INTERNAL_NODES();
			bestscore = -alphabeta_shallow(board, -beta, -alpha, 1);
			BOARD_RESTORE_PLAYER(board);
		}
	}

	return bestscore;
}

/*!
 * \brief Evaluate a position with a deep Principal Variation Search algorithm.
 *
 * This function is used when there are still many empty squares on the board. Move
 * ordering, hash table cutoff, enhanced transposition cutoff, etc. are used in
 * order to diminish the size of the tree to analyse, but at the expense of a
 * slower speed.
 *
 * \param board      board.
 * \param hash_table hash_table.
 * \param alpha      lower bound.
 * \param beta       upper bound.
 * \param passed     a flag indicating if previous move was a pass.
 * \return the final score, as a disc difference.
 */
int PVS_deep(Board *board, HashTable *hash_table, int alpha, int beta, int passed)
{
	int score, bestscore, lower, upper, bestmove;
	unsigned long hash_lock, hash_index;
	MoveList movelist[MAX_MOVE + 2], *iter;
	Move *move;
	Hash *hash;
	HashEntry *hash_entry;

	bestmove = NOMOVE;
	lower = alpha;
	upper = beta;
	/* transposition cutoff ? */
#if USE_HASH_TABLE
	hash = hash_get(hash_table, board);
	if (hash != NULL) {
		if (upper > hash->upper) {
			upper = hash->upper;
			if (upper <= lower) return upper;
		}
		if (lower < hash->lower) {
			lower = hash->lower;
			if (lower >= upper) return lower;
		}
		bestmove = hash->move;
	}
#endif
	board_get_movelist(board, movelist);
	if (movelist->next == NULL) {
		if (passed) {
			BOARD_CORRECT_TERMINAL_NODES();
			alpha = -(beta = +INF_SCORE);
			bestscore = board_get_final_score(board);
			bestmove = NOMOVE;
		} else {
			board_update_pass(board);
			bestscore = -PVS_deep(board, hash_table, -upper, -lower, 1);
			bestmove = PASS;
			board_restore_pass(board);
		}
	} else {
		/* enhanced transposition cutoff */
#if USE_ENHANCED_TRANSPOSITION_CUTOFF
		if (board->n_empties > EMPTIES_DEEP_TO_SHALLOW_SEARCH &&
			HASH_TABLE_OK(hash_table)) {
			if (bestmove != NOMOVE) movelist_sort_bestmove(movelist, bestmove);
			for (iter = movelist->next; iter != NULL; iter = iter->next) {
				move = &(iter->move);
				hash_index = (board->hash_code[0] ^ move->hash_code[0]);
				hash_lock = (board->hash_code[1] ^ move->hash_code[1]);
				hash_entry = hash_table->hash_entry + hash_index;
				BOARD_UPDATE_ALL_NODES();
				if (hash_entry->deepest.lock ==  hash_lock && -hash_entry->deepest.upper >= upper)
					return -hash_entry->deepest.upper;
				if (hash_entry->newest.lock ==  hash_lock && -hash_entry->newest.upper >= upper)
					return -hash_entry->newest.upper;
			}
		}
#endif
		/* move sorting */
#if PLAY_FAST_SUBTREE_FIRST
		if (board->n_empties > EMPTIES_DEEP_TO_SHALLOW_SEARCH)
			movelist_sort_fastfirst(movelist, board);
#endif
#if PLAY_BEST_MOVE_IN_MEMORY_FIRST
		if (bestmove != NOMOVE && bestmove != *movelist->next->move.position)
			movelist_sort_bestmove(movelist, bestmove);
#endif

		/* first move */
		iter = movelist->next;
		move = &(iter->move);
		board_update_move(board, move);
		if (board->n_empties < EMPTIES_DEEP_TO_SHALLOW_SEARCH) {
			bestscore = -alphabeta_shallow(board, -upper, -lower, 0);
		} else {
			bestscore = -PVS_deep(board, hash_table, -upper, -lower, 0);
		}
		bestmove = *move->position;
		if (bestscore > lower) lower = bestscore;
		board_restore_move(board, move);

		/* other moves : try to refute the first/best one */
		for (iter = iter->next; lower < upper && iter != NULL; iter = iter->next) {
			move = &(iter->move);
			board_update_move(board, move);
			if (board->n_empties < EMPTIES_DEEP_TO_SHALLOW_SEARCH) {
				score = -alphabeta_shallow(board, -lower - 1, -lower, 0);
				if (lower < score && score < upper)
					score = -alphabeta_shallow(board, -upper, -score, 0);
			} else {
				score = -PVS_deep(board, hash_table, -lower - 1, -lower, 0);
				if (lower < score && score < upper)
					score = -PVS_deep(board, hash_table, -upper, -score, 0);
			}
			board_restore_move(board, move);
			if (score > bestscore) {
				bestscore = score;
				bestmove = *move->position;
				if (bestscore > lower) lower = bestscore;
			}
		}
	}
#if USE_HASH_TABLE
	hash_update(hash_table, board, alpha, beta, bestscore, bestmove);
#endif

	return bestscore;
}

/*!
 * \brief Principal Variation Search algorithm at the root of the tree.
 *
 * This function solves the position provided within the limits set by the alpha
 * and beta bounds. The movelist parameter is updated so that the bestmove is the
 * first of the list when the search ended.
 *
 * \param board      board.
 * \param hash_table hash table to memorize the analysis.
 * \param alpha      lower bound.
 * \param beta       upper bound.
 * \param movelist   List of legal moves (should actually contain moves !).
 */
void PVS_root(Board *board, HashTable *hash_table, int alpha, int beta,
	MoveList *movelist)
{
	int lower, upper;
	MoveList *iter;
	Move *move, *bestmove;

	lower = alpha;
	upper = beta;
	board->n_nodes++;

	/* first move */
	iter = movelist->next;
	bestmove = &(iter->move);
	board_update_move(board, bestmove);
	if (board->n_empties == 0) {
		bestmove->score = -board_get_final_score_0(board);
	} else if (board->n_empties == 1) {
		bestmove->score = -board_get_final_score_1(board);
	} else if (board->n_empties == 2) {
		bestmove->score = -board_get_final_score_2(board, -upper, -lower, 0);
	} else if (board->n_empties < EMPTIES_DEEP_TO_SHALLOW_SEARCH) {
		bestmove->score = -alphabeta_shallow(board, -upper, -lower, 0);
	} else {
		bestmove->score = -PVS_deep(board, hash_table, -upper, -lower, 0);
	}
	if (bestmove->score > lower) lower = bestmove->score;
	board_restore_move(board, bestmove);

	/* other moves : try to refute the first/best one */
	for (iter = iter->next; lower < upper && iter != NULL; iter = iter->next) {
		move = &(iter->move);
		board_update_move(board, move);
		if (board->n_empties == 0) {
			move->score = -board_get_final_score_0(board);
		} else if (board->n_empties == 1) {
			move->score = -board_get_final_score_1(board);
		} else if (board->n_empties == 2) {
			move->score = -board_get_final_score_2(board, -upper, -lower, 0);
		} else if (board->n_empties < EMPTIES_DEEP_TO_SHALLOW_SEARCH) {
			move->score = -alphabeta_shallow(board, -lower - 1, -lower, 0);
			if (lower < move->score && move->score < u