/******************************************
* Needle - a bitboard based chess engine. *
* (C) 2004 Mikko Nummelin                 *
******************************************/

#define _THINKING_C

#include "needle.h"

#define ASPIRATION_RADIUS	100
#define ILLEGAL_MOVE	32000
#define EXITING_LOOP	32001

#ifdef DEBUG
extern FILE *errlog;
#endif

int maxdepth;
Chessclock tmpclock;

void engine_interrupt(void){
	if(time_left_in_clock(&(evars.this_move_clock))<=0.0){
		evars.flags|=HALT;
	}
}

void init_PVlist(PVlist *pvlist){
	pvlist->size=0;
	pvlist->moves[0][0]=0;
}

void copy_PVlist(PVlist *new_pvlist, PVlist *old_pvlist){
	int i;
	new_pvlist->size=old_pvlist->size;
	for(i=0;i<old_pvlist->size;i++){
		strncpy(new_pvlist->moves[i],old_pvlist->moves[i],6);
	}
	new_pvlist->moves[old_pvlist->size][0]=0;
}

void print_PVlist(PVlist *principal_variation){
	int i;
	for(i=principal_variation->size-1;i>=0;i--){
		printf("%s ",principal_variation->moves[i]);
	}
	printf("\n");
}

void print_movelist_moves(Movelist *mvl){
	int i;
	for(i=0;i<mvl->size;i++){
		printf("%c : %5s : %c : %7d\n",
		mvl->moves[i].moving_piece,
		mvl->moves[i].move,
		mvl->moves[i].captured_piece,
		mvl->moves[i].approx_move_value);
	}
	fflush(stdout);
}

void reset_engine_variables(){
	init_notebook(&(evars.ntb));
	init_zobtrace(&(evars.zt));
	stop_clock(&(evars.computers_clock));
	stop_clock(&(evars.opponents_clock));
	evars.flags |= COMP_BLACK;
	evars.flags &= ~COMP_WHITE;
	evars.flags &= ~PONDER;
	evars.flags |= POST;
	evars.flags &= ~ANALYZE;
	evars.flags &= ~ICS;
	evars.flags &= ~CURRENTLY_PONDERING;
	evars.flags &= ~CURRENTLY_THINKING;
	evars.flags &= ~HALT;
	evars.flags &= ~DISPOSE;
	evars.flags &= ~TERMINATE;
	evars.sd=999;
}

void init_opening_book() {
	Board tmp_brd;
	int i,j;
	char str[128];
	FILE *opbfile;
	opbfile=fopen("needle.bk","rb");
	if(opbfile==NULL) {
		/* Empty opening book in case there is no opening
		 * book file */
		evars.opb.number_of_positions=0;
		return;
	}
	fgets(str,127,opbfile);
	replace_newline(str);
	evars.opb.number_of_positions=atoi(str);
	evars.opb.positions=malloc(evars.opb.number_of_positions*sizeof(Book_node));
	for(i=0;i<evars.opb.number_of_positions;i++) {
		fgets(str,127,opbfile);
		replace_newline(str);
		import_fen(&tmp_brd,str);
		evars.opb.positions[i].z.whole=tmp_brd.key.whole;
		fgets(str,127,opbfile);
		replace_newline(str);
		evars.opb.positions[i].number_of_moves=atoi(str);
		evars.opb.positions[i].moves=
			malloc(evars.opb.positions[i].number_of_moves*6*sizeof(char));
		for(j=0;j<evars.opb.positions[i].number_of_moves;j++) {
			fgets(str,127,opbfile);
			replace_newline(str);
			strncpy(&(evars.opb.positions[i].moves[6*j]),str,6);
		}
	}
	fclose(opbfile);
}

void free_opening_book() {
	int i;
	for(i=0;i<evars.opb.number_of_positions;i++) {
		free(evars.opb.positions[i].moves);
	}
	if(evars.opb.number_of_positions>=0) {
		free(evars.opb.positions);
	}
}

char *get_move_from_book(Board *brd) {
	int i,moveno;
	double randno;
	for(i=0;i<evars.opb.number_of_positions;i++) {
		if(brd->key.whole==evars.opb.positions[i].z.whole) {
			/* This position is a book position */
			randno=(double)evars.opb.positions[i].number_of_moves*rand()/
				RAND_MAX;
			moveno=(int)randno;
			return &(evars.opb.positions[i].moves[6*moveno]);
		}
	}
	return NULL; /* Not a book position */
}

