solver.c

黑白棋终局解算程序

/*!\mainpage
 *
 * solver.c : a program to solve Othello endgame script.
 * - copyleft (c) 2001-2004
 * - version 1.4 (2004-04-12 18:00:00)
 * - author: Richard A Delorme
 * - e-mail: [e-mail]
 * - web site: http://perso.club-internet.fr/abulmo/resources/
 *
 *
 * \section lic Licence
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *
 * \section dl Download
 * You can download the source with its documentation here:
 * http://perso.club-internet.fr/abulmo/resources/solver/solver.1-4.zip
 *
 *
 * \section pres Presentation
 *
 *      "The important decisions in design are not what to put in but what to
 *       leave out."
 *                  Tony Hoare
 *
 * At ftp://ftp.nj.nec.com/pub/igord/IOS/src, an Othello archive site, there
 * is a program about endgame solving firstly written by Jean-Christophe Weill,
 * then improved by Warren D Smith and further improved by Gunnar Anderson.
 * Although my work was greatly influenced by these programs, the solver I
 * present here is not another improvement but a complete re-implementation,
 * done in a few hours by cutting and pasting code from my own program Edax.
 * I tried to write an optimized but readable code, two incompatible things. Do
 * not forget that the C language is a write-only language :-(
 * Compared to their previous works:
 *    - more general user interface. In addition to the best score, this solver
 * also provides the best move and (if hash table is ON) the best principal
 * variation, some performance data and, on demand, the tested board. The
 * test positions (too easy, IMHO) are no more included into the code but are
 * present within an external standardized script file "endgame.scr". Moreover,
 * you may try "fforum-1-19.scr", "fforum-20-39.scr", and "fforum-40-59.scr",
 * that contain problems published in the magazine of the Federation Francaise
 * d'Othello: FFORUM.
 *    - strict ansi-C89 conformance.
 *    - more modular code. I put into functions many things sparsed into the
 * same function.
 *    - avoidance of global variables. Instead I organize them into structures
 * passed to functions as pointers. Structure and function naming was carefully
 * chosen to give an object-oriented-programming feeling.
 *    - to keep code clear but fast, I overuse macro inlining.
 *    - more and better algorithms used:
 *         - fast (due to inlining and loop-unrolling) move generators.
 *         - Principal Variation Search (an enhanced alphabeta) [1].
 *         - move sorting according to the type of the squares.
 *         - move sorting to play fastest & stablest lines first.
 *         - move sorting based on approximated parity.
 *         - hash table [2] used to:
 *               - anticipate cutoff at present level (if position is stored).
 *               - anticipate cutoff at the next level (enhanced transposition
 *                 cutoff [3]).
 *               - replay known bestmove first.
 *
 * A faster endgame solver would need:
 *    - a good evaluation function.
 *    - iterative deepening.
 *    - move sorting using shallow search.
 *    - "hard coding" of move generation, ...
 *    - 64 bit board representation (bitboard) on 64 bit machine.
 *    - other heuristics: conspiracy number, ...
 *
 * but the following code is already much too long. Whatever, this solver is
 * very fast for positions with less than 15 empties and still quiet good until
 * 20 empties. The source has been kept in a single file to mimic other similar
 * but older othello endgame solvers ; however, any clever implementation
 * should split it in smaller files gathering the same logical content.
 *
 *
 * \section comp Compilation
 * I recommend to compile it with very aggressive optimizing settings, for
 * example with the gnu compiler:
 *
 *    gcc -O3 -fomit-frame-pointer -funroll-loops -march=<your-CPU> solver.c -o solver
 *
 * A few #define at the top of the code may be changed to test/tune
 * the effect of different parameters.
 *
 *
 * \section us Usage
 * Usage: solver [options] script_file
 *
 * Options:
 *    - -v            verbose mode.
 *    - -vv           very verbose mode.
 *    - -wdl          search for win/draw/loss.
 *    - -wd           search for win/(draw-loss).
 *    - -dl           search for (win-draw)/loss.
 *    - -h <nbits>    set hash table size.
 *
 * Note: the best value for the '-h' option, i.e. the  hash table size in bit
 * number is approximately the number of empty squares of the position.
 * Example: solver -v -h 20 fforum-20-39.scr
 *
 *
 * \section hist History
 * - version 1.0: 2001-10-31
 * - version 1.1: 2001-12-19
 *      - added stablest square based sorting
 *      - node counter as Macros
 *      - cosmetic enhancements.
 * - version 1.2: 2003-12-06
 *      - added parity based sorting
 *      - plain alphabeta near the leaves
 *      - better comments & documentation (compatible with doxygen).
 *      - suppression of annoying statistic routines.
 *      - minor bug removals.
 *      - minor speed enhancements.
 *      - cosmetic enhancements.
 * - version 1.3: 2004-02-18
 *      - major bug removals: parity missing initialisation.
 *      - minor bug removals.
 * - version 1.4: 2004-04-12
 *      - major bug removal: wrong score returned from game-over positions.
 *      - minor speed enhancements: board update/restore unrolling.
 *
 *
 * \section ref Reference
 * -# Marsland T.A. (1983) Relative efficiency of alpha-beta implementations.
 *     8th IIJCAI. p 763-766.
 * -# 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.
 * -# Plaat A, Schaeffer J., Wirn P. & de Bruin A.(1996) Exploiting Graph
 *     Properties of Game Trees.
 *
 *
 * \section thk Thanks
 *     - to Christophe Lanuit, for the stablest sorting heuristics.
 *     - to Bruno Causse, who discovered an illogical bug when passing.
 *     - to Gunnar Anderson, who gave me the idea about the parity based on
 * quadrant, as a fast sorting algorithm at shallow depth.
 *     - to Bj鰎n Lindberg, who reported a bug in version 1.3.
 *     - to people at GGS for their invaluable comments about this file.
 *
 */

