
// sections - groups of moves to sort
#define SORT_NONE		0
#define SORT_TRANS		1	// Search()		 -
#define SORT_MATE		2	// Search()		 -
#define SORT_CAPTURE	3	// Search() & QSearch() 
#define SORT_KILLER		4	// Search()      -
#define SORT_QUIET		5	// Search()      -
#define SORT_CHECK		6	//	  -		  QSearch()
#define SORT_EVASION	7	// Search()	& QSearch()

#define MOVE_IS_BAD(b,m)		((PieceValues[m->Piece()] <= PieceValues[m->Capture()]) ? false : (b->SEE(m) < 0))
#define BAD_MOVE_SCORE			(-(HISTORY_MAX_VALUE))	// see CaptureValue()
#define SCORE_CAPTURES(ml)		{for(int ic = 0; ic < ml->Size(); ic++)		ml->value[ic] = CaptureValue(b, ml->move[ic]);}
#define SCORE_QCAPTURES(ml)		{for(int iq = 0; iq < ml->Size(); iq++)		ml->value[iq] = QCaptureValue(b, ml->move[iq]);}
#define SCORE_QUIET(ml)			{for(int qm = 0; qm < ml->Size(); qm++)		ml->value[qm] = QuietValue(b, h, ml->move[qm]);}

#define SORT_KILLER_SIZE	4
#define KILLER_SIZE			2

class SearchStack;

// history
#define HISTORY_MAX_VALUE						32000
#define TRANS_MOVE_VALUE						2*HISTORY_MAX_VALUE
#define EVASION_SEE_VALUE(see_val)				(((see_val) >= 0) ? (HISTORY_MAX_VALUE + (see_val)) : (see_val))
#define HISTORY_COLOURED_PIECE(piece ,colour)	(2*(piece-1) + colour)	// total: 12
//#define FULL_HISTORY
#ifdef FULL_HISTORY
	#define HISTORY_SIZE						(2*6*64*65)				// colour, type, from, to
	#define HISTORY_INDEX(m,stm)				(12*(m->From() + 64*m->To()) + HISTORY_COLOURED_PIECE(m->Piece(),stm))
#else
	#define HISTORY_SIZE						(2*6*64)				// colour, type, to
	#define HISTORY_INDEX(m,stm)				(m->To()*12 + HISTORY_COLOURED_PIECE(m->Piece(),stm))
#endif

class History {
private:
	int history[HISTORY_SIZE];
	int success[HISTORY_SIZE];
	int failure[HISTORY_SIZE];	
public:	
	History() {Clear()		;}
	void Clear() {
		for(int i = 0; i < HISTORY_SIZE; i++)
			history[i] = success[i] = failure[i] = 0;
	}
	void GoodMove(Move *m, int stm, float depth) {
		if(m->IsCapProm())	return;
		int index = HISTORY_INDEX(m,stm);
		success[index] += 1;
		history[index] += int(depth*depth);
		// detect overflow 
		if(history[index] >= HISTORY_MAX_VALUE)
			for(int i = 0; i < HISTORY_SIZE; i++)
				history[i] = (history[i]+1) / 2;
	}
	void BadMove(Move *m, int stm) {
		int index = HISTORY_INDEX(m,stm);
		failure[index] += 1;
		// detect overflow 		
		if(failure[index] >= HISTORY_MAX_VALUE) {
			success[index] = (success[index]+1) / 2;
			failure[index] = (failure[index]+1) / 2;
		}
	}
	int Score(Move *m, int stm) {
		int index = HISTORY_INDEX(m,stm);
		ASSERT(HISTORY_COLOURED_PIECE(m->Piece(), stm) >= 0);
		ASSERT(HISTORY_COLOURED_PIECE(m->Piece(), stm) < 12);
		return history[index];
	}
	bool CanPrune(Move *m, int stm, float depth) {
		int index = HISTORY_INDEX(m,stm);
		const int prune_ratio = int(depth);		
		return success[index] * prune_ratio < failure[index];
	}
	bool CanReduce(Move *m, int stm) {
		int index = HISTORY_INDEX(m,stm);
		const int reduce_ratio = 30;				
		return success[index] * reduce_ratio/100 < failure[index];
	}
};