void alloc_hashtable(int lb_of_cluster_amount,int lb_of_cluster_size){
	int i,cluster_amount,cluster_size;

	cluster_amount=0x1<<lb_of_cluster_amount;
	cluster_size=0x1<<lb_of_cluster_size;
	evars.ht.lb_of_cluster_amount=lb_of_cluster_amount;
	evars.ht.clusters=malloc(cluster_amount*sizeof(Lookup_cluster));
	if(evars.ht.clusters==NULL){
		fprintf(stderr,"Memory allocation error with hashtable.\n");
		exit(0);
	}
	for(i=0;i<cluster_amount;i++){
		evars.ht.clusters[i].lb_of_cluster_size=lb_of_cluster_size;
		evars.ht.clusters[i].nodes=malloc(cluster_size*sizeof(Lookup_node));
		if(evars.ht.clusters[i].nodes==NULL){
			fprintf(stderr,"Memory allocation error with hashtable.\n");
			exit(0);
		}
	}
	clear_hashtable();
}

void clear_hashtable(){
	int i,j,cluster_amount,cluster_size;
	cluster_amount=0x1<<evars.ht.lb_of_cluster_amount;
	for(i=0;i<cluster_amount;i++){
		cluster_size=0x1<<evars.ht.clusters[i].lb_of_cluster_size;
		evars.ht.clusters[i].next_insert=0;
		for(j=0;j<cluster_size;j++){
			evars.ht.clusters[i].nodes[j].z.whole=BITBOARD_ZERO;
			evars.ht.clusters[i].nodes[j].depth_until_bottom=0;
			evars.ht.clusters[i].nodes[j].suggested_move[0]=0;
			evars.ht.clusters[i].nodes[j].position_value_type=0;
			evars.ht.clusters[i].nodes[j].position_value=0;
		}
	}
}

void free_hashtable(){
	int i,cluster_amount,cluster_size;

	cluster_amount=0x1<<evars.ht.lb_of_cluster_amount;
	for(i=0;i<cluster_amount;i++){
		cluster_size=0x1<<evars.ht.clusters[i].lb_of_cluster_size;
		free(evars.ht.clusters[i].nodes);
	}
	free(evars.ht.clusters);
}

void add_to_hashtable(Board *brd,
	char depth_until_bottom,
	unsigned char position_value_type,
	short position_value,
	char *suggested_move){

	Lookup_node *lkpnode;

	lkpnode=find_from_hashtable(brd);
	if(!lkpnode){
		lkpnode=find_next_empty_from_hashtable(brd);
	}

	if(lkpnode->depth_until_bottom<=depth_until_bottom) {
		if(((lkpnode->position_value >= 29000) &&
			(lkpnode->position_value<position_value)) ||
			((lkpnode->position_value <= -29000) &&
			(lkpnode->position_value>position_value)) ||
			((lkpnode->position_value > -29000) &&
			(lkpnode->position_value < 29000))) {

			lkpnode->z.whole=brd->key.whole;
			lkpnode->depth_until_bottom=depth_until_bottom;
			lkpnode->position_value_type=position_value_type;
			lkpnode->position_value=position_value;
			strncpy(lkpnode->suggested_move,suggested_move,6);
		}
	}
}

Lookup_node *find_from_hashtable(Board *brd) {
	int i,cluster_number,cluster_size,mask;
	Zobrist z;

	z=brd->key;
	mask = (0x1<<evars.ht.lb_of_cluster_amount)-1;
	cluster_number = mask & (z.halves[0]^z.halves[1]);
	cluster_size = 0x1<<evars.ht.clusters[cluster_number].lb_of_cluster_size;
	for(i=0;i<cluster_size;i++) {
		if(zkequals(evars.ht.clusters[cluster_number].nodes[i].z,z)){
			return &(evars.ht.clusters[cluster_number].nodes[i]);
		}
	}
	return NULL;
}

Lookup_node *find_next_empty_from_hashtable(Board *brd){
	int cluster_number,cluster_size,mask,next_insert;
	Zobrist z;

	z=brd->key;
	mask = (0x1<<evars.ht.lb_of_cluster_amount)-1;
	cluster_number = mask & (z.halves[0]^z.halves[1]);
	cluster_size = 0x1<<evars.ht.clusters[cluster_number].lb_of_cluster_size;
	next_insert=evars.ht.clusters[cluster_number].next_insert;
	evars.ht.clusters[cluster_number].next_insert++;
	if(evars.ht.clusters[cluster_number].next_insert>=cluster_size)
		evars.ht.clusters[cluster_number].next_insert=0;

	return(&(evars.ht.clusters[cluster_number].nodes[next_insert]));
}

