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

Subversion Repositories Games.Chess Giants

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