class Sort {
private:	
public:		
	BitBoard sections, checkers, pinned_rooks, pinned_bishops, 
		discovered_rooks, discovered_bishops, capture_mask;
	Move trans_move[1],
		mate_killer[1],
		killer[SORT_KILLER_SIZE];
	Move best_move[1];	// current best move
	MoveList sml[1];   // sort move list	
	uint status;
	int quiet,
		checks,		
		evasions,
		captures,
		in_check;
	bool generate;	
	bool use_killers;
	bool good_capture;
	int killer_equal;
				
	Move *GetMoveQs(Board *b, History *h);
	Move *GetMove(Board *b, History *h);

	void FindPinned(Board *b)		{b->FindPinned(checkers, &pinned_rooks, &pinned_bishops)	;}
	void FindDiscovered(Board *b)	{b->FindDiscovered(&discovered_rooks, &discovered_bishops)	;}
	void Init() {
		sml->Clear();
		capture_mask = AllSquares;
		sections = SORT_NONE;
		in_check = SORT_NONE;
		good_capture = false;
		status = SORT_NONE;
		killer_equal = 0;
		evasions = -1;
		captures = -1;		
		checks = -1;
	}	
	Sort() {Init()	;}

	int CaptureValue(Board *b, Move *m) {
		int result, see = b->SEE(m);
		if((see >= 0)
		&& !m->IsPromote()) 
			result = PieceValues[m->Capture()] - m->Piece();
		else result = see;
		result += HISTORY_MAX_VALUE - KING_VALUE;

		ASSERT(result < HISTORY_MAX_VALUE);
		ASSERT(result >= 0);
		return result;
	}
	int QCaptureValue(Board *b, Move *m) {		
		if(!m->IsPromote()) 
			return PieceValues[m->Capture()] - m->Piece();
		return PieceValues[QUEEN];		
	}
	int QuietValue(Board *b, History *h, Move *m) {			
		return h->Score(m, b->stm);		
	}	
};

Move *Sort::GetMoveQs(Board *b, History *h) {	
	
	best_move->Clear();	

	while(sections || (sml->Size() > 0)) {
		
		if(generate = sml->Size() == 0)	
			status = ExtractFirstBit(sections);			
		ASSERT(status);	
		
		if(status == SORT_CAPTURE) {
			if(generate) {					
				b->GenCaptures(sml, pinned_rooks, pinned_bishops, capture_mask);				
				if((captures = sml->Size()) == 0)	continue;
				SCORE_QCAPTURES(sml);				
			}			
			sml->QuickSort(SORT_ALL);			
			*best_move = *sml->move[0]; 
			sml->DeleteMove(DELETE_BEST_MOVE);
			if(MOVE_IS_BAD(b, best_move))			continue;
			
		} else if(status == SORT_CHECK) {
			if(generate) {						
				b->GenQuietChecks(sml, pinned_rooks, pinned_bishops);
				if((checks = sml->Size()) == 0)		continue;
			}			
			*best_move = *sml->move[0];
			sml->DeleteMove(DELETE_BEST_MOVE);
			if(MOVE_IS_BAD(b, best_move))			continue;
			
		} else if(status == SORT_EVASION) {	
			if(generate) {					
				b->GenEvasions(sml, pinned_rooks, pinned_bishops, checkers, in_check);				
				if((evasions = sml->Size()) == 0)	continue;
				// score evasions
				for(int i = 0; i < sml->Size(); i++) {
					if(sml->move[i]->IsCapProm()) {
						int see_value = b->SEE(sml->move[i]);
						sml->value[i] = EVASION_SEE_VALUE(see_value);
					} else {
						sml->value[i] = h->Score(sml->move[i], b->stm);
						ASSERT(sml->value[i] >= 0);
					}
				}
			}
			sml->QuickSort(SORT_ALL);
			*best_move = *sml->move[0];
			sml->DeleteMove(DELETE_BEST_MOVE);
		}
		return best_move;
	}
	best_move->Clear();
	ASSERT(!(best_move->From() == E2 && best_move->To() == D7));
	return best_move;
}