int iterativedeep(Board *brd, int mdepth,
	char *best_move, PVlist *principal_variation) {

	Movelist pseudolegal_moves_list;
	PVlist stored_principal_variation;
	char stored_best_move[6],*bookmove;
	int i,stored_value=0,value=0,reliable;
	double time_left;
	init_PVlist(principal_variation);
	evars.flags &= ~HALT;
	time_left=time_left_in_clock(&(evars.computers_clock));
	if(!(evars.flags & STMOVE)) {
		if(time_left>=60.0) {
			set_clock(&(evars.this_move_clock),time_left/30+
				(double)evars.inc/2);
		} else {
			set_clock(&(evars.this_move_clock),time_left/30);
		}
	} else {
		set_clock(&(evars.this_move_clock),evars.st);
	}
	set_clock(&tmpclock,0);
	start_clock(&(evars.this_move_clock));
	start_clock(&tmpclock);
	evars.positions_seen=0;

	bookmove=get_move_from_book(brd);
	if(bookmove!=NULL) {
		init_PVlist(principal_variation);
		strncpy(best_move,bookmove,6);
		return 0;
	}

	for(i=1;(i<=evars.sd)&&(!(evars.flags & EXIT_THINKING_LOOP));i++) {
		stored_value=value;
		strncpy(stored_best_move,best_move,6);
		copy_PVlist(&stored_principal_variation,principal_variation);
		maxdepth=i;
		evars.zt.size=0;
		init_PVlist(principal_variation);
		if(i==1) {
			value=alpha_beta(brd,0,0,-30000,30000,best_move,
				NULL,&pseudolegal_moves_list,
				principal_variation,&reliable);
		} else {
			value=alpha_beta(brd,0,0,stored_value-ASPIRATION_RADIUS,
				stored_value+ASPIRATION_RADIUS,
				best_move,&pseudolegal_moves_list,&pseudolegal_moves_list,
				principal_variation,&reliable);
			if(value>=stored_value+ASPIRATION_RADIUS) {
				value=alpha_beta(brd,0,0,stored_value-ASPIRATION_RADIUS,30000,
					best_move,&pseudolegal_moves_list,&pseudolegal_moves_list,
					principal_variation,&reliable);
				if(value<=stored_value-ASPIRATION_RADIUS) {
				value=alpha_beta(brd,0,0,-30000,30000,best_move,
					&pseudolegal_moves_list,&pseudolegal_moves_list,
					principal_variation,&reliable);
				}
			} else if(value<=stored_value-ASPIRATION_RADIUS) {
				value=alpha_beta(brd,0,0,-30000,stored_value+ASPIRATION_RADIUS,
					best_move,&pseudolegal_moves_list,&pseudolegal_moves_list,
					principal_variation,&reliable);
				if(value>=stored_value+ASPIRATION_RADIUS) {
				value=alpha_beta(brd,0,0,-30000,30000,best_move,
					&pseudolegal_moves_list,&pseudolegal_moves_list,
					principal_variation,&reliable);
				}
			}
		}
		if(value>=29980){
			evars.flags|=HALT;
		}
	}

	/* The last value may be nonreliable due to forced halt */
	if(reliable==FALSE) {
		strncpy(best_move,stored_best_move,6);
		copy_PVlist(principal_variation,&stored_principal_variation);
		value=stored_value;
	}

	return value;
}