#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#ifdef _WIN32
	#include <windows.h>
#endif

/*!
 * \defgroup mac Macros, constants, globals & declarations
 */
 /*@{*/

/* YOU MAY MODIFY FOLLOWING DATA TO CONTROL THE USAGE OF SOME HEURISTICS */

/*! depth switch from a slow but efficient PVS near the root to a fast PVS
  near the leaves. (default = 7) */
#define EMPTIES_DEEP_TO_SHALLOW_SEARCH 7

/*! use the hash table heuristics. 1 = on, 0 = off. (default = 1) */
#define USE_HASH_TABLE 1

/*! use the enhanced transposition cutoff heuristic. 1 = on, 0 = off.
  (default = 1) */
#define USE_ENHANCED_TRANSPOSITION_CUTOFF (1 && USE_HASH_TABLE)

/*! play odd square first   1 = on, 0 = off. (default = 1) */
#define PLAY_ODD_SQUARE_FIRST 1

/*! step through the 'smallest' subtree first to find the solution faster.
   1 = on, 0 = off. (default = 1) */
#define PLAY_FAST_SUBTREE_FIRST 1

/*! among equally 'small' subtree choose the one with more stable squares.
   1 = on, 0 = off. (default = 1) */
#define PLAY_STABLEST_SUBTREE (1 && PLAY_FAST_SUBTREE_FIRST)

/*! use the best move stored in the hash table. 1 = on, 0 = off. (default = 1) */
#define PLAY_BEST_MOVE_IN_MEMORY_FIRST (1 && USE_HASH_TABLE)

/*! use presorted squares. 1 = on, 0 = off. (default = 1) */
#define USE_PRESORTED_SQUARES 1

/*! node counter 0 = off. 1 = internal_nodes, 2 = internal_nodes + leave_nodes,
   3 = all. (default = 3, more spectacular!) */
#define COUNT_NODES 3

/* FOLLOWING DATA SHOULD NOT BE CHANGED */
/*! infinite score: a huge value unreachable as a score and fitting in a char */
#define INF_SCORE 127