Move *Sort::GetMove(Board *b, History *h) {
	
	best_move->Clear();	

	while(sections || (sml->Size() > 0)) {
		
		if(generate = sml->Size() == 0)	
			status = ExtractFirstBit(sections);			
		ASSERT(status);	
		
		if(status == SORT_TRANS) {			
			if(!b->MoveIsLegal(trans_move, pinned_rooks, pinned_bishops))	continue;
			return trans_move;			

		} else if(status == SORT_MATE) {
			if(mate_killer->Equal(trans_move))								continue;
			*best_move = *mate_killer;			
			if(!b->MoveIsLegal(best_move, pinned_rooks, pinned_bishops))	continue;
			return best_move;

		} else if(status == SORT_CAPTURE) {
			if(generate) {				
				b->GenCaptures(sml, pinned_rooks, pinned_bishops, capture_mask);				
				if((captures = sml->Size()) == 0)							continue;
				good_capture = true;
				SCORE_CAPTURES(sml);				
			}			
			sml->QuickSort(SORT_ALL);
			*best_move = *sml->move[0];
			if(best_move->Equal(trans_move)
			|| best_move->Equal(mate_killer)) {
				sml->DeleteMove(DELETE_BEST_MOVE);
				continue;
			}
			// move is good?
			if(BEST_MOVE_VALUE(sml) >= 0) {
				if(MOVE_IS_BAD(b, best_move)) {
					sml->value[0] += BAD_MOVE_SCORE;					
					// now this move has negative value
					// so it can`t be picked as good yet
					ASSERT(sml->value[0] < 0);
					continue;
				}
			} else good_capture = false;						
			sml->DeleteMove(DELETE_BEST_MOVE);			

		} else if(status == SORT_KILLER) {
			if(generate) {				
				for(int i = 0; i < SORT_KILLER_SIZE; i++) {
					if(!killer[i].IsReal()
					|| killer[i].Equal(trans_move)
					|| killer[i].Equal(mate_killer)
					|| killer[i].IsCapProm())	
						continue;
					sml->Add(killer[i]);					
				}
				if(sml->Size() == 0)										continue;
			}
			*best_move = *sml->move[0];
			sml->DeleteMove(DELETE_BEST_MOVE);				
			if(!b->MoveIsLegal(best_move, pinned_rooks, pinned_bishops))	continue;

		} else if(status == SORT_QUIET) {	
			if(generate) {				
				b->GenQuietMoves(sml, pinned_rooks, pinned_bishops);				
				if((quiet = sml->Size()) == 0)								continue;
				SCORE_QUIET(sml);				
			}
			killer_equal = 0;
			sml->QuickSort(SORT_ALL);
			*best_move = *sml->move[0];

			if(best_move->Equal(trans_move)
			|| best_move->Equal(mate_killer)) {
				sml->DeleteMove(DELETE_BEST_MOVE);
				continue;
			} if(use_killers) {
				for(int k = 0; k < SORT_KILLER_SIZE; k++) {
					if(killer[k].Equal(best_move)) {
						killer_equal = 1;
						break;
					}
				} 
				if(killer_equal == 1) {
					sml->DeleteMove(DELETE_BEST_MOVE);
					continue;
				}
			}
			sml->DeleteMove(DELETE_BEST_MOVE);
		} else if(status == SORT_EVASION) {	
			if(generate) {				
				b->GenEvasions(sml, pinned_rooks, pinned_bishops, checkers, in_check);				
				if((evasions = sml->Size()) == 0)	continue;
				// score evasions
				for(int i = 0; i < sml->Size(); i++) {
					if(sml->move[i]->Equal(trans_move))	{	
						sml->value[i] = TRANS_MOVE_VALUE;
					} else if(sml->move[i]->IsCapProm()) {
						int see_value = b->SEE(sml->move[i]);						
						sml->value[i] = EVASION_SEE_VALUE(see_value);
					} else {sml->value[i] = h->Score(sml->move[i], b->stm);}
				}
			}
			sml->QuickSort(SORT_ALL);		
			*best_move = *sml->move[0];
			sml->DeleteMove(DELETE_BEST_MOVE);
		}

		return best_move;
	}
	best_move->Clear();	
	return best_move;
}