int alpha_beta(Board *brd,
	int depth,
	int extension,
	int prev_alpha,
	int prev_beta,
	char *best_move,
	Movelist *pre_defined_list,
	Movelist *new_list_template,
	PVlist *principal_variation,
	int *is_reliable)
{
	Movelist *mvl_in_use,nlt;
	Lookup_node *lkpnode;
	PVlist new_principal_variation;
	int i,j,this_extension,value, best_value, alpha, beta, legal_move_found;
	char new_best_move[6];

	Bitboard key_backup,ep_backup,epr_backup,epnw_backup,epne_backup;
	int half_moves_backup,full_moves_backup;
	unsigned char castling_flags_backup;

	engine_interrupt();

	legal_move_found=FALSE;
	if(is_reliable)
		*is_reliable=FALSE;
	evars.positions_seen++;

	if(evars.flags & EXIT_THINKING_LOOP)
		return EXITING_LOOP;

	if(is_illegal(brd)){
		return ILLEGAL_MOVE;
	}

	alpha=prev_alpha;beta=prev_beta;value=0;best_value=-1000000;best_move[0]=0;
	this_extension=extension;

	if(brd->half_moves>=100){
		return 0; /* 50 move rule */
	}

	evars.zt.zkeys[depth].whole=brd->key.whole;
	evars.zt.size=depth+1;
	if(is_threefold_repetition(&(evars.ntb),&(evars.zt),brd->half_moves)){
		return 0; /* Threefold repetition */
	}

	lkpnode=find_from_hashtable(brd);
	if((depth>0)&& lkpnode) {
		if((lkpnode->position_value_type==EXACT_VALUE)&&
			(lkpnode->depth_until_bottom>=maxdepth-depth+this_extension)){
			return lkpnode->position_value;
		} else if((lkpnode->position_value_type==LOWER_BOUND)&&
			(lkpnode->depth_until_bottom>=maxdepth-depth+this_extension)&&
			(lkpnode->position_value<=alpha)){
			return alpha;
		} else if((lkpnode->position_value_type==UPPER_BOUND)&&
			(lkpnode->depth_until_bottom>=maxdepth-depth+this_extension)&&
			(lkpnode->position_value>=beta)){
			return beta;
		}
	}

	if(depth>=maxdepth){
		return qsearch(brd,depth,prev_alpha,prev_beta,
			best_move,principal_variation);
	}

	if(!pre_defined_list) {
		if(is_check(brd)){
			if(depth>=maxdepth+this_extension-1){
				this_extension++;
			}
			generate_check_evasions(brd,new_list_template);
		} else {
			generate_moves(brd,new_list_template);
		}
		mvl_in_use=new_list_template;
	} else {
		mvl_in_use=pre_defined_list;
	}

	if(lkpnode) {
		for(i=0;i<mvl_in_use->size;i++){
			if(!strncmp(lkpnode->suggested_move,
				mvl_in_use->moves[i].move,6)){
				mvl_in_use->moves[i].approx_move_value=1000000;
				break;
			}
		}
	}

	qsort(mvl_in_use->moves,
		mvl_in_use->size,
		sizeof(Move_node),
		compare_move_values);

	for(i=0;i<mvl_in_use->size;i++){
		init_PVlist(&new_principal_variation);

		/* Backups otherwise irrevertible information */
		key_backup.whole=brd->key.whole;
		half_moves_backup=brd->half_moves;
		full_moves_backup=brd->full_moves;
		ep_backup.whole=brd->ep.whole;
		epr_backup.whole=brd->epr.whole;
		epnw_backup.whole=brd->epnw.whole;
		epne_backup.whole=brd->epne.whole;
		castling_flags_backup=brd->castling_flags;

		make_move(brd,&(mvl_in_use->moves[i]));
		if(legal_move_found==FALSE) {
		value=-alpha_beta(brd,depth+1,this_extension,-beta,-alpha,
			new_best_move,NULL,&nlt,&new_principal_variation,NULL);
		} else {
		value=-alpha_beta(brd,depth+1,this_extension,-alpha-1,-alpha,
			new_best_move,NULL,&nlt,&new_principal_variation,NULL);
		if((value>alpha)&&(value<beta)){
		value=-alpha_beta(brd,depth+1,this_extension,-beta,-alpha,
			new_best_move,NULL,&nlt,&new_principal_variation,NULL);
		}
		}

		unmake_move(brd,&(mvl_in_use->moves[i]));

		/* Restores backup */
		brd->key.whole=key_backup.whole;
		brd->half_moves=half_moves_backup;
		brd->full_moves=full_moves_backup;
		brd->ep.whole=ep_backup.whole;
		brd->epr.whole=epr_backup.whole;
		brd->epnw.whole=epnw_backup.whole;
		brd->epne.whole=epne_backup.whole;
		brd->castling_flags=castling_flags_backup;

		if((value==-EXITING_LOOP)||(value==EXITING_LOOP)){
			return EXITING_LOOP;
		}
		if(value!=-ILLEGAL_MOVE) {
			if(value>29000)
				value--;
			if(value<-29000)
				value++;
			legal_move_found=TRUE;
			if(value>best_value){
				best_value=value;
			}
			if(value>=beta){
				mvl_in_use->moves[i].approx_move_value=beta;
				add_to_hashtable(brd,maxdepth-depth+this_extension,
					UPPER_BOUND,
					(short)beta,mvl_in_use->moves[i].move);
				return best_value; /* Fail high */
			}
			if(value>alpha){
				mvl_in_use->moves[i].approx_move_value=value;
				alpha=value;
				strncpy(best_move,mvl_in_use->moves[i].move,6);
				copy_PVlist(principal_variation,&new_principal_variation);
				strncpy(principal_variation->moves[principal_variation->size],best_move,6);
				principal_variation->size++;

				/* Signs that there is a best move and PV which can be returned */
				if(is_reliable)
					*is_reliable=TRUE;

				if((depth==0)&&(evars.flags&POST)){
					printf("%d %d %d %d ",maxdepth,value,
						(int)(-time_left_in_clock(&tmpclock)*100),
						evars.positions_seen);
					for(j=principal_variation->size-1;j>=0;j--){
						printf("%s ",principal_variation->moves[j]);
					}
					printf("\n");
					fflush(stdout);
				}
			} else {
				mvl_in_use->moves[i].approx_move_value=-500000;
			}
		} else {
			mvl_in_use->moves[i].approx_move_value = -1000000;
		}
	}

	if(legal_move_found==FALSE){
		if(is_check(brd)){
			return -30000; /* Checkmate */
		} else {
			return 0; /* Stalemate */
		}
	}

	if(best_value<=prev_alpha) {
		add_to_hashtable(brd,maxdepth-depth+this_extension,
			LOWER_BOUND,(short)prev_alpha,best_move);
	} else {
		add_to_hashtable(brd,maxdepth-depth+this_extension,
			EXACT_VALUE,(short)best_value,best_move);
	}

	return best_value;
}

