solver.c

黑白棋终局解算程序

		else if (square[2 * dir] == o) {                        \
			if (square[3 * dir] == p) n_flips += 2;             \
			else if (square[3 * dir] == o) {                    \
				if (square[4 * dir] == p) n_flips += 3;         \
				else if (square[4 * dir] == o                   \
						 && square[5 * dir] == p) n_flips += 4; \
	}}}

/*! macro to flip discs along a direction */
#define BOARD_FLIP(dir, max_flip)           \
	if (BOARD_CHECK_MOVE_##max_flip(dir)) { \
		int z = x + (dir);                  \
		do {                                \
			board->square[z] = p;           \
			move->position[++move->n] = z;  \
			z += (dir);                     \
		} while (board->square[z] == o);    \
	}

/*! macro to get a move along a direction */
#define BOARD_GET_MOVE(dir, max_flip)                        \
	if (BOARD_CHECK_MOVE_##max_flip(dir)) {                  \
		int z = x + (dir);                                   \
		do {                                                 \
			move->position[++move->n] = z;                   \
			move->hash_code[0] ^= hash_code_flip_disc[z][0]; \
			move->hash_code[1] ^= hash_code_flip_disc[z][1]; \
			z += (dir);                                      \
		} while (board->square[z] == o);                     \
	}

/*! update board */
#define BOARD_UPDATE_SQUARE(board, move) switch((move)->n) {  \
	case 18: board->square[(move)->position[18]] = p;  \
	case 17: board->square[(move)->position[17]] = p;  \
	case 16: board->square[(move)->position[16]] = p;  \
	case 15: board->square[(move)->position[15]] = p;  \
	case 14: board->square[(move)->position[14]] = p;  \
	case 13: board->square[(move)->position[13]] = p;  \
	case 12: board->square[(move)->position[12]] = p;  \
	case 11: board->square[(move)->position[11]] = p;  \
	case 10: board->square[(move)->position[10]] = p;  \
	case  9: board->square[(move)->position[ 9]] = p;  \
	case  8: board->square[(move)->position[ 8]] = p;  \
	case  7: board->square[(move)->position[ 7]] = p;  \
	case  6: board->square[(move)->position[ 6]] = p;  \
	case  5: board->square[(move)->position[ 5]] = p;  \
	case  4: board->square[(move)->position[ 4]] = p;  \
	case  3: board->square[(move)->position[ 3]] = p;  \
	case  2: board->square[(move)->position[ 2]] = p;  \
	case  1: board->square[(move)->position[ 1]] = p;  \
	case  0: board->square[(move)->position[ 0]] = p;  \
} 

/*! restore board */
#define BOARD_RESTORE_SQUARE(board, move) switch((move)->n) {  \
	case 18: board->square[(move)->position[18]] = o;  \
	case 17: board->square[(move)->position[17]] = o;  \
	case 16: board->square[(move)->position[16]] = o;  \
	case 15: board->square[(move)->position[15]] = o;  \
	case 14: board->square[(move)->position[14]] = o;  \
	case 13: board->square[(move)->position[13]] = o;  \
	case 12: board->square[(move)->position[12]] = o;  \
	case 11: board->square[(move)->position[11]] = o;  \
	case 10: board->square[(move)->position[10]] = o;  \
	case  9: board->square[(move)->position[ 9]] = o;  \
	case  8: board->square[(move)->position[ 8]] = o;  \
	case  7: board->square[(move)->position[ 7]] = o;  \
	case  6: board->square[(move)->position[ 6]] = o;  \
	case  5: board->square[(move)->position[ 5]] = o;  \
	case  4: board->square[(move)->position[ 4]] = o;  \
	case  3: board->square[(move)->position[ 3]] = o;  \
	case  2: board->square[(move)->position[ 2]] = o;  \
	case  1: board->square[(move)->position[ 1]] = o;  \
	case  0: board->square[(move)->position[ 0]] = EMPTY;  \
} 


/*! macro to update player */
#define BOARD_UPDATE_PLAYER(board) (board->player = o)

/*! macro to restore player */
#define BOARD_RESTORE_PLAYER(board) (board->player = p)

/*! macro to update disc counter */
#define BOARD_UPDATE_DISCS(board, n_flips)     \
	board->n_discs[(int)p] += n_flips + 1;     \
	board->n_discs[(int)o] -= n_flips;         \
	board->n_empties--;

