WebSVN – Games.Chess Giants – Blame – //engine-senpai/senpai_10.cpp

Rev	Author	Line No.	Line
98	pmbaty	1
		2	/*
		3	Senpai 1.0 Copyright (C) 2014 Fabien Letouzey.
		4
		5	This program is free software: you can redistribute it and/or modify
		6	it under the terms of the GNU General Public License as published by
		7	the Free Software Foundation, either version 3 of the License, or
		8	(at your option) any later version.
		9
		10	This program is distributed in the hope that it will be useful,
		11	but WITHOUT ANY WARRANTY; without even the implied warranty of
		12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		13	GNU General Public License for more details.
		14
		15	You should have received a copy of the GNU General Public License
		16	along with this program. If not, see <http://www.gnu.org/licenses/>.
		17	*/
		18
		19	// macros
		20
		21	#ifndef DEBUG
		22	# ifndef NDEBUG // Pierre-Marie Baty -- protect macro redefinition
		23	# define NDEBUG
		24	# endif // Pierre-Marie Baty -- protect macro redefinition
		25	#endif
		26
		27	// C includes
		28
		29	#include <cassert> // needs NDEBUG
		30	#include <cctype>
		31	#include <cmath>
		32	#include <cstdlib>
		33	#include <ctime>
		34	#ifdef _MSC_VER
		35	#include <algorithm> // Pierre-Marie Baty -- for std::min and std::max
		36	#include <windows.h> // Pierre-Marie Baty -- for ExitProcess()
		37	#undef max // Pierre-Marie Baty -- for std::min and std::max
		38	#undef min // Pierre-Marie Baty -- for std::min and std::max
		39	#endif // _MSC_VER
		40
		41	// C++ includes
		42
		43	#include <fstream>
		44	#include <iostream>
		45	#include <sstream>
		46	#include <string>
		47	#include <vector>
		48
		49	// C++11 includes
		50
		51	#include <chrono>
		52	#include <condition_variable>
		53	#include <mutex>
		54	#include <thread>
		55
		56	// macros
		57
		58	#ifdef _MSC_VER
		59	# define I64(n) (n##i64)
		60	# define U64(u) (u##ui64)
		61	#else
		62	# define I64(n) (n##LL)
		63	# define U64(u) (u##ULL)
		64	#endif
		65
		66	#ifndef __builtin_popcountll // Pierre-Marie Baty -- __builtin_popcountll support for MSVC 32-bit
102	pmbaty	67	int __builtin_popcountll (unsigned long long x) {
		68	static const unsigned long long m1 = 0x5555555555555555; //binary: 0101...
		69	static const unsigned long long m2 = 0x3333333333333333; //binary: 00110011..
		70	static const unsigned long long m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
		71	static const unsigned long long h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
		72	x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
		73	x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
		74	x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
		75	return static_cast<int>((x * h01) >> 56); //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
		76	}
98	pmbaty	77	#endif // Pierre-Marie Baty -- __builtin_popcountll support for MSVC 32-bit
		78
		79	#ifndef __builtin_ctzll // Pierre-Marie Baty -- __builtin_ctzll support for MSVC 32-bit
		80	#include <intrin.h>