int qsearch(Board *brd,
	int depth,
	int prev_alpha,
	int prev_beta,
	char *best_move,
	PVlist *principal_variation)
{
	Movelist pseudolegal_moves_list;
	PVlist new_principal_variation;
	int i, value, alpha, beta, legal_move_found;
	char new_best_move[6];

	Bitboard key_backup,ep_backup,epr_backup,epnw_backup,epne_backup;
	int half_moves_backup,full_moves_backup;
	unsigned char castling_flags_backup;

	engine_interrupt();

	legal_move_found=FALSE;
	evars.positions_seen++;

	if(evars.flags & EXIT_THINKING_LOOP)
		return EXITING_LOOP;

	if(is_illegal(brd)){
		return ILLEGAL_MOVE;
	}

	alpha = prev_alpha; beta=prev_beta;

	value=evaluate_for_color(brd);
	if(value>=beta) {
		return beta;
	}
	if(value>alpha) {
		alpha=value;
	}

	generate_nonquiescent_moves(brd,&pseudolegal_moves_list);

	qsort(pseudolegal_moves_list.moves,
		pseudolegal_moves_list.size,
		sizeof(Move_node),
		compare_move_values);

	for(i=0;i<pseudolegal_moves_list.size;i++) {
		init_PVlist(&new_principal_variation);

		/* Backups otherwise irrevertible information */
		key_backup.whole=brd->key.whole;
		half_moves_backup=brd->half_moves;
		full_moves_backup=brd->full_moves;
		ep_backup.whole=brd->ep.whole;
		epr_backup.whole=brd->epr.whole;
		epnw_backup.whole=brd->epnw.whole;
		epne_backup.whole=brd->epne.whole;
		castling_flags_backup=brd->castling_flags;

		make_move(brd,&(pseudolegal_moves_list.moves[i]));
		value=-qsearch(brd,depth+1,-beta,-alpha,
			new_best_move,&new_principal_variation);

		unmake_move(brd,&(pseudolegal_moves_list.moves[i]));

		/* Restores backup */
		brd->key.whole=key_backup.whole;
		brd->half_moves=half_moves_backup;
		brd->full_moves=full_moves_backup;
		brd->ep.whole=ep_backup.whole;
		brd->epr.whole=epr_backup.whole;
		brd->epnw.whole=epnw_backup.whole;
		brd->epne.whole=epne_backup.whole;
		brd->castling_flags=castling_flags_backup;

		if(value==-EXITING_LOOP){
			return EXITING_LOOP;
		}
		if(value!=-ILLEGAL_MOVE) {
			legal_move_found=TRUE;
			if(value>=beta){
				return beta; /* Fail high */
			}
			if(value>alpha){
				alpha=value;
				strncpy(best_move,pseudolegal_moves_list.moves[i].move,6);
				copy_PVlist(principal_variation,&new_principal_variation);
				strncpy(principal_variation->moves[principal_variation->size],
					best_move,6);
				principal_variation->size++;
			}
		}
	}

	if(legal_move_found==FALSE){
		return evaluate_for_color(brd);
	}

	return alpha;
}