/* macro to restore disc counter */
#define BOARD_RESTORE_DISCS(board, n_flips)     \
	board->n_discs[(int)p] -= n_flips + 1;      \
	board->n_discs[(int)o] += n_flips;          \
	board->n_empties++;

#if PLAY_ODD_SQUARE_FIRST
	/*! macro to update parity */
	#define BOARD_UPDATE_PARITY(board, x) (board->parity[QUADRANT_ID[x]] ^= 1)
	/*! macro to restore parity */
	#define BOARD_RESTORE_PARITY(board, x) (board->parity[QUADRANT_ID[x]] ^= 1)
#else
	#define BOARD_UPDATE_PARITY(board, x)
	#define BOARD_RESTORE_PARITY(board, x)
#endif

/*! macro to update the list of empty squares */
#define BOARD_UPDATE_EMPTIES(board, empties, x) \
	empties = board->position_to_empties[x];    \
	empties->previous->next = empties->next;    \
	empties->next->previous = empties->previous;

/*! macro to restore the list of empty squares */
#define BOARD_RESTORE_EMPTIES(board, empties, x) \
	empties = board->position_to_empties[x];     \
	empties->previous->next = empties;           \
	empties->next->previous = empties;

/*! macro to update for the last time the list of empty squares */
#define BOARD_LAST_UPDATE_EMPTIES(board, empties, x) \
	empties = board->position_to_empties[x];         \
	empties->previous->next = empties->next;

/*! macro to restore for the last time the list of empty squares */
#define BOARD_LAST_RESTORE_EMPTIES(board, empties, x) \
	empties = board->position_to_empties[x];          \
	empties->previous->next = empties;

/*! macro to update the hash codes */
#define BOARD_UPDATE_HASH_CODE(board, code) \
	board->hash_code[0] ^= code[0];         \
	board->hash_code[1] ^= code[1];

/*! macro to restore the hash codes */
#define BOARD_RESTORE_HASH_CODE(board, code) \
	board->hash_code[0] ^= code[0];          \
	board->hash_code[1] ^= code[1];

/*! macro to swap colors */
#define OPPONENT(p) ((p) ^ 1)

/*! test if hash table exists */
#define HASH_TABLE_OK(hash_table) (hash_table->hash_mask != 0)

/*! convert clock ticks to hours */
#define TICK_TO_H(t) (int)((t) / 3600 / CLOCKS_PER_SEC)

/*! convert clock ticks to minutes */
#define TICK_TO_M(t) (int)(((t) / 60 / CLOCKS_PER_SEC) % 60)

/*! convert clock ticks to seconds */
#define TICK_TO_S(t) (int)(((t) / CLOCKS_PER_SEC) % 60)

/*! convert clock ticks to tenth of seconds */
#define TICK_TO_DS(t) (int)(((t) / (CLOCKS_PER_SEC / 10)) % 10)

/*@}*/
/*!
 * \defgroup hash Hash table module
 * The hash table is an efficient memory system to remember the previously
 * analysed positions and re-use the collected data when needed.
 * The hash table contains entries of analysed data where the board is uniquely
 * identified through a 32-bit key and the results of the analysis recorded are
 * two score bounds, the depth of the analysis and the best move found.
 *
 * For more information about how this hash table implementation works, you may
 * read: Breuker D.M., Uiterwijk J.W.H.M. & van den Herik H.J. (1996) Replacement
 * Schemes and Two-Level Tables. ICCA J 19-3 p 183-193.
 */
/*@{*/

/*!
 * \brief Pseudo-random number generator.
 *
 * A good random generator (similar to rand48 or Java's one) to set the hash codes.
 * \return a 32 bits random unsigned long integer.
 */
unsigned long hash_random(void)
{
	static unsigned long x[3] = {0xe66du, 0xdeecu, 0x5u};
	const unsigned long MASK = 0x0000ffffu;
	const unsigned long A[3] = {0xe66du, 0xdeecu, 0x5u};
	const unsigned long B = 0xBu;
	unsigned long product[3];

	product[0] = A[0] * x[0] + B;
	product[1] = A[1] * x[0] + (product[0] >> 16);
	product[2] = A[1] * x[1] + A[0] * x[2] + A[2] * x[0] + (product[1] >> 16);
	product[1] = A[0] * x[1] + (product[1] & MASK);
	product[2] += (product[1] >> 16);
	x[0] = (product[0] & MASK);
	x[1] = (product[1] & MASK);
	x[2] = (product[2] & MASK);

	return x[1] + (x[2] << 16);
}