102	pmbaty	81	int __builtin_ctzll (unsigned long long x)
		82	{
98	pmbaty	83	// Returns the number of trailing 0-bits in x, starting at the least significant bit position.
		84	// If x is zero, the result is undefined.
		85	// This uses a binary search algorithm from Hacker's Delight.
		86	int n = 1;
		87	if ((x & 0x00000000FFFFFFFF) == 0) { n = n + 32; x = x >> 32; }
		88	if ((x & 0x000000000000FFFF) == 0) { n = n + 16; x = x >> 16; }
		89	if ((x & 0x00000000000000FF) == 0) { n = n + 8; x = x >> 8; }
		90	if ((x & 0x000000000000000F) == 0) { n = n + 4; x = x >> 4; }
		91	if ((x & 0x0000000000000003) == 0) { n = n + 2; x = x >> 2; }
		92	return (n - (x & 1));
		93	}
		94	#endif // Pierre-Marie Baty -- __builtin_ctzll support for MSVC 32-bit
		95
		96	// types
		97
		98	typedef signed char int8;
		99	typedef unsigned char uint8;
		100
		101	typedef signed short int int16;
		102	typedef unsigned short int uint16;
		103
		104	typedef signed int int32;
		105	typedef unsigned int uint32;
		106
		107	typedef signed long long int int64;
		108	typedef unsigned long long int uint64;
		109
		110	typedef uint64 bit_t;
		111	typedef uint64 hash_t; // key_t is used by Unix :(
		112
		113	// modules
		114
		115	namespace util {
		116
		117	class Timer {
		118
		119	private:
		120
		121	typedef std::chrono::time_point<std::chrono::system_clock> time_t;
		122	typedef std::chrono::duration<int, std::ratio<1, 1000>> millisecond_t;
		123
		124	int p_elapsed;
		125	bool p_running;
		126	time_t p_start;
		127
		128	static time_t now() {
		129	return std::chrono::system_clock::now();
		130	}
		131
		132	int time() const {
		133	assert(p_running);
		134	return std::chrono::duration_cast<millisecond_t>(now() - p_start).count();
		135	}
		136
		137	public:
		138
		139	Timer() {
		140	reset();
		141	}
		142
		143	void reset() {
		144	p_elapsed = 0;
		145	p_running = false;
		146	}
		147
		148	void start() {
		149	p_start = now();
		150	p_running = true;
		151	}
		152
		153	void stop() {
		154	p_elapsed += time();
		155	p_running = false;
		156	}
		157
		158	int elapsed() const {
		159	int time = p_elapsed;
		160	if (p_running) time += this->time();
		161	return time;
		162	}
		163
		164	};
		165
		166	class Lockable {
		167
		168	protected: // HACK for Waitable::wait()
		169
		170	mutable std::mutex p_mutex;
		171
		172	public:
		173
		174	void lock () const { p_mutex.lock(); }
		175	void unlock () const { p_mutex.unlock(); }
		176	};
		177
		178	class Waitable : public Lockable {
		179
		180	private:
		181
		182	std::condition_variable_any p_cond;
		183
		184	public:
		185
		186	void wait () { p_cond.wait(p_mutex); } // HACK: direct access
		187	void signal () { p_cond.notify_one(); }
		188	};
		189
		190	int round(double x) {
		191	return int(std::floor(x + 0.5));
		192	}
		193
		194	int div(int a, int b) {
		195
		196	assert(b > 0);
		197
		198	int div = a / b;
		199	if (a < 0 && a != b * div) div--; // fix buggy C semantics
		200
		201	return div;
		202	}
		203
		204	int sqrt(int n) {
		205	return int(std::sqrt(double(n)));
		206	}
		207
		208	bool is_square(int n) {
		209	int i = sqrt(n);
		210	return i * i == n;
		211	}
		212
		213	double rand_float() {
		214	return double(std::rand()) / (double(RAND_MAX) + 1.0);
		215	}
		216
		217	int rand_int(int n) {
		218	assert(n > 0);
		219	return int(rand_float() * double(n));
		220	}
		221
		222	int string_find(const std::string & s, char c) {
		223	return int(s.find(c));
		224	}
		225
		226	bool string_case_equal(const std::string & s0, const std::string & s1) {
		227
		228	if (s0.size() != s1.size()) return false;
		229
		230	for (int i = 0; i < int(s0.size()); i++) {
		231	if (std::tolower(s0[i]) != std::tolower(s1[i])) return false;
		232	}
		233
		234	return true;
		235	}
		236
		237	bool to_bool(const std::string & s) {
		238	if (string_case_equal(s, "true")) {
		239	return true;
		240	} else if (string_case_equal(s, "false")) {
		241	return false;
		242	} else {
		243	std::cerr << "not a boolean: \"" << s << "\"" << std::endl;
		244	std::exit(EXIT_FAILURE);
		245	}
		246	}
		247
		248	int64 to_int(const std::string & s) {
		249	std::stringstream ss(s);
		250	int64 n;
		251	ss >> n;
		252	return n;
		253	}
		254
		255	std::string to_string(int n) {
		256	std::stringstream ss;
		257	ss << n;
		258	return ss.str();
		259	}
		260
		261	std::string to_string(double x) {
		262	std::stringstream ss;
		263	ss << x;
		264	return ss.str();
		265	}
		266
		267	void log(const std::string & s) {
		268	std::ofstream log_file("log.txt", std::ios_base::app);
		269	log_file << s << std::endl;
		270	}
		271
		272	}
		273
		274	namespace input {
		275
		276	class Input : public util::Waitable {
		277
		278	bool volatile p_has_input;
		279	bool p_eof;
		280	std::string p_line;
		281
		282	public:
		283
		284	Input() {
		285	p_has_input = false;
		286	p_eof = false;
		287	}
		288
		289	bool has_input() const {
		290	return p_has_input;
		291	}
		292
		293	bool get_line(std::string & line) {
		294
		295	lock();
		296
		297	while (!p_has_input) {
		298	wait();
		299	}
		300
		301	bool line_ok = !p_eof;
		302	if (line_ok) line = p_line;
		303
		304	p_has_input = false;
		305	signal();
		306
		307	unlock();
		308
		309	return line_ok;
		310	}
		311
		312	void set_eof() {
		313
		314	lock();
		315
		316	while (p_has_input) {
		317	wait();
		318	}
		319
		320	p_eof = true;
		321
		322	p_has_input = true;
		323	signal();
		324
		325	unlock();
		326	}
		327
		328	void set_line(std::string & line) {
		329
		330	lock();
		331
		332	while (p_has_input) {
		333	wait();
		334	}
		335
		336	p_line = line;
		337
		338	p_has_input = true;
		339	signal();
		340
		341	unlock();
		342	}
		343
		344	};
		345
		346	Input input;
		347	std::thread thread;
		348
		349	void input_program(Input * input) {
		350
		351	std::string line;
		352
		353	while (std::getline(std::cin, line)) {
		354	input->set_line(line);
		355	}
		356
		357	input->set_eof();
		358	}
		359
		360	void init() {
		361	thread = std::thread(input_program, &input);
		362	thread.detach();
		363	}
		364
		365	};
		366
		367	namespace side {
		368
		369	const int SIZE = 2;
		370
		371	enum {
		372	WHITE,
		373	BLACK,
		374	};
		375
		376	int opposit(int sd) {
		377	return sd ^ 1;
		378	}
		379
		380	}
		381
		382	namespace square {
		383
		384	const int FILE_SIZE = 8;
		385	const int RANK_SIZE = 8;
		386	const int SIZE = FILE_SIZE * RANK_SIZE;
		387
		388	enum {
		389	FILE_A,
		390	FILE_B,
		391	FILE_C,
		392	FILE_D,
		393	FILE_E,
		394	FILE_F,
		395	FILE_G,
		396	FILE_H,
		397	};
		398
		399	enum {
		400	RANK_1,
		401	RANK_2,
		402	RANK_3,
		403	RANK_4,
		404	RANK_5,
		405	RANK_6,
		406	RANK_7,
		407	RANK_8,
		408	};
		409
		410	enum {
		411	NONE = -1,
		412	A1, A2, A3, A4, A5, A6, A7, A8,
		413	B1, B2, B3, B4, B5, B6, B7, B8,
		414	C1, C2, C3, C4, C5, C6, C7, C8,
		415	D1, D2, D3, D4, D5, D6, D7, D8,
		416	E1, E2, E3, E4, E5, E6, E7, E8,
		417	F1, F2, F3, F4, F5, F6, F7, F8,
		418	G1, G2, G3, G4, G5, G6, G7, G8,
		419	H1, H2, H3, H4, H5, H6, H7, H8,
		420	};
		421
		422	enum {
		423	INC_LEFT = -8,
		424	INC_RIGHT = +8,
		425	};
		426
		427	const int CASTLING_DELTA = 16;
		428	const int DOUBLE_PAWN_DELTA = 2;
		429
		430	int make(int fl, int rk) {
		431
		432	assert(fl < 8);
		433	assert(rk < 8);
		434
		435	return (fl << 3) \| rk;
		436	}
		437
		438	int make(int fl, int rk, int sd) {
		439
		440	assert(fl < 8);
		441	assert(rk < 8);
		442
		443	return make(fl, (rk ^ -sd) & 7);
		444	}
		445
		446	int file(int sq) {
		447	return sq >> 3;
		448	}
		449
		450	int rank(int sq) {
		451	return sq & 7;
		452	}
		453
		454	int rank(int sq, int sd) {
		455	return (sq ^ -sd) & 7;
		456	}
		457
		458	int opposit_file(int sq) {
		459	return sq ^ 070;
		460	}
		461
		462	int opposit_rank(int sq) {
		463	return sq ^ 007;
		464	}
		465
		466	bool is_promotion(int sq) {
		467	int rk = rank(sq);
		468	return rk == RANK_1 \|\| rk == RANK_8;
		469	}
		470
		471	int colour(int sq) {
		472	return ((sq >> 3) ^ sq) & 1;
		473	}
		474
		475	bool same_colour(int s0, int s1) {
		476	int diff = s0 ^ s1;
		477	return (((diff >> 3) ^ diff) & 1) == 0;
		478	}
		479
		480	bool same_line(int s0, int s1) {
		481	return file(s0) == file(s1) \|\| rank(s0) == rank(s1);
		482	}
		483
		484	int file_distance(int s0, int s1) {
		485	return std::abs(file(s1) - file(s0));
		486	}
		487
		488	int rank_distance(int s0, int s1) {
		489	return std::abs(rank(s1) - rank(s0));
		490	}
		491
		492	int distance(int s0, int s1) {
		493	return std::max(file_distance(s0, s1), rank_distance(s0, s1));
		494	}
		495
		496	int pawn_inc(int sd) {
		497	return (sd == side::WHITE) ? +1 : -1;
		498	}
		499
		500	int stop(int sq, int sd) {
		501	return sq + pawn_inc(sd);
		502	}
		503
		504	int promotion(int sq, int sd) {
		505	return make(file(sq), RANK_8, sd);
		506	}
		507
		508	bool is_valid_88(int s88) {
		509	return (s88 & ~0x77) == 0;
		510	}
		511
		512	int to_88(int sq) {
		513	return sq + (sq & 070);
		514	}
		515
		516	int from_88(int s88) {
		517	assert(is_valid_88(s88));
		518	return (s88 + (s88 & 7)) >> 1;
		519	}
		520
		521	int from_fen(int sq) {
		522	return make(sq & 7, (sq >> 3) ^ 7);
		523	}
		524
		525	int from_string(const std::string & s) {
		526	assert(s.length() == 2);
		527	return make(s[0] - 'a', s[1] - '1');
		528	}
		529
		530	std::string to_string(int sq) {
		531
		532	std::string s;
		533	s += 'a' + file(sq);
		534	s += '1' + rank(sq);
		535
		536	return s;
		537	}
		538
		539	}
		540
		541	namespace wing {
		542
		543	const int SIZE = 2;
		544
		545	enum {
		546	KING,
		547	QUEEN,
		548	};
		549
		550	const int shelter_file[SIZE] = { square::FILE_G, square::FILE_B }; // for pawn-shelter eval
		551
		552	}
		553
		554	namespace piece {
		555
		556	const int SIZE = 7;
		557	const int SIDE_SIZE = 12;
		558
		559	enum Piece {
		560	PAWN,
		561	KNIGHT,
		562	BISHOP,
		563	ROOK,
		564	QUEEN,
		565	KING,
		566	NONE,
		567	};
		568
		569	enum Side_Piece {
		570	WHITE_PAWN,
		571	BLACK_PAWN,
		572	WHITE_KNIGHT,
		573	BLACK_KNIGHT,
		574	WHITE_BISHOP,
		575	BLACK_BISHOP,
		576	WHITE_ROOK,
		577	BLACK_ROOK,
		578	WHITE_QUEEN,
		579	BLACK_QUEEN,
		580	WHITE_KING,
		581	BLACK_KING,
		582	};
		583
		584	const int PAWN_VALUE = 100;
		585	const int KNIGHT_VALUE = 325;
		586	const int BISHOP_VALUE = 325;
		587	const int ROOK_VALUE = 500;
		588	const int QUEEN_VALUE = 975;
		589	const int KING_VALUE = 10000; // for SEE
		590
		591	const std::string Char = "PNBRQK?";
		592	const std::string Fen_Char = "PpNnBbRrQqKk";
		593
		594	bool is_minor(int pc) {
		595	assert(pc < SIZE);
		596	return pc == KNIGHT \|\| pc == BISHOP;
		597	}
		598
		599	bool is_major(int pc) {
		600	assert(pc < SIZE);
		601	return pc == ROOK \|\| pc == QUEEN;
		602	}
		603
		604	bool is_slider(int pc) {
		605	assert(pc < SIZE);
		606	return pc >= BISHOP && pc <= QUEEN;
		607	}
		608
		609	int score(int pc) { // for MVV/LVA
		610	assert(pc < SIZE);
		611	assert(pc != NONE);
		612	return pc;
		613	}
		614
		615	int value(int pc) {
		616	assert(pc < SIZE);
		617	static const int value[SIZE] = { PAWN_VALUE, KNIGHT_VALUE, BISHOP_VALUE, ROOK_VALUE, QUEEN_VALUE, KING_VALUE, 0 };
		618	return value[pc];
		619	}
		620
		621	int make(int pc, int sd) {
		622	assert(pc < SIZE);
		623	assert(pc != NONE);
		624	assert(sd < side::SIZE);
		625	return (pc << 1) \| sd;
		626	}
		627
		628	int piece(int p12) {
		629	assert(p12 < SIDE_SIZE);
		630	return p12 >> 1;
		631	}
		632
		633	int side(int p12) {
		634	assert(p12 < SIDE_SIZE);
		635	return p12 & 1;
		636	}
		637
		638	int from_char(char c) {
		639	return util::string_find(Char, c);
		640	}
		641
		642	char to_char(int pc) {
		643	assert(pc < SIZE);
		644	return Char[pc];
		645	}
		646
		647	int from_fen(char c) {
		648	return util::string_find(Fen_Char, c);
		649	}
		650
		651	char to_fen(int p12) {
		652	assert(p12 < SIDE_SIZE);
		653	return Fen_Char[p12];
		654	}
		655
		656	}
		657
		658	namespace move {
		659
		660	const int FLAGS_BITS = 9;
		661	const int FLAGS_SIZE = 1 << FLAGS_BITS;
		662	const int FLAGS_MASK = FLAGS_SIZE - 1;
		663
		664	const int BITS = FLAGS_BITS + 12;
		665	const int SIZE = 1 << BITS;
		666	const int MASK = SIZE - 1;
		667
		668	const int SCORE_BITS = 32 - BITS;
		669	const int SCORE_SIZE = 1 << SCORE_BITS;
		670	const int SCORE_MASK = SCORE_SIZE - 1;
		671
		672	enum Move {
		673	NONE = 0,
		674	NULL_ = 1,
		675	};
		676
		677	int make_flags(int pc, int cp, int pp = piece::NONE) {
		678
		679	assert(pc < piece::SIZE);
		680	assert(cp < piece::SIZE);
		681	assert(pp < piece::SIZE);
		682
		683	return (pc << 6) \| (cp << 3) \| pp;
		684	}
		685
		686	int make(int f, int t, int pc, int cp, int pp = piece::NONE) {
		687
		688	assert(f < square::SIZE);
		689	assert(t < square::SIZE);
		690	assert(pc < piece::SIZE);
		691	assert(cp < piece::SIZE);
		692	assert(pp < piece::SIZE);
		693
		694	assert(pc != piece::NONE);
		695	assert(pp == piece::NONE \|\| pc == piece::PAWN);
		696
		697	return (pc << 18) \| (cp << 15) \| (pp << 12) \| (f << 6) \| t;
		698	}
		699
		700	int from(int mv) {
		701	assert(mv != NONE);
		702	assert(mv != NULL_);
		703	return (mv >> 6) & 077;
		704	}
		705
		706	int to(int mv) {
		707	assert(mv != NONE);
		708	assert(mv != NULL_);
		709	return mv & 077;
		710	}
		711
		712	int piece(int mv) {
		713	assert(mv != NONE);
		714	assert(mv != NULL_);
		715	return (mv >> 18) & 7;
		716	}
		717
		718	int cap(int mv) {
		719	assert(mv != NONE);
		720	assert(mv != NULL_);
		721	return (mv >> 15) & 7;
		722	}
		723
		724	int prom(int mv) {
		725	assert(mv != NONE);
		726	assert(mv != NULL_);
		727	return (mv >> 12) & 7;
		728	}
		729
		730	int flags(int mv) {
		731	assert(mv != NONE);
		732	assert(mv != NULL_);
		733	return (mv >> 12) & 0777;
		734	}
		735
		736	std::string to_can(int mv) {
		737
		738	assert(mv != NONE);
		739
		740	if (mv == NONE) return "0000";
		741	if (mv == NULL_) return "0000";
		742
		743	std::string s;
		744
		745	s += square::to_string(from(mv));
		746	s += square::to_string(to(mv));
		747
		748	if (prom(mv) != piece::NONE) {
		749	s += std::tolower(piece::to_char(prom(mv)));
		750	}
		751
		752	return s;
		753	}
		754
		755	}
		756
		757	namespace bit {
		758
		759	bit_t p_left[8];
		760	bit_t p_right[8];
		761	bit_t p_front[8];
		762	bit_t p_rear[8];
		763
		764	bit_t p_side_front[side::SIZE][8];
		765	bit_t p_side_rear[side::SIZE][8];
		766
		767	bit_t bit(int n) {
		768	assert(n < 64);
		769	return U64(1) << n;
		770	}
		771
		772	void set(bit_t & b, int n) {
		773	b \|= bit(n);
		774	}
		775
		776	void clear(bit_t & b, int n) {
		777	b &= ~bit(n);
		778	}
		779
		780	bool is_set(bit_t b, int n) {
		781	return (b & bit(n)) != 0;
		782	}
		783
		784	int first(bit_t b) {
		785
		786	assert(b != 0);
		787
		788	/*
		789	static const int index[64] = {
		790	0, 1, 2, 7, 3, 13, 8, 19,
		791	4, 25, 14, 28, 9, 34, 20, 40,
		792	5, 17, 26, 38, 15, 46, 29, 48,
		793	10, 31, 35, 54, 21, 50, 41, 57,
		794	63, 6, 12, 18, 24, 27, 33, 39,
		795	16, 37, 45, 47, 30, 53, 49, 56,
		796	62, 11, 23, 32, 36, 44, 52, 55,
		797	61, 22, 43, 51, 60, 42, 59, 58,
		798	};
		799
		800	return index[((b & -b) * U64(0x218A392CD3D5DBF)) >> (64 - 6)];
		801	*/
		802
		803	return __builtin_ctzll(b); // GCC
		804	}
		805
		806	bit_t rest(bit_t b) {
		807	assert(b != 0);
		808	return b & (b - 1);
		809	}
		810
		811	int count(bit_t b) {
		812
		813	/*
		814	b = b - ((b >> 1) & U64(0x5555555555555555));
		815	b = (b & U64(0x3333333333333333)) + ((b >> 2) & U64(0x3333333333333333));
		816	b = (b + (b >> 4)) & U64(0x0F0F0F0F0F0F0F0F);
		817	return (b * U64(0x0101010101010101)) >> 56;
		818	*/
		819
		820	return __builtin_popcountll(b); // GCC
		821	}
		822
		823	int count_loop(bit_t b) {
		824
		825	/*
		826	int n = 0;
		827
		828	for (; b != 0; b = rest(b)) {
		829	n++;
		830	}
		831
		832	return n;
		833	*/
		834
		835	return __builtin_popcountll(b); // GCC
		836	}
		837
		838	bool single(bit_t b) {
		839	assert(b != 0);
		840	return rest(b) == 0;
		841	}
		842
		843	bit_t file(int fl) {
		844	assert(fl < 8);
		845	return U64(0xFF) << (fl * 8);
		846	}
		847
		848	bit_t rank(int rk) {
		849	assert(rk < 8);
		850	return U64(0x0101010101010101) << rk;
		851	}
		852
		853	bit_t files(int fl) {
		854	assert(fl < 8);
		855	bit_t file = bit::file(fl);
		856	return (file << 8) \| file \| (file >> 8);
		857	}
		858
		859	bit_t left(int fl) {
		860	assert(fl < 8);
		861	return p_left[fl];
		862	}
		863
		864	bit_t right(int fl) {
		865	assert(fl < 8);
		866	return p_right[fl];
		867	}
		868
		869	bit_t front(int rk) {
		870	assert(rk < 8);
		871	return p_front[rk];
		872	}
		873
		874	bit_t rear(int rk) {
		875	assert(rk < 8);
		876	return p_rear[rk];
		877	}
		878
		879	bit_t front(int sq, int sd) {
		880	int rk = square::rank(sq);
		881	return p_side_front[sd][rk];
		882	}
		883
		884	bit_t rear(int sq, int sd) {
		885	int rk = square::rank(sq);
		886	return p_side_rear[sd][rk];
		887	}
		888
		889	void init() {
		890
		891	{
		892	bit_t bf = 0;
		893	bit_t br = 0;
		894
		895	for (int i = 0; i < 8; i++) {
		896	p_left[i] = bf;
		897	p_rear[i] = br;
		898	bf \|= file(i);
		899	br \|= rank(i);
		900	}
		901	}
		902
		903	{
		904	bit_t bf = 0;
		905	bit_t br = 0;
		906
		907	for (int i = 7; i >= 0; i--) {
		908	p_right[i] = bf;
		909	p_front[i] = br;
		910	bf \|= file(i);
		911	br \|= rank(i);
		912	}
		913	}
		914
		915	for (int rk = 0; rk < 8; rk++) {
		916	p_side_front[side::WHITE][rk] = front(rk);
		917	p_side_front[side::BLACK][rk] = rear(rk);
		918	p_side_rear [side::WHITE][rk] = rear(rk);
		919	p_side_rear [side::BLACK][rk] = front(rk);
		920	}
		921	}
		922
		923	}
		924
		925	namespace hash {
		926
		927	const int TURN = piece::SIDE_SIZE * square::SIZE;
		928	const int CASTLE = TURN + 1;
		929	const int EN_PASSANT = CASTLE + 4;
		930	const int SIZE = EN_PASSANT + 8;
		931
		932	hash_t p_rand[SIZE];
		933
		934	hash_t rand_64() {
		935
		936	hash_t rand = 0;
		937
		938	for (int i = 0; i < 4; i++) {
		939	rand = (rand << 16) \| util::rand_int(1 << 16);
		940	}
		941
		942	return rand;
		943	}
		944
		945	hash_t rand_key(int index) {
		946	assert(index >= 0 && index < SIZE);
		947	return p_rand[index];
		948	}
		949
		950	hash_t piece_key(int p12, int sq) {
		951	return rand_key(p12 * square::SIZE + sq);
		952	}
		953
		954	hash_t turn_key(int turn) {
		955	return (turn == side::WHITE) ? 0 : rand_key(TURN);
		956	}
		957
		958	hash_t turn_flip() {
		959	return rand_key(TURN);
		960	}
		961
		962	hash_t flag_key(int flag) {
		963	assert(flag < 4);
		964	return rand_key(CASTLE + flag);
		965	}
		966
		967	hash_t en_passant_key(int sq) {
		968	return (sq == square::NONE) ? 0 : rand_key(EN_PASSANT + square::file(sq));
		969	}
		970
		971	int64 index(hash_t key) {
		972	return int64(key);
		973	}
		974
		975	uint32 lock(hash_t key) {
		976	return uint32(key >> 32);
		977	}
		978
		979	void init() {
		980	for (int i = 0; i < SIZE; i++) {
		981	p_rand[i] = rand_64();
		982	}
		983	}
		984
		985	}
		986
		987	namespace castling {
		988
		989	struct Info {
		990	int kf;
		991	int kt;
		992	int rf;
		993	int rt;
		994	};
		995
		996	const Info info[4] = {
		997	{ square::E1, square::G1, square::H1, square::F1 },
		998	{ square::E1, square::C1, square::A1, square::D1 },
		999	{ square::E8, square::G8, square::H8, square::F8 },
		1000	{ square::E8, square::C8, square::A8, square::D8 },
		1001	};
		1002
		1003	int flags_mask[square::SIZE];
		1004	hash_t flags_key[1 << 4];
		1005
		1006	int index(int sd, int wg) {
		1007	return sd * 2 + wg;
		1008	}
		1009
		1010	int side(int index) {
		1011	return index / 2;
		1012	}
		1013
		1014	bool flag(int flags, int index) {
		1015	assert(index < 4);
		1016	return bool((flags >> index) & 1);
		1017	}
		1018
		1019	void set_flag(int & flags, int index) {
		1020	assert(index < 4);
		1021	flags \|= 1 << index;
		1022	}
		1023
		1024	hash_t flags_key_debug(int flags) {
		1025
		1026	hash_t key = 0;
		1027
		1028	for (int index = 0; index < 4; index++) {
		1029	if (flag(flags, index)) {
		1030	key ^= hash::flag_key(index);
		1031	}
		1032	}
		1033
		1034	return key;
		1035	}
		1036
		1037	void init() {
		1038
		1039	for (int sq = 0; sq < square::SIZE; sq++) {
		1040	flags_mask[sq] = 0;
		1041	}
		1042
		1043	set_flag(flags_mask[square::E1], 0);
		1044	set_flag(flags_mask[square::E1], 1);
		1045	set_flag(flags_mask[square::H1], 0);
		1046	set_flag(flags_mask[square::A1], 1);
		1047
		1048	set_flag(flags_mask[square::E8], 2);
		1049	set_flag(flags_mask[square::E8], 3);
		1050	set_flag(flags_mask[square::H8], 2);
		1051	set_flag(flags_mask[square::A8], 3);
		1052
		1053	for (int flags = 0; flags < (1 << 4); flags++) {
		1054	flags_key[flags] = flags_key_debug(flags);
		1055	}
		1056	}
		1057
		1058	}
		1059
		1060	namespace stage {
		1061
		1062	const int SIZE = 2;
		1063
		1064	enum {
		1065	MG,
		1066	EG,
		1067	};
		1068
		1069	}
		1070
		1071	namespace material {
		1072
		1073	const int PAWN_PHASE = 0;
		1074	const int KNIGHT_PHASE = 1;
		1075	const int BISHOP_PHASE = 1;
		1076	const int ROOK_PHASE = 2;
		1077	const int QUEEN_PHASE = 4;
		1078
		1079	const int TOTAL_PHASE = PAWN_PHASE * 16 + KNIGHT_PHASE * 4 + BISHOP_PHASE * 4 + ROOK_PHASE * 4 + QUEEN_PHASE * 2;
		1080
		1081	const int p_phase[piece::SIZE] = { PAWN_PHASE, KNIGHT_PHASE, BISHOP_PHASE, ROOK_PHASE, QUEEN_PHASE, 0, 0 };
		1082
		1083	int phase(int pc) {
		1084	assert(pc < piece::SIZE);
		1085	return p_phase[pc];
		1086	}
		1087
		1088	}
		1089
		1090	namespace board {
		1091
		1092	struct Copy {
		1093	hash_t key;
		1094	hash_t pawn_key;
		1095	int flags;
		1096	int ep_sq;
		1097	int moves;
		1098	int recap;
		1099	int phase;
		1100	};
		1101
		1102	struct Undo {
		1103	Copy copy;
		1104	int move;
		1105	int cap_sq;
		1106	bool castling;
		1107	};
		1108
		1109	const std::string start_fen = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -";
		1110
		1111	class Board {
		1112
		1113	private:
		1114
		1115	static const int SCORE_NONE = -10000; // HACK because "score::NONE" is defined later
		1116
		1117	bit_t p_piece[piece::SIZE];
		1118	bit_t p_side[side::SIZE];
		1119	bit_t p_all;
		1120
		1121	int p_king[side::SIZE];
		1122	int p_count[piece::SIDE_SIZE];
		1123
		1124	int p_square[square::SIZE];
		1125	int p_turn;
		1126	Copy p_copy;
		1127
		1128	int p_root;
		1129	int p_sp;
		1130	Undo p_stack[1024];
		1131
		1132	public:
		1133
		1134	void operator=(const Board & bd) {
		1135
		1136	for (int pc = 0; pc < piece::SIZE; pc++) {
		1137	p_piece[pc] = bd.p_piece[pc];
		1138	}
		1139
		1140	for (int sd = 0; sd < side::SIZE; sd++) {
		1141	p_side[sd] = bd.p_side[sd];
		1142	p_king[sd] = bd.p_king[sd];
		1143	}
		1144
		1145	p_all = bd.p_all;
		1146
		1147	for (int p12 = 0; p12 < piece::SIDE_SIZE; p12++) {
		1148	p_count[p12] = bd.p_count[p12];
		1149	}
		1150
		1151	for (int sq = 0; sq < square::SIZE; sq++) {
		1152	p_square[sq] = bd.p_square[sq];
		1153	}
		1154
		1155	p_turn = bd.p_turn;
		1156	p_copy = bd.p_copy;
		1157
		1158	p_root = bd.p_root;
		1159	p_sp = bd.p_sp;
		1160
		1161	for (int sp = 0; sp < bd.p_sp; sp++) {
		1162	p_stack[sp] = bd.p_stack[sp];
		1163	}
		1164
		1165	assert(moves() == bd.moves());
		1166	}
		1167
		1168	bit_t piece(int pc) const {
		1169	assert(pc < piece::SIZE);
		1170	assert(pc != piece::NONE);
		1171	return p_piece[pc];
		1172	}
		1173
		1174	bit_t piece(int pc, int sd) const {
		1175	assert(pc < piece::SIZE);
		1176	assert(pc != piece::NONE);
		1177	return p_piece[pc] & p_side[sd];
		1178	}
		1179
		1180	int count(int pc, int sd) const {
		1181	assert(pc < piece::SIZE);
		1182	assert(pc != piece::NONE);
		1183	// return bit::count(piece(pc, sd));
		1184	return p_count[piece::make(pc, sd)];
		1185	}
		1186
		1187	bit_t side(int sd) const {
		1188	return p_side[sd];
		1189	}
		1190
		1191	bit_t pieces(int sd) const {
		1192	return p_side[sd] & ~piece(piece::PAWN, sd);
		1193	}
		1194
		1195	bit_t all() const {
		1196	return p_all;
		1197	}
		1198
		1199	bit_t empty() const {
		1200	return ~p_all;
		1201	}
		1202
		1203	int square(int sq) const {
		1204	return p_square[sq];
		1205	}
		1206
		1207	int square_side(int sq) const {
		1208	assert(p_square[sq] != piece::NONE);
		1209	return (p_side[side::BLACK] >> sq) & 1; // HACK: uses Side internals
		1210	}
		1211
		1212	bool square_is(int sq, int pc, int sd) const {
		1213	assert(pc < piece::SIZE);
		1214	assert(pc != piece::NONE);
		1215	return square(sq) == pc && square_side(sq) == sd;
		1216	}
		1217
		1218	int king(int sd) const {
		1219	int sq = p_king[sd];
		1220	assert(sq == bit::first(piece(piece::KING, sd)));
		1221	return sq;
		1222	}
		1223
		1224	int turn() const {
		1225	return p_turn;
		1226	}
		1227
		1228	hash_t key() const {
		1229	hash_t key = p_copy.key;
		1230	key ^= castling::flags_key[p_copy.flags];
		1231	key ^= hash::en_passant_key(p_copy.ep_sq);
		1232	return key;
		1233	}
		1234
		1235	hash_t pawn_key() const {
		1236	return p_copy.pawn_key;
		1237	}
		1238
		1239	hash_t eval_key() const {
		1240	hash_t key = p_copy.key;
		1241	key ^= hash::turn_key(p_turn); // remove incremental STM
		1242	key ^= castling::flags_key[p_copy.flags];
		1243	return key;
		1244	}
		1245
		1246	int flags() const {
		1247	return p_copy.flags;
		1248	}
		1249
		1250	int ep_sq() const {
		1251	return p_copy.ep_sq;
		1252	}
		1253
		1254	int moves() const {
		1255	return p_copy.moves;
		1256	}
		1257
		1258	int recap() const {
		1259	return p_copy.recap;
		1260	}
		1261
		1262	int phase() const {
		1263	return p_copy.phase;
		1264	}
		1265
		1266	int ply() const {
		1267	assert(p_sp >= p_root);
		1268	return p_sp - p_root;
		1269	}
		1270
		1271	int last_move() const {
		1272	return (p_sp == 0) ? move::NONE : p_stack[p_sp - 1].move;
		1273	}
		1274
		1275	bool is_draw() const {
		1276
		1277	if (p_copy.moves > 100) { // TODO: check for mate
		1278	return true;
		1279	}
		1280
		1281	hash_t key = p_copy.key; // HACK: ignores castling flags and e.p. square
		1282
		1283	assert(p_copy.moves <= p_sp);
		1284
		1285	for (int i = 4; i < p_copy.moves; i += 2) {
		1286	if (p_stack[p_sp - i].copy.key == key) {
		1287	return true;
		1288	}
		1289	}
		1290
		1291	return false;
		1292	}
		1293
		1294	void set_root() {
		1295	p_root = p_sp;
		1296	}
		1297
		1298	void clear() {
		1299
		1300	for (int pc = 0; pc < piece::SIZE; pc++) {
		1301	p_piece[pc] = 0;
		1302	}
		1303
		1304	for (int sd = 0; sd < side::SIZE; sd++) {
		1305	p_side[sd] = 0;
		1306	}
		1307
		1308	for (int sq = 0; sq < square::SIZE; sq++) {
		1309	p_square[sq] = piece::NONE;
		1310	}
		1311
		1312	for (int sd = 0; sd < side::SIZE; sd++) {
		1313	p_king[sd] = square::NONE;
		1314	}
		1315
		1316	for (int p12 = 0; p12 < piece::SIDE_SIZE; p12++) {
		1317	p_count[p12] = 0;
		1318	}
		1319
		1320	p_turn = side::WHITE;
		1321
		1322	p_copy.key = 0;
		1323	p_copy.pawn_key = 0;
		1324	p_copy.flags = 0;
		1325	p_copy.ep_sq = square::NONE;
		1326	p_copy.moves = 0;
		1327	p_copy.recap = square::NONE;
		1328	p_copy.phase = 0;
		1329
		1330	p_root = 0;
		1331	p_sp = 0;
		1332	}
		1333
		1334	void clear_square(int pc, int sd, int sq, bool update_copy) {
		1335
		1336	assert(pc < piece::SIZE);
		1337	assert(pc != piece::NONE);
		1338	assert(sq >= 0 && sq < square::SIZE);
		1339
		1340	assert(pc == p_square[sq]);
		1341
		1342	assert(bit::is_set(p_piece[pc], sq));
		1343	bit::clear(p_piece[pc], sq);
		1344
		1345	assert(bit::is_set(p_side[sd], sq));
		1346	bit::clear(p_side[sd], sq);
		1347
		1348	assert(p_square[sq] != piece::NONE);
		1349	p_square[sq] = piece::NONE;
		1350
		1351	int p12 = piece::make(pc, sd);
		1352
		1353	assert(p_count[p12] != 0);
		1354	p_count[p12]--;
		1355
		1356	if (update_copy) {
		1357
		1358	hash_t key = hash::piece_key(p12, sq);
		1359	p_copy.key ^= key;
		1360	if (pc == piece::PAWN) p_copy.pawn_key ^= key;
		1361
		1362	p_copy.phase -= material::phase(pc);
		1363	}
		1364	}
		1365
		1366	void set_square(int pc, int sd, int sq, bool update_copy) {
		1367
		1368	assert(pc < piece::SIZE);
		1369	assert(pc != piece::NONE);
		1370	assert(sq >= 0 && sq < square::SIZE);
		1371
		1372	assert(!bit::is_set(p_piece[pc], sq));
		1373	bit::set(p_piece[pc], sq);
		1374
		1375	assert(!bit::is_set(p_side[sd], sq));
		1376	bit::set(p_side[sd], sq);
		1377
		1378	assert(p_square[sq] == piece::NONE);
		1379	p_square[sq] = pc;
		1380
		1381	if (pc == piece::KING) {
		1382	p_king[sd] = sq;
		1383	}
		1384
		1385	int p12 = piece::make(pc, sd);
		1386
		1387	p_count[p12]++;
		1388
		1389	if (update_copy) {
		1390
		1391	hash_t key = hash::piece_key(p12, sq);
		1392	p_copy.key ^= key;
		1393	if (pc == piece::PAWN) p_copy.pawn_key ^= key;
		1394
		1395	p_copy.phase += material::phase(pc);
		1396	}
		1397	}
		1398
		1399	void move_square(int pc, int sd, int f, int t, bool update_copy) { // TODO
		1400	clear_square(pc, sd, f, update_copy);
		1401	set_square(pc, sd, t, update_copy);
		1402	}
		1403
		1404	void flip_turn() {
		1405	p_turn = side::opposit(p_turn);
		1406	p_copy.key ^= hash::turn_flip();
		1407	}
		1408
		1409	void update() {
		1410
		1411	p_all = p_side[side::WHITE] \| p_side[side::BLACK];
		1412
		1413	#ifdef DEBUG
		1414
		1415	for (int p12 = 0; p12 < piece::SIDE_SIZE; p12++) {
		1416	assert(p_count[p12] == bit::count(piece(piece::piece(p12), piece::side(p12))));
		1417	}
		1418
		1419	assert(p_count[piece::WHITE_KING] == 1);
		1420	assert(p_count[piece::BLACK_KING] == 1);
		1421
		1422	assert((p_piece[piece::PAWN] & bit::rank(square::RANK_1)) == 0);
		1423	assert((p_piece[piece::PAWN] & bit::rank(square::RANK_8)) == 0);
		1424
		1425	for (int sd = 0; sd < side::SIZE; sd++) {
		1426	for (int wg = 0; wg < side::SIZE; wg++) {
		1427	int index = castling::index(sd, wg);
		1428	if (castling::flag(p_copy.flags, index)) {
		1429	assert(square_is(castling::info[index].kf, piece::KING, sd));
		1430	assert(square_is(castling::info[index].rf, piece::ROOK, sd));
		1431	}
		1432	}
		1433	}
		1434
		1435	#endif
		1436
		1437	}
		1438
		1439	bool can_castle(int index) const {
		1440
		1441	int sd = castling::side(index);
		1442
		1443	return square_is(castling::info[index].kf, piece::KING, sd)
		1444	&& square_is(castling::info[index].rf, piece::ROOK, sd);
		1445	}
		1446
		1447	bool pawn_is_attacked(int sq, int sd) const {
		1448
		1449	int fl = square::file(sq);
		1450	sq -= square::pawn_inc(sd);
		1451
		1452	return (fl != square::FILE_A && square_is(sq + square::INC_LEFT, piece::PAWN, sd))
		1453	\|\| (fl != square::FILE_H && square_is(sq + square::INC_RIGHT, piece::PAWN, sd));
		1454	}
		1455
		1456	void init_fen(const std::string & s) {
		1457
		1458	clear();
		1459
		1460	int pos = 0;
		1461
		1462	// piece placement
		1463
		1464	int sq = 0;
		1465
		1466	while (pos < int(s.size())) {
		1467
		1468	assert(sq <= square::SIZE);
		1469
		1470	char c = s[pos++];
		1471
		1472	if (false) {
		1473
		1474	} else if (c == ' ') {
		1475
		1476	break;
		1477
		1478	} else if (c == '/') {
		1479
		1480	continue;
		1481
		1482	} else if (std::isdigit(c)) {
		1483
		1484	sq += c - '0';
		1485
		1486	} else { // assume piece
		1487
		1488	int p12 = piece::from_fen(c);
		1489	int pc = piece::piece(p12);
		1490	int sd = piece::side(p12);
		1491	set_square(pc, sd, square::from_fen(sq), true);
		1492	sq++;
		1493	}
		1494	}
		1495
		1496	assert(sq == square::SIZE);
		1497
		1498	// turn
		1499
		1500	p_turn = side::WHITE;
		1501
		1502	if (pos < int(s.size())) {
		1503
		1504	p_turn = util::string_find("wb", s[pos++]);
		1505
		1506	if (pos < int(s.size())) {
		1507	assert(s[pos] == ' ');
		1508	pos++;
		1509	}
		1510	}
		1511
		1512	p_copy.key ^= hash::turn_key(p_turn);
		1513
		1514	// castling flags
		1515
		1516	p_copy.flags = 0;
		1517
		1518	if (pos < int(s.size())) { // read from FEN
		1519
		1520	while (pos < int(s.size())) {
		1521
		1522	char c = s[pos++];
		1523	if (c == ' ') break;
		1524	if (c == '-') continue;
		1525
		1526	int index = util::string_find("KQkq", c);
		1527
		1528	if (can_castle(index)) {
		1529	castling::set_flag(p_copy.flags, index);
		1530	}
		1531	}
		1532
		1533	} else { // guess from position
		1534
		1535	for (int index = 0; index < 4; index++) {
		1536	if (can_castle(index)) {
		1537	castling::set_flag(p_copy.flags, index);
		1538	}
		1539	}
		1540	}
		1541
		1542	// en-passant square
		1543
		1544	p_copy.ep_sq = square::NONE;
		1545
		1546	if (pos < int(s.size())) { // read from FEN
		1547
		1548	std::string ep_string;
		1549
		1550	while (pos < int(s.size())) {
		1551
		1552	char c = s[pos++];
		1553	if (c == ' ') break;
		1554
		1555	ep_string += c;
		1556	}
		1557
		1558	if (ep_string != "-") {
		1559
		1560	int sq = square::from_string(ep_string);
		1561
		1562	if (pawn_is_attacked(sq, p_turn)) {
		1563	p_copy.ep_sq = sq;
		1564	}
		1565	}
		1566	}
		1567
		1568	update();
		1569	}
		1570
		1571	void move(int mv) {
		1572
		1573	assert(mv != move::NONE);
		1574	assert(mv != move::NULL_);
		1575
		1576	int sd = p_turn;
		1577	int xd = side::opposit(sd);
		1578
		1579	int f = move::from(mv);
		1580	int t = move::to(mv);
		1581
		1582	int pc = move::piece(mv);
		1583	int cp = move::cap(mv);
		1584	int pp = move::prom(mv);
		1585
		1586	assert(p_square[f] == pc);
		1587	assert(square_side(f) == sd);
		1588
		1589	assert(p_sp < 1024);
		1590	Undo & undo = p_stack[p_sp++];
		1591
		1592	undo.copy = p_copy;
		1593	undo.move = mv;
		1594	undo.castling = false;
		1595
		1596	p_copy.moves++;
		1597	p_copy.recap = square::NONE;
		1598
		1599	// capture
		1600
		1601	assert(cp != piece::KING);
		1602
		1603	if (pc == piece::PAWN && t == p_copy.ep_sq) {
		1604
		1605	int cap_sq = t - square::pawn_inc(sd);
		1606	assert(p_square[cap_sq] == cp);
		1607	assert(cp == piece::PAWN);
		1608
		1609	undo.cap_sq = cap_sq;
		1610
		1611	clear_square(cp, xd, cap_sq, true);
		1612
		1613	} else if (cp != piece::NONE) {
		1614
		1615	assert(p_square[t] == cp);
		1616	assert(square_side(t) == xd);
		1617
		1618	undo.cap_sq = t;
		1619
		1620	clear_square(cp, xd, t, true);
		1621
		1622	} else {
		1623
		1624	assert(p_square[t] == cp);
		1625	}
		1626
		1627	// promotion
		1628
		1629	if (pp != piece::NONE) {
		1630	assert(pc == piece::PAWN);
		1631	clear_square(piece::PAWN, sd, f, true);
		1632	set_square(pp, sd, t, true);
		1633	} else {
		1634	move_square(pc, sd, f, t, true);
		1635	}
		1636
		1637	// castling rook
		1638
		1639	if (pc == piece::KING && std::abs(t - f) == square::CASTLING_DELTA) {
		1640
		1641	undo.castling = true;
		1642
		1643	int wg = (t > f) ? wing::KING : wing::QUEEN;
		1644	int index = castling::index(sd, wg);
		1645
		1646	assert(castling::flag(p_copy.flags, index));
		1647
		1648	assert(f == castling::info[index].kf);
		1649	assert(t == castling::info[index].kt);
		1650
		1651	move_square(piece::ROOK, sd, castling::info[index].rf, castling::info[index].rt, true);
		1652	}
		1653
		1654	// turn
		1655
		1656	flip_turn();
		1657
		1658	// castling flags
		1659
		1660	p_copy.flags &= ~castling::flags_mask[f];
		1661	p_copy.flags &= ~castling::flags_mask[t];
		1662
		1663	// en-passant square
		1664
		1665	p_copy.ep_sq = square::NONE;
		1666
		1667	if (pc == piece::PAWN && std::abs(t - f) == square::DOUBLE_PAWN_DELTA) {
		1668	int sq = (f + t) / 2;
		1669	if (pawn_is_attacked(sq, xd)) {
		1670	p_copy.ep_sq = sq;
		1671	}
		1672	}
		1673
		1674	// move counter
		1675
		1676	if (cp != piece::NONE \|\| pc == piece::PAWN) {
		1677	p_copy.moves = 0; // conversion;
		1678	}
		1679
		1680	// recapture
		1681
		1682	if (cp != piece::NONE \|\| pp != piece::NONE) {
		1683	p_copy.recap = t;
		1684	}
		1685
		1686	update();
		1687	}
		1688
		1689	void undo() {
		1690
		1691	assert(p_sp > 0);
		1692	const Undo & undo = p_stack[--p_sp];
		1693
		1694	int mv = undo.move;
		1695
		1696	int f = move::from(mv);
		1697	int t = move::to(mv);
		1698
		1699	int pc = move::piece(mv);
		1700	int cp = move::cap(mv);
		1701	int pp = move::prom(mv);
		1702
		1703	int xd = p_turn;
		1704	int sd = side::opposit(xd);
		1705
		1706	assert(p_square[t] == pc \|\| p_square[t] == pp);
		1707	assert(square_side(t) == sd);
		1708
		1709	// castling rook
		1710
		1711	if (undo.castling) {
		1712
		1713	int wg = (t > f) ? wing::KING : wing::QUEEN;
		1714	int index = castling::index(sd, wg);
		1715
		1716	assert(f == castling::info[index].kf);
		1717	assert(t == castling::info[index].kt);
		1718
		1719	move_square(piece::ROOK, sd, castling::info[index].rt, castling::info[index].rf, false);
		1720	}
		1721
		1722	// promotion
		1723
		1724	if (pp != piece::NONE) {
		1725	assert(pc == piece::PAWN);
		1726	clear_square(pp, sd, t, false);
		1727	set_square(piece::PAWN, sd, f, false);
		1728	} else {
		1729	move_square(pc, sd, t, f, false);
		1730	}
		1731
		1732	// capture
		1733
		1734	if (cp != piece::NONE) {
		1735	set_square(cp, xd, undo.cap_sq, false);
		1736	}
		1737
		1738	flip_turn();
		1739	p_copy = undo.copy;
		1740
		1741	update();
		1742	}
		1743
		1744	void move_null() {
		1745
		1746	assert(p_sp < 1024);
		1747	Undo & undo = p_stack[p_sp++];
		1748
		1749	undo.move = move::NULL_;
		1750
		1751	undo.copy = p_copy;
		1752
		1753	flip_turn();
		1754	p_copy.ep_sq = square::NONE;
		1755	p_copy.moves = 0; // HACK: conversion
		1756	p_copy.recap = square::NONE;
		1757
		1758	update();
		1759	}
		1760
		1761	void undo_null() {
		1762
		1763	assert(p_sp > 0);
		1764	const Undo & undo = p_stack[--p_sp];
		1765
		1766	assert(undo.move == move::NULL_);
		1767
		1768	flip_turn();
		1769	p_copy = undo.copy;
		1770
		1771	update();
		1772	}
		1773
		1774	};
		1775
		1776	}
		1777
		1778	namespace attack {
		1779
		1780	struct Attacks {
		1781	int size;
		1782	int square[2];
		1783	bit_t avoid;
		1784	bit_t pinned;
		1785	};
		1786
		1787	const int Pawn_Move[side::SIZE] = { +1, -1 };
		1788	const int Pawn_Attack[side::SIZE][2] = { { -15, +17 }, { -17, +15 } };
		1789
		1790	const int Knight_Inc[] = { -33, -31, -18, -14, +14, +18, +31, +33, 0 };
		1791	const int Bishop_Inc[] = { -17, -15, +15, +17, 0 };
		1792	const int Rook_Inc[] = { -16, -1, +1, +16, 0 };
		1793	const int Queen_Inc[] = { -17, -16, -15, -1, +1, +15, +16, +17, 0 };
		1794
		1795	const int * Piece_Inc[piece::SIZE] = { NULL, Knight_Inc, Bishop_Inc, Rook_Inc, Queen_Inc, Queen_Inc, NULL };
		1796
		1797	bit_t Pawn_Moves[side::SIZE][square::SIZE];
		1798	bit_t Pawn_Attacks[side::SIZE][square::SIZE];
		1799	bit_t Piece_Attacks[piece::SIZE][square::SIZE];
		1800	bit_t Blockers[piece::SIZE][square::SIZE];
		1801
		1802	bit_t Between[square::SIZE][square::SIZE];
		1803	bit_t Behind[square::SIZE][square::SIZE];
		1804
		1805	bool line_is_empty(int f, int t, const board::Board & bd) {
		1806	return (bd.all() & Between[f][t]) == 0;
		1807	}
		1808
		1809	bit_t ray(int f, int t) {
		1810	return Between[f][t] \| Behind[f][t]; // HACK: t should be included
		1811	}
		1812
		1813	bool pawn_move(int sd, int f, int t, const board::Board & bd) {
		1814	assert(sd < side::SIZE);
		1815	return bit::is_set(Pawn_Moves[sd][f], t) && line_is_empty(f, t, bd);
		1816	}
		1817
		1818	bool pawn_attack(int sd, int f, int t) {
		1819	assert(sd < side::SIZE);
		1820	return bit::is_set(Pawn_Attacks[sd][f], t);
		1821	}
		1822
		1823	bool piece_attack(int pc, int f, int t, const board::Board & bd) {
		1824	assert(pc != piece::PAWN);
		1825	return bit::is_set(Piece_Attacks[pc][f], t) && line_is_empty(f, t, bd);
		1826	}
		1827
		1828	bool attack(int pc, int sd, int f, int t, const board::Board & bd) {
		1829	assert(sd < side::SIZE);
		1830	if (pc == piece::PAWN) {
		1831	return pawn_attack(sd, f, t);
		1832	} else {
		1833	return piece_attack(pc, f, t, bd);
		1834	}
		1835	}
		1836
		1837	bit_t pawn_moves_from(int sd, const board::Board & bd) { // for pawn mobility
		1838
		1839	assert(sd < side::SIZE);
		1840
		1841	bit_t fs = bd.piece(piece::PAWN, sd);
		1842
		1843	if (sd == side::WHITE) {
		1844	return fs << 1;
		1845	} else {
		1846	return fs >> 1;
		1847	}
		1848	}
		1849
		1850	bit_t pawn_moves_to(int sd, bit_t ts, const board::Board & bd) {
		1851
		1852	assert(sd < side::SIZE);
		1853	assert((bd.all() & ts) == 0);
		1854
		1855	bit_t pawns = bd.piece(piece::PAWN, sd);
		1856	bit_t empty = bd.empty();
		1857
		1858	bit_t fs = 0;
		1859
		1860	if (sd == side::WHITE) {
		1861	fs \|= (ts >> 1);
		1862	fs \|= (ts >> 2) & (empty >> 1) & bit::rank(square::RANK_2);
		1863	} else {
		1864	fs \|= (ts << 1);
		1865	fs \|= (ts << 2) & (empty << 1) & bit::rank(square::RANK_7);
		1866	}
		1867
		1868	return pawns & fs;
		1869	}
		1870
		1871	bit_t pawn_attacks_from(int sd, const board::Board & bd) {
		1872
		1873	assert(sd < side::SIZE);
		1874
		1875	bit_t fs = bd.piece(piece::PAWN, sd);
		1876
		1877	if (sd == side::WHITE) {
		1878	return (fs >> 7) \| (fs << 9);
		1879	} else {
		1880	return (fs >> 9) \| (fs << 7);
		1881	}
		1882	}
		1883
		1884	bit_t pawn_attacks_tos(int sd, bit_t ts) {
		1885
		1886	assert(sd < side::SIZE);
		1887
		1888	if (sd == side::WHITE) {
		1889	return (ts >> 9) \| (ts << 7);
		1890	} else {
		1891	return (ts >> 7) \| (ts << 9);
		1892	}
		1893	}
		1894
		1895	bit_t pawn_attacks_from(int sd, int f) {
		1896	assert(sd < side::SIZE);
		1897	return Pawn_Attacks[sd][f];
		1898	}
		1899
		1900	bit_t pawn_attacks_to(int sd, int t) {
		1901	assert(sd < side::SIZE);
		1902	return pawn_attacks_from(side::opposit(sd), t);
		1903	}
		1904
		1905	bit_t piece_attacks_from(int pc, int f, const board::Board & bd) {
		1906
		1907	assert(pc != piece::PAWN);
		1908
		1909	bit_t ts = Piece_Attacks[pc][f];
		1910
		1911	for (bit_t b = bd.all() & Blockers[pc][f]; b != 0; b = bit::rest(b)) {
		1912	int sq = bit::first(b);
		1913	ts &= ~Behind[f][sq];
		1914	}
		1915
		1916	return ts;
		1917	}
		1918
		1919	bit_t piece_attacks_to(int pc, int t, const board::Board & bd) {
		1920	assert(pc != piece::PAWN);
		1921	return piece_attacks_from(pc, t, bd);
		1922	}
		1923
		1924	bit_t piece_moves_from(int pc, int sd, int f, const board::Board & bd) {
		1925	if (pc == piece::PAWN) {
		1926	assert(false); // TODO: blockers
		1927	return Pawn_Moves[sd][f];
		1928	} else {
		1929	return piece_attacks_from(pc, f, bd);
		1930	}
		1931	}
		1932
		1933	bit_t attacks_from(int pc, int sd, int f, const board::Board & bd) {
		1934	if (pc == piece::PAWN) {
		1935	return Pawn_Attacks[sd][f];
		1936	} else {
		1937	return piece_attacks_from(pc, f, bd);
		1938	}
		1939	}
		1940
		1941	bit_t attacks_to(int pc, int sd, int t, const board::Board & bd) {
		1942	return attacks_from(pc, side::opposit(sd), t, bd); // HACK for pawns
		1943	}
		1944
		1945	bit_t pseudo_attacks_from(int pc, int sd, int f) {
		1946	if (pc == piece::PAWN) {
		1947	return Pawn_Attacks[sd][f];
		1948	} else {
		1949	return Piece_Attacks[pc][f];
		1950	}
		1951	}
		1952
		1953	bit_t pseudo_attacks_to(int pc, int sd, int t) {
		1954	return pseudo_attacks_from(pc, side::opposit(sd), t); // HACK for pawns
		1955	}
		1956
		1957	bit_t slider_pseudo_attacks_to(int sd, int t, const board::Board & bd) {
		1958
		1959	assert(sd < side::SIZE);
		1960
		1961	bit_t b = 0;
		1962	b \|= bd.piece(piece::BISHOP, sd) & Piece_Attacks[piece::BISHOP][t];
		1963	b \|= bd.piece(piece::ROOK, sd) & Piece_Attacks[piece::ROOK][t];
		1964	b \|= bd.piece(piece::QUEEN, sd) & Piece_Attacks[piece::QUEEN][t];
		1965
		1966	return b;
		1967	}
		1968
		1969	bool attack_behind(int f, int t, int sd, const board::Board & bd) {
		1970
		1971	assert(bd.square(t) != piece::NONE);
		1972
		1973	bit_t behind = Behind[f][t];
		1974	if (behind == 0) return false;
		1975
		1976	for (bit_t b = slider_pseudo_attacks_to(sd, t, bd) & behind; b != 0; b = bit::rest(b)) {
		1977
		1978	int sq = bit::first(b);
		1979
		1980	if (bit::single(bd.all() & Between[sq][f])) {
		1981	return true;
		1982	}
		1983	}
		1984
		1985	return false;
		1986	}
		1987
		1988	bool is_attacked(int t, int sd, const board::Board & bd) {
		1989
		1990	// non-sliders
		1991
		1992	if ((bd.piece(piece::PAWN, sd) & Pawn_Attacks[side::opposit(sd)][t]) != 0) { // HACK
		1993	return true;
		1994	}
		1995
		1996	if ((bd.piece(piece::KNIGHT, sd) & Piece_Attacks[piece::KNIGHT][t]) != 0) {
		1997	return true;
		1998	}
		1999
		2000	if ((bd.piece(piece::KING, sd) & Piece_Attacks[piece::KING][t]) != 0) {
		2001	return true;
		2002	}
		2003
		2004	// sliders
		2005
		2006	for (bit_t b = slider_pseudo_attacks_to(sd, t, bd); b != 0; b = bit::rest(b)) {
		2007
		2008	int f = bit::first(b);
		2009
		2010	if ((bd.all() & Between[f][t]) == 0) {
		2011	return true;
		2012	}
		2013	}
		2014
		2015	return false;
		2016	}
		2017
		2018	bit_t pinned_by(int t, int sd, const board::Board & bd) {
		2019
		2020	bit_t pinned = 0;
		2021
		2022	for (bit_t b = slider_pseudo_attacks_to(sd, t, bd); b != 0; b = bit::rest(b)) {
		2023
		2024	int f = bit::first(b);
		2025
		2026	bit_t bb = bd.all() & Between[f][t];
		2027
		2028	if (bb != 0 && bit::single(bb)) {
		2029	pinned \|= bb;
		2030	}
		2031	}
		2032
		2033	return pinned;
		2034	}
		2035
		2036	void init_attacks(Attacks & attacks, int sd, const board::Board & bd) { // for strictly-legal moves
		2037
		2038	int atk = side::opposit(sd);
		2039	int def = sd;
		2040
		2041	int t = bd.king(def);
		2042
		2043	attacks.size = 0;
		2044	attacks.avoid = 0;
		2045	attacks.pinned = 0;
		2046
		2047	// non-sliders
		2048
		2049	{
		2050	bit_t b = 0;
		2051	b \|= bd.piece(piece::PAWN, atk) & Pawn_Attacks[def][t]; // HACK
		2052	b \|= bd.piece(piece::KNIGHT, atk) & Piece_Attacks[piece::KNIGHT][t];
		2053
		2054	if (b != 0) {
		2055	assert(bit::single(b));
		2056	assert(attacks.size < 2);
		2057	attacks.square[attacks.size++] = bit::first(b);
		2058	}
		2059	}
		2060
		2061	// sliders
		2062
		2063	for (bit_t b = slider_pseudo_attacks_to(atk, t, bd); b != 0; b = bit::rest(b)) {
		2064
		2065	int f = bit::first(b);
		2066
		2067	bit_t bb = bd.all() & Between[f][t];
		2068
		2069	if (bb == 0) {
		2070	assert(attacks.size < 2);
		2071	attacks.square[attacks.size++] = f;
		2072	attacks.avoid \|= ray(f, t);
		2073	} else if (bit::single(bb)) {
		2074	attacks.pinned \|= bb;
		2075	}
		2076	}
		2077	}
		2078
		2079	void init_attacks(Attacks & attacks, const board::Board & bd) {
		2080	init_attacks(attacks, bd.turn(), bd);
		2081	}
		2082
		2083	bool is_legal(const board::Board & bd) {
		2084
		2085	int atk = bd.turn();
		2086	int def = side::opposit(atk);
		2087
		2088	return !is_attacked(bd.king(def), atk, bd);
		2089	}
		2090
		2091	bool is_in_check(const board::Board & bd) {
		2092
		2093	int atk = bd.turn();
		2094	int def = side::opposit(atk);
		2095
		2096	return is_attacked(bd.king(atk), def, bd);
		2097	}
		2098
		2099	bit_t pawn_moves_debug(int sd, int sq) {
		2100
		2101	assert(sd < side::SIZE);
		2102
		2103	bit_t b = 0;
		2104
		2105	int f = square::to_88(sq);
		2106	int inc = Pawn_Move[sd];
		2107
		2108	int t = f + inc;
		2109
		2110	if (square::is_valid_88(t)) {
		2111	bit::set(b, square::from_88(t));
		2112	}
		2113
		2114	if (square::rank(sq, sd) == square::RANK_2) {
		2115	t += inc;
		2116	assert(square::is_valid_88(t));
		2117	bit::set(b, square::from_88(t));
		2118	}
		2119
		2120	return b;
		2121	}
		2122
		2123	bit_t pawn_attacks_debug(int sd, int sq) {
		2124
		2125	assert(sd < side::SIZE);
		2126
		2127	bit_t b = 0;
		2128
		2129	int f = square::to_88(sq);
		2130
		2131	for (int dir = 0; dir < 2; dir++) {
		2132	int t = f + Pawn_Attack[sd][dir];
		2133	if (square::is_valid_88(t)) {
		2134	bit::set(b, square::from_88(t));
		2135	}
		2136	}
		2137
		2138	return b;
		2139	}
		2140
		2141	bit_t piece_attacks_debug(int pc, int sq) {
		2142
		2143	assert(pc != piece::PAWN);
		2144
		2145	bit_t b = 0;
		2146
		2147	int f = square::to_88(sq);
		2148
		2149	for (int dir = 0; true; dir++) {
		2150
		2151	int inc = Piece_Inc[pc][dir];
		2152	if (inc == 0) break;
		2153
		2154	if (piece::is_slider(pc)) {
		2155
		2156	for (int t = f + inc; square::is_valid_88(t); t += inc) {
		2157	bit::set(b, square::from_88(t));
		2158	}
		2159
		2160	} else {
		2161
		2162	int t = f + inc;
		2163
		2164	if (square::is_valid_88(t)) {
		2165	bit::set(b, square::from_88(t));
		2166	}
		2167	}
		2168	}
		2169
		2170	return b;
		2171	}
		2172
		2173	int delta_inc(int f, int t) {
		2174
		2175	for (int dir = 0; dir < 8; dir++) {
		2176
		2177	int inc = Queen_Inc[dir];
		2178
		2179	for (int sq = f + inc; square::is_valid_88(sq); sq += inc) {
		2180	if (sq == t) {
		2181	return inc;
		2182	}
		2183	}
		2184	}
		2185
		2186	return 0;
		2187	}
		2188
		2189	bit_t between_debug(int f, int t) {
		2190
		2191	f = square::to_88(f);
		2192	t = square::to_88(t);
		2193
		2194	bit_t b = 0;
		2195
		2196	int inc = delta_inc(f, t);
		2197
		2198	if (inc != 0) {
		2199	for (int sq = f + inc; sq != t; sq += inc) {
		2200	bit::set(b, square::from_88(sq));
		2201	}
		2202	}
		2203
		2204	return b;
		2205	}
		2206
		2207	bit_t behind_debug(int f, int t) {
		2208
		2209	f = square::to_88(f);
		2210	t = square::to_88(t);
		2211
		2212	bit_t b = 0;
		2213
		2214	int inc = delta_inc(f, t);
		2215
		2216	if (inc != 0) {
		2217	for (int sq = t + inc; square::is_valid_88(sq); sq += inc) {
		2218	bit::set(b, square::from_88(sq));
		2219	}
		2220	}
		2221
		2222	return b;
		2223	}
		2224
		2225	bit_t blockers_debug(int pc, int f) {
		2226
		2227	assert(pc != piece::PAWN);
		2228
		2229	bit_t b = 0;
		2230
		2231	bit_t attacks = piece_attacks_debug(pc, f);
		2232
		2233	for (bit_t bb = attacks; bb != 0; bb = bit::rest(bb)) {
		2234	int sq = bit::first(bb);
		2235	if ((attacks & behind_debug(f, sq)) != 0) {
		2236	bit::set(b, sq);
		2237	}
		2238	}
		2239
		2240	return b;
		2241	}
		2242
		2243	void init() {
		2244
		2245	for (int sd = 0; sd < side::SIZE; sd++) {
		2246	for (int sq = 0; sq < square::SIZE; sq++) {
		2247	Pawn_Moves[sd][sq] = pawn_moves_debug(sd, sq);
		2248	Pawn_Attacks[sd][sq] = pawn_attacks_debug(sd, sq);
		2249	}
		2250	}
		2251
		2252	for (int pc = piece::KNIGHT; pc <= piece::KING; pc++) {
		2253	for (int sq = 0; sq < square::SIZE; sq++) {
		2254	Piece_Attacks[pc][sq] = piece_attacks_debug(pc, sq);
		2255	Blockers[pc][sq] = blockers_debug(pc, sq);
		2256	}
		2257	}
		2258
		2259	for (int f = 0; f < square::SIZE; f++) {
		2260	for (int t = 0; t < square::SIZE; t++) {
		2261	Between[f][t] = between_debug(f, t);
		2262	Behind[f][t] = behind_debug(f, t);
		2263	}
		2264	}
		2265	}
		2266
		2267	}
		2268
		2269	namespace gen {
		2270
		2271	class List {
		2272
		2273	private:
		2274
		2275	static const int SIZE = 256;
		2276
		2277	int p_size;
		2278	uint32 p_pair[SIZE];
		2279
		2280	void move_to(int pf, int pt) {
		2281
		2282	assert(pt <= pf && pf < p_size);
		2283
		2284	uint32 p = p_pair[pf];
		2285
		2286	for (int i = pf; i > pt; i--) {
		2287	p_pair[i] = p_pair[i - 1];
		2288	}
		2289
		2290	p_pair[pt] = p;
		2291	}
		2292
		2293	void add_pair(uint32 p) {
		2294	assert(p_size < SIZE);
		2295	p_pair[p_size++] = p;
		2296	}
		2297
		2298	uint32 pair(int pos) const {
		2299	assert(pos < p_size);
		2300	return p_pair[pos];
		2301	}
		2302
		2303	public:
		2304
		2305	List() {
		2306	clear();
		2307	}
		2308
		2309	void operator=(const List & ml) {
		2310
		2311	clear();
		2312
		2313	for (int pos = 0; pos < ml.size(); pos++) {
		2314	uint32 p = ml.pair(pos);
		2315	add_pair(p);
		2316	}
		2317	}
		2318
		2319	void clear() {
		2320	p_size = 0;
		2321	}
		2322
		2323	void add(int mv, int sc = 0) {
		2324	assert(mv >= 0 && mv < move::SIZE);
		2325	assert(sc >= 0 && sc < move::SCORE_SIZE);
		2326	assert(!contain(mv));
		2327	add_pair((sc << move::BITS) \| mv);
		2328	}
		2329
		2330	void set_score(int pos, int sc) {
		2331	assert(pos < p_size);
		2332	assert(sc >= 0 && sc < move::SCORE_SIZE);
		2333	p_pair[pos] = (sc << move::BITS) \| move(pos);
		2334	assert(score(pos) == sc);
		2335	}
		2336
		2337	void move_to_front(int pos) {
		2338	move_to(pos, 0);
		2339	}
		2340
		2341	void sort() { // insertion sort
		2342
		2343	for (int i = 1; i < p_size; i++) {
		2344
		2345	uint32 p = p_pair[i];
		2346
		2347	int j;
		2348
		2349	for (j = i; j > 0 && p_pair[j - 1] < p; j--) {
		2350	p_pair[j] = p_pair[j - 1];
		2351	}
		2352
		2353	p_pair[j] = p;
		2354	}
		2355
		2356	for (int i = 0; i < p_size - 1; i++) {
		2357	assert(p_pair[i] >= p_pair[i + 1]);
		2358	}
		2359	}
		2360
		2361	int size() const {
		2362	return p_size;
		2363	}
		2364
		2365	int move(int pos) const {
		2366	return pair(pos) & move::MASK;
		2367	}
		2368
		2369	int score(int pos) const {
		2370	return pair(pos) >> move::BITS;
		2371	}
		2372
		2373	bool contain(int mv) const {
		2374
		2375	for (int pos = 0; pos < size(); pos++) {
		2376	if (move(pos) == mv) {
		2377	return true;
		2378	}
		2379	}
		2380
		2381	return false;
		2382	}
		2383
		2384	};
		2385
		2386	void add_pawn_move(List & ml, int f, int t, const board::Board & bd) {
		2387
		2388	assert(bd.square(f) == piece::PAWN);
		2389
		2390	int pc = bd.square(f);
		2391	int cp = bd.square(t);
		2392
		2393	if (square::is_promotion(t)) {
		2394	ml.add(move::make(f, t, pc, cp, piece::QUEEN));
		2395	ml.add(move::make(f, t, pc, cp, piece::KNIGHT));
		2396	ml.add(move::make(f, t, pc, cp, piece::ROOK));
		2397	ml.add(move::make(f, t, pc, cp, piece::BISHOP));
		2398	} else {
		2399	ml.add(move::make(f, t, pc, cp));
		2400	}
		2401	}
		2402
		2403	void add_piece_move(List & ml, int f, int t, const board::Board & bd) {
		2404	assert(bd.square(f) != piece::PAWN);
		2405	ml.add(move::make(f, t, bd.square(f), bd.square(t)));
		2406	}
		2407
		2408	void add_move(List & ml, int f, int t, const board::Board & bd) {
		2409	if (bd.square(f) == piece::PAWN) {
		2410	add_pawn_move(ml, f, t, bd);
		2411	} else {
		2412	add_piece_move(ml, f, t, bd);
		2413	}
		2414	}
		2415
		2416	void add_piece_moves_from(List & ml, int f, bit_t ts, const board::Board & bd) {
		2417
		2418	int pc = bd.square(f);
		2419
		2420	for (bit_t b = attack::piece_attacks_from(pc, f, bd) & ts; b != 0; b = bit::rest(b)) {
		2421	int t = bit::first(b);
		2422	add_piece_move(ml, f, t, bd);
		2423	}
		2424	}
		2425
		2426	void add_captures_to(List & ml, int sd, int t, const board::Board & bd) {
		2427
		2428	for (int pc = piece::PAWN; pc <= piece::KING; pc++) {
		2429	for (bit_t b = bd.piece(pc, sd) & attack::attacks_to(pc, sd, t, bd); b != 0; b = bit::rest(b)) {
		2430	int f = bit::first(b);
		2431	add_move(ml, f, t, bd);
		2432	}
		2433	}
		2434	}
		2435
		2436	void add_captures_to_no_king(List & ml, int sd, int t, const board::Board & bd) { // for evasions
		2437
		2438	for (int pc = piece::PAWN; pc <= piece::QUEEN; pc++) { // skip king
		2439	for (bit_t b = bd.piece(pc, sd) & attack::attacks_to(pc, sd, t, bd); b != 0; b = bit::rest(b)) {
		2440	int f = bit::first(b);
		2441	add_move(ml, f, t, bd);
		2442	}
		2443	}
		2444	}
		2445
		2446	void add_pawn_captures(List & ml, int sd, bit_t ts, const board::Board & bd) {
		2447
		2448	bit_t pawns = bd.piece(piece::PAWN, sd);
		2449	ts &= bd.side(side::opposit(sd)); // not needed
		2450
		2451	if (sd == side::WHITE) {
		2452
		2453	for (bit_t b = (ts << 7) & pawns; b != 0; b = bit::rest(b)) {
		2454	int f = bit::first(b);
		2455	int t = f - 7;
		2456	add_pawn_move(ml, f, t, bd);
		2457	}
		2458
		2459	for (bit_t b = (ts >> 9) & pawns; b != 0; b = bit::rest(b)) {
		2460	int f = bit::first(b);
		2461	int t = f + 9;
		2462	add_pawn_move(ml, f, t, bd);
		2463	}
		2464
		2465	} else {
		2466
		2467	for (bit_t b = (ts << 9) & pawns; b != 0; b = bit::rest(b)) {
		2468	int f = bit::first(b);
		2469	int t = f - 9;
		2470	add_pawn_move(ml, f, t, bd);
		2471	}
		2472
		2473	for (bit_t b = (ts >> 7) & pawns; b != 0; b = bit::rest(b)) {
		2474	int f = bit::first(b);
		2475	int t = f + 7;
		2476	add_pawn_move(ml, f, t, bd);
		2477	}
		2478	}
		2479	}
		2480
		2481	void add_promotions(List & ml, int sd, bit_t ts, const board::Board & bd) {
		2482
		2483	bit_t pawns = bd.piece(piece::PAWN, sd);
		2484
		2485	if (sd == side::WHITE) {
		2486
		2487	for (bit_t b = pawns & (ts >> 1) & bit::rank(square::RANK_7); b != 0; b = bit::rest(b)) {
		2488	int f = bit::first(b);
		2489	int t = f + 1;
		2490	assert(bd.square(t) == piece::NONE);
		2491	assert(square::is_promotion(t));
		2492	add_pawn_move(ml, f, t, bd);
		2493	}
		2494
		2495	} else {
		2496
		2497	for (bit_t b = pawns & (ts << 1) & bit::rank(square::RANK_2); b != 0; b = bit::rest(b)) {
		2498	int f = bit::first(b);
		2499	int t = f - 1;
		2500	assert(bd.square(t) == piece::NONE);
		2501	assert(square::is_promotion(t));
		2502	add_pawn_move(ml, f, t, bd);
		2503	}
		2504	}
		2505	}
		2506
		2507	void add_promotions(List & ml, int sd, const board::Board & bd) {
		2508	add_promotions(ml, sd, bd.empty(), bd);
		2509	}
		2510
		2511	void add_pawn_quiets(List & ml, int sd, bit_t ts, const board::Board & bd) {
		2512
		2513	bit_t pawns = bd.piece(piece::PAWN, sd);
		2514	bit_t empty = bd.empty();
		2515
		2516	if (sd == side::WHITE) {
		2517
		2518	for (bit_t b = pawns & (ts >> 1) & ~bit::rank(square::RANK_7); b != 0; b = bit::rest(b)) { // don't generate promotions
		2519	int f = bit::first(b);
		2520	int t = f + 1;
		2521	assert(bd.square(t) == piece::NONE);
		2522	assert(!square::is_promotion(t));
		2523	add_pawn_move(ml, f, t, bd);
		2524	}
		2525
		2526	for (bit_t b = pawns & (ts >> 2) & (empty >> 1) & bit::rank(square::RANK_2); b != 0; b = bit::rest(b)) {
		2527	int f = bit::first(b);
		2528	int t = f + 2;
		2529	assert(bd.square(t) == piece::NONE);
		2530	assert(!square::is_promotion(t));
		2531	add_pawn_move(ml, f, t, bd);
		2532	}
		2533
		2534	} else {
		2535
		2536	for (bit_t b = pawns & (ts << 1) & ~bit::rank(square::RANK_2); b != 0; b = bit::rest(b)) { // don't generate promotions
		2537	int f = bit::first(b);
		2538	int t = f - 1;
		2539	assert(bd.square(t) == piece::NONE);
		2540	assert(!square::is_promotion(t));
		2541	add_pawn_move(ml, f, t, bd);
		2542	}
		2543
		2544	for (bit_t b = pawns & (ts << 2) & (empty << 1) & bit::rank(square::RANK_7); b != 0; b = bit::rest(b)) {
		2545	int f = bit::first(b);
		2546	int t = f - 2;
		2547	assert(bd.square(t) == piece::NONE);
		2548	assert(!square::is_promotion(t));
		2549	add_pawn_move(ml, f, t, bd);
		2550	}
		2551	}
		2552	}
		2553
		2554	void add_pawn_pushes(List & ml, int sd, const board::Board & bd) {
		2555
		2556	bit_t ts = 0;
		2557
		2558	if (sd == side::WHITE) {
		2559
		2560	ts \|= bit::rank(square::RANK_7);
		2561	ts \|= bit::rank(square::RANK_6) & ~attack::pawn_attacks_from(side::BLACK, bd) & (~bd.piece(piece::PAWN) >> 1); // HACK: direct access
		2562
		2563	} else {
		2564
		2565	ts \|= bit::rank(square::RANK_2);
		2566	ts \|= bit::rank(square::RANK_3) & ~attack::pawn_attacks_from(side::WHITE, bd) & (~bd.piece(piece::PAWN) << 1); // HACK: direct access
		2567	}
		2568
		2569	add_pawn_quiets(ml, sd, ts & bd.empty(), bd);
		2570	}
		2571
		2572	void add_en_passant(List & ml, int sd, const board::Board & bd) {
		2573
		2574	int t = bd.ep_sq();
		2575
		2576	if (t != square::NONE) {
		2577
		2578	bit_t fs = bd.piece(piece::PAWN, sd) & attack::Pawn_Attacks[side::opposit(sd)][t];
		2579
		2580	for (bit_t b = fs; b != 0; b = bit::rest(b)) {
		2581	int f = bit::first(b);
		2582	ml.add(move::make(f, t, piece::PAWN, piece::PAWN));
		2583	}
		2584	}
		2585	}
		2586
		2587	bool can_castle(int sd, int wg, const board::Board & bd) {
		2588
		2589	int index = castling::index(sd, wg);
		2590
		2591	if (castling::flag(bd.flags(), index)) {
		2592
		2593	int kf = castling::info[index].kf;
		2594	// int kt = castling::info[index].kt;
		2595	int rf = castling::info[index].rf;
		2596	int rt = castling::info[index].rt;
		2597
		2598	assert(bd.square_is(kf, piece::KING, sd));
		2599	assert(bd.square_is(rf, piece::ROOK, sd));
		2600
		2601	return attack::line_is_empty(kf, rf, bd) && !attack::is_attacked(rt, side::opposit(sd), bd);
		2602	}
		2603
		2604	return false;
		2605	}
		2606
		2607	void add_castling(List & ml, int sd, const board::Board & bd) {
		2608
		2609	for (int wg = 0; wg < wing::SIZE; wg++) {
		2610	if (can_castle(sd, wg, bd)) {
		2611	int index = castling::index(sd, wg);
		2612	add_piece_move(ml, castling::info[index].kf, castling::info[index].kt, bd);
		2613	}
		2614	}
		2615	}
		2616
		2617	void add_piece_moves(List & ml, int sd, bit_t ts, const board::Board & bd) {
		2618
		2619	assert(ts != 0);
		2620
		2621	for (int pc = piece::KNIGHT; pc <= piece::KING; pc++) {
		2622	for (bit_t b = bd.piece(pc, sd); b != 0; b = bit::rest(b)) {
		2623	int f = bit::first(b);
		2624	add_piece_moves_from(ml, f, ts, bd);
		2625	}
		2626	}
		2627	}
		2628
		2629	void add_piece_moves_no_king(List & ml, int sd, bit_t ts, const board::Board & bd) { // for evasions
		2630
		2631	assert(ts != 0);
		2632
		2633	for (int pc = piece::KNIGHT; pc <= piece::QUEEN; pc++) { // skip king
		2634	for (bit_t b = bd.piece(pc, sd); b != 0; b = bit::rest(b)) {
		2635	int f = bit::first(b);
		2636	add_piece_moves_from(ml, f, ts, bd);
		2637	}
		2638	}
		2639	}
		2640
		2641	void add_piece_moves_rare(List & ml, int sd, bit_t ts, const board::Board & bd) { // for captures
		2642
		2643	assert(ts != 0);
		2644
		2645	for (int pc = piece::KNIGHT; pc <= piece::KING; pc++) {
		2646
		2647	for (bit_t b = bd.piece(pc, sd); b != 0; b = bit::rest(b)) {
		2648
		2649	int f = bit::first(b);
		2650
		2651	for (bit_t bb = attack::pseudo_attacks_from(pc, sd, f) & ts; bb != 0; bb = bit::rest(bb)) {
		2652
		2653	int t = bit::first(bb);
		2654
		2655	if (attack::line_is_empty(f, t, bd)) {
		2656	add_piece_move(ml, f, t, bd);
		2657	}
		2658	}
		2659	}
		2660	}
		2661	}
		2662
		2663	void add_captures(List & ml, int sd, const board::Board & bd) {
		2664
		2665	bit_t ts = bd.side(side::opposit(sd));
		2666
		2667	add_pawn_captures(ml, sd, ts, bd);
		2668	add_piece_moves_rare(ml, sd, ts, bd);
		2669	add_en_passant(ml, sd, bd);
		2670	}
		2671
		2672	void add_captures_mvv_lva(List & ml, int sd, const board::Board & bd) { // unused
		2673
		2674	for (int pc = piece::QUEEN; pc >= piece::PAWN; pc--) {
		2675	for (bit_t b = bd.piece(pc, side::opposit(sd)); b != 0; b = bit::rest(b)) {
		2676	int t = bit::first(b);
		2677	add_captures_to(ml, sd, t, bd);
		2678	}
		2679	}
		2680
		2681	add_en_passant(ml, sd, bd);
		2682	}
		2683
		2684	bool is_move(int mv, const board::Board & bd) { // for TT-move legality
		2685
		2686	int sd = bd.turn();
		2687
		2688	int f = move::from(mv);
		2689	int t = move::to(mv);
		2690
		2691	int pc = move::piece(mv);
		2692	int cp = move::cap(mv);
		2693
		2694	if (!(bd.square(f) == pc && bd.square_side(f) == sd)) {
		2695	return false;
		2696	}
		2697
		2698	if (bd.square(t) != piece::NONE && bd.square_side(t) == sd) {
		2699	return false;
		2700	}
		2701
		2702	if (pc == piece::PAWN && t == bd.ep_sq()) {
		2703	if (cp != piece::PAWN) {
		2704	return false;
		2705	}
		2706	} else if (bd.square(t) != cp) {
		2707	return false;
		2708	}
		2709
		2710	if (cp == piece::KING) {
		2711	return false;
		2712	}
		2713
		2714	if (pc == piece::PAWN) {
		2715
		2716	// TODO
		2717
		2718	return true;
		2719
		2720	} else {
		2721
		2722	// TODO: castling
		2723
		2724	// return attack::piece_attack(pc, f, t, bd);
		2725
		2726	return true;
		2727	}
		2728
		2729	assert(false);
		2730	}
		2731
		2732	bool is_quiet_move(int mv, const board::Board & bd) { // for killer legality
		2733
		2734	int sd = bd.turn();
		2735
		2736	int f = move::from(mv);
		2737	int t = move::to(mv);
		2738
		2739	int pc = move::piece(mv);
		2740	assert(move::cap(mv) == piece::NONE);
		2741	assert(move::prom(mv) == piece::NONE);
		2742
		2743	if (!(bd.square(f) == pc && bd.square_side(f) == sd)) {
		2744	return false;
		2745	}
		2746
		2747	if (bd.square(t) != piece::NONE) {
		2748	return false;
		2749	}
		2750
		2751	if (pc == piece::PAWN) {
		2752
		2753	int inc = square::pawn_inc(sd);
		2754
		2755	if (false) {
		2756	} else if (t - f == inc && !square::is_promotion(t)) {
		2757	return true;
		2758	} else if (t - f == inc * 2 && square::rank(f, sd) == square::RANK_2) {
		2759	return bd.square(f + inc) == piece::NONE;
		2760	} else {
		2761	return false;
		2762	}
		2763
		2764	} else {
		2765
		2766	// TODO: castling
		2767
		2768	return attack::piece_attack(pc, f, t, bd);
		2769	}
		2770
		2771	assert(false);
		2772	}
		2773
		2774	void add_quiets(List & ml, int sd, const board::Board & bd) {
		2775	add_castling(ml, sd, bd);
		2776	add_piece_moves(ml, sd, bd.empty(), bd);
		2777	add_pawn_quiets(ml, sd, bd.empty(), bd);
		2778	}
		2779
		2780	void add_evasions(List & ml, int sd, const board::Board & bd, const attack::Attacks & attacks) {
		2781
		2782	assert(attacks.size > 0);
		2783
		2784	int king = bd.king(sd);
		2785
		2786	add_piece_moves_from(ml, king, ~bd.side(sd) & ~attacks.avoid, bd);
		2787
		2788	if (attacks.size == 1) {
		2789
		2790	int t = attacks.square[0];
		2791
		2792	add_captures_to_no_king(ml, sd, t, bd);
		2793	add_en_passant(ml, sd, bd);
		2794
		2795	bit_t ts = attack::Between[king][t];
		2796	assert(attack::line_is_empty(king, t, bd));
		2797
		2798	if (ts != 0) {
		2799	add_pawn_quiets(ml, sd, ts, bd);
		2800	add_promotions(ml, sd, ts, bd);
		2801	add_piece_moves_no_king(ml, sd, ts, bd);
		2802	}
		2803	}
		2804	}
		2805
		2806	void add_evasions(List & ml, int sd, const board::Board & bd) {
		2807	attack::Attacks attacks;
		2808	attack::init_attacks(attacks, sd, bd);
		2809	add_evasions(ml, sd, bd, attacks);
		2810	}
		2811
		2812	void add_checks(List & ml, int sd, const board::Board & bd) {
		2813
		2814	int atk = sd;
		2815	int def = side::opposit(sd);
		2816
		2817	int king = bd.king(def);
		2818	bit_t pinned = attack::pinned_by(king, atk, bd);
		2819	bit_t empty = bd.empty();
		2820	empty &= ~attack::pawn_attacks_from(side::opposit(sd), bd); // pawn-safe
		2821
		2822	// discovered checks
		2823
		2824	for (bit_t fs = bd.pieces(atk) & pinned; fs != 0; fs = bit::rest(fs)) { // TODO: pawns
		2825	int f = bit::first(fs);
		2826	bit_t ts = empty & ~attack::ray(king, f); // needed only for pawns
		2827	add_piece_moves_from(ml, f, ts, bd);
		2828	}
		2829
		2830	// direct checks, pawns
		2831
		2832	{
		2833	bit_t ts = attack::pseudo_attacks_to(piece::PAWN, sd, king) & empty;
		2834
		2835	add_pawn_quiets(ml, sd, ts, bd);
		2836	}
		2837
		2838	// direct checks, knights
		2839
		2840	{
		2841	int pc = piece::KNIGHT;
		2842
		2843	bit_t attacks = attack::pseudo_attacks_to(pc, sd, king) & empty;
		2844
		2845	for (bit_t b = bd.piece(pc, sd) & ~pinned; b != 0; b = bit::rest(b)) {
		2846
		2847	int f = bit::first(b);
		2848
		2849	bit_t moves = attack::pseudo_attacks_from(pc, sd, f);
		2850
		2851	for (bit_t bb = moves & attacks; bb != 0; bb = bit::rest(bb)) {
		2852	int t = bit::first(bb);
		2853	add_piece_move(ml, f, t, bd);
		2854	}
		2855	}
		2856	}
		2857
		2858	// direct checks, sliders
		2859
		2860	for (int pc = piece::BISHOP; pc <= piece::QUEEN; pc++) {
		2861
		2862	bit_t attacks = attack::pseudo_attacks_to(pc, sd, king) & empty;
		2863
		2864	for (bit_t b = bd.piece(pc, sd) & ~pinned; b != 0; b = bit::rest(b)) {
		2865
		2866	int f = bit::first(b);
		2867
		2868	bit_t moves = attack::pseudo_attacks_from(pc, sd, f);
		2869
		2870	for (bit_t bb = moves & attacks; bb != 0; bb = bit::rest(bb)) {
		2871
		2872	int t = bit::first(bb);
		2873
		2874	if (attack::line_is_empty(f, t, bd) && attack::line_is_empty(t, king, bd)) {
		2875	add_piece_move(ml, f, t, bd);
		2876	}
		2877	}
		2878	}
		2879	}
		2880	}
		2881
		2882	bool is_legal_debug(int mv, board::Board & bd) { // HACK: duplicate from Move_Type
		2883
		2884	bd.move(mv);
		2885	bool b = attack::is_legal(bd);
		2886	bd.undo();
		2887
		2888	return b;
		2889	}
		2890
		2891	void gen_moves_debug(List & ml, const board::Board & bd) {
		2892
		2893	ml.clear();
		2894
		2895	int sd = bd.turn();
		2896
		2897	if (attack::is_in_check(bd)) {
		2898	add_evasions(ml, sd, bd);
		2899	} else {
		2900	add_captures(ml, sd, bd);
		2901	add_promotions(ml, sd, bd);
		2902	add_quiets(ml, sd, bd);
		2903	}
		2904	}
		2905
		2906	void filter_legals(List & dst, const List & src, board::Board & bd) {
		2907
		2908	dst.clear();
		2909
		2910	for (int pos = 0; pos < src.size(); pos++) {
		2911
		2912	int mv = src.move(pos);
		2913
		2914	if (is_legal_debug(mv, bd)) {
		2915	dst.add(mv);
		2916	}
		2917	}
		2918	}
		2919
		2920	void gen_legals(List & ml, board::Board & bd) {
		2921
		2922	List pseudos;
		2923	gen_moves_debug(pseudos, bd);
		2924
		2925	filter_legals(ml, pseudos, bd);
		2926	}
		2927
		2928	void gen_legal_evasions(List & ml, board::Board & bd) {
		2929
		2930	int sd = bd.turn();
		2931
		2932	attack::Attacks attacks;
		2933	attack::init_attacks(attacks, sd, bd);
		2934
		2935	if (attacks.size == 0) {
		2936	ml.clear();
		2937	return;
		2938	}
		2939
		2940	List pseudos;
		2941	add_evasions(pseudos, sd, bd, attacks);
		2942
		2943	filter_legals(ml, pseudos, bd);
		2944	}
		2945
		2946	}
		2947
		2948	namespace score {
		2949
		2950	enum {
		2951	NONE = -10000,
		2952	MIN = -9999,
		2953	EVAL_MIN = -8999,
		2954	EVAL_MAX = +8999,
		2955	MAX = +9999,
		2956	MATE = +10000,
		2957	};
		2958
		2959	enum {
		2960	FLAGS_NONE = 0,
		2961	FLAGS_LOWER = 1 << 0,
		2962	FLAGS_UPPER = 1 << 1,
		2963	FLAGS_EXACT = FLAGS_LOWER \| FLAGS_UPPER,
		2964	};
		2965
		2966	bool is_mate(int sc) {
		2967	return sc < EVAL_MIN \|\| sc > EVAL_MAX;
		2968	}
		2969
		2970	int signed_mate(int sc) {
		2971	if (sc < EVAL_MIN) { // -MATE
		2972	return -(MATE + sc) / 2;
		2973	} else if (sc > EVAL_MAX) { // +MATE
		2974	return (MATE - sc + 1) / 2;
		2975	} else {
		2976	assert(false);
		2977	return 0;
		2978	}
		2979	}
		2980
		2981	int side_score(int sc, int sd) {
		2982	return (sd == side::WHITE) ? +sc : -sc;
		2983	}
		2984
		2985	int from_trans(int sc, int ply) {
		2986	if (sc < EVAL_MIN) {
		2987	return sc + ply;
		2988	} else if (sc > EVAL_MAX) {
		2989	return sc - ply;
		2990	} else {
		2991	return sc;
		2992	}
		2993	}
		2994
		2995	int to_trans(int sc, int ply) {
		2996	if (sc < EVAL_MIN) {
		2997	return sc - ply;
		2998	} else if (sc > EVAL_MAX) {
		2999	return sc + ply;
		3000	} else {
		3001	return sc;
		3002	}
		3003	}
		3004
		3005	int flags(int sc, int alpha, int beta) {
		3006
		3007	int flags = FLAGS_NONE;
		3008	if (sc > alpha) flags \|= FLAGS_LOWER;
		3009	if (sc < beta) flags \|= FLAGS_UPPER;
		3010
		3011	return flags;
		3012	}
		3013
		3014	}
		3015
		3016	namespace trans {
		3017
		3018	struct Entry { // 16 bytes
		3019	uint32 lock;
		3020	uint32 move; // TODO: uint16 #
		3021	uint16 pad_1;
		3022	int16 score;
		3023	uint8 date;
		3024	int8 depth;
		3025	uint8 flags;
		3026	uint8 pad_2;
		3027	};
		3028
		3029	void clear_entry(Entry & entry) {
		3030
		3031	assert(sizeof(Entry) == 16);
		3032
		3033	entry.lock = 0;
		3034	entry.move = move::NONE;
		3035	entry.pad_1 = 0;
		3036	entry.score = 0;
		3037	entry.date = 0;
		3038	entry.depth = -1;
		3039	entry.flags = score::FLAGS_NONE;
		3040	entry.pad_2 = 0;
		3041	}
		3042
		3043	class Table {
		3044
		3045	private:
		3046
		3047	Entry * p_table;
		3048	int p_bits;
		3049	uint64 p_size;
		3050	uint64 p_mask;
		3051
		3052	int p_date;
		3053	uint64 p_used;
		3054
		3055	int size_to_bits(int size) {
		3056
		3057	int bits = 0;
		3058
		3059	for (uint64 entries = (uint64(size) << 20) / sizeof(Entry); entries > 1; entries /= 2) {
		3060	bits++;
		3061	}
		3062
		3063	return bits;
		3064	}
		3065
		3066	public:
		3067
		3068	Table() {
		3069
		3070	p_table = NULL;
		3071	p_bits = 0;
		3072	p_size = 1;
		3073	p_mask = 0;
		3074
		3075	p_date = 0;
		3076	p_used = 0;
		3077	}
		3078
		3079	void set_size(int size) {
		3080
		3081	int bits = size_to_bits(size);
		3082	if (bits == p_bits) return;
		3083
		3084	p_bits = bits;
		3085	p_size = U64(1) << bits;
		3086	p_mask = p_size - 1;
		3087
		3088	if (p_table != NULL) {
		3089	free();
		3090	alloc();
		3091	}
		3092	}
		3093
		3094	void alloc() {
		3095	assert(p_table == NULL);
		3096	p_table = new Entry[(unsigned int) p_size]; // Pierre-Marie Baty -- added type cast
		3097	clear();
		3098	}
		3099
		3100	void free() {
		3101	assert(p_table != NULL);
		3102	delete [] p_table;
		3103	p_table = NULL;
		3104	}
		3105
		3106	void clear() {
		3107
		3108	Entry e;
		3109	clear_entry(e);
		3110
		3111	for (uint64 i = 0; i < p_size; i++) {
		3112	p_table[i] = e;
		3113	}
		3114
		3115	p_date = 1;
		3116	p_used = 0;
		3117	}
		3118
		3119	void inc_date() {
		3120	p_date = (p_date + 1) % 256;
		3121	p_used = 0;
		3122	}
		3123
		3124	void store(hash_t key, int depth, int ply, int move, int score, int flags) {
		3125
		3126	assert(depth >= 0 && depth < 100);
		3127	assert(move != move::NULL_);
		3128	assert(score >= score::MIN && score <= score::MAX);
		3129
		3130	score = score::to_trans(score, ply);
		3131
		3132	uint64 index = hash::index(key) & p_mask;
		3133	uint32 lock = hash::lock(key);
		3134
		3135	Entry * be = NULL;
		3136	int bs = -1;
		3137
		3138	for (uint64 i = 0; i < 4; i++) {
		3139
		3140	uint64 idx = (index + i) & p_mask;
		3141	assert(idx < p_size);
		3142	Entry & entry = p_table[idx];
		3143
		3144	if (entry.lock == lock) {
		3145
		3146	if (entry.date != p_date) {
		3147	entry.date = p_date;
		3148	p_used++;
		3149	}
		3150
		3151	if (depth >= entry.depth) {
		3152	if (move != move::NONE) entry.move = move;
		3153	entry.depth = depth;
		3154	entry.score = score;
		3155	entry.flags = flags;
		3156	} else if (entry.move == move::NONE) {
		3157	entry.move = move;
		3158	}
		3159
		3160	return;
		3161	}
		3162
		3163	int sc = 99 - entry.depth; // NOTE: entry.depth can be -1
		3164	if (entry.date != p_date) sc += 101;
		3165	assert(sc >= 0 && sc < 202);
		3166
		3167	if (sc > bs) {
		3168	be = &entry;
		3169	bs = sc;
		3170	}
		3171	}
		3172
		3173	assert(be != NULL);
		3174
		3175	if (be->date != p_date) p_used++;
		3176
		3177	be->lock = lock;
		3178	be->date = p_date;
		3179	be->move = move;
		3180	be->depth = depth;
		3181	be->score = score;
		3182	be->flags = flags;
		3183	}
		3184
		3185	bool retrieve(hash_t key, int depth, int ply, int & move, int & score, int & flags) {
		3186
		3187	assert(depth >= 0 && depth < 100);
		3188
		3189	uint64 index = hash::index(key) & p_mask;
		3190	uint32 lock = hash::lock(key);
		3191
		3192	for (uint64 i = 0; i < 4; i++) {
		3193
		3194	uint64 idx = (index + i) & p_mask;
		3195	assert(idx < p_size);
		3196	Entry & entry = p_table[idx];
		3197
		3198	if (entry.lock == lock) {
		3199
		3200	if (entry.date != p_date) {
		3201	entry.date = p_date; // touch entry
		3202	p_used++;
		3203	}
		3204
		3205	move = entry.move;
		3206	score = score::from_trans(entry.score, ply);
		3207	flags = entry.flags;
		3208
		3209	if (entry.depth >= depth) {
		3210	return true;
		3211	} else if (score::is_mate(score)) {
		3212	flags &= ~(score < 0 ? score::FLAGS_LOWER : score::FLAGS_UPPER);
		3213	return true;
		3214	}
		3215
		3216	return false;
		3217	}
		3218	}
		3219
		3220	return false;
		3221	}
		3222
		3223	int used() const {
		3224	return int((p_used * 1000 + p_size / 2) / p_size);
		3225	}
		3226
		3227	};
		3228
		3229	}
		3230
		3231	namespace engine {
		3232
		3233	struct Engine {
		3234	int hash;
		3235	bool ponder;
		3236	int threads;
		3237	bool log;
		3238	};
		3239
		3240	Engine engine;
		3241
		3242	void init() {
		3243	engine.hash = 64;
		3244	engine.ponder = false;
		3245	engine.threads = 1;
		3246	engine.log = false;
		3247	}
		3248
		3249	}
		3250
		3251	namespace pawn { // HACK: early declaration for pawn-pushes move type
		3252
		3253	bit_t passed_me[square::SIZE][side::SIZE];
		3254	bit_t passed_opp[square::SIZE][side::SIZE];
		3255
		3256	bool is_passed(int sq, int sd, const board::Board & bd) {
		3257	return (bd.piece(piece::PAWN, side::opposit(sd)) & passed_opp[sq][sd]) == 0
		3258	&& (bd.piece(piece::PAWN, sd) & passed_me[sq][sd]) == 0;
		3259	}
		3260
		3261	int square_distance(int ks, int ps, int sd) {
		3262	int prom = square::promotion(ps, sd);
		3263	return square::distance(ks, prom) - square::distance(ps, prom);
		3264	}
		3265
		3266	}
		3267
		3268	namespace move {
		3269
		3270	bool is_win (int mv, const board::Board & bd);
		3271
		3272	class SEE {
		3273
		3274	private:
		3275
		3276	const board::Board * p_board;
		3277	int p_to;
		3278	bit_t p_all;
		3279
		3280	int p_val;
		3281	int p_side;
		3282
		3283	void init(int t, int sd) {
		3284
		3285	p_to = t;
		3286	p_all = p_board->all();
		3287
		3288	int pc = p_board->square(t);
		3289
		3290	p_val = piece::value(pc);
		3291	p_side = sd;
		3292	}
		3293
		3294	int move(int f) {
		3295
		3296	assert(bit::is_set(p_all, f));
		3297	bit::clear(p_all, f);
		3298
		3299	int pc = p_board->square(f);
		3300	assert(pc != piece::NONE && p_board->square_side(f) == p_side);
		3301
		3302	int val = p_val;
		3303	p_val = piece::value(pc);
		3304
		3305	if (pc == piece::PAWN && square::is_promotion(p_to)) {
		3306	int delta = piece::QUEEN_VALUE - piece::PAWN_VALUE;
		3307	val += delta;
		3308	p_val += delta;
		3309	}
		3310
		3311	if (val == piece::KING_VALUE) { // stop at king capture
		3312	p_all = 0; // HACK: erase all attackers
		3313	}
		3314
		3315	p_side = side::opposit(p_side);
		3316
		3317	return val;
		3318	}
		3319
		3320	int see_rec(int alpha, int beta) {
		3321
		3322	assert(alpha < beta);
		3323
		3324	int s0 = 0;
		3325
		3326	if (s0 > alpha) {
		3327	alpha = s0;
		3328	if (s0 >= beta) return s0;
		3329	}
		3330
		3331	if (p_val <= alpha) { // FP, NOTE: fails for promotions
		3332	return p_val;
		3333	}
		3334
		3335	int f = pick_lva();
		3336
		3337	if (f == square::NONE) {
		3338	return s0;
		3339	}
		3340
		3341	int cap = move(f); // NOTE: has side effect
		3342	int s1 = cap - see_rec(cap - beta, cap - alpha);
		3343
		3344	return std::max(s0, s1);
		3345	}
		3346
		3347	int pick_lva() const {
		3348
		3349	int sd = p_side;
		3350
		3351	for (int pc = piece::PAWN; pc <= piece::KING; pc++) {
		3352
		3353	bit_t fs = p_board->piece(pc, sd) & attack::pseudo_attacks_to(pc, sd, p_to) & p_all;
		3354
		3355	for (bit_t b = fs; b != 0; b = bit::rest(b)) {
		3356
		3357	int f = bit::first(b);
		3358
		3359	if ((p_all & attack::Between[f][p_to]) == 0) {
		3360	return f;
		3361	}
		3362	}
		3363	}
		3364
		3365	return square::NONE;
		3366	}
		3367
		3368	public:
		3369
		3370	int see(int mv, int alpha, int beta, const board::Board & bd) {
		3371
		3372	assert(alpha < beta);
		3373
		3374	p_board = &bd;
		3375
		3376	int f = from(mv);
		3377	int t = to(mv);
		3378
		3379	int pc = p_board->square(f);
		3380	int sd = p_board->square_side(f);
		3381
		3382	init(t, sd);
		3383	int cap = move(f); // NOTE: assumes queen promotion
		3384
		3385	if (pc == piece::PAWN && square::is_promotion(t)) { // adjust for under-promotion
		3386	int delta = piece::QUEEN_VALUE - piece::value(prom(mv));
		3387	cap -= delta;
		3388	p_val -= delta;
		3389	}
		3390
		3391	return cap - see_rec(cap - beta, cap - alpha);
		3392	}
		3393
		3394	};
		3395
		3396	bool is_capture(int mv) {
		3397	return cap(mv) != piece::NONE;
		3398	}
		3399
		3400	bool is_en_passant(int mv, const board::Board & bd) {
		3401	return piece(mv) == piece::PAWN && to(mv) == bd.ep_sq();
		3402	}
		3403
		3404	bool is_recapture(int mv, const board::Board & bd) {
		3405	return to(mv) == bd.recap() && is_win(mv, bd);
		3406	}
		3407
		3408	bool is_promotion(int mv) {
		3409	return prom(mv) != piece::NONE;
		3410	}
		3411
		3412	bool is_queen_promotion(int mv) {
		3413	return prom(mv) == piece::QUEEN;
		3414	}
		3415
		3416	bool is_under_promotion(int mv) {
		3417	int pp = prom(mv);
		3418	return pp != piece::NONE && pp != piece::QUEEN;
		3419	}
		3420
		3421	bool is_tactical(int mv) {
		3422	return is_capture(mv) \|\| is_promotion(mv);
		3423	}
		3424
		3425	bool is_pawn_push(int mv, const board::Board & bd) {
		3426
		3427	if (is_tactical(mv)) {
		3428	return false;
		3429	}
		3430
		3431	int f = from(mv);
		3432	int t = to(mv);
		3433
		3434	int pc = bd.square(f);
		3435	int sd = bd.square_side(f);
		3436
		3437	return pc == piece::PAWN && square::rank(t, sd) >= square::RANK_6 && pawn::is_passed(t, sd, bd) && !is_capture(mv);
		3438	}
		3439
		3440	bool is_castling(int mv) {
		3441	return piece(mv) == piece::KING && std::abs(to(mv) - from(mv)) == square::CASTLING_DELTA;
		3442	}
		3443
		3444	bool is_conversion(int mv) {
		3445	return is_capture(mv) \|\| piece(mv) == piece::PAWN \|\| is_castling(mv);
		3446	}
		3447
		3448	int make(int f, int t, int pp, const board::Board & bd) {
		3449
		3450	int pc = bd.square(f);
		3451	int cp = bd.square(t);
		3452
		3453	if (pc == piece::PAWN && t == bd.ep_sq()) {
		3454	cp = piece::PAWN;
		3455	}
		3456
		3457	if (pc == piece::PAWN && square::is_promotion(t) && pp == piece::NONE) { // not needed
		3458	pp = piece::QUEEN;
		3459	}
		3460
		3461	return make(f, t, pc, cp, pp);
		3462	}
		3463
		3464	int from_string(const std::string & s, const board::Board & bd) {
		3465
		3466	assert(s.length() >= 4);
		3467
		3468	int f = square::from_string(s.substr(0, 2));
		3469	int t = square::from_string(s.substr(2, 2));
		3470	int pp = (s.length() > 4) ? piece::from_char(std::toupper(s[4])) : piece::NONE;
		3471
		3472	return make(f, t, pp, bd);
		3473	}
		3474
		3475	int see(int mv, int alpha, int beta, const board::Board & bd) {
		3476	SEE see;
		3477	return see.see(mv, alpha, beta, bd);
		3478	}
		3479
		3480	int see_max(int mv) {
		3481
		3482	assert(is_tactical(mv));
		3483
		3484	int sc = piece::value(cap(mv));
		3485
		3486	int pp = prom(mv);
		3487	if (pp != piece::NONE) sc += piece::value(pp) - piece::PAWN_VALUE;
		3488
		3489	return sc;
		3490	}
		3491
		3492	bool is_safe(int mv, const board::Board & bd) {
		3493
		3494	int pc = piece(mv);
		3495	int cp = cap(mv);
		3496	int pp = prom(mv);
		3497
		3498	if (false) {
		3499	} else if (pc == piece::KING) {
		3500	return true;
		3501	} else if (piece::value(cp) >= piece::value(pc)) {
		3502	return true;
		3503	} else if (pp != piece::NONE && pp != piece::QUEEN) { // under-promotion
		3504	return false;
		3505	} else {
		3506	return see(mv, -1, 0, bd) >= 0;
		3507	}
		3508	}
		3509
		3510	bool is_win(int mv, const board::Board & bd) {
		3511
		3512	assert(is_tactical(mv));
		3513
		3514	int pc = piece(mv);
		3515	int cp = cap(mv);
		3516	int pp = prom(mv);
		3517
		3518	if (false) {
		3519	} else if (pc == piece::KING) {
		3520	return true;
		3521	} else if (piece::value(cp) > piece::value(pc)) {
		3522	return true;
		3523	} else if (pp != piece::NONE && pp != piece::QUEEN) { // under-promotion
		3524	return false;
		3525	} else {
		3526	return see(mv, 0, +1, bd) > 0;
		3527	}
		3528	}
		3529
		3530	bool is_legal_debug(int mv, board::Board & bd) {
		3531
		3532	bd.move(mv);
		3533	bool b = attack::is_legal(bd);
		3534	bd.undo();
		3535
		3536	return b;
		3537	}
		3538
		3539	bool is_legal(int mv, board::Board & bd, const attack::Attacks & attacks) {
		3540
		3541	int sd = bd.turn();
		3542
		3543	int f = from(mv);
		3544	int t = to(mv);
		3545
		3546	if (is_en_passant(mv, bd)) {
		3547	return is_legal_debug(mv, bd);
		3548	}
		3549
		3550	if (piece(mv) == piece::KING) {
		3551	return !attack::is_attacked(t, side::opposit(sd), bd);
		3552	}
		3553
		3554	if (!bit::is_set(attacks.pinned, f)) {
		3555	return true;
		3556	}
		3557
		3558	if (bit::is_set(attack::ray(bd.king(sd), f), t)) {
		3559	return true;
		3560	}
		3561
		3562	return false;
		3563	}
		3564
		3565	bool is_check_debug(int mv, board::Board & bd) {
		3566
		3567	bd.move(mv);
		3568	bool b = attack::is_in_check(bd);
		3569	bd.undo();
		3570
		3571	return b;
		3572	}
		3573
		3574	bool is_check(int mv, board::Board & bd) {
		3575
		3576	if (is_promotion(mv) \|\| is_en_passant(mv, bd) \|\| is_castling(mv)) {
		3577	return is_check_debug(mv, bd);
		3578	}
		3579
		3580	int f = from(mv);
		3581	int t = to(mv);
		3582
		3583	int pc = (prom(mv) != piece::NONE) ? prom(mv) : piece(mv);
		3584	int sd = bd.square_side(f);
		3585
		3586	int king = bd.king(side::opposit(sd));
		3587
		3588	if (attack::attack(pc, sd, t, king, bd)) {
		3589	return true;
		3590	}
		3591
		3592	if (attack::attack_behind(king, f, sd, bd) && !bit::is_set(attack::ray(king, f), t)) {
		3593	return true;
		3594	}
		3595
		3596	return false;
		3597	}
		3598
		3599	}
		3600
		3601	namespace sort {
		3602
		3603	class Killer {
		3604
		3605	private:
		3606
		3607	static const int PLY = 100;
		3608
		3609	struct List {
		3610	int k0;
		3611	int k1;
		3612	};
		3613
		3614	List p_killer[PLY];
		3615
		3616	public:
		3617
		3618	void clear() {
		3619	for (int ply = 0; ply < PLY; ply++) {
		3620	p_killer[ply].k0 = move::NONE;
		3621	p_killer[ply].k1 = move::NONE;
		3622	}
		3623	}
		3624
		3625	void add(int mv, int ply) {
		3626	if (p_killer[ply].k0 != mv) {
		3627	p_killer[ply].k1 = p_killer[ply].k0;
		3628	p_killer[ply].k0 = mv;
		3629	}
		3630	}
		3631
		3632	int killer_0(int ply) const {
		3633	return p_killer[ply].k0;
		3634	}
		3635
		3636	int killer_1(int ply) const {
		3637	return p_killer[ply].k1;
		3638	}
		3639
		3640	};
		3641
		3642	class History {
		3643
		3644	private:
		3645
		3646	static const int PROB_BIT = 11;
		3647	static const int PROB_ONE = 1 << PROB_BIT;
		3648	static const int PROB_HALF = 1 << (PROB_BIT - 1);
		3649	static const int PROB_SHIFT = 5;
		3650
		3651	int p_prob[piece::SIDE_SIZE * square::SIZE];
		3652
		3653	static int index(int mv, const board::Board & bd) {
		3654
		3655	assert(!move::is_tactical(mv));
		3656
		3657	int sd = bd.square_side(move::from(mv));
		3658	int p12 = piece::make(move::piece(mv), sd);
		3659
		3660	int idx = p12 * square::SIZE + move::to(mv);
		3661	assert(idx < piece::SIDE_SIZE * square::SIZE);
		3662
		3663	return idx;
		3664	}
		3665
		3666	void update_good(int mv, const board::Board & bd) {
		3667	if (!move::is_tactical(mv)) {
		3668	int idx = index(mv, bd);
		3669	p_prob[idx] += (PROB_ONE - p_prob[idx]) >> PROB_SHIFT;
		3670	}
		3671	}
		3672
		3673	void update_bad(int mv, const board::Board & bd) {
		3674	if (!move::is_tactical(mv)) {
		3675	int idx = index(mv, bd);
		3676	p_prob[idx] -= p_prob[idx] >> PROB_SHIFT;
		3677	}
		3678	}
		3679
		3680	public:
		3681
		3682	void clear() {
		3683	for (int idx = 0; idx < piece::SIDE_SIZE * square::SIZE; idx++) {
		3684	p_prob[idx] = PROB_HALF;
		3685	}
		3686	}
		3687
		3688	void add(int bm, const gen::List & searched, const board::Board & bd) {
		3689
		3690	assert(bm != move::NONE);
		3691
		3692	update_good(bm, bd);
		3693
		3694	for (int pos = 0; pos < searched.size(); pos++) {
		3695	int mv = searched.move(pos);
		3696	if (mv != bm) update_bad(mv, bd);
		3697	}
		3698	}
		3699
		3700	int score(int mv, const board::Board & bd) const {
		3701	int idx = index(mv, bd);
		3702	return p_prob[idx];
		3703	}
		3704
		3705	};
		3706
		3707	int capture_score_debug(int pc, int cp) {
		3708	int sc = piece::score(cp) * 6 + (5 - piece::score(pc));
		3709	assert(sc >= 0 && sc < 36);
		3710	return sc;
		3711	}
		3712
		3713	int promotion_score_debug(int pp) {
		3714	switch (pp) {
		3715	case piece::QUEEN:
		3716	return 3;
		3717	case piece::KNIGHT:
		3718	return 2;
		3719	case piece::ROOK:
		3720	return 1;
		3721	case piece::BISHOP:
		3722	return 0;
		3723	default:
		3724	assert(false);
		3725	return 0;
		3726	}
		3727	}
		3728
		3729	int tactical_score_debug(int pc, int cp, int pp) {
		3730
		3731	int sc;
		3732
		3733	if (cp != piece::NONE) {
		3734	sc = capture_score_debug(pc, cp) + 4;
		3735	} else {
		3736	sc = promotion_score_debug(pp);
		3737	}
		3738
		3739	assert(sc >= 0 && sc < 40);
		3740	return sc;
		3741	}
		3742
		3743	int capture_score(int mv) {
		3744	assert(move::is_capture(mv));
		3745	return capture_score_debug(move::piece(mv), move::cap(mv));
		3746	}
		3747
		3748	int promotion_score(int mv) {
		3749	assert(move::is_promotion(mv) && !move::is_capture(mv));
		3750	return promotion_score_debug(move::prom(mv));
		3751	}
		3752
		3753	int tactical_score(int mv) {
		3754	assert(move::is_tactical(mv));
		3755	return tactical_score_debug(move::piece(mv), move::cap(mv), move::prom(mv));
		3756	}
		3757
		3758	int evasion_score(int mv, int trans_move) {
		3759
		3760	int sc;
		3761
		3762	if (false) {
		3763	} else if (mv == trans_move) {
		3764	sc = move::SCORE_MASK;
		3765	} else if (move::is_tactical(mv)) {
		3766	sc = tactical_score(mv) + 1;
		3767	assert (sc >= 1 && sc < 41);
		3768	} else {
		3769	sc = 0;
		3770	}
		3771
		3772	return sc;
		3773	}
		3774
		3775	void sort_tacticals(gen::List & ml) {
		3776
		3777	for (int pos = 0; pos < ml.size(); pos++) {
		3778	int mv = ml.move(pos);
		3779	int sc = tactical_score(mv);
		3780	ml.set_score(pos, sc);
		3781	}
		3782
		3783	ml.sort();
		3784	}
		3785
		3786	void sort_history(gen::List & ml, const board::Board & bd, const History & history) {
		3787
		3788	for (int pos = 0; pos < ml.size(); pos++) {
		3789	int mv = ml.move(pos);
		3790	int sc = history.score(mv, bd);
		3791	ml.set_score(pos, sc);
		3792	}
		3793
		3794	ml.sort();
		3795	}
		3796
		3797	void sort_evasions(gen::List & ml, int trans_move) {
		3798
		3799	for (int pos = 0; pos < ml.size(); pos++) {
		3800	int mv = ml.move(pos);
		3801	int sc = evasion_score(mv, trans_move);
		3802	ml.set_score(pos, sc);
		3803	}
		3804
		3805	ml.sort();
		3806	}
		3807
		3808	}
		3809
		3810	namespace gen_sort {
		3811
		3812	// HACK: outside of List class because of C++ "static const" limitations :(
		3813
		3814	enum Inst {
		3815	GEN_EVASION,
		3816	GEN_TRANS,
		3817	GEN_TACTICAL,
		3818	GEN_KILLER,
		3819	GEN_CHECK,
		3820	GEN_PAWN,
		3821	GEN_QUIET,
		3822	GEN_BAD,
		3823	GEN_END,
		3824	POST_MOVE,
		3825	POST_MOVE_SEE,
		3826	POST_KILLER,
		3827	POST_KILLER_SEE,
		3828	POST_BAD,
		3829	};
		3830
		3831	const Inst Prog_Main[] = { GEN_TRANS, POST_KILLER, GEN_TACTICAL, POST_MOVE_SEE, GEN_KILLER, POST_KILLER_SEE, GEN_QUIET, POST_MOVE_SEE, GEN_BAD, POST_BAD, GEN_END };
		3832	const Inst Prog_QS_Root[] = { GEN_TRANS, POST_KILLER, GEN_TACTICAL, POST_MOVE, GEN_CHECK, POST_KILLER, GEN_PAWN, POST_MOVE, GEN_END };
		3833	const Inst Prog_QS[] = { GEN_TRANS, POST_KILLER, GEN_TACTICAL, POST_MOVE, GEN_END };
		3834	const Inst Prog_Evasion[] = { GEN_EVASION, POST_MOVE_SEE, GEN_BAD, POST_BAD, GEN_END };
		3835
		3836	class List {
		3837
		3838	private:
		3839
		3840	board::Board * p_board;
		3841	const attack::Attacks * p_attacks;
		3842	const sort::Killer * p_killer;
		3843	const sort::History * p_hist;
		3844	int p_trans_move;
		3845
		3846	const Inst * p_ip;
		3847	Inst p_gen;
		3848	Inst p_post;
		3849
		3850	gen::List p_todo;
		3851	gen::List p_done;
		3852	gen::List p_bad;
		3853
		3854	int p_pos;
		3855	bool p_candidate;
		3856
		3857	bool gen() {
		3858
		3859	p_todo.clear();
		3860	p_pos = 0;
		3861
		3862	switch (p_gen) { {
		3863
		3864	} case GEN_EVASION: {
		3865
		3866	gen::add_evasions(p_todo, p_board->turn(), p_board, p_attacks);
		3867	sort::sort_evasions(p_todo, p_trans_move);
		3868	break;
		3869
		3870	} case GEN_TRANS: {
		3871
		3872	int mv = p_trans_move;
		3873
		3874	if (mv != move::NONE && gen::is_move(mv, *p_board)) {
		3875	p_todo.add(mv);
		3876	}
		3877
		3878	p_candidate = true;
		3879
		3880	break;
		3881
		3882	} case GEN_TACTICAL: {
		3883
		3884	gen::add_captures(p_todo, p_board->turn(), *p_board);
		3885	gen::add_promotions(p_todo, p_board->turn(), *p_board);
		3886	sort::sort_tacticals(p_todo);
		3887
		3888	p_candidate = true;
		3889
		3890	break;
		3891
		3892	} case GEN_KILLER: {
		3893
		3894	int k0 = p_killer->killer_0(p_board->ply());
		3895
		3896	if (k0 != move::NONE && gen::is_quiet_move(k0, *p_board)) {
		3897	p_todo.add(k0);
		3898	}
		3899
		3900	int k1 = p_killer->killer_1(p_board->ply());
		3901
		3902	if (k1 != move::NONE && gen::is_quiet_move(k1, *p_board)) {
		3903	p_todo.add(k1);
		3904	}
		3905
		3906	p_candidate = true;
		3907
		3908	break;
		3909
		3910	} case GEN_CHECK: {
		3911
		3912	gen::add_checks(p_todo, p_board->turn(), *p_board);
		3913
		3914	p_candidate = true; // not needed yet
		3915
		3916	break;
		3917
		3918	} case GEN_PAWN: {
		3919
		3920	gen::add_castling(p_todo, p_board->turn(), *p_board);
		3921	gen::add_pawn_pushes(p_todo, p_board->turn(), *p_board);
		3922
		3923	p_candidate = true; // not needed yet
		3924
		3925	break;
		3926
		3927	} case GEN_QUIET: {
		3928
		3929	gen::add_quiets(p_todo, p_board->turn(), *p_board);
		3930	sort::sort_history(p_todo, p_board, p_hist);
		3931
		3932	p_candidate = false;
		3933
		3934	break;
		3935
		3936	} case GEN_BAD: {
		3937
		3938	p_todo = p_bad;
		3939
		3940	p_candidate = false;
		3941
		3942	break;
		3943
		3944	} case GEN_END: {
		3945
		3946	return false;
		3947
		3948	} default: {
		3949
		3950	assert(false);
		3951
		3952	} }
		3953
		3954	return true;
		3955	}
		3956
		3957	bool post(int mv) {
		3958
		3959	assert(mv != move::NONE);
		3960
		3961	switch (p_post) { {
		3962
		3963	} case POST_MOVE: {
		3964
		3965	if (p_done.contain(mv)) {
		3966	return false;
		3967	}
		3968
		3969	if (!move::is_legal(mv, p_board, p_attacks)) {
		3970	return false;
		3971	}
		3972
		3973	break;
		3974
		3975	} case POST_MOVE_SEE: {
		3976
		3977	if (p_done.contain(mv)) {
		3978	return false;
		3979	}
		3980
		3981	if (!move::is_legal(mv, p_board, p_attacks)) {
		3982	return false;
		3983	}
		3984
		3985	if (!move::is_safe(mv, *p_board)) {
		3986	p_bad.add(mv);
		3987	return false;
		3988	}
		3989
		3990	break;
		3991
		3992	} case POST_KILLER: {
		3993
		3994	if (p_done.contain(mv)) {
		3995	return false;
		3996	}
		3997
		3998	if (!move::is_legal(mv, p_board, p_attacks)) {
		3999	return false;
		4000	}
		4001
		4002	p_done.add(mv);
		4003
		4004	break;
		4005
		4006	} case POST_KILLER_SEE: {
		4007
		4008	if (p_done.contain(mv)) {
		4009	return false;
		4010	}
		4011
		4012	if (!move::is_legal(mv, p_board, p_attacks)) {
		4013	return false;
		4014	}
		4015
		4016	p_done.add(mv);
		4017
		4018	if (!move::is_safe(mv, *p_board)) {
		4019	p_bad.add(mv);
		4020	return false;
		4021	}
		4022
		4023	break;
		4024
		4025	} case POST_BAD: {
		4026
		4027	assert(move::is_legal(mv, p_board, p_attacks));
		4028
		4029	break;
		4030
		4031	} default: {
		4032
		4033	assert(false);
		4034
		4035	} }
		4036
		4037	return true;
		4038	}
		4039
		4040	public:
		4041
		4042	void init(int depth, board::Board & bd, const attack::Attacks & attacks, int trans_move, const sort::Killer & killer, const sort::History & history, bool use_fp = false) {
		4043
		4044	p_board = &bd;
		4045	p_attacks = &attacks;
		4046	p_killer = &killer;
		4047	p_hist = &history;
		4048	p_trans_move = trans_move;
		4049
		4050	if (false) {
		4051	} else if (attacks.size != 0) { // in check
		4052	p_ip = Prog_Evasion;
		4053	} else if (depth < 0) {
		4054	p_ip = Prog_QS;
		4055	} else if (depth == 0) {
		4056	p_ip = Prog_QS_Root;
		4057	} else if (use_fp) {
		4058	p_ip = Prog_QS_Root;
		4059	} else {
		4060	p_ip = Prog_Main;
		4061	}
		4062
		4063	p_todo.clear();
		4064	p_done.clear();
		4065	p_bad.clear();
		4066
		4067	p_pos = 0;
		4068	p_candidate = false;
		4069	}
		4070
		4071	int next() {
		4072
		4073	while (true) {
		4074
		4075	while (p_pos >= p_todo.size()) {
		4076
		4077	p_gen = *p_ip++;
		4078	p_post = *p_ip++;
		4079
		4080	if (!gen()) return move::NONE;
		4081	}
		4082
		4083	int mv = p_todo.move(p_pos++);
		4084	if (post(mv)) return mv;
		4085	}
		4086	}
		4087
		4088	bool is_candidate() const {
		4089	return p_candidate;
		4090	}
		4091
		4092	};
		4093
		4094	}
		4095
		4096	namespace material {
		4097
		4098	const int p_power[piece::SIZE] = { 0, 1, 1, 2, 4, 0, 0 };
		4099	const int p_score[piece::SIZE][stage::SIZE] = { { 85, 95 }, { 325, 325 }, { 325, 325 }, { 460, 540 }, { 975, 975 }, { 0, 0 }, { 0, 0 } };
		4100
		4101	int phase_weight[TOTAL_PHASE + 1];
		4102
		4103	int power(int pc) {
		4104	assert(pc < piece::SIZE);
		4105	return p_power[pc];
		4106	}
		4107
		4108	int score(int pc, int stage) {
		4109	assert(pc < piece::SIZE);
		4110	assert(stage < stage::SIZE);
		4111	return p_score[pc][stage];
		4112	}
		4113
		4114	int force(int sd, const board::Board & bd) { // for draw eval
		4115
		4116	int force = 0;
		4117
		4118	for (int pc = piece::KNIGHT; pc <= piece::QUEEN; pc++) {
		4119	force += bd.count(pc, sd) * power(pc);
		4120	}
		4121
		4122	return force;
		4123	}
		4124
		4125	bool lone_king(int sd, const board::Board & bd) {
		4126
		4127	return bd.count(piece::KNIGHT, sd) == 0
		4128	&& bd.count(piece::BISHOP, sd) == 0
		4129	&& bd.count(piece::ROOK, sd) == 0
		4130	&& bd.count(piece::QUEEN, sd) == 0;
		4131	}
		4132
		4133	bool lone_bishop(int sd, const board::Board & bd) {
		4134
		4135	return bd.count(piece::KNIGHT, sd) == 0
		4136	&& bd.count(piece::BISHOP, sd) == 1
		4137	&& bd.count(piece::ROOK, sd) == 0
		4138	&& bd.count(piece::QUEEN, sd) == 0;
		4139	}
		4140
		4141	bool lone_king_or_bishop(int sd, const board::Board & bd) {
		4142
		4143	return bd.count(piece::KNIGHT, sd) == 0
		4144	&& bd.count(piece::BISHOP, sd) <= 1
		4145	&& bd.count(piece::ROOK, sd) == 0
		4146	&& bd.count(piece::QUEEN, sd) == 0;
		4147	}
		4148
		4149	bool lone_king_or_minor(int sd, const board::Board & bd) {
		4150
		4151	return bd.count(piece::KNIGHT, sd) + bd.count(piece::BISHOP, sd) <= 1
		4152	&& bd.count(piece::ROOK, sd) == 0
		4153	&& bd.count(piece::QUEEN, sd) == 0;
		4154	}
		4155
		4156	bool two_knights(int sd, const board::Board & bd) {
		4157
		4158	return bd.count(piece::KNIGHT, sd) == 2
		4159	&& bd.count(piece::BISHOP, sd) == 0
		4160	&& bd.count(piece::ROOK, sd) == 0
		4161	&& bd.count(piece::QUEEN, sd) == 0;
		4162	}
		4163
		4164	int interpolation(int mg, int eg, const board::Board & bd) {
		4165
		4166	int phase = std::min(bd.phase(), TOTAL_PHASE);
		4167	assert(phase >= 0 && phase <= TOTAL_PHASE);
		4168
		4169	int weight = phase_weight[phase];
		4170	return (mg * weight + eg * (256 - weight) + 128) >> 8;
		4171	}
		4172
		4173	void init() {
		4174
		4175	for (int i = 0; i <= TOTAL_PHASE; i++) {
		4176	double x = double(i) / double(TOTAL_PHASE / 2) - 1.0;
		4177	double y = 1.0 / (1.0 + std::exp(-x * 5.0));
		4178	phase_weight[i] = util::round(y * 256.0);
		4179	}
		4180	}
		4181
		4182	}
		4183
		4184	namespace pst {
		4185
		4186	const int Knight_Line[8] = { -4, -2, 0, +1, +1, 0, -2, -4 };
		4187	const int King_Line[8] = { -3, -1, 0, +1, +1, 0, -1, -3 };
		4188	const int King_File[8] = { +1, +2, 0, -2, -2, 0, +2, +1 };
		4189	const int King_Rank[8] = { +1, 0, -2, -4, -6, -8,-10,-12 };
		4190
		4191	const int Advance_Rank[8] = { -3, -2, -1, 0, +1, +2, +1, 0 };
		4192
		4193	int p_score[piece::SIDE_SIZE][square::SIZE][stage::SIZE];
		4194
		4195	int score(int p12, int sq, int stage) {
		4196	return p_score[p12][sq][stage];
		4197	}
		4198
		4199	void init() {
		4200
		4201	for (int p12 = 0; p12 < piece::SIDE_SIZE; p12++) {
		4202	for (int sq = 0; sq < square::SIZE; sq++) {
		4203	p_score[p12][sq][stage::MG] = 0;
		4204	p_score[p12][sq][stage::EG] = 0;
		4205	}
		4206	}
		4207
		4208	for (int sq = 0; sq < square::SIZE; sq++) {
		4209
		4210	int fl = square::file(sq);
		4211	int rk = square::rank(sq);
		4212
		4213	p_score[piece::WHITE_PAWN][sq][stage::MG] = 0;
		4214	p_score[piece::WHITE_PAWN][sq][stage::EG] = 0;
		4215
		4216	p_score[piece::WHITE_KNIGHT][sq][stage::MG] = (Knight_Line[fl] + Knight_Line[rk] + Advance_Rank[rk]) * 4;
		4217	p_score[piece::WHITE_KNIGHT][sq][stage::EG] = (Knight_Line[fl] + Knight_Line[rk] + Advance_Rank[rk]) * 4;
		4218
		4219	p_score[piece::WHITE_BISHOP][sq][stage::MG] = (King_Line[fl] + King_Line[rk]) * 2;
		4220	p_score[piece::WHITE_BISHOP][sq][stage::EG] = (King_Line[fl] + King_Line[rk]) * 2;
		4221
		4222	p_score[piece::WHITE_ROOK][sq][stage::MG] = King_Line[fl] * 5;
		4223	p_score[piece::WHITE_ROOK][sq][stage::EG] = 0;
		4224
		4225	p_score[piece::WHITE_QUEEN][sq][stage::MG] = (King_Line[fl] + King_Line[rk]) * 1;
		4226	p_score[piece::WHITE_QUEEN][sq][stage::EG] = (King_Line[fl] + King_Line[rk]) * 1;
		4227
		4228	p_score[piece::WHITE_KING][sq][stage::MG] = (King_File[fl] + King_Rank[rk]) * 8;
		4229	p_score[piece::WHITE_KING][sq][stage::EG] = (King_Line[fl] + King_Line[rk] + Advance_Rank[rk]) * 8;
		4230	}
		4231
		4232	for (int pc = piece::PAWN; pc <= piece::KING; pc++) {
		4233
		4234	int wp = piece::make(pc, side::WHITE);
		4235	int bp = piece::make(pc, side::BLACK);
		4236
		4237	for (int bs = 0; bs < square::SIZE; bs++) {
		4238
		4239	int ws = square::opposit_rank(bs);
		4240
		4241	p_score[bp][bs][stage::MG] = p_score[wp][ws][stage::MG];
		4242	p_score[bp][bs][stage::EG] = p_score[wp][ws][stage::EG];
		4243	}
		4244	}
		4245	}
		4246
		4247	}
		4248
		4249	namespace pawn {
		4250
		4251	struct Info { // 80 bytes; TODO: merge some bitboards and/or file info?
		4252	int8 open[square::FILE_SIZE][side::SIZE];
		4253	uint8 shelter[square::FILE_SIZE][side::SIZE];
		4254	bit_t passed;
		4255	bit_t target[side::SIZE];
		4256	bit_t safe;
		4257	uint32 lock;
		4258	int16 mg;
		4259	int16 eg;
		4260	int8 left_file;
		4261	int8 right_file;
		4262	};
		4263
		4264	void clear_info (Info & info);
		4265	void comp_info (Info & info, const board::Board & bd);
		4266
		4267	class Table {
		4268
		4269	private:
		4270
		4271	static const int BITS = 12;
		4272	static const int SIZE = 1 << BITS;
		4273	static const int MASK = SIZE - 1;
		4274
		4275	Info p_table[SIZE];
		4276
		4277	public:
		4278
		4279	void clear() {
		4280
		4281	Info info;
		4282	clear_info(info);
		4283
		4284	for (int index = 0; index < SIZE; index++) {
		4285	p_table[index] = info;
		4286	}
		4287	}
		4288
		4289	void clear_fast() {
		4290	for (int index = 0; index < SIZE; index++) {
		4291	p_table[index].lock = 1; // board w/o pawns has key 0!
		4292	}
		4293	}
		4294
		4295	const Info & info(const board::Board & bd) {
		4296
		4297	hash_t key = bd.pawn_key();
		4298
		4299	int index = hash::index(key) & MASK;
		4300	uint32 lock = hash::lock(key);
		4301
		4302	Info & entry = p_table[index];
		4303
		4304	if (entry.lock != lock) {
		4305	entry.lock = lock;
		4306	comp_info(entry, bd);
		4307	}
		4308
		4309	return entry;
		4310	}
		4311
		4312	};
		4313
		4314	bit_t duo[square::SIZE];
		4315
		4316	void clear_info(Info & info) {
		4317
		4318	info.passed = 0;
		4319	info.safe = 0;
		4320	info.lock = 1; // board w/o pawns has key 0!
		4321	info.mg = 0;
		4322	info.eg = 0;
		4323	info.left_file = square::FILE_A;
		4324	info.right_file = square::FILE_H;
		4325
		4326	for (int sd = 0; sd < side::SIZE; sd++) {
		4327	info.target[sd] = 0;
		4328	}
		4329
		4330	for (int fl = 0; fl < square::FILE_SIZE; fl++) {
		4331	for (int sd = 0; sd < side::SIZE; sd++) {
		4332	info.open[fl][sd] = 0;
		4333	info.shelter[fl][sd] = 0;
		4334	}
		4335	}
		4336	}
		4337
		4338	bool is_empty(int sq, const board::Board & bd) {
		4339	return bd.square(sq) != piece::PAWN;
		4340	}
		4341
		4342	bool is_attacked(int sq, int sd, const board::Board & bd) {
		4343	return (bd.piece(piece::PAWN, sd) & attack::pawn_attacks_to(sd, sq)) != 0;
		4344	}
		4345
		4346	bool is_controlled(int sq, int sd, const board::Board & bd) {
		4347
		4348	bit_t attackers = bd.piece(piece::PAWN, sd) & attack::pawn_attacks_to(sd, sq);
		4349	bit_t defenders = bd.piece(piece::PAWN, side::opposit(sd)) & attack::pawn_attacks_to(side::opposit(sd), sq);
		4350
		4351	return bit::count_loop(attackers) > bit::count_loop(defenders);
		4352	}
		4353
		4354	bool is_safe(int sq, int sd, const board::Board & bd) {
		4355	return is_empty(sq, bd) && !is_controlled(sq, side::opposit(sd), bd);
		4356	}
		4357
		4358	bit_t potential_attacks(int sq, int sd, const board::Board & bd) {
		4359
		4360	int inc = square::pawn_inc(sd);
		4361
		4362	bit_t attacks = attack::pawn_attacks_from(sd, sq);
		4363
		4364	for (sq += inc; !square::is_promotion(sq) && is_safe(sq, sd, bd); sq += inc) {
		4365	attacks \|= attack::pawn_attacks_from(sd, sq);
		4366	}
		4367
		4368	return attacks;
		4369	}
		4370
		4371	bool is_duo(int sq, int sd, const board::Board & bd) {
		4372	return (bd.piece(piece::PAWN, sd) & duo[sq]) != 0;
		4373	}
		4374
		4375	bool is_isolated(int sq, int sd, const board::Board & bd) {
		4376
		4377	int fl = square::file(sq);
		4378	bit_t files = bit::files(fl) & ~bit::file(fl);
		4379
		4380	return (bd.piece(piece::PAWN, sd) & files) == 0;
		4381	}
		4382
		4383	bool is_weak(int sq, int sd, const board::Board & bd) {
		4384
		4385	int fl = square::file(sq);
		4386	int rk = square::rank(sq, sd);
		4387
		4388	uint64 pawns = bd.piece(piece::PAWN, sd);
		4389	int inc = square::pawn_inc(sd);
		4390
		4391	// already fine?
		4392
		4393	if ((pawns & duo[sq]) != 0) {
		4394	return false;
		4395	}
		4396
		4397	if (is_attacked(sq, sd, bd)) {
		4398	return false;
		4399	}
		4400
		4401	// can advance next to other pawn in one move?
		4402
		4403	int s1 = sq + inc;
		4404	int s2 = s1 + inc;
		4405
		4406	if ((pawns & duo[s1]) != 0 && is_safe(s1, sd, bd)) {
		4407	return false;
		4408	}
		4409
		4410	if (rk == square::RANK_2 && (pawns & duo[s2]) != 0 && is_safe(s1, sd, bd) && is_safe(s2, sd, bd)) {
		4411	return false;
		4412	}
		4413
		4414	// can be defended in one move?
		4415
		4416	if (fl != square::FILE_A) {
		4417
		4418	int s0 = sq + square::INC_LEFT;
		4419	int s1 = s0 - inc;
		4420	int s2 = s1 - inc;
		4421	int s3 = s2 - inc;
		4422
		4423	if (bd.square_is(s2, piece::PAWN, sd) && is_safe(s1, sd, bd)) {
		4424	return false;
		4425	}
		4426
		4427	if (rk == square::RANK_5 && bd.square_is(s3, piece::PAWN, sd) && is_safe(s2, sd, bd) && is_safe(s1, sd, bd)) {
		4428	return false;
		4429	}
		4430	}
		4431
		4432	if (fl != square::FILE_H) {
		4433
		4434	int s0 = sq + square::INC_RIGHT;
		4435	int s1 = s0 - inc;
		4436	int s2 = s1 - inc;
		4437	int s3 = s2 - inc;
		4438
		4439	if (bd.square_is(s2, piece::PAWN, sd) && is_safe(s1, sd, bd)) {
		4440	return false;
		4441	}
		4442
		4443	if (rk == square::RANK_5 && bd.square_is(s3, piece::PAWN, sd) && is_safe(s2, sd, bd) && is_safe(s1, sd, bd)) {
		4444	return false;
		4445	}
		4446	}
		4447
		4448	return true;
		4449	}
		4450
		4451	bool is_doubled(int sq, int sd, const board::Board & bd) {
		4452	int fl = square::file(sq);
		4453	return (bd.piece(piece::PAWN, sd) & bit::file(fl) & bit::rear(sq, sd)) != 0;
		4454	}
		4455
		4456	bool is_blocked(int sq, int sd, const board::Board & bd) {
		4457	return !is_safe(square::stop(sq, sd), sd, bd) && !is_attacked(sq, side::opposit(sd), bd);
		4458	}
		4459
		4460	int shelter_file(int fl, int sd, const board::Board & bd) {
		4461
		4462	assert(fl >= 0 && fl < 8);
		4463
		4464	if (false) {
		4465	} else if (bd.square_is(square::make(fl, square::RANK_2, sd), piece::PAWN, sd)) {
		4466	return 2;
		4467	} else if (bd.square_is(square::make(fl, square::RANK_3, sd), piece::PAWN, sd)) {
		4468	return 1;
		4469	} else {
		4470	return 0;
		4471	}
		4472	}
		4473
		4474	int shelter_files(int fl, int sd, const board::Board & bd) {
		4475
		4476	int fl_left = (fl == square::FILE_A) ? fl + 1 : fl - 1;
		4477	int fl_right = (fl == square::FILE_H) ? fl - 1 : fl + 1;
		4478
		4479	int sc = shelter_file(fl, sd, bd) * 2 + shelter_file(fl_left, sd, bd) + shelter_file(fl_right, sd, bd);
		4480	assert(sc >= 0 && sc <= 8);
		4481
		4482	return sc;
		4483	}
		4484
		4485	void comp_info(Info & info, const board::Board & bd) {
		4486
		4487	info.passed = 0;
		4488	info.safe = 0;
		4489
		4490	info.mg = 0;
		4491	info.eg = 0;
		4492
		4493	info.left_file = square::FILE_H + 1;
		4494	info.right_file = square::FILE_A - 1;
		4495
		4496	for (int sd = 0; sd < side::SIZE; sd++) {
		4497	info.target[sd] = 0;
		4498	}
		4499
		4500	bit_t weak = 0;
		4501	bit_t strong = 0;
		4502	bit_t safe[side::SIZE] = { bit_t(~0), bit_t(~0) };
		4503
		4504	for (int sd = 0; sd < side::SIZE; sd++) {
		4505
		4506	int p12 = piece::make(piece::PAWN, sd);
		4507
		4508	strong \|= bd.piece(piece::PAWN, sd) & attack::pawn_attacks_from(sd, bd); // defended pawns
		4509
		4510	{
		4511	int n = bd.count(piece::PAWN, sd);
		4512	info.mg += n * material::score(piece::PAWN, stage::MG);
		4513	info.eg += n * material::score(piece::PAWN, stage::EG);
		4514	}
		4515
		4516	for (bit_t b = bd.piece(piece::PAWN, sd); b != 0; b = bit::rest(b)) {
		4517
		4518	int sq = bit::first(b);
		4519
		4520	int fl = square::file(sq);
		4521	int rk = square::rank(sq, sd);
		4522
		4523	if (fl < info.left_file) info.left_file = fl;
		4524	if (fl > info.right_file) info.right_file = fl;
		4525
		4526	info.mg += pst::score(p12, sq, stage::MG);
		4527	info.eg += pst::score(p12, sq, stage::EG);
		4528
		4529	if (is_isolated(sq, sd, bd)) {
		4530
		4531	bit::set(weak, sq);
		4532
		4533	info.mg -= 10;
		4534	info.eg -= 20;
		4535
		4536	} else if (is_weak(sq, sd, bd)) {
		4537
		4538	bit::set(weak, sq);
		4539
		4540	info.mg -= 5;
		4541	info.eg -= 10;
		4542	}
		4543
		4544	if (is_doubled(sq, sd, bd)) {
		4545	info.mg -= 5;
		4546	info.eg -= 10;
		4547	}
		4548
		4549	if (is_passed(sq, sd, bd)) {
		4550
		4551	bit::set(info.passed, sq);
		4552
		4553	info.mg += 10;
		4554	info.eg += 20;
		4555
		4556	if (rk >= square::RANK_5) {
		4557	int stop = square::stop(sq, sd);
		4558	if (is_duo(sq, sd, bd) && rk <= square::RANK_6) stop += square::pawn_inc(sd); // stop one line "later" for duos
		4559	bit::set(info.target[side::opposit(sd)], stop);
		4560	}
		4561	}
		4562
		4563	safe[side::opposit(sd)] &= ~potential_attacks(sq, sd, bd);
		4564	}
		4565
		4566	for (int fl = 0; fl < square::FILE_SIZE; fl++) {
		4567	info.shelter[fl][sd] = shelter_files(fl, sd, bd) * 4;
		4568	}
		4569
		4570	info.mg = -info.mg;
		4571	info.eg = -info.eg;
		4572	}
		4573
		4574	weak &= ~strong; // defended doubled pawns are not weak
		4575	assert((weak & strong) == 0);
		4576
		4577	info.target[side::WHITE] \|= bd.piece(piece::PAWN, side::BLACK) & weak;
		4578	info.target[side::BLACK] \|= bd.piece(piece::PAWN, side::WHITE) & weak;
		4579
		4580	info.safe = (safe[side::WHITE] & bit::front(square::RANK_4))
		4581	\| (safe[side::BLACK] & bit::rear (square::RANK_5));
		4582
		4583	if (info.left_file > info.right_file) { // no pawns
		4584	info.left_file = square::FILE_A;
		4585	info.right_file = square::FILE_H;
		4586	}
		4587
		4588	assert(info.left_file <= info.right_file);
		4589
		4590	// file "openness"
		4591
		4592	for (int sd = 0; sd < side::SIZE; sd++) {
		4593
		4594	for (int fl = 0; fl < square::FILE_SIZE; fl++) {
		4595
		4596	bit_t file = bit::file(fl);
		4597
		4598	int open;
		4599
		4600	if (false) {
		4601	} else if ((bd.piece(piece::PAWN, sd) & file) != 0) {
		4602	open = 0;
		4603	} else if ((bd.piece(piece::PAWN, side::opposit(sd)) & file) == 0) {
		4604	open = 4;
		4605	} else if ((strong & file) != 0) {
		4606	open = 1;
		4607	} else if ((weak & file) != 0) {
		4608	open = 3;
		4609	} else {
		4610	open = 2;
		4611	}
		4612
		4613	info.open[fl][sd] = open * 5;
		4614	}
		4615	}
		4616	}
		4617
		4618	void init() {
		4619
		4620	for (int sq = 0; sq < square::SIZE; sq++) {
		4621
		4622	int fl = square::file(sq);
		4623	int rk = square::rank(sq);
		4624
		4625	passed_me[sq][side::WHITE] = bit::file(fl) & bit::front(rk);
		4626	passed_me[sq][side::BLACK] = bit::file(fl) & bit::rear(rk);
		4627
		4628	passed_opp[sq][side::WHITE] = bit::files(fl) & bit::front(rk);
		4629	passed_opp[sq][side::BLACK] = bit::files(fl) & bit::rear(rk);
		4630
		4631	bit_t b = 0;
		4632	if (fl != square::FILE_A) bit::set(b, sq + square::INC_LEFT);
		4633	if (fl != square::FILE_H) bit::set(b, sq + square::INC_RIGHT);
		4634	duo[sq] = b;
		4635	}
		4636	}
		4637
		4638	}
		4639
		4640	namespace eval {
		4641
		4642	int comp_eval (const board::Board & bd, pawn::Table & pawn_table);
		4643
		4644	struct Entry {
		4645	uint32 lock;
		4646	int eval;
		4647	};
		4648
		4649	class Table {
		4650
		4651	private:
		4652
		4653	static const int BITS = 16;
		4654	static const int SIZE = 1 << BITS;
		4655	static const int MASK = SIZE - 1;
		4656
		4657	Entry p_table[SIZE];
		4658
		4659	public:
		4660
		4661	void clear() {
		4662	for (int index = 0; index < SIZE; index++) {
		4663	p_table[index].lock = 0;
		4664	p_table[index].eval = 0;
		4665	}
		4666	}
		4667
		4668	int eval(const board::Board & bd, pawn::Table & pawn_table) { // NOTE: score for white
		4669
		4670	hash_t key = bd.eval_key();
		4671
		4672	int index = hash::index(key) & MASK;
		4673	uint32 lock = hash::lock(key);
		4674
		4675	Entry & entry = p_table[index];
		4676
		4677	if (entry.lock == lock) {
		4678	return entry.eval;
		4679	}
		4680
		4681	int eval = comp_eval(bd, pawn_table);
		4682
		4683	entry.lock = lock;
		4684	entry.eval = eval;
		4685
		4686	return eval;
		4687	}
		4688
		4689	};
		4690
		4691	struct Attack_Info {
		4692
		4693	bit_t piece_attacks[square::SIZE];
		4694	bit_t all_attacks[side::SIZE];
		4695	bit_t multiple_attacks[side::SIZE];
		4696
		4697	bit_t ge_pieces[side::SIZE][piece::SIZE];
		4698
		4699	bit_t lt_attacks[side::SIZE][piece::SIZE];
		4700	bit_t le_attacks[side::SIZE][piece::SIZE];
		4701
		4702	bit_t king_evasions[side::SIZE];
		4703
		4704	bit_t pinned;
		4705	};
		4706
		4707	const int attack_weight[piece::SIZE] = { 0, 4, 4, 2, 1, 4, 0 };
		4708	const int attacked_weight[piece::SIZE] = { 0, 1, 1, 2, 4, 8, 0 };
		4709
		4710	int mob_weight[32];
		4711	int dist_weight[8]; // for king-passer distance
		4712
		4713	bit_t small_centre, medium_centre, large_centre;
		4714	bit_t centre_0, centre_1;
		4715
		4716	bit_t side_area[side::SIZE];
		4717	bit_t king_area[side::SIZE][square::SIZE];
		4718
		4719	void comp_attacks(Attack_Info & ai, const board::Board & bd) {
		4720
		4721	// prepare for adding defended opponent pieces
		4722
		4723	for (int sd = 0; sd < side::SIZE; sd++) {
		4724
		4725	bit_t b = 0;
		4726
		4727	for (int pc = piece::KING; pc >= piece::KNIGHT; pc--) {
		4728	b \|= bd.piece(pc, sd);
		4729	ai.ge_pieces[sd][pc] = b;
		4730	}
		4731
		4732	ai.ge_pieces[sd][piece::BISHOP] = ai.ge_pieces[sd][piece::KNIGHT]; // minors are equal
		4733	}
		4734
		4735	// pawn attacks
		4736
		4737	{
		4738	int pc = piece::PAWN;
		4739
		4740	for (int sd = 0; sd < side::SIZE; sd++) {
		4741
		4742	bit_t b = attack::pawn_attacks_from(sd, bd);
		4743
		4744	ai.lt_attacks[sd][pc] = 0; // not needed
		4745	ai.le_attacks[sd][pc] = b;
		4746	ai.all_attacks[sd] = b;
		4747	}
		4748	}
		4749
		4750	// piece attacks
		4751
		4752	ai.multiple_attacks[side::WHITE] = 0;
		4753	ai.multiple_attacks[side::BLACK] = 0;
		4754
		4755	for (int pc = piece::KNIGHT; pc <= piece::KING; pc++) {
		4756
		4757	int lower_piece = (pc == piece::BISHOP) ? piece::PAWN : pc - 1; // HACK: direct access
		4758	assert(lower_piece >= piece::PAWN && lower_piece < pc);
		4759
		4760	for (int sd = 0; sd < side::SIZE; sd++) {
		4761	ai.lt_attacks[sd][pc] = ai.le_attacks[sd][lower_piece];
		4762	}
		4763
		4764	for (int sd = 0; sd < side::SIZE; sd++) {
		4765
		4766	for (bit_t fs = bd.piece(pc, sd); fs != 0; fs = bit::rest(fs)) {
		4767
		4768	int sq = bit::first(fs);
		4769
		4770	bit_t ts = attack::piece_attacks_from(pc, sq, bd);
		4771	ai.piece_attacks[sq] = ts;
		4772
		4773	ai.multiple_attacks[sd] \|= ts & ai.all_attacks[sd];
		4774	ai.all_attacks[sd] \|= ts;
		4775	}
		4776
		4777	ai.le_attacks[sd][pc] = ai.all_attacks[sd];
		4778	assert((ai.le_attacks[sd][pc] & ai.lt_attacks[sd][pc]) == ai.lt_attacks[sd][pc]);
		4779
		4780	if (pc == piece::BISHOP) { // minors are equal
		4781	ai.le_attacks[sd][piece::KNIGHT] = ai.le_attacks[sd][piece::BISHOP];
		4782	}
		4783	}
		4784	}
		4785
		4786	for (int sd = 0; sd < side::SIZE; sd++) {
		4787	int king = bd.king(sd);
		4788	bit_t ts = attack::pseudo_attacks_from(piece::KING, sd, king);
		4789	ai.king_evasions[sd] = ts & ~bd.side(sd) & ~ai.all_attacks[side::opposit(sd)];
		4790	}
		4791
		4792	// pinned pieces
		4793
		4794	ai.pinned = 0;
		4795
		4796	for (int sd = 0; sd < side::SIZE; sd++) {
		4797	int sq = bd.king(sd);
		4798	ai.pinned \|= bd.side(sd) & attack::pinned_by(sq, side::opposit(sd), bd);
		4799	}
		4800	}
		4801
		4802	int mul_shift(int a, int b, int c) {
		4803	int bias = 1 << (c - 1);
		4804	return (a * b + bias) >> c;
		4805	}
		4806
		4807	int passed_score(int sc, int rk) {
		4808	static const int passed_weight[8] = { 0, 0, 0, 2, 6, 12, 20, 0 };
		4809	return mul_shift(sc, passed_weight[rk], 4);
		4810	}
		4811
		4812	int mobility_score(int /* pc */, bit_t ts) {
		4813	// assert(pc < piece::SIZE);
		4814	int mob = bit::count(ts);
		4815	return mul_shift(20, mob_weight[mob], 8);
		4816	}
		4817
		4818	int attack_mg_score(int pc, int sd, bit_t ts) {
		4819
		4820	assert(pc < piece::SIZE);
		4821
		4822	int c0 = bit::count(ts & centre_0);
		4823	int c1 = bit::count(ts & centre_1);
		4824	int sc = c1 * 2 + c0;
		4825
		4826	sc += bit::count(ts & side_area[side::opposit(sd)]);
		4827
		4828	return (sc - 4) * attack_weight[pc] / 2;
		4829	}
		4830
		4831	int attack_eg_score(int pc, int sd, bit_t ts, const pawn::Info & pi) {
		4832	assert(pc < piece::SIZE);
		4833	return bit::count(ts & pi.target[sd]) * attack_weight[pc] * 4;
		4834	}
		4835
		4836	int capture_score(int pc, int sd, bit_t ts, const board::Board & bd, const Attack_Info & ai) {
		4837
		4838	assert(pc < piece::SIZE);
		4839
		4840	int sc = 0;
		4841
		4842	for (bit_t b = ts & bd.pieces(side::opposit(sd)); b != 0; b = bit::rest(b)) {
		4843
		4844	int t = bit::first(b);
		4845
		4846	int cp = bd.square(t);
		4847	sc += attacked_weight[cp];
		4848	if (bit::is_set(ai.pinned, t)) sc += attacked_weight[cp] * 2;
		4849	}
		4850
		4851	return attack_weight[pc] * sc * 4;
		4852	}
		4853
		4854	int shelter_score(int sq, int sd, const board::Board & bd, const pawn::Info & pi) {
		4855
		4856	if (square::rank(sq, sd) > square::RANK_2) {
		4857	return 0;
		4858	}
		4859
		4860	int s0 = pi.shelter[square::file(sq)][sd];
		4861
		4862	int s1 = 0;
		4863
		4864	for (int wg = 0; wg < wing::SIZE; wg++) {
		4865
		4866	int index = castling::index(sd, wg);
		4867
		4868	if (castling::flag(bd.flags(), index)) {
		4869	int fl = wing::shelter_file[wg];
		4870	s1 = std::max(s1, int(pi.shelter[fl][sd]));
		4871	}
		4872	}
		4873
		4874	if (s1 > s0) {
		4875	return (s0 + s1) / 2;
		4876	} else {
		4877	return s0;
		4878	}
		4879	}
		4880
		4881	int king_score(int sc, int n) {
		4882	int weight = 256 - (256 >> n);
		4883	return mul_shift(sc, weight, 8);
		4884	}
		4885
		4886	int eval_outpost(int sq, int sd, const board::Board & bd, const pawn::Info & pi) {
		4887
		4888	assert(square::rank(sq, sd) >= square::RANK_5);
		4889
		4890	int xd = side::opposit(sd);
		4891
		4892	int weight = 0;
		4893
		4894	if (bit::is_set(pi.safe, sq)) { // safe square
		4895	weight += 2;
		4896	}
		4897
		4898	if (bd.square_is(square::stop(sq, sd), piece::PAWN, xd)) { // shielded
		4899	weight++;
		4900	}
		4901
		4902	if (pawn::is_attacked(sq, sd, bd)) { // defended
		4903	weight++;
		4904	}
		4905
		4906	return weight - 2;
		4907	}
		4908
		4909	bool passer_is_unstoppable(int sq, int sd, const board::Board & bd) {
		4910
		4911	if (!material::lone_king(side::opposit(sd), bd)) return false;
		4912
		4913	int fl = square::file(sq);
		4914	bit_t front = bit::file(fl) & bit::front(sq, sd);
		4915
		4916	if ((bd.all() & front) != 0) { // path not free
		4917	return false;
		4918	}
		4919
		4920	if (pawn::square_distance(bd.king(side::opposit(sd)), sq, sd) >= 2) { // opponent king outside square
		4921	return true;
		4922	}
		4923
		4924	if ((front & ~attack::pseudo_attacks_from(piece::KING, sd, bd.king(sd))) == 0) { // king controls promotion path
		4925	return true;
		4926	}
		4927
		4928	return false;
		4929	}
		4930
		4931	int eval_passed(int sq, int sd, const board::Board & bd, const Attack_Info & ai) {
		4932
		4933	int fl = square::file(sq);
		4934	int xd = side::opposit(sd);
		4935
		4936	int weight = 4;
		4937
		4938	// blocker
		4939
		4940	if (bd.square(square::stop(sq, sd)) != piece::NONE) {
		4941	weight--;
		4942	}
		4943
		4944	// free path
		4945
		4946	bit_t front = bit::file(fl) & bit::front(sq, sd);
		4947	bit_t rear = bit::file(fl) & bit::rear (sq, sd);
		4948
		4949	if ((bd.all() & front) == 0) {
		4950
		4951	bool major_behind = false;
		4952	bit_t majors = bd.piece(piece::ROOK, xd) \| bd.piece(piece::QUEEN, xd);
		4953
		4954	for (bit_t b = majors & rear; b != 0; b = bit::rest(b)) {
		4955
		4956	int f = bit::first(b);
		4957
		4958	if (attack::line_is_empty(f, sq, bd)) {
		4959	major_behind = true;
		4960	}
		4961	}
		4962
		4963	if (!major_behind && (ai.all_attacks[xd] & front) == 0) {
		4964	weight += 2;
		4965	}
		4966	}
		4967
		4968	return weight;
		4969	}
		4970
		4971	int eval_pawn_cap(int sd, const board::Board & bd, const Attack_Info & ai) {
		4972
		4973	bit_t ts = attack::pawn_attacks_from(sd, bd);
		4974
		4975	int sc = 0;
		4976
		4977	for (bit_t b = ts & bd.pieces(side::opposit(sd)); b != 0; b = bit::rest(b)) {
		4978
		4979	int t = bit::first(b);
		4980
		4981	int cp = bd.square(t);
		4982	if (cp == piece::KING) continue;
		4983
		4984	sc += piece::value(cp) - 50;
		4985	if (bit::is_set(ai.pinned, t)) sc += (piece::value(cp) - 50) * 2;
		4986	}
		4987
		4988	return sc / 10;
		4989	}
		4990
		4991	int eval_pattern(const board::Board & bd) {
		4992
		4993	int eval = 0;
		4994
		4995	// fianchetto
		4996
		4997	if (bd.square_is(square::B2, piece::BISHOP, side::WHITE)
		4998	&& bd.square_is(square::B3, piece::PAWN, side::WHITE)
		4999	&& bd.square_is(square::C2, piece::PAWN, side::WHITE)) {
		5000	eval += 20;
		5001	}
		5002
		5003	if (bd.square_is(square::G2, piece::BISHOP, side::WHITE)
		5004	&& bd.square_is(square::G3, piece::PAWN, side::WHITE)
		5005	&& bd.square_is(square::F2, piece::PAWN, side::WHITE)) {
		5006	eval += 20;
		5007	}
		5008
		5009	if (bd.square_is(square::B7, piece::BISHOP, side::BLACK)
		5010	&& bd.square_is(square::B6, piece::PAWN, side::BLACK)
		5011	&& bd.square_is(square::C7, piece::PAWN, side::BLACK)) {
		5012	eval -= 20;
		5013	}
		5014
		5015	if (bd.square_is(square::G7, piece::BISHOP, side::BLACK)
		5016	&& bd.square_is(square::G6, piece::PAWN, side::BLACK)
		5017	&& bd.square_is(square::F7, piece::PAWN, side::BLACK)) {
		5018	eval -= 20;
		5019	}
		5020
		5021	return eval;
		5022	}
		5023
		5024	bool has_minor(int sd, const board::Board & bd) {
		5025	return bd.count(piece::KNIGHT, sd) + bd.count(piece::BISHOP, sd) != 0;
		5026	}
		5027
		5028	int draw_mul(int sd, const board::Board & bd, const pawn::Info & pi) {
		5029
		5030	int xd = side::opposit(sd);
		5031
		5032	int pawn[side::SIZE];
		5033	pawn[side::WHITE] = bd.count(piece::PAWN, side::WHITE);
		5034	pawn[side::BLACK] = bd.count(piece::PAWN, side::BLACK);
		5035
		5036	int force = material::force(sd, bd) - material::force(xd, bd);
		5037
		5038	// rook-file pawns
		5039
		5040	if (material::lone_king_or_bishop(sd, bd) && pawn[sd] != 0) {
		5041
		5042	bit_t b = bd.piece(piece::BISHOP, sd);
		5043
		5044	if ((bd.piece(piece::PAWN, sd) & ~bit::file(square::FILE_A)) == 0
		5045	&& (bd.piece(piece::PAWN, xd) & bit::file(square::FILE_B)) == 0) {
		5046
		5047	int prom = (sd == side::WHITE) ? square::A8 : square::A1;
		5048
		5049	if (square::distance(bd.king(xd), prom) <= 1) {
		5050	if (b == 0 \|\| !square::same_colour(bit::first(b), prom)) {
		5051	return 1;
		5052	}
		5053	}
		5054	}
		5055
		5056	if ((bd.piece(piece::PAWN, sd) & ~bit::file(square::FILE_H)) == 0
		5057	&& (bd.piece(piece::PAWN, xd) & bit::file(square::FILE_G)) == 0) {
		5058
		5059	int prom = (sd == side::WHITE) ? square::H8 : square::H1;
		5060
		5061	if (square::distance(bd.king(xd), prom) <= 1) {
		5062	if (b == 0 \|\| !square::same_colour(bit::first(b), prom)) {
		5063	return 1;
		5064	}
		5065	}
		5066	}
		5067	}
		5068
		5069	if (pawn[sd] == 0 && material::lone_king_or_minor(sd, bd)) {
		5070	return 1;
		5071	}
		5072
		5073	if (pawn[sd] == 0 && material::two_knights(sd, bd)) {
		5074	return 2;
		5075	}
		5076
		5077	if (pawn[sd] == 0 && force <= 1) {
		5078	return 2;
		5079	}
		5080
		5081	if (pawn[sd] == 1 && force == 0 && has_minor(xd, bd)) {
		5082	return 4;
		5083	}
		5084
		5085	if (pawn[sd] == 1 && force == 0) {
		5086
		5087	int king = bd.king(xd);
		5088	int pawn = bit::first(bd.piece(piece::PAWN, sd));
		5089	int stop = square::stop(pawn, sd);
		5090
		5091	if (king == stop \|\| (square::rank(pawn, sd) <= square::RANK_6 && king == square::stop(stop, sd))) {
		5092	return 4;
		5093	}
		5094	}
		5095
		5096	if (pawn[sd] == 2 && pawn[xd] >= 1 && force == 0 && has_minor(xd, bd) && (bd.piece(piece::PAWN, sd) & pi.passed) == 0) {
		5097	return 8;
		5098	}
		5099
		5100	if (material::lone_bishop(side::WHITE, bd) && material::lone_bishop(side::BLACK, bd) && std::abs(pawn[side::WHITE] - pawn[side::BLACK]) <= 2) { // opposit-colour bishops
		5101
		5102	int wb = bit::first(bd.piece(piece::BISHOP, side::WHITE));
		5103	int bb = bit::first(bd.piece(piece::BISHOP, side::BLACK));
		5104
		5105	if (!square::same_colour(wb, bb)) {
		5106	return 8;
		5107	}
		5108	}
		5109
		5110	return 16;
		5111	}
		5112
		5113	int my_distance(int f, int t, int weight) {
		5114	int dist = square::distance(f, t);
		5115	return mul_shift(dist_weight[dist], weight, 8);
		5116	}
		5117
		5118	int check_number(int pc, int sd, bit_t ts, int king, const board::Board & bd) {
		5119
		5120	assert(pc != piece::KING);
		5121
		5122	int xd = side::opposit(sd);
		5123	bit_t checks = ts & ~bd.side(sd) & attack::pseudo_attacks_to(pc, sd, king);
		5124
		5125	if (!piece::is_slider(pc)) {
		5126	return bit::count_loop(checks);
		5127	}
		5128
		5129	int n = 0;
		5130
		5131	bit_t b = checks & attack::pseudo_attacks_to(piece::KING, xd, king); // contact checks
		5132	n += bit::count_loop(b) * 2;
		5133	checks &= ~b;
		5134
		5135	for (bit_t b = checks; b != 0; b = bit::rest(b)) {
		5136
		5137	int t = bit::first(b);
		5138
		5139	if (attack::line_is_empty(t, king, bd)) {
		5140	n++;
		5141	}
		5142	}
		5143
		5144	return n;
		5145	}
		5146
		5147	int comp_eval(const board::Board & bd, pawn::Table & pawn_table) { // NOTE: score for white
		5148
		5149	Attack_Info ai;
		5150	comp_attacks(ai, bd);
		5151
		5152	const pawn::Info & pi = pawn_table.info(bd);
		5153
		5154	int eval = 0;
		5155	int mg = 0;
		5156	int eg = 0;
		5157
		5158	int shelter[side::SIZE];
		5159
		5160	for (int sd = 0; sd < side::SIZE; sd++) {
		5161	shelter[sd] = shelter_score(bd.king(sd), sd, bd, pi);
		5162	}
		5163
		5164	for (int sd = 0; sd < side::SIZE; sd++) {
		5165
		5166	int xd = side::opposit(sd);
		5167
		5168	int my_king = bd.king(sd);
		5169	int op_king = bd.king(xd);
		5170
		5171	bit_t target = ~(bd.piece(piece::PAWN, sd) \| attack::pawn_attacks_from(xd, bd));
		5172
		5173	int king_n = 0;
		5174	int king_power = 0;
		5175
		5176	// pawns
		5177
		5178	{
		5179	bit_t fs = bd.piece(piece::PAWN, sd);
		5180
		5181	bit_t front = (sd == side::WHITE) ? bit::front(square::RANK_3) : bit::rear(square::RANK_6);
		5182
		5183	for (bit_t b = fs & pi.passed & front; b != 0; b = bit::rest(b)) {
		5184
		5185	int sq = bit::first(b);
		5186
		5187	int rk = square::rank(sq, sd);
		5188
		5189	if (passer_is_unstoppable(sq, sd, bd)) {
		5190
		5191	int weight = std::max(rk - square::RANK_3, 0);
		5192	assert(weight >= 0 and weight < 5);
		5193
		5194	eg += (piece::QUEEN_VALUE - piece::PAWN_VALUE) * weight / 5;
		5195
		5196	} else {
		5197
		5198	int sc = eval_passed(sq, sd, bd, ai);
		5199
		5200	int sc_mg = sc * 20;
		5201	int sc_eg = sc * 25;
		5202
		5203	int stop = square::stop(sq, sd);
		5204	sc_eg -= my_distance(my_king, stop, 10);
		5205	sc_eg += my_distance(op_king, stop, 20);
		5206
		5207	mg += passed_score(sc_mg, rk);
		5208	eg += passed_score(sc_eg, rk);
		5209	}
		5210	}
		5211
		5212	eval += bit::count(attack::pawn_moves_from(sd, bd) & bd.empty()) * 4 - bd.count(piece::PAWN, sd) * 2;
		5213
		5214	eval += eval_pawn_cap(sd, bd, ai);
		5215	}
		5216
		5217	// pieces
		5218
		5219	for (int pc = piece::KNIGHT; pc <= piece::KING; pc++) {
		5220
		5221	int p12 = piece::make(pc, sd); // for PST
		5222
		5223	{
		5224	int n = bd.count(pc, sd);
		5225	mg += n * material::score(pc, stage::MG);
		5226	eg += n * material::score(pc, stage::EG);
		5227	}
		5228
		5229	for (bit_t b = bd.piece(pc, sd); b != 0; b = bit::rest(b)) {
		5230
		5231	int sq = bit::first(b);
		5232
		5233	int fl = square::file(sq);
		5234	int rk = square::rank(sq, sd);
		5235
		5236	// compute safe attacks
		5237
		5238	bit_t ts_all = ai.piece_attacks[sq];
		5239	bit_t ts_pawn_safe = ts_all & target;
		5240
		5241	bit_t safe = ~ai.all_attacks[xd] \| ai.multiple_attacks[sd];
		5242
		5243	if (true && piece::is_slider(pc)) { // battery support
		5244
		5245	bit_t bishops = bd.piece(piece::BISHOP, sd) \| bd.piece(piece::QUEEN, sd);
		5246	bit_t rooks = bd.piece(piece::ROOK, sd) \| bd.piece(piece::QUEEN, sd);
		5247
		5248	bit_t support = 0;
		5249	support \|= bishops & attack::pseudo_attacks_to(piece::BISHOP, sd, sq);
		5250	support \|= rooks & attack::pseudo_attacks_to(piece::ROOK, sd, sq);
		5251
		5252	for (bit_t b = ts_all & support; b != 0; b = bit::rest(b)) {
		5253	int f = bit::first(b);
		5254	assert(attack::line_is_empty(f, sq, bd));
		5255	safe \|= attack::Behind[f][sq];
		5256	}
		5257	}
		5258
		5259	bit_t ts_safe = ts_pawn_safe & ~ai.lt_attacks[xd][pc] & safe;
		5260
		5261	mg += pst::score(p12, sq, stage::MG);
		5262	eg += pst::score(p12, sq, stage::EG);
		5263
		5264	if (pc == piece::KING) {
		5265	eg += mobility_score(pc, ts_safe);
		5266	} else {
		5267	eval += mobility_score(pc, ts_safe);
		5268	}
		5269
		5270	if (pc != piece::KING) {
		5271	mg += attack_mg_score(pc, sd, ts_pawn_safe);
		5272	}
		5273
		5274	eg += attack_eg_score(pc, sd, ts_pawn_safe, pi);
		5275
		5276	eval += capture_score(pc, sd, ts_all & (ai.ge_pieces[xd][pc] \| target), bd, ai);
		5277
		5278	if (pc != piece::KING) {
		5279	eval += check_number(pc, sd, ts_safe, op_king, bd) * material::power(pc) * 6;
		5280	}
		5281
		5282	if (pc != piece::KING && (ts_safe & king_area[xd][op_king]) != 0) { // king attack
		5283	king_n++;
		5284	king_power += material::power(pc);
		5285	}
		5286
		5287	if (piece::is_minor(pc) && rk >= square::RANK_5 && rk <= square::RANK_6 && fl >= square::FILE_C && fl <= square::FILE_F) { // outpost
		5288	eval += eval_outpost(sq, sd, bd, pi) * 5;
		5289	}
		5290
		5291	if (piece::is_minor(pc) && rk >= square::RANK_5 && !bit::is_set(ai.all_attacks[sd], sq)) { // loose minor
		5292	mg -= 10;
		5293	}
		5294
		5295	if (piece::is_minor(pc) && rk >= square::RANK_3 && rk <= square::RANK_4 && bd.square_is(square::stop(sq, sd), piece::PAWN, sd)) { // shielded minor
		5296	mg += 10;
		5297	}
		5298
		5299	if (pc == piece::ROOK) { // open file
		5300
		5301	int sc = pi.open[fl][sd];
		5302
		5303	bit_t minors = bd.piece(piece::KNIGHT, xd) \| bd.piece(piece::BISHOP, xd);
		5304	if (true && sc >= 10 && (minors & bit::file(fl) & ~target) != 0) { // blocked by minor
		5305	sc = 5;
		5306	}
		5307
		5308	eval += sc - 10;
		5309
		5310	if (sc >= 10 && std::abs(square::file(op_king) - fl) <= 1) { // open file on king
		5311	int weight = (square::file(op_king) == fl) ? 2 : 1;
		5312	mg += sc * weight / 2;
		5313	}
		5314	}
		5315
		5316	if (pc == piece::ROOK && rk == square::RANK_7) { // 7th rank
		5317
		5318	bit_t pawns = bd.piece(piece::PAWN, xd) & bit::rank(square::rank(sq));
		5319
		5320	if (square::rank(op_king, sd) >= square::RANK_7 \|\| pawns != 0) {
		5321	mg += 10;
		5322	eg += 20;
		5323	}
		5324	}
		5325
		5326	if (pc == piece::KING) { // king out
		5327
		5328	int dl = (pi.left_file - 1) - fl;
		5329	if (dl > 0) eg -= dl * 20;
		5330
		5331	int dr = fl - (pi.right_file + 1);
		5332	if (dr > 0) eg -= dr * 20;
		5333	}
		5334	}
		5335	}
		5336
		5337	if (bd.count(piece::BISHOP, sd) >= 2) {
		5338	mg += 30;
		5339	eg += 50;
		5340	}
		5341
		5342	mg += shelter[sd];
		5343	mg += mul_shift(king_score(king_power * 30, king_n), 32 - shelter[xd], 5);
		5344
		5345	eval = -eval;
		5346	mg = -mg;
		5347	eg = -eg;
		5348	}
		5349
		5350	mg += pi.mg;
		5351	eg += pi.eg;
		5352
		5353	eval += eval_pattern(bd);
		5354
		5355	eval += material::interpolation(mg, eg, bd);
		5356
		5357	if (eval != 0) { // draw multiplier
		5358	int winner = (eval > 0) ? side::WHITE : side::BLACK;
		5359	eval = mul_shift(eval, draw_mul(winner, bd, pi), 4);
		5360	}
		5361
		5362	assert(eval >= score::EVAL_MIN && eval <= score::EVAL_MAX);
		5363	return eval;
		5364	}
		5365
		5366	int eval(board::Board & bd, Table & table, pawn::Table & pawn_table) {
		5367	return score::side_score(table.eval(bd, pawn_table), bd.turn());
		5368	}
		5369
		5370	void init() {
		5371
		5372	small_centre = 0;
		5373	medium_centre = 0;
		5374	large_centre = 0;
		5375
		5376	for (int sq = 0; sq < square::SIZE; sq++) {
		5377
		5378	int fl = square::file(sq);
		5379	int rk = square::rank(sq);
		5380
		5381	if (fl >= square::FILE_D && fl <= square::FILE_E && rk >= square::RANK_4 && rk <= square::RANK_5) {
		5382	bit::set(small_centre, sq);
		5383	}
		5384
		5385	if (fl >= square::FILE_C && fl <= square::FILE_F && rk >= square::RANK_3 && rk <= square::RANK_6) {
		5386	bit::set(medium_centre, sq);
		5387	}
		5388
		5389	if (fl >= square::FILE_B && fl <= square::FILE_G && rk >= square::RANK_2 && rk <= square::RANK_7) {
		5390	bit::set(large_centre, sq);
		5391	}
		5392	}
		5393
		5394	large_centre &= ~medium_centre;
		5395	medium_centre &= ~small_centre;
		5396
		5397	centre_0 = small_centre \| large_centre;
		5398	centre_1 = small_centre \| medium_centre;
		5399
		5400	side_area[side::WHITE] = 0;
		5401	side_area[side::BLACK] = 0;
		5402
		5403	for (int sq = 0; sq < square::SIZE; sq++) {
		5404	if (square::rank(sq) <= square::RANK_4) {
		5405	bit::set(side_area[side::WHITE], sq);
		5406	} else {
		5407	bit::set(side_area[side::BLACK], sq);
		5408	}
		5409	}
		5410
		5411	for (int ks = 0; ks < square::SIZE; ks++) {
		5412
		5413	king_area[side::WHITE][ks] = 0;
		5414	king_area[side::BLACK][ks] = 0;
		5415
		5416	for (int as = 0; as < square::SIZE; as++) {
		5417
		5418	int df = square::file(as) - square::file(ks);
		5419	int dr = square::rank(as) - square::rank(ks);
		5420
		5421	if (std::abs(df) <= 1 && dr >= -1 && dr <= +2) {
		5422	bit::set(king_area[side::WHITE][ks], as);
		5423	}
		5424
		5425	if (std::abs(df) <= 1 && dr >= -2 && dr <= +1) {
		5426	bit::set(king_area[side::BLACK][ks], as);
		5427	}
		5428	}
		5429	}
		5430
		5431	for (int i = 0; i < 32; i++) {
		5432	double x = double(i) * 0.5;
		5433	double y = 1.0 - std::exp(-x);
		5434	mob_weight[i] = util::round(y * 512.0) - 256;
		5435	}
		5436
		5437	for (int i = 0; i < 8; i++) {
		5438	double x = double(i) - 3.0;
		5439	double y = 1.0 / (1.0 + std::exp(-x));
		5440	dist_weight[i] = util::round(y * 7.0 * 256.0);
		5441	}
		5442	}
		5443
		5444	}
		5445
		5446	namespace uci {
		5447
		5448	bool infinite; // for UCI-design mistake :(
		5449
		5450	}
		5451
		5452	namespace search {
		5453
		5454	const int MAX_DEPTH = 100;
		5455	const int MAX_PLY = 100;
		5456	const int NODE_PERIOD = 1024;
		5457
		5458	const int MAX_THREADS = 16;
		5459
		5460	class Abort : public std::exception { // SP fail-high exception
		5461
		5462	};
		5463
		5464	void update_current ();
		5465
		5466	class PV {
		5467
		5468	private:
		5469
		5470	static const int SIZE = MAX_PLY;
		5471
		5472	int p_size;
		5473	int p_move[SIZE];
		5474
		5475	public:
		5476
		5477	PV() {
		5478	clear();
		5479	}
		5480
		5481	void operator=(const PV & pv) {
		5482	clear();
		5483	add(pv);
		5484	}
		5485
		5486	void clear() {
		5487	p_size = 0;
		5488	}
		5489
		5490	void add(int mv) {
		5491	if (p_size < SIZE) {
		5492	p_move[p_size++] = mv;
		5493	}
		5494	}
		5495
		5496	void add(const PV & pv) {
		5497	for (int pos = 0; pos < pv.size(); pos++) {
		5498	int mv = pv.move(pos);
		5499	add(mv);
		5500	}
		5501	}
		5502
		5503	void cat(int mv, const PV & pv) {
		5504	clear();
		5505	add(mv);
		5506	add(pv);
		5507	}
		5508
		5509	int size() const {
		5510	return p_size;
		5511	}
		5512
		5513	int move(int pos) const {
		5514	return p_move[pos];
		5515	}
		5516
		5517	std::string to_can() const {
		5518
		5519	std::string s;
		5520
		5521	for (int pos = 0; pos < size(); pos++) {
		5522	int mv = move(pos);
		5523	if (pos != 0) s += " ";
		5524	s += move::to_can(mv);
		5525	}
		5526
		5527	return s;
		5528	}
		5529
		5530	};
		5531
		5532	struct Time {
		5533	bool depth_limited;
		5534	bool node_limited;
		5535	bool time_limited;
		5536	int depth_limit;
		5537	int64 node_limit;
		5538	int64 time_limit;
		5539	bool smart;
		5540	bool ponder;
		5541	bool flag;
		5542	int64 limit_0;
		5543	int64 limit_1;
		5544	int64 limit_2;
		5545	int last_score;
		5546	bool drop;
		5547	util::Timer timer;
		5548	};
		5549
		5550	struct Current {
		5551
		5552	int depth;
		5553	int max_ply;
		5554	int64 node;
		5555	int time;
		5556	int speed;
		5557
		5558	int move;
		5559	int pos;
		5560	int size;
		5561	bool fail_high;
		5562
		5563	int last_time;
		5564	};
		5565
		5566	struct Best {
		5567	int depth;
		5568	int move;
		5569	int score;
		5570	int flags;
		5571	PV pv;
		5572	};
		5573
		5574	Time p_time;
		5575	Current current;
		5576	Best best;
		5577
		5578	class Search_Global : public util::Lockable {
		5579
		5580	public:
		5581
		5582	trans::Table trans;
		5583	sort::History history;
		5584
		5585	};
		5586
		5587	Search_Global sg;
		5588
		5589	class SMP : public util::Lockable {
		5590
		5591	};
		5592
		5593	SMP smp;
		5594
		5595	class Search_Local;
		5596	class Split_Point;
		5597
		5598	//void clear_iteration(Search_Local & sl); // Pierre-Marie Baty -- function not found
		5599	void search_root(Search_Local & sl, gen::List & ml, int depth, int alpha, int beta);
		5600	int search(Search_Local & sl, int depth, int alpha, int beta, PV & pv);
		5601	int split(Search_Local & sl, int depth, int old_alpha, int alpha, int beta, PV & pv, gen_sort::List & todo, const gen::List & done, int bs, int bm);
		5602	void master_split_point(Search_Local & sl, Split_Point & sp);
		5603	void search_split_point(Search_Local & sl, Split_Point & sp);
		5604	int qs_static(Search_Local & sl, int beta, int gain);
		5605	void inc_node(Search_Local & sl);
		5606	bool poll();
		5607	void move(Search_Local & sl, int mv);
		5608	void undo(Search_Local & sl);
		5609	int eval(Search_Local & sl);
		5610	int extension(Search_Local & sl, int mv, int depth, bool pv_node);
		5611	static int reduction(Search_Local & sl, int mv, int depth, bool pv_node, bool in_check, int searched_size, bool dangerous);
		5612	void gen_sort(Search_Local & sl, gen::List & ml);
		5613
		5614	void sg_abort ();
		5615
		5616	void sl_init_early (Search_Local & sl, int id);
		5617	void sl_init_late (Search_Local & sl);
		5618	void sl_set_root (Search_Local & sl, const board::Board & bd);
		5619	void sl_signal (Search_Local & sl);
		5620	bool sl_stop (const Search_Local & sl);
		5621	bool sl_idle (const Search_Local & sl, Split_Point * sp);
		5622	void sl_push (Search_Local & sl, Split_Point & sp);
		5623	void sl_pop (Search_Local & sl);
		5624	Split_Point & sl_top (const Search_Local & sl);
		5625
		5626	class Split_Point : public util::Lockable {
		5627
		5628	private:
		5629
		5630	Search_Local * p_master;
		5631	Split_Point * p_parent;
		5632
		5633	board::Board p_board;
		5634	int p_depth;
		5635	int p_old_alpha;
		5636	int volatile p_alpha;
		5637	int p_beta;
		5638
		5639	gen::List p_todo;
		5640	gen::List p_done;
		5641
		5642	int volatile p_workers;
		5643	int volatile p_sent;
		5644	int volatile p_received;
		5645
		5646	int volatile p_bs;
		5647	int volatile p_bm;
		5648	PV p_pv;
		5649
		5650	public:
		5651
		5652	void init_root(Search_Local & master) {
		5653
		5654	p_master = &master;
		5655	p_parent = NULL;
		5656
		5657	p_bs = score::NONE;
		5658	p_beta = score::MAX;
		5659	p_todo.clear();
		5660
		5661	p_workers = 1;
		5662	p_received = -1; // HACK
		5663	}
		5664
		5665	void init(Search_Local & master, Split_Point & parent, const board::Board & bd, int depth, int old_alpha, int alpha, int beta, gen_sort::List & todo, const gen::List & done, int bs, int bm, const PV & pv) {
		5666
		5667	assert(depth > 4);
		5668	assert(old_alpha <= alpha);
		5669	assert(alpha < beta);
		5670	assert(done.size() != 0);
		5671	assert(bs != score::NONE);
		5672
		5673	p_master = &master;
		5674	p_parent = &parent;
		5675
		5676	p_board = bd;
		5677	p_depth = depth;
		5678	p_old_alpha = old_alpha;
		5679	p_alpha = alpha;
		5680	p_beta = beta;
		5681
		5682	p_todo.clear();
		5683
		5684	for (int mv = todo.next(); mv != move::NONE; mv = todo.next()) {
		5685	p_todo.add(mv);
		5686	}
		5687
		5688	p_done = done;
		5689
		5690	p_workers = 0;
		5691	p_sent = 0;
		5692	p_received = 0;
		5693
		5694	p_bs = bs;
		5695	p_bm = bm;
		5696	p_pv = pv;
		5697	}
		5698
		5699	void enter() {
		5700	lock();
		5701	p_workers++;
		5702	unlock();
		5703	}
		5704
		5705	void leave() {
		5706
		5707	lock();
		5708
		5709	assert(p_workers > 0);
		5710	p_workers--;
		5711
		5712	if (p_workers == 0) sl_signal(*p_master);
		5713
		5714	unlock();
		5715	}
		5716
		5717	int next_move() {
		5718
		5719	// lock();
		5720
		5721	int mv = move::NONE;
		5722
		5723	if (p_bs < p_beta && p_sent < p_todo.size()) {
		5724	mv = p_todo.move(p_sent++);
		5725	}
		5726
		5727	// unlock();
		5728
		5729	return mv;
		5730	}
		5731
		5732	void update_root() {
		5733	lock();
		5734	p_received = 0;
		5735	p_workers = 0;
		5736	unlock();
		5737	}
		5738
		5739	void update(int mv, int sc, const PV & pv) {
		5740
		5741	lock();
		5742
		5743	p_done.add(mv);
		5744
		5745	assert(p_received < p_todo.size());
		5746	p_received++;
		5747
		5748	if (sc > p_bs) {
		5749
		5750	p_bs = sc;
		5751	p_pv.cat(mv, pv);
		5752
		5753	if (sc > p_alpha) {
		5754	p_bm = mv;
		5755	p_alpha = sc;
		5756	}
		5757	}
		5758
		5759	unlock();
		5760	}
		5761
		5762	const board::Board & board() const { return p_board; }
		5763
		5764	Split_Point * parent() const { return p_parent; }
		5765
		5766	int depth() const { return p_depth; }
		5767	int alpha() const { return p_alpha; }
		5768	int beta() const { return p_beta; }
		5769	int old_alpha() const { return p_old_alpha; }
		5770	int bs() const { return p_bs; }
		5771	int bm() const { return p_bm; }
		5772	bool solved() const { return p_bs >= p_beta \|\| p_received == p_todo.size(); }
		5773	bool free() const { return p_workers == 0; }
		5774
		5775	const gen::List & searched() const { return p_done; }
		5776	int searched_size() const { return p_done.size(); }
		5777
		5778	int result(PV & pv) const {
		5779	pv = p_pv;
		5780	return p_bs;
		5781	}
		5782
		5783	};
		5784
		5785	Split_Point root_sp;
		5786
		5787	class Search_Local : public util::Waitable {
		5788
		5789	public:
		5790
		5791	int id;
		5792	std::thread thread;
		5793
		5794	bool volatile todo;
		5795	Split_Point * volatile todo_sp;
		5796
		5797	board::Board board;
		5798	sort::Killer killer;
		5799	pawn::Table pawn_table;
		5800	eval::Table eval_table;
		5801
		5802	int64 volatile node;
		5803	int volatile max_ply;
		5804
		5805	Split_Point msp_stack[16];
		5806	int msp_stack_size;
		5807
		5808	Split_Point * ssp_stack[64];
		5809	int ssp_stack_size;
		5810	};
		5811
		5812	Search_Local p_sl[MAX_THREADS];
		5813
		5814	void new_search() {
		5815
		5816	p_time.depth_limited = true;
		5817	p_time.node_limited = false;
		5818	p_time.time_limited = false;
		5819
		5820	p_time.depth_limit = MAX_DEPTH - 1;
		5821
		5822	p_time.smart = false;
		5823	p_time.ponder = false;
		5824	}
		5825
		5826	void set_depth_limit(int depth) {
		5827	p_time.depth_limited = true;
		5828	p_time.depth_limit = depth;
		5829	}
		5830
		5831	void set_node_limit(int64 node) {
		5832	p_time.node_limited = true;
		5833	p_time.node_limit = node;
		5834	}
		5835
		5836	void set_time_limit(int64 time) {
		5837	p_time.time_limited = true;
		5838	p_time.time_limit = time;
		5839	}
		5840
		5841	void set_ponder() {
		5842	p_time.ponder = true;
		5843	}
		5844
		5845	void clear() {
		5846
		5847	p_time.flag = false;
		5848	p_time.timer.reset();
		5849	p_time.timer.start();
		5850
		5851	current.depth = 0;
		5852	current.max_ply = 0;
		5853	current.node = 0;
		5854	current.time = 0;
		5855	current.speed = 0;
		5856
		5857	current.move = move::NONE;
		5858	current.pos = 0;
		5859	current.size = 0;
		5860	current.fail_high = false;
		5861
		5862	current.last_time = 0;
		5863
		5864	best.depth = 0;
		5865	best.move = move::NONE;
		5866	best.score = score::NONE;
		5867	best.flags = score::FLAGS_NONE;
		5868	best.pv.clear();
		5869	}
		5870
		5871	void update_current() {
		5872
		5873	int64 node = 0;
		5874	int max_ply = 0;
		5875
		5876	for (int id = 0; id < engine::engine.threads; id++) {
		5877
		5878	Search_Local & sl = p_sl[id];
		5879
		5880	node += sl.node;
		5881	if (sl.max_ply > max_ply) max_ply = sl.max_ply;
		5882	}
		5883
		5884	current.node = node;
		5885	current.max_ply = max_ply;
		5886
		5887	current.time = p_time.timer.elapsed();
		5888	current.speed = (current.time < 10) ? 0 : int(current.node * 1000 / current.time);
		5889	}
		5890
		5891	void write_pv(Best & best) {
		5892
		5893	sg.lock();
		5894
		5895	std::cout << "info";
		5896	std::cout << " depth " << best.depth;
		5897	std::cout << " seldepth " << current.max_ply;
		5898	std::cout << " nodes " << current.node;
		5899	std::cout << " time " << current.time;
		5900
		5901	if (score::is_mate(best.score)) {
		5902	std::cout << " score mate " << score::signed_mate(best.score);
		5903	} else {
		5904	std::cout << " score cp " << best.score;
		5905	}
		5906	if (best.flags == score::FLAGS_LOWER) std::cout << " lowerbound";
		5907	if (best.flags == score::FLAGS_UPPER) std::cout << " upperbound";
		5908
		5909	std::cout << " pv " << best.pv.to_can();
		5910	std::cout << std::endl;
		5911
		5912	sg.unlock();
		5913	}
		5914
		5915	void write_info() {
		5916
		5917	sg.lock();
		5918
		5919	std::cout << "info";
		5920	std::cout << " depth " << current.depth;
		5921	std::cout << " seldepth " << current.max_ply;
		5922	std::cout << " currmove " << move::to_can(current.move);
		5923	std::cout << " currmovenumber " << current.pos + 1;
		5924	std::cout << " nodes " << current.node;
		5925	std::cout << " time " << current.time;
		5926	if (current.speed != 0) std::cout << " nps " << current.speed;
		5927	std::cout << " hashfull " << sg.trans.used();
		5928	std::cout << std::endl;
		5929
		5930	sg.unlock();
		5931	}
		5932
		5933	void write_info_opt() {
		5934
		5935	int time = current.time;
		5936
		5937	if (time >= current.last_time + 1000) {
		5938	write_info();
		5939	current.last_time = time - time % 1000;
		5940	}
		5941	}
		5942
		5943	void depth_start(int depth) {
		5944	current.depth = depth;
		5945	}
		5946
		5947	void depth_end() {
		5948	}
		5949
		5950	void move_start(int mv, int pos, int size) {
		5951
		5952	assert(size > 0);
		5953	assert(pos < size);
		5954
		5955	current.move = mv;
		5956	current.pos = pos;
		5957	current.size = size;
		5958
		5959	current.fail_high = false;
		5960	}
		5961
		5962	void move_fail_high() {
		5963	current.fail_high = true;
		5964	p_time.flag = false;
		5965	}
		5966
		5967	void move_end() {
		5968	current.fail_high = false;
		5969	}
		5970
		5971	void update_best(Best & best, int sc, int flags, const PV & pv) {
		5972
		5973	assert(sc != score::NONE);
		5974	assert(pv.size() != 0);
		5975
		5976	p_time.drop = flags == score::FLAGS_UPPER \|\| (sc <= p_time.last_score - 30 && current.size > 1);
		5977
		5978	if (pv.move(0) != best.move \|\| p_time.drop) {
		5979	p_time.flag = false;
		5980	}
		5981
		5982	best.depth = current.depth;
		5983	best.move = pv.move(0);
		5984	best.score = sc;
		5985	best.flags = flags;
		5986	best.pv = pv;
		5987	}
		5988
		5989	void search_end() {
		5990	p_time.timer.stop();
		5991	update_current();
		5992	write_info();
		5993	}
		5994
		5995	void idle_loop(Search_Local & sl, Split_Point & wait_sp) {
		5996
		5997	sl_push(sl, wait_sp);
		5998
		5999	while (true) {
		6000
		6001	sl.lock();
		6002
		6003	assert(sl.todo);
		6004	assert(sl.todo_sp == NULL);
		6005
		6006	sl.todo = false;
		6007	sl.todo_sp = NULL;
		6008
		6009	while (!wait_sp.free() && sl.todo_sp == NULL) {
		6010	sl.wait();
		6011	}
		6012
		6013	Split_Point & sp = *sl.todo_sp;
		6014	sl.todo = true;
		6015	sl.todo_sp = NULL;
		6016
		6017	sl.unlock();
		6018
		6019	if (&sp == NULL) {
		6020	break;
		6021	}
		6022
		6023	// sp.enter();
		6024
		6025	sl_push(sl, sp);
		6026
		6027	try {
		6028	search_split_point(sl, sp);
		6029	} catch (const Abort & /* abort */) {
		6030	// no-op
		6031	}
		6032
		6033	sl_pop(sl);
		6034
		6035	sp.leave();
		6036	}
		6037
		6038	sl_pop(sl);
		6039	}
		6040
		6041	void helper_program(Search_Local * sl) {
		6042	sl_init_late(*sl);
		6043	idle_loop(*sl, root_sp);
		6044	}
		6045
		6046	bool can_split(Search_Local & master, Split_Point & parent) {
		6047
		6048	if (engine::engine.threads == 1) return false;
		6049	if (master.msp_stack_size >= 16) return false;
		6050	if (sl_stop(master)) return false;
		6051
		6052	for (int id = 0; id < engine::engine.threads; id++) {
		6053	Search_Local & worker = p_sl[id];
		6054	if (&worker != &master && sl_idle(worker, &parent)) return true;
		6055	}
		6056
		6057	return false;
		6058	}
		6059
		6060	void send_work(Search_Local & worker, Split_Point & sp) {
		6061
		6062	worker.lock();
		6063
		6064	if (sl_idle(worker, sp.parent())) {
		6065
		6066	sp.enter();
		6067
		6068	worker.todo = true;
		6069	worker.todo_sp = &sp;
		6070	worker.signal();
		6071	}
		6072
		6073	worker.unlock();
		6074	}
		6075
		6076	void init_sg() {
		6077	sg.history.clear();
		6078	}
		6079
		6080	void search_root(Search_Local & sl, gen::List & ml, int depth, int alpha, int beta) {
		6081
		6082	assert(depth > 0 && depth < MAX_DEPTH);
		6083	assert(alpha < beta);
		6084
		6085	board::Board & bd = sl.board;
		6086	assert(attack::is_legal(bd));
		6087
		6088	bool pv_node = true;
		6089
		6090	int bs = score::NONE;
		6091	int bm = move::NONE;
		6092	int old_alpha = alpha;
		6093
		6094	// transposition table
		6095
		6096	hash_t key = 0;
		6097
		6098	if (depth >= 0) {
		6099	key = bd.key();
		6100	}
		6101
		6102	// move loop
		6103
		6104	bool in_check = attack::is_in_check(bd);
		6105
		6106	int searched_size = 0;
		6107
		6108	for (int pos = 0; pos < ml.size(); pos++) {
		6109
		6110	int mv = ml.move(pos);
		6111
		6112	bool dangerous = in_check \|\| move::is_tactical(mv) \|\| move::is_check(mv, bd) \|\| move::is_castling(mv) \|\| move::is_pawn_push(mv, bd);
		6113
		6114	int ext = extension(sl, mv, depth, pv_node);
		6115	int red = reduction(sl, mv, depth, pv_node, in_check, searched_size, dangerous); // LMR
		6116
		6117	if (ext != 0) red = 0;
		6118	assert(ext == 0 \|\| red == 0);
		6119
		6120	int sc;
		6121	PV npv;
		6122
		6123	move_start(mv, pos, ml.size());
		6124
		6125	move(sl, mv);
		6126
		6127	if ((pv_node && searched_size != 0) \|\| red != 0) {
		6128
		6129	sc = -search(sl, depth + ext - red - 1, -alpha - 1, -alpha, npv);
		6130
		6131	if (sc > alpha) { // PVS/LMR re-search
		6132	move_fail_high();
		6133	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6134	}
		6135
		6136	} else {
		6137
		6138	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6139	}
		6140
		6141	undo(sl);
		6142
		6143	move_end();
		6144
		6145	searched_size++;
		6146
		6147	if (sc > bs) {
		6148
		6149	bs = sc;
		6150
		6151	PV pv;
		6152	pv.cat(mv, npv);
		6153
		6154	update_best(best, sc, score::flags(sc, alpha, beta), pv);
		6155
		6156	update_current();
		6157	write_pv(best);
		6158
		6159	if (sc > alpha) {
		6160
		6161	bm = mv;
		6162	alpha = sc;
		6163
		6164	// ml.set_score(pos, sc); // not needed
		6165	ml.move_to_front(pos);
		6166
		6167	if (depth >= 0) {
		6168	sg.trans.store(key, depth, bd.ply(), mv, sc, score::FLAGS_LOWER);
		6169	}
		6170
		6171	if (sc >= beta) return;
		6172	}
		6173	}
		6174	}
		6175
		6176	assert(bs != score::NONE);
		6177	assert(bs < beta);
		6178
		6179	if (depth >= 0) {
		6180	int flags = score::flags(bs, old_alpha, beta);
		6181	sg.trans.store(key, depth, bd.ply(), bm, bs, flags);
		6182	}
		6183	}
		6184
		6185	int search(Search_Local & sl, int depth, int alpha, int beta, PV & pv) {
		6186
		6187	assert(depth < MAX_DEPTH);
		6188	assert(alpha < beta);
		6189
		6190	board::Board & bd = sl.board;
		6191	assert(attack::is_legal(bd));
		6192
		6193	pv.clear();
		6194
		6195	bool pv_node = depth > 0 && beta != alpha + 1;
		6196
		6197	// mate-distance pruning
		6198
		6199	{
		6200	int sc = score::from_trans(score::MATE - 1, bd.ply());
		6201
		6202	if (sc < beta) {
		6203
		6204	beta = sc;
		6205
		6206	if (sc <= alpha) {
		6207	return sc;
		6208	}
		6209	}
		6210	}
		6211
		6212	// transposition table
		6213
		6214	if (bd.is_draw()) return 0;
		6215
		6216	attack::Attacks attacks;
		6217	attack::init_attacks(attacks, bd);
		6218	bool in_check = attacks.size != 0;
		6219
		6220	bool use_trans = depth >= 0;
		6221	int trans_depth = depth;
		6222
		6223	if (depth < 0 && in_check) {
		6224	use_trans = true;
		6225	trans_depth = 0;
		6226	}
		6227
		6228	hash_t key = 0;
		6229	int trans_move = move::NONE;
		6230
		6231	if (use_trans) {
		6232
		6233	key = bd.key();
		6234
		6235	int score;
		6236	int flags;
		6237
		6238	if (sg.trans.retrieve(key, trans_depth, bd.ply(), trans_move, score, flags) && !pv_node) { // assigns trans_move #
		6239	if (flags == score::FLAGS_LOWER && score >= beta) return score;
		6240	if (flags == score::FLAGS_UPPER && score <= alpha) return score;
		6241	if (flags == score::FLAGS_EXACT) return score;
		6242	}
		6243	}
		6244
		6245	// ply limit
		6246
		6247	if (bd.ply() >= MAX_PLY) return eval(sl);
		6248
		6249	// beta pruning
		6250
		6251	if (!pv_node && depth > 0 && depth <= 3 && !score::is_mate(beta) && !in_check) {
		6252
		6253	int sc = eval(sl) - depth * 50;
		6254
		6255	if (sc >= beta) {
		6256	return sc;
		6257	}
		6258	}
		6259
		6260	// null-move pruning
		6261
		6262	if (!pv_node && depth > 0 && !score::is_mate(beta) && !in_check && !material::lone_king(bd.turn(), bd) && eval(sl) >= beta) {
		6263
		6264	bd.move_null(); // TODO: use sl?
		6265
		6266	int sc = score::MIN;
		6267
		6268	if (depth <= 3) { // static
		6269	sc = -qs_static(sl, -beta + 1, 100);
		6270	} else { // dynamic
		6271	PV npv;
		6272	sc = -search(sl, depth - 3 - 1, -beta, -beta + 1, npv);
		6273	}
		6274
		6275	bd.undo_null(); // TODO: use sl?
		6276
		6277	if (sc >= beta) {
		6278
		6279	if (use_trans) {
		6280	sg.trans.store(key, trans_depth, bd.ply(), move::NONE, sc, score::FLAGS_LOWER);
		6281	}
		6282
		6283	return sc;
		6284	}
		6285	}
		6286
		6287	// stand pat
		6288
		6289	int bs = score::NONE;
		6290	int bm = move::NONE;
		6291	int old_alpha = alpha;
		6292	int val = score::NONE; // for delta pruning
		6293
		6294	if (depth <= 0 && !in_check) {
		6295
		6296	bs = eval(sl);
		6297	val = bs + 100; // QS-DP margin
		6298
		6299	if (bs > alpha) {
		6300
		6301	alpha = bs;
		6302
		6303	if (bs >= beta) {
		6304	return bs;
		6305	}
		6306	}
		6307	}
		6308
		6309	// futility-pruning condition
		6310
		6311	bool use_fp = false;
		6312
		6313	if (depth > 0 && depth <= 8 && !score::is_mate(alpha) && !in_check) {
		6314
		6315	int sc = eval(sl) + depth * 40;
		6316	val = sc + 50; // FP-DP margin, extra 50 for captures
		6317
		6318	if (sc <= alpha) {
		6319	bs = sc;
		6320	use_fp = true;
		6321	}
		6322	}
		6323
		6324	if (depth <= 0 && !in_check) { // unify FP and QS
		6325	use_fp = true;
		6326	}
		6327
		6328	// IID
		6329
		6330	if (pv_node && depth >= 3 && trans_move == move::NONE) {
		6331
		6332	PV npv;
		6333	int sc = search(sl, depth - 2, alpha, beta, npv); // to keep PV-node property
		6334
		6335	if (sc > alpha && npv.size() != 0) {
		6336	trans_move = npv.move(0);
		6337	}
		6338	}
		6339
		6340	// move loop
		6341
		6342	gen_sort::List ml;
		6343	ml.init(depth, bd, attacks, trans_move, sl.killer, sg.history, use_fp);
		6344
		6345	gen::List searched;
		6346
		6347	for (int mv = ml.next(); mv != move::NONE; mv = ml.next()) {
		6348
		6349	bool dangerous = in_check \|\| move::is_tactical(mv) \|\| move::is_check(mv, bd) \|\| move::is_castling(mv) \|\| move::is_pawn_push(mv, bd) \|\| ml.is_candidate();
		6350
		6351	if (use_fp && move::is_tactical(mv) && !move::is_check(mv, bd) && val + move::see_max(mv) <= alpha) { // delta pruning
		6352	continue;
		6353	}
		6354
		6355	if (use_fp && !move::is_safe(mv, bd)) { // SEE pruning
		6356	continue;
		6357	}
		6358
		6359	if (!pv_node && depth > 0 && depth <= 3 && !score::is_mate(bs) && searched.size() >= depth * 4 && !dangerous) { // late-move pruning
		6360	continue;
		6361	}
		6362
		6363	int ext = extension(sl, mv, depth, pv_node);
		6364	int red = reduction(sl, mv, depth, pv_node, in_check, searched.size(), dangerous); // LMR
		6365
		6366	if (ext != 0) red = 0;
		6367	assert(ext == 0 \|\| red == 0);
		6368
		6369	int sc;
		6370	PV npv;
		6371
		6372	move(sl, mv);
		6373
		6374	if ((pv_node && searched.size() != 0) \|\| red != 0) {
		6375
		6376	sc = -search(sl, depth + ext - red - 1, -alpha - 1, -alpha, npv);
		6377
		6378	if (sc > alpha) { // PVS/LMR re-search
		6379	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6380	}
		6381
		6382	} else {
		6383
		6384	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6385	}
		6386
		6387	undo(sl);
		6388
		6389	searched.add(mv);
		6390
		6391	if (sc > bs) {
		6392
		6393	bs = sc;
		6394	pv.cat(mv, npv);
		6395
		6396	if (sc > alpha) {
		6397
		6398	bm = mv;
		6399	alpha = sc;
		6400
		6401	if (use_trans) {
		6402	sg.trans.store(key, trans_depth, bd.ply(), mv, sc, score::FLAGS_LOWER);
		6403	}
		6404
		6405	if (sc >= beta) {
		6406
		6407	if (depth > 0 && !in_check && !move::is_tactical(mv)) {
		6408	sl.killer.add(mv, bd.ply());
		6409	sg.history.add(mv, searched, bd);
		6410	}
		6411
		6412	return sc;
		6413	}
		6414	}
		6415	}
		6416
		6417	if (depth >= 6 && !in_check && !use_fp && can_split(sl, sl_top(sl))) {
		6418	return split(sl, depth, old_alpha, alpha, beta, pv, ml, searched, bs, bm);
		6419	}
		6420	}
		6421
		6422	if (bs == score::NONE) {
		6423	assert(depth > 0 \|\| in_check);
		6424	return in_check ? -score::MATE + bd.ply() : 0;
		6425	}
		6426
		6427	assert(bs < beta);
		6428
		6429	if (use_trans) {
		6430	int flags = score::flags(bs, old_alpha, beta);
		6431	sg.trans.store(key, trans_depth, bd.ply(), bm, bs, flags);
		6432	}
		6433
		6434	return bs;
		6435	}
		6436
		6437	int split(Search_Local & master, int depth, int old_alpha, int alpha, int beta, PV & pv, gen_sort::List & todo, const gen::List & done, int bs, int bm) {
		6438
		6439	smp.lock();
		6440
		6441	assert(master.msp_stack_size < 16);
		6442	Split_Point & sp = master.msp_stack[master.msp_stack_size++];
		6443
		6444	Split_Point & parent = sl_top(master);
		6445
		6446	sp.init(master, parent, master.board, depth, old_alpha, alpha, beta, todo, done, bs, bm, pv);
		6447
		6448	for (int id = 0; id < engine::engine.threads; id++) {
		6449
		6450	Search_Local & worker = p_sl[id];
		6451
		6452	if (&worker != &master && sl_idle(worker, &parent)) {
		6453	send_work(worker, sp);
		6454	}
		6455	}
		6456
		6457	smp.unlock();
		6458
		6459	try {
		6460	master_split_point(master, sp);
		6461	} catch (const Abort & /* abort */) {
		6462	// no-op
		6463	}
		6464
		6465	assert(master.msp_stack_size > 0);
		6466	assert(&master.msp_stack[master.msp_stack_size - 1] == &sp);
		6467	master.msp_stack_size--;
		6468
		6469	return sp.result(pv);
		6470	}
		6471
		6472	void master_split_point(Search_Local & sl, Split_Point & sp) {
		6473
		6474	sp.enter();
		6475
		6476	sl_push(sl, sp);
		6477
		6478	try {
		6479	search_split_point(sl, sp);
		6480	} catch (const Abort & /* abort */) {
		6481	// no-op
		6482	}
		6483
		6484	sl_pop(sl);
		6485
		6486	sp.leave();
		6487
		6488	idle_loop(sl, sp);
		6489	sl.board = sp.board();
		6490
		6491	assert(sp.free());
		6492
		6493	// update move-ordering tables
		6494
		6495	board::Board & bd = sl.board;
		6496
		6497	int depth = sp.depth();
		6498	int ply = bd.ply();
		6499
		6500	int bs = sp.bs();
		6501	int bm = sp.bm();
		6502
		6503	assert(bs != score::NONE);
		6504
		6505	if (bs >= sp.beta() && depth > 0 && !attack::is_in_check(bd) && !move::is_tactical(bm)) {
		6506	sl.killer.add(bm, ply);
		6507	sg.history.add(bm, sp.searched(), bd);
		6508	}
		6509
		6510	if (depth >= 0) {
		6511	int flags = score::flags(bs, sp.old_alpha(), sp.beta());
		6512	sg.trans.store(bd.key(), depth, ply, bm, bs, flags);
		6513	}
		6514	}
		6515
		6516	void search_split_point(Search_Local & sl, Split_Point & sp) {
		6517
		6518	board::Board & bd = sl.board;
		6519	bd = sp.board();
		6520
		6521	int depth = sp.depth();
		6522	int old_alpha = sp.old_alpha();
		6523	int beta = sp.beta();
		6524
		6525	bool pv_node = depth > 0 && beta != old_alpha + 1;
		6526
		6527	bool in_check = attack::is_in_check(bd);
		6528
		6529	while (true) {
		6530
		6531	sp.lock();
		6532	int mv = sp.next_move();
		6533	int alpha = sp.alpha();
		6534	int searched_size = sp.searched_size();
		6535	sp.unlock();
		6536
		6537	if (mv == move::NONE) {
		6538	break;
		6539	}
		6540
		6541	assert(alpha < beta);
		6542
		6543	bool dangerous = in_check \|\| move::is_tactical(mv) \|\| move::is_check(mv, bd) \|\| move::is_castling(mv) \|\| move::is_pawn_push(mv, bd);
		6544
		6545	int ext = extension(sl, mv, depth, pv_node);
		6546	int red = reduction(sl, mv, depth, pv_node, in_check, searched_size, dangerous); // LMR
		6547
		6548	if (ext != 0) red = 0;
		6549	assert(ext == 0 \|\| red == 0);
		6550
		6551	int sc;
		6552	PV npv;
		6553
		6554	move(sl, mv);
		6555
		6556	if ((pv_node && searched_size != 0) \|\| red != 0) {
		6557
		6558	sc = -search(sl, depth + ext - red - 1, -alpha - 1, -alpha, npv);
		6559
		6560	if (sc > alpha) { // PVS/LMR re-search
		6561	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6562	}
		6563
		6564	} else {
		6565
		6566	sc = -search(sl, depth + ext - 1, -beta, -alpha, npv);
		6567	}
		6568
		6569	undo(sl);
		6570
		6571	sp.update(mv, sc, npv);
		6572	}
		6573	}
		6574
		6575	int qs_static(Search_Local & sl, int beta, int gain) { // for static NMP
		6576
		6577	board::Board & bd = sl.board;
		6578
		6579	assert(attack::is_legal(bd));
		6580	// assert(!attack::is_in_check()); // triggers for root move ordering
		6581
		6582	// stand pat
		6583
		6584	int bs = eval(sl);
		6585	int val = bs + gain;
		6586
		6587	if (bs >= beta) {
		6588	return bs;
		6589	}
		6590
		6591	// move loop
		6592
		6593	attack::Attacks attacks;
		6594	attack::init_attacks(attacks, bd);
		6595
		6596	gen_sort::List ml;
		6597	ml.init(-1, bd, attacks, move::NONE, sl.killer, sg.history, false); // QS move generator
		6598
		6599	bit_t done = 0;
		6600
		6601	for (int mv = ml.next(); mv != move::NONE; mv = ml.next()) {
		6602
		6603	if (bit::is_set(done, move::to(mv))) { // process only LVA capture for each opponent piece
		6604	continue;
		6605	}
		6606
		6607	bit::set(done, move::to(mv));
		6608
		6609	int see = move::see(mv, 0, score::EVAL_MAX, bd); // TODO: beta - val?
		6610	if (see <= 0) continue; // don't consider equal captures as "threats"
		6611
		6612	int sc = val + see;
		6613
		6614	if (sc > bs) {
		6615
		6616	bs = sc;
		6617
		6618	if (sc >= beta) {
		6619	return sc;
		6620	}
		6621	}
		6622	}
		6623
		6624	assert(bs < beta);
		6625
		6626	return bs;
		6627	}
		6628
		6629	void inc_node(Search_Local & sl) {
		6630
		6631	sl.node++;
		6632
		6633	if (sl.node % NODE_PERIOD == 0) {
		6634
		6635	bool abort = false;
		6636
		6637	update_current();
		6638
		6639	if (poll()) abort = true;
		6640
		6641	if (p_time.node_limited && current.node >= p_time.node_limit) {
		6642	abort = true;
		6643	}
		6644
		6645	if (p_time.time_limited && current.time >= p_time.time_limit) {
		6646	abort = true;
		6647	}
		6648
		6649	if (p_time.smart && current.depth > 1 && current.time >= p_time.limit_0) {
		6650	if (current.pos == 0 \|\| current.time >= p_time.limit_1) {
		6651	if (!(p_time.drop \|\| current.fail_high) \|\| current.time >= p_time.limit_2) {
		6652	if (p_time.ponder) {
		6653	p_time.flag = true;
		6654	} else {
		6655	abort = true;
		6656	}
		6657	}
		6658	}
		6659	}
		6660
		6661	if (p_time.smart && current.depth > 1 && current.size == 1 && current.time >= p_time.limit_0 / 8) {
		6662	if (p_time.ponder) {
		6663	p_time.flag = true;
		6664	} else {
		6665	abort = true;
		6666	}
		6667	}
		6668
		6669	if (abort) sg_abort();
		6670	}
		6671
		6672	if (sl_stop(sl)) throw Abort();
		6673	}
		6674
		6675	bool poll() {
		6676
		6677	write_info_opt();
		6678
		6679	sg.lock();
		6680
		6681	if (!input::input.has_input()) {
		6682	sg.unlock();
		6683	return false;
		6684	}
		6685
		6686	std::string line;
		6687	bool eof = !input::input.get_line(line);
		6688	if (engine::engine.log) util::log(line);
		6689
		6690	sg.unlock();
		6691
		6692	if (false) {
		6693	} else if (eof) {
		6694	std::exit(EXIT_SUCCESS);
		6695	} else if (line == "isready") {
		6696	std::cout << "readyok" << std::endl;
		6697	return false;
		6698	} else if (line == "stop") {
		6699	uci::infinite = false;
		6700	return true;
		6701	} else if (line == "ponderhit") {
		6702	uci::infinite = false;
		6703	p_time.ponder = false;
		6704	return p_time.flag;
		6705	} else if (line == "quit") {
		6706	#ifdef _MSC_VER
		6707	ExitProcess (0); // Pierre-Marie Baty -- use ExitProcess() instead of std::exit() on Win32 apps
		6708	#else // !_MSC_VER
		6709	std::exit (EXIT_SUCCESS);
		6710	#endif // _MSC_VER
		6711	}
		6712
		6713	return false;
		6714	}
		6715
		6716	void move(Search_Local & sl, int mv) {
		6717
		6718	board::Board & bd = sl.board;
		6719
		6720	inc_node(sl);
		6721	bd.move(mv);
		6722
		6723	int ply = bd.ply();
		6724
		6725	if (ply > sl.max_ply) {
		6726	assert(ply <= MAX_PLY);
		6727	sl.max_ply = ply;
		6728	}
		6729	}
		6730
		6731	void undo(Search_Local & sl) {
		6732	board::Board & bd = sl.board;
		6733	bd.undo();
		6734	}
		6735
		6736	int eval(Search_Local & sl) {
		6737	board::Board & bd = sl.board;
		6738	return eval::eval(bd, sl.eval_table, sl.pawn_table);
		6739	}
		6740
		6741	int extension(Search_Local & sl, int mv, int depth, bool pv_node) {
		6742
		6743	board::Board & bd = sl.board;
		6744
		6745	if ((depth <= 4 && move::is_check(mv, bd))
		6746	\|\| (depth <= 4 && move::is_recapture(mv, bd))
		6747	\|\| (pv_node && move::is_check(mv, bd))
		6748	\|\| (pv_node && move::is_tactical(mv) && move::is_win(mv, bd))
		6749	\|\| (pv_node && move::is_pawn_push(mv, bd))) {
		6750	return 1;
		6751	} else {
		6752	return 0;
		6753	}
		6754	}
		6755
		6756	int reduction(Search_Local & /* sl /, int / mv /, int depth, bool / pv_node /, bool / in_check */, int searched_size, bool dangerous) {
		6757
		6758	int red = 0;
		6759
		6760	if (depth >= 3 && searched_size >= 3 && !dangerous) {
		6761	red = (searched_size >= 6) ? depth / 3 : 1;
		6762	}
		6763
		6764	return red;
		6765	}
		6766
		6767	void gen_sort(Search_Local & sl, gen::List & ml) {
		6768
		6769	board::Board & bd = sl.board;
		6770
		6771	gen::gen_legals(ml, bd);
		6772
		6773	int v = eval(sl);
		6774
		6775	for (int pos = 0; pos < ml.size(); pos++) {
		6776
		6777	int mv = ml.move(pos);
		6778
		6779	move(sl, mv);
		6780	int sc = -qs_static(sl, score::MAX, 0);
		6781	undo(sl);
		6782
		6783	sc = ((sc - v) / 4) + 1024; // HACK for unsigned 11-bit move-list scores
		6784	assert(sc >= 0 && sc < move::SCORE_SIZE);
		6785
		6786	ml.set_score(pos, sc);
		6787	}
		6788
		6789	ml.sort();
		6790	}
		6791
		6792	void sl_init_early(Search_Local & sl, int id) {
		6793
		6794	sl.id = id;
		6795
		6796	sl.todo = true;
		6797	sl.todo_sp = NULL;
		6798
		6799	sl.node = 0;
		6800	sl.max_ply = 0;
		6801
		6802	sl.msp_stack_size = 0;
		6803	sl.ssp_stack_size = 0;
		6804	}
		6805
		6806	void sl_init_late(Search_Local & sl) {
		6807	sl.killer.clear();
		6808	sl.pawn_table.clear(); // pawn-eval cache
		6809	sl.eval_table.clear(); // eval cache
		6810	}
		6811
		6812	void sl_set_root(Search_Local & sl, const board::Board & bd) {
		6813	sl.board = bd;
		6814	sl.board.set_root();
		6815	}
		6816
		6817	void sl_signal(Search_Local & sl) {
		6818	sl.lock();
		6819	sl.signal();
		6820	sl.unlock();
		6821	}
		6822
		6823	bool sl_stop(const Search_Local & sl) {
		6824
		6825	for (Split_Point * sp = &sl_top(sl); sp != NULL; sp = sp->parent()) {
		6826	if (sp->solved()) return true;
		6827	}
		6828
		6829	return false;
		6830	}
		6831
		6832	bool sl_idle(const Search_Local & worker, Split_Point * sp) {
		6833
		6834	assert(sp != NULL);
		6835
		6836	if (worker.todo) return false;
		6837	if (worker.todo_sp != NULL) return false;
		6838
		6839	Split_Point & wait_sp = sl_top(worker);
		6840
		6841	for (; sp != NULL; sp = sp->parent()) {
		6842	if (sp == &wait_sp) return true;
		6843	}
		6844
		6845	return false;
		6846	}
		6847
		6848	void sl_push(Search_Local & sl, Split_Point & sp) {
		6849	assert(sl.ssp_stack_size < 16);
		6850	sl.ssp_stack[sl.ssp_stack_size++] = &sp;
		6851	}
		6852
		6853	void sl_pop(Search_Local & sl) {
		6854	assert(sl.ssp_stack_size > 0);
		6855	sl.ssp_stack_size--;
		6856	}
		6857
		6858	Split_Point & sl_top(const Search_Local & sl) {
		6859	assert(sl.ssp_stack_size > 0);
		6860	return *sl.ssp_stack[sl.ssp_stack_size - 1];
		6861	}
		6862
		6863	void sg_abort() {
		6864
		6865	root_sp.update_root();
		6866
		6867	for (int id = 0; id < engine::engine.threads; id++) {
		6868	sl_signal(p_sl[id]);
		6869	}
		6870	}
		6871
		6872	void search_asp(gen::List & ml, int depth) {
		6873
		6874	Search_Local & sl = p_sl[0];
		6875
		6876	assert(depth <= 1 \|\| p_time.last_score == best.score);
		6877
		6878	if (depth >= 6 && !score::is_mate(p_time.last_score)) {
		6879
		6880	for (int margin = 10; margin < 500; margin *= 2) {
		6881
		6882	int a = p_time.last_score - margin;
		6883	int b = p_time.last_score + margin;
		6884	assert(score::EVAL_MIN <= a && a < b && b <= score::EVAL_MAX);
		6885
		6886	search_root(sl, ml, depth, a, b);
		6887
		6888	if (best.score > a && best.score < b) {
		6889	return;
		6890	} else if (score::is_mate(best.score)) {
		6891	break;
		6892	}
		6893	}
		6894	}
		6895
		6896	search_root(sl, ml, depth, score::MIN, score::MAX);
		6897	}
		6898
		6899	void search_id(const board::Board & bd) {
		6900
		6901	Search_Local & sl = p_sl[0];
		6902
		6903	sl_set_root(sl, bd);
		6904
		6905	sl_push(sl, root_sp);
		6906
		6907	// move generation
		6908
		6909	gen::List ml;
		6910	gen_sort(sl, ml);
		6911	assert(ml.size() != 0);
		6912
		6913	best.move = ml.move(0);
		6914	best.score = 0;
		6915
		6916	bool easy = (ml.size() == 1 \|\| (ml.size() > 1 && ml.score(0) - ml.score(1) >= 50 / 4)); // HACK: uses gen_sort() internals
		6917	int easy_move = ml.move(0);
		6918
		6919	p_time.last_score = score::NONE;
		6920
		6921	// iterative deepening
		6922
		6923	assert(p_time.depth_limited);
		6924
		6925	for (int depth = 1; depth <= p_time.depth_limit; depth++) {
		6926
		6927	depth_start(depth);
		6928	search_asp(ml, depth);
		6929	depth_end();
		6930
		6931	// p_time.drop = (best.score <= p_time.last_score - 50); // moved to update_best()
		6932	p_time.last_score = best.score;
		6933
		6934	if (best.move != easy_move \|\| p_time.drop) {
		6935	easy = false;
		6936	}
		6937
		6938	if (p_time.smart && !p_time.drop) {
		6939
		6940	bool abort = false;
		6941
		6942	update_current();
		6943
		6944	if (ml.size() == 1 && current.time >= p_time.limit_0 / 16) {
		6945	abort = true;
		6946	}
		6947
		6948	if (easy && current.time >= p_time.limit_0 / 4) {
		6949	abort = true;
		6950	}
		6951
		6952	if (current.time >= p_time.limit_0 / 2) {
		6953	abort = true;
		6954	}
		6955
		6956	if (abort) {
		6957	if (p_time.ponder) {
		6958	p_time.flag = true;
		6959	} else {
		6960	break;
		6961	}
		6962	}
		6963	}
		6964	}
		6965
		6966	sl_pop(sl);
		6967	}
		6968
		6969	void search_go(const board::Board & bd) {
		6970
		6971	clear();
		6972
		6973	init_sg();
		6974	sg.trans.inc_date();
		6975
		6976	for (int id = 0; id < engine::engine.threads; id++) {
		6977	sl_init_early(p_sl[id], id);
		6978	}
		6979
		6980	root_sp.init_root(p_sl[0]);
		6981
		6982	for (int id = 1; id < engine::engine.threads; id++) { // skip 0
		6983	p_sl[id].thread = std::thread(helper_program, &p_sl[id]);
		6984	}
		6985
		6986	sl_init_late(p_sl[0]);
		6987
		6988	try {
		6989	search_id(bd);
		6990	} catch (const Abort & /* abort */) {
		6991	// no-op
		6992	}
		6993
		6994	sg_abort();
		6995
		6996	for (int id = 1; id < engine::engine.threads; id++) { // skip 0
		6997	p_sl[id].thread.join();
		6998	}
		6999
		7000	search_end();
		7001	}
		7002
		7003	void search_dumb(const board::Board & bd) {
		7004
		7005	p_time.smart = false;
		7006	p_time.last_score = score::NONE;
		7007	p_time.drop = false;
		7008
		7009	search_go(bd);
		7010	}
		7011
		7012	void search_smart(const board::Board & bd, int moves, int64 time, int64 inc) {
		7013
		7014	if (moves == 0) moves = 40;
		7015	moves = std::min(moves, material::interpolation(35, 15, bd));
		7016	assert(moves > 0);
		7017
		7018	int64 total = time + inc * (moves - 1);
		7019	int factor = engine::engine.ponder ? 140 : 120;
		7020	int64 alloc = total / moves * factor / 100;
		7021	int64 reserve = total * (moves - 1) / 40;
		7022	int64 max = std::min(time, total - reserve);
		7023	max = std::min(max - 60, max * 95 / 100); // 60ms for lag
		7024
		7025	alloc = std::max(alloc, I64(0));
		7026	max = std::max(max, I64(0));
		7027
		7028	p_time.smart = true;
		7029	p_time.limit_0 = std::min(alloc, max);
		7030	p_time.limit_1 = std::min(alloc * 4, max);
		7031	p_time.limit_2 = max;
		7032	p_time.last_score = score::NONE;
		7033	p_time.drop = false;
		7034
		7035	assert(0 <= p_time.limit_0 && p_time.limit_0 <= p_time.limit_1 && p_time.limit_1 <= p_time.limit_2);
		7036
		7037	search_go(bd);
		7038	}
		7039
		7040	void init() {
		7041	sg.trans.set_size(engine::engine.hash);
		7042	sg.trans.alloc();
		7043	}
		7044
		7045	}
		7046
		7047	namespace uci {
		7048
		7049	board::Board bd;
		7050	bool delay;
		7051
		7052	class Scanner {
		7053
		7054	private:
		7055
		7056	std::stringstream * p_ss;
		7057	std::vector<std::string> p_keywords;
		7058
		7059	bool p_undo;
		7060	std::string p_word;
		7061
		7062	bool is_keyword(const std::string & word) const {
		7063
		7064	for (int i = 0; i < int(p_keywords.size()); i++) {
		7065	if (p_keywords[i] == word) return true;
		7066	}
		7067
		7068	return false;
		7069	}
		7070
		7071	public:
		7072
		7073	Scanner(std::stringstream & ss) {
		7074	p_ss = &ss;
		7075	p_undo = false;
		7076	add_keyword("");
		7077	}
		7078
		7079	void add_keyword(const std::string & keyword) {
		7080	p_keywords.push_back(keyword);
		7081	}
		7082
		7083	std::string get_keyword() {
		7084
		7085	std::string word = get_word();
		7086	assert(is_keyword(word));
		7087
		7088	return word;
		7089	}
		7090
		7091	std::string get_args() {
		7092
		7093	std::string args;
		7094	std::string word;
		7095
		7096	while (true) {
		7097
		7098	std::string word = get_word();
		7099
		7100	if (is_keyword(word)) {
		7101	unget_word();
		7102	break;
		7103	}
		7104
		7105	if (args != "") args += " ";
		7106	args += word;
		7107	}
		7108
		7109	return args;
		7110	}
		7111
		7112	std::string get_word() {
		7113
		7114	if (p_undo) {
		7115	p_undo = false;
		7116	} else if (!(*p_ss >> p_word)) { // NOTE: reads as a side effect
		7117	p_word = "";
		7118	}
		7119
		7120	return p_word;
		7121	}
		7122
		7123	void unget_word() {
		7124	assert(!p_undo);
		7125	p_undo = true;
		7126	}
		7127
		7128	};
		7129
		7130	void fen(const std::string & fen) {
		7131	bd.init_fen(fen);
		7132	}
		7133
		7134	void move(const std::string & move) {
		7135	int mv = move::from_string(move, bd);
		7136	bd.move(mv);
		7137	}
		7138
		7139	void send_bestmove() {
		7140
		7141	std::cout << "bestmove " << move::to_can(search::best.move);
		7142	if (search::best.pv.size() > 1) std::cout << " ponder " << move::to_can(search::best.pv.move(1));
		7143	std::cout << std::endl;
		7144
		7145	delay = false;
		7146	}
		7147
		7148	void command(Scanner & scan) {
		7149
		7150	std::string command = scan.get_word();
		7151
		7152	if (false) {
		7153
		7154	} else if (command == "uci") {
		7155
		7156	std::cout << "id name Senpai 1.0" << std::endl;
		7157	std::cout << "id author Fabien Letouzey" << std::endl;
		7158
		7159	std::cout << "option name Hash type spin default " << engine::engine.hash << " min 16 max 16384" << std::endl;
		7160	std::cout << "option name Ponder type check default " << engine::engine.ponder << std::endl;
		7161	std::cout << "option name Threads type spin default " << engine::engine.threads << " min 1 max 16" << std::endl;
		7162	std::cout << "option name Log File type check default " << engine::engine.log << std::endl;
		7163
		7164	std::cout << "uciok" << std::endl;
		7165
		7166	} else if (command == "isready") {
		7167
		7168	std::cout << "readyok" << std::endl;
		7169
		7170	} else if (command == "setoption") {
		7171
		7172	scan.add_keyword("name");
		7173	scan.add_keyword("value");
		7174
		7175	std::string name;
		7176	std::string value;
		7177
		7178	std::string part;
		7179
		7180	while ((part = scan.get_keyword()) != "") {
		7181
		7182	if (false) {
		7183	} else if (part == "name") {
		7184	name = scan.get_args();
		7185	} else if (part == "value") {
		7186	value = scan.get_args();
		7187	}
		7188	}
		7189
		7190	if (false) {
		7191	} else if (util::string_case_equal(name, "Hash")) {
		7192	engine::engine.hash = int(util::to_int(value));
		7193	search::sg.trans.set_size(engine::engine.hash);
		7194	} else if (util::string_case_equal(name, "Ponder")) {
		7195	engine::engine.ponder = util::to_bool(value);
		7196	} else if (util::string_case_equal(name, "Threads") \|\| util::string_case_equal(name, "Cores")) {
		7197	engine::engine.threads = int(util::to_int(value));
		7198	} else if (util::string_case_equal(name, "Log File")) {
		7199	engine::engine.log = util::to_bool(value);
		7200	}
		7201
		7202	} else if (command == "ucinewgame") {
		7203
		7204	search::sg.trans.clear();
		7205
		7206	} else if (command == "position") {
		7207
		7208	scan.add_keyword("fen");
		7209	scan.add_keyword("startpos");
		7210	scan.add_keyword("moves");
		7211
		7212	std::string part;
		7213
		7214	while ((part = scan.get_keyword()) != "") {
		7215
		7216	if (false) {
		7217
		7218	} else if (part == "fen") {
		7219
		7220	fen(scan.get_args());
		7221
		7222	} else if (part == "startpos") {
		7223
		7224	fen(board::start_fen);
		7225
		7226	} else if (part == "moves") {
		7227
		7228	std::string arg;
		7229
		7230	while ((arg = scan.get_word()) != "") {
		7231	uci::move(arg);
		7232	}
		7233	}
		7234	}
		7235
		7236	} else if (command == "go") {
		7237
		7238	scan.add_keyword("searchmoves");
		7239	scan.add_keyword("ponder");
		7240	scan.add_keyword("wtime");
		7241	scan.add_keyword("btime");
		7242	scan.add_keyword("winc");
		7243	scan.add_keyword("binc");
		7244	scan.add_keyword("movestogo");
		7245	scan.add_keyword("depth");
		7246	scan.add_keyword("nodes");
		7247	scan.add_keyword("mate");
		7248	scan.add_keyword("movetime");
		7249	scan.add_keyword("infinite");
		7250
		7251	search::new_search();
		7252
		7253	infinite = false;
		7254	delay = false;
		7255
		7256	bool smart = false;
		7257	int time = 60000;
		7258	int inc = 0;
		7259	int movestogo = 0;
		7260
		7261	std::string part;
		7262
		7263	while ((part = scan.get_keyword()) != "") {
		7264
		7265	std::string args = scan.get_args();
		7266
		7267	if (false) {
		7268
		7269	} else if (part == "ponder") {
		7270
		7271	infinite = true;
		7272	search::set_ponder();
		7273
		7274	} else if (part == "wtime") {
		7275
		7276	if (bd.turn() == side::WHITE) {
		7277	smart = true;
		7278	time = int(util::to_int(args));
		7279	}
		7280
		7281	} else if (part == "btime") {
		7282
		7283	if (bd.turn() == side::BLACK) {
		7284	smart = true;
		7285	time = int(util::to_int(args));
		7286	}
		7287
		7288	} else if (part == "winc") {
		7289
		7290	if (bd.turn() == side::WHITE) {
		7291	smart = true;
		7292	inc = int(util::to_int(args));
		7293	}
		7294
		7295	} else if (part == "binc") {
		7296
		7297	if (bd.turn() == side::BLACK) {
		7298	smart = true;
		7299	inc = int(util::to_int(args));
		7300	}
		7301
		7302	} else if (part == "movestogo") {
		7303
		7304	smart = true;
		7305	movestogo = int(util::to_int(args));
		7306
		7307	} else if (part == "depth") {
		7308
		7309	search::set_depth_limit(int(util::to_int(args)));
		7310
		7311	} else if (part == "nodes") {
		7312
		7313	search::set_node_limit(util::to_int(args));
		7314
		7315	} else if (part == "movetime") {
		7316
		7317	search::set_time_limit(int(util::to_int(args)));
		7318
		7319	} else if (part == "infinite") {
		7320
		7321	infinite = true;
		7322	}
		7323	}
		7324
		7325	if (smart) {
		7326	search::search_smart(bd, movestogo, time, inc);
		7327	} else {
		7328	search::search_dumb(bd);
		7329	}
		7330
		7331	if (infinite) { // let's implement the UCI-design mistake :(
		7332	delay = true;
		7333	} else {
		7334	send_bestmove();
		7335	}
		7336
		7337	} else if (command == "stop") {
		7338
		7339	if (delay) send_bestmove();
		7340
		7341	} else if (command == "ponderhit") {
		7342
		7343	if (delay) send_bestmove();
		7344
		7345	} else if (command == "quit") {
		7346	#ifdef _MSC_VER
		7347	ExitProcess(0); // Pierre-Marie Baty -- use ExitProcess() instead of exit() on Win32 apps
		7348	#else // !_MSC_VER
		7349	std::exit(EXIT_SUCCESS);
		7350	#endif // _MSC_VER
		7351	}
		7352	}
		7353
		7354	void line(const std::string & line) {
		7355
		7356	if (engine::engine.log) util::log(line);
		7357
		7358	std::stringstream args(line);
		7359	Scanner scan(args);
		7360	command(scan);
		7361	}
		7362
		7363	void loop() {
		7364
		7365	std::cout << std::boolalpha;
		7366
		7367	infinite = false;
		7368	delay = false;
		7369
		7370	fen(board::start_fen);
		7371
		7372	std::string line;
		7373
		7374	while (input::input.get_line(line)) {
		7375	uci::line(line);
		7376	}
		7377	}
		7378
		7379	}
		7380
		7381	int main(int /* argc /, char /* argv */ []) {
		7382
		7383	assert(sizeof(uint8) == 1);
		7384	assert(sizeof(uint16) == 2);
		7385	assert(sizeof(uint32) == 4);
		7386	assert(sizeof(uint64) == 8);
		7387
		7388	input::init();
		7389	bit::init();
		7390	hash::init();
		7391	castling::init();
		7392	attack::init();
		7393	engine::init();
		7394	material::init();
		7395	pst::init();
		7396	pawn::init();
		7397	eval::init();
		7398	search::init();
		7399
		7400	uci::loop();
		7401
		7402	return EXIT_SUCCESS;
		7403	}
		7404

Subversion Repositories Games.Chess Giants

Games.Chess Giants//engine-senpai/senpai_10.cpp – Rev 102