/*! size of the board */
#define BOARD_SIZE 91

/*! maximal number of moves */
#define MAX_MOVE 32

/*! maximal number of squares flipped + 1 */
#define MAX_FLIP 20

/*! maximal score */
#define MAX_SCORE 64

/*! constants for square coordinates */
enum {
	NOMOVE = 0, PASS,
	A1 = 10, B1, C1, D1, E1, F1, G1, H1,
	A2 = 19, B2, C2, D2, E2, F2, G2, H2,
	A3 = 28, B3, C3, D3, E3, F3, G3, H3,
	A4 = 37, B4, C4, D4, E4, F4, G4, H4,
	A5 = 46, B5, C5, D5, E5, F5, G5, H5,
	A6 = 55, B6, C6, D6, E6, F6, G6, H6,
	A7 = 64, B7, C7, D7, E7, F7, G7, H7,
	A8 = 73, B8, C8, D8, E8, F8, G8, H8
};

/*! flipping directions */
enum {
	NW = -10,
	N  =  -9,
	NE =  -8,
	 W =  -1,
	 E =  +1,
	SW =  +8,
	S  =  +9,
	SE = +10
};

/*! a flipping direction ID for each square */
const int FLIPPING_DIRECTION_ID[BOARD_SIZE] = {
	0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 1, 1, 2, 2, 2, 2, 3, 3,
	0, 1, 1, 2, 2, 2, 2, 3, 3,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 7, 7, 8, 8, 8, 8, 9, 9,
	0, 7, 7, 8, 8, 8, 8, 9, 9,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

/*! a quadrant id for each square */
const int QUADRANT_ID[BOARD_SIZE] = {
	4, 4, 4, 4, 4, 4, 4, 4, 4,
	4, 0, 0, 0, 0, 1, 1, 1, 1,
	4, 0, 0, 0, 0, 1, 1, 1, 1,
	4, 0, 0, 0, 0, 1, 1, 1, 1,
	4, 0, 0, 0, 0, 1, 1, 1, 1,
	4, 2, 2, 2, 2, 3, 3, 3, 3,
	4, 2, 2, 2, 2, 3, 3, 3, 3,
	4, 2, 2, 2, 2, 3, 3, 3, 3,
	4, 2, 2, 2, 2, 3, 3, 3, 3,
	4, 4, 4, 4, 4, 4, 4, 4, 4, 4
};

/*! constants for colors */
enum {
	BLACK = 0,
	WHITE,
	EMPTY,
	OFF_SIDE
};

/*! constants for search mode */
enum {
	EXACT_SCORE,
	WDL_SCORE,
	WD_SCORE,
	DL_SCORE
};

/*! hashing global data */
static unsigned long hash_code_set_disc[BOARD_SIZE][3][2];
static unsigned long hash_code_flip_disc[BOARD_SIZE][2];
static unsigned long hash_code_swap_player[2];

/*! move representation */
typedef struct Move {
	int position[MAX_FLIP];      /*< affected square position */
	int n;                       /*< number of flipped discs */
	int score;                   /*< score for this move */
	unsigned long hash_code[2];  /*< 64 bit hash code */
} Move;

/*! (double linked) list of squares */
typedef struct SquareList {
	int position;                 /*!< square position */
	struct SquareList *previous;  /*!< link to previous square */
	struct SquareList *next;      /*!< link to next square */
} SquareList;

/*! (simple) list of a legal moves */
typedef struct MoveList {
	Move move;                /*!< a legal move */
	struct MoveList *next;    /*!< link to next legal move */
} MoveList;

/*! board representation */
typedef struct Board {
	char square[BOARD_SIZE];           /*!< square content */
	char player;                       /*!< player to move */
	int n_discs[2];                    /*!< disc numbers */
	int n_empties;                     /*!< number of empty squares */
	double n_nodes;                    /*!< node counter */
	unsigned long hash_code[2];        /*!< 64 bit hash code */
	unsigned char parity[4];           /*!< quadrant parity */
	SquareList empties[MAX_SCORE - 2]; /*!< list of empty squares */
	SquareList *position_to_empties[BOARD_SIZE]; /*!< link position to the list */
} Board;

/*! Hash : item stored in the hash table */
typedef struct Hash {
	unsigned long lock;       /*!< hash lock */
	signed char lower;        /*!< lower bound of the position score */
	signed char upper;        /*!< upper bound of the position score */
	unsigned char move;       /*!< best move */
	unsigned char depth;      /*!< depth of the analysis ( = board->n_empties) */
} Hash;

/*! HashEntry: an entry, with two items, of the hash table */
typedef struct HashEntry {
	Hash deepest; /*!< entry for the highest cost search */
	Hash newest;  /*!< entry for the most recent search */
} HashEntry;

/*! HashTable : hash table */
typedef struct HashTable {
	HashEntry *hash_entry;  /*!< array of entry */
	unsigned long hash_mask; /*!< a bit mask */
} HashTable;

#if COUNT_NODES > 0
	/*! node counter for internal nodes */
	#define BOARD_UPDATE_INTERNAL_NODES() board->n_nodes++;
#else
	/*! no node counter for internal nodes */
	#define BOARD_UPDATE_INTERNAL_NODES()
#endif
#if COUNT_NODES > 1
	/*! node counter for terminal nodes (leaves) */
	#define BOARD_UPDATE_TERMINAL_NODES() board->n_nodes++;
	/*! node counter correction for terminal nodes */
	#define BOARD_CORRECT_TERMINAL_NODES() board->n_nodes--;
#else
	/*! no node counter */
	#define BOARD_UPDATE_TERMINAL_NODES()
	/*! node counter correction for terminal nodes */
	#define BOARD_CORRECT_TERMINAL_NODES() board->n_nodes -= 2;
#endif
#if COUNT_NODES > 2
	/*! more general node counter */
	#define BOARD_UPDATE_ALL_NODES() board->n_nodes++
#else
	/*! no general node counter */
	#define BOARD_UPDATE_ALL_NODES()
#endif

/*! macros to check if a move (<= 6 flips) is correct along a direction */
#define BOARD_CHECK_MOVE_6(dir)                         \
	( square[dir] == o &&                               \
	( square[2 * dir] == p || (square[2 * dir] == o &&  \
	( square[3 * dir] == p || (square[3 * dir] == o &&  \
	( square[4 * dir] == p || (square[4 * dir] == o &&  \
	( square[5 * dir] == p || (square[5 * dir] == o &&  \
	( square[6 * dir] == p || (square[6 * dir] == o &&  \
	  square[7 * dir] == p)))))))))))

/*! macros to check if a move (<= 4 flips) is correct along a direction */
#define BOARD_CHECK_MOVE_4(dir)                         \
	( square[dir] == o &&                               \
	( square[2 * dir] == p || (square[2 * dir] == o &&  \
	( square[3 * dir] == p || (square[3 * dir] == o &&  \
	( square[4 * dir] == p || (square[4 * dir] == o &&  \
	  square[5 * dir] == p)))))))

/*! macro to count (at most 6) discs flipped along a direction */
#define BOARD_COUNT_FLIPS_6(dir)                                     \
	if (square[dir] == o) {                                          \
		if (square[2 * dir] == p) n_flips++;                         \
		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) {                     \
						if (square[5 * dir] == p) n_flips += 4;      \
						else if (square[5 * dir] == o) {             \
							if (square[6 * dir] == p) n_flips += 5;  \
							else if (square[6 * dir] == o            \
							 && square[7 * dir] == p) n_flips += 6;  \
	}}}}}

/*! macro to count (at most 4) discs flipped along a direction */
#define BOARD_COUNT_FLIPS_4(dir)                                \
	if (square[dir] == o) {                                     \
		if (square[2 * dir] == p) n_flips++;                    \