/*!
 * \brief Initialise the hashtable.
 *
 * Allocate the hash table entries and initialise the hash masks and codes.
 * \param hash_table hash table to setup.
 * \param n_bits     requested size for the hash table in number of bits.
 */
void hash_init(HashTable *hash_table, int n_bits)
{
	int i,j;
	unsigned long hash_mask[2], size = 1u << n_bits;

	if (hash_table->hash_entry != NULL) free(hash_table->hash_entry);
	hash_table->hash_entry = malloc(size * sizeof (HashEntry));
	if (hash_table->hash_entry == NULL) {
		fprintf(stderr, "hash_init: cannot allocate the hash table\n");
		exit(EXIT_FAILURE);
	}
	hash_mask[0] = hash_table->hash_mask = size - 1;
	hash_mask[1] = 0xffffffff;

	for (j = 0; j < 2; j++) {
		hash_code_swap_player[j] = (hash_random() & hash_mask[j]);
		for (i = 0; i < BOARD_SIZE; i++) {
			hash_code_set_disc[i][BLACK][j] = (hash_random() & hash_mask[j]);
			hash_code_set_disc[i][WHITE][j] = (hash_random() & hash_mask[j]);
			hash_code_set_disc[i][EMPTY][j] = 0;
			hash_code_flip_disc[i][j] = hash_code_set_disc[i][BLACK][j] ^
				hash_code_set_disc[i][WHITE][j];
			hash_code_set_disc[i][BLACK][j] ^= hash_code_swap_player[j];
			hash_code_set_disc[i][WHITE][j] ^= hash_code_swap_player[j];
		}
	}
}

/*!
 * \brief Clear the hashtable.
 *
 * Set all hash table entries to zero.
 * \param hash_table hash table to clear.
 */
void hash_clear(HashTable *hash_table)
{
	unsigned long i;
	static const HashEntry init_entry = {
		{0, -INF_SCORE, +INF_SCORE, 0, 0},
		{0, -INF_SCORE, +INF_SCORE, 0, 0}};

	if (HASH_TABLE_OK(hash_table)) {
		for (i = 0; i <= hash_table->hash_mask; i++) {
			hash_table->hash_entry[i] = init_entry;
		}
	}
}

/*!
 * \brief Free the hashtable.
 *
 * Free the memory allocated by the hash table entries
 * \param hash_table hash_table to free.
 */
void hash_free(HashTable *hash_table)
{
	free(hash_table->hash_entry);
	hash_table->hash_entry = NULL;
}

/*!
 * \brief Update an hashtable entry
 *
 * Find an hash table entry according to the evaluated board hash codes. Then
 * update the entry if it already exists otherwise create a new one. Collisions
 * are managed in such a way that better existing entries are always preserved
 * and the new evaluated data is always added. Lower and  upper score bounds
 * are then updated/set from the alpha, beta and score values according to the
 * following alphabeta property (where alpha < beta):
 *     -if (score >= beta) score is a lower bound of the real score
 *     -if (score <= alpha) score is an upper bound of the real score
 *     -if (alpha < score && score < beta) score equals the real score
 * So:  
 *     -if (score < beta) update the upper bound of the hash entry
 *     -if (score > alpha) update the lower bound of the hash entry
 * The best move is also stored.
 * \param hash_table hash table to update.
 * \param board      evaluated board.
 * \param alpha      alpha bound when calling the alphabeta function.
 * \param beta       beta bound when calling the alphabeta function.
 * \param score      best score found.
 * \param move       best move found.
 */
void hash_update(HashTable *hash_table, const Board *board, int alpha, int beta, int score, int move)
{
	HashEntry *hash_entry;
	Hash *deepest, *newest;

	if (!HASH_TABLE_OK(hash_table)) return;

	hash_entry = hash_table->hash_entry + board->hash_code[0];
	deepest = &(hash_entry->deepest);
	newest = &(hash_entry->newest);
	/* try to update deepest entry */
	if (board->hash_code[1] == deepest->lock) {
		if (score < beta && score < deepest->upper) 
			deepest->upper = (char) score;
		if (score > alpha && score > deepest->lower)
			deepest->lower = (char) score;
		deepest->move = (char) move;
	/* else try to update newest entry */
	} else if (board->hash_code[1] == newest->lock) {
		if (score < beta && score < newest->upper)
			newest->upper = (char) score;
		if (score > alpha && score > newest->lower)
			newest->lower = (char) score;
		newest->move = (char) move;
	/* else try to add to deepest entry */
	} else if (deepest->depth < board->n_empties) {
		if (newest->depth < deepest->depth) *newest = *deepest;
		deepest->lock = board->hash_code[1];
		deepest->depth = (char) board->n_empties;
		deepest->lower = -INF_SCORE;
		deepest->upper = +INF_SCORE;
		if (score < beta) deepest->upper = (char) score;
		if (score > alpha) deepest->lower = (char) score;
		deepest->move = (char) move;
	/* else add to newest entry */
	} else {
		newest->lock = board->hash_code[1];
		newest->depth = (char) board->n_empties;
		newest->lower = -INF_SCORE;
		newest->upper = +INF_SCORE;
		if (score < beta) newest->upper = (char) score;
		if (score > alpha) newest->lower = (char) score;
		newest->move = (char) move;
	}
}

/*!
 * \brief Find an hash table entry according to the evaluated board hash codes.
 *
 * The data recorded within the entry will then be used to reframe the alpha
 * beta bounds and set the move to search first. In some cases, an alphabeta
 * cut will be immediately found so avoiding the entire search and gaining a
 * (lot of) time.
 *
 * \param hash_table : hash table.
 * \param board      : evaluated board.
 * \return : an hash table entry if the board was found, NULL otherwise.
 */
Hash *hash_get(HashTable *hash_table, const Board *board)
{
	HashEntry *hash_entry;

	if (HASH_TABLE_OK(hash_table)) {
		hash_entry = hash_table->hash_entry + board->hash_code[0];
		if (board->hash_code[1] == hash_entry->deepest.lock)
			return &(hash_entry->deepest);
		if (board->hash_code[1] == hash_entry->newest.lock)
			return &(hash_entry->newest);
	}
	return NULL;
}

/*@}*/
/*!
 * \defgroup board Board module
 *
 * This module deals with the Board management.
 *
 * The Board is represented with a structure containing the following data:
 *  - a 1-D array with the square contents.
 *  - the player to move.
 *  - the disc number for each players.
 *  - the number of remaining empty squares.
 *  - a list of empty squares for a fast navigation through them.
 *  - hash table codes identifying the board in the hash table.
 *  - a node counter.
 *
 * High level functions are provided to set/modify the board data or to compute
 * some board properties. Most of the functions are optimized to be as fast as
 * possible, while remaining readable.
 *
 */
/*@{*/

/*!
 * \brief Set a board from a string description.
 *
 * Read a standardized string (See http://www.nada.kth.se/~gunnar/download2.html
 * for details) and translate it into our internal Board structure.
 * \param board : the board to set
 * \param string : string describing the board
 */
void board_set(Board *board, const char *string)
{
	int i, j;
	SquareList *empties;
#if USE_PRESORTED_SQUARES
	const int presorted_position[] = {
		A1, A8, H1, H8,                    /* Corner */
		A3, A6, C1, C8, F1, F8, H3, H6,    /* A */
		C3, C6, F3, F6,                    /* D */
		A4, A5, D1, D8, E1, E8, H4, H5,    /* B */
		C4, C5, D3, D6, E3, E6, F4, F5,    /* E */
		B4, B5, D2, D7, E2, E7, G4, G5,    /* G */
		B3, B6, C2, C7, F2, F7, G3, G6,    /* F */
		A2, A7, B1, B8, G1, G8, H2, H7,    /* C */
		B2, B7, G2, G7,                    /* X */
	};
#else
	const int presorted_position[] = {     /* A1 -> H8 */
		A1, A2, A3, A4, A5, A6, A7, A8,
		B1, B2, B3, B4, B5, B6, B7, B8,
		C1, C2, C3, C4, C5, C6, C7, C8,
		D1, D2, D3,         D6, D7, D8,
		E1, E2, E3,         E6, E7, E8,