// ****************************************************************************
// *                                                                          *
// *                      Velena Source Code V1.0                             *
// *                   Written by Giuliano Bertoletti                         *
// *       Based on the knowledged approach of Louis Victor Allis             *
// *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
// *                                                                          *
// ****************************************************************************

// Portable engine version.
// read the README file for further informations.

// ==========================================================================


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#include "connect4.h"
#include "con4vals.h"
#include "rules.h"
#include "pnsearch.h"
#include "proto.h"

#include "heurist.h"

extern short nodeseq[];
extern struct board *auxboard;

struct bintree *streeroot;
struct node *rootnode;

char fight_for_win=0;

void fight(char t)
    {
    fight_for_win=t;
    }

short whatfight()
    {
    return (short)fight_for_win;
    }

long her_node_expanded,her_node_not_expanded;

void her_generate_all_children(struct node *node)
	{
	struct node *dummy,*symm;
	short x,y,x1,y1,backtrace;

	for(x=0;x<BOARDX;x++)
		{
		if(node->child[x]) fatal_error("Tried to allocate a node twice!");
		else if(node->stack[x]<BOARDY)
			{
			node->child[x]=(struct node *)c4_malloc(sizeof(struct node));
			symm=(struct node *)c4_malloc(sizeof(struct node));

			if(!node->child[x] || !symm)
				printf ("her_generate_all_children1\n");

			memcpy(node->child[x]->square,node->square,(BOARDX+1)*(BOARDY+2));
			memcpy(node->child[x]->stack,node->stack,BOARDX+1);
			backtrace=x;

			node->child[x]->square[ELM(x,node->child[x]->stack[x]++)]=node->turn;
			node->child[x]->turn=node->turn^SWITCHSIDE;
			symm->turn=node->turn^SWITCHSIDE;

			for(y1=0;y1<BOARDY;y1++)
				{
				symm->square[ELM(BOARDX,y1)]=node->child[x]->square[ELM(BOARDX,y1)];
				for(x1=0;x1<BOARDX;x1++)
					symm->square[ELM(x1,y1)]=node->child[x]->square[ELM(BOARDX-x1-1,y1)];
				}

			symm->stack[BOARDX]=node->child[x]->stack[BOARDX];
			for(x1=0;x1<BOARDX;x1++)
				symm->stack[x1]=node->child[x]->stack[BOARDX-x1-1];

			if(bin_compare(symm->square,node->child[x]->square)>0)
				{
				dummy=symm;
				symm=node->child[x];
				node->child[x]=dummy;
				backtrace=BOARDX-x-1;
				}

            dummy=fast_check_node(streeroot,node->child[x],0);
			if(dummy)
				{
				free(node->child[x]);
				node->child[x]=dummy;
				node->child[x]->parent[backtrace]=node;
				her_node_not_expanded++;
				}
			else
				{
				node->child[x]->expanded=NO;
				node->child[x]->evaluated=NO;

				for(y=0;y<BOARDX;y++)
					node->child[x]->parent[y]=NULL;

				node->child[x]->parent[backtrace]=node;

				for(y=0;y<BOARDX;y++)
					node->child[x]->child[y]=NULL;

				her_node_expanded++;

				if(node->type==AND_TYPE) node->child[x]->type=OR_TYPE;
				else if(node->type==OR_TYPE) node->child[x]->type=AND_TYPE;
				else fatal_error("Could not recognize node type!");

				/*add_node(streeroot,node->child[x]);*/
				}

			node->symmetric[x]=backtrace;
			free(symm);
			}

		else node->child[x]=NULL;
		}
	}

void her_free_whole_tree(struct bintree *tree)
	{
	short x;

	if(!tree) return;
	if(tree->lson) her_free_whole_tree(tree->lson);
	if(tree->rson) her_free_whole_tree(tree->rson);

	free(tree->node);
	}

short her_evaluate(struct node *node)
	{
    short x,bestmove;

	node->evaluated=YES;

	for(x=0;x<64;x++)
		auxboard->square[x]=(short)node->square[x];

	auxboard->turn=node->turn;
	auxboard->filled=0;

	for(x=0;x<BOARDX+1;x++)
		{
		auxboard->stack[x]=(short)node->stack[x];
		if(x<BOARDX) auxboard->filled+=auxboard->stack[x];
		}

	if(auxboard->filled==MAXMEN)
		{
        if(rootnode->turn==WHITE)
            {
            if(!fight_for_win)
                {
                if(rootnode->type==OR_TYPE) node->value=DISPROVED;
                else node->value=PROVED;
                }
            else
                {
                if(rootnode->type==OR_TYPE) node->value=PROVED;
                else node->value=DISPROVED;
                }
            }
        else
            {
            if(!fight_for_win)
                {
                if(rootnode->type==OR_TYPE) node->value=PROVED;
                else node->value=DISPROVED;
                }
            else
                {
                if(rootnode->type==OR_TYPE) node->value=DISPROVED;
                else node->value=PROVED;
                }
            }
		return -1;
		}

    bestmove=fast_try_to_win(auxboard);
    if(bestmove!=-1)
        {
        if(node->type==OR_TYPE)  node->value=PROVED;
        if(node->type==AND_TYPE) node->value=DISPROVED;
        }

    else node->value=UNKNOWN;

    return bestmove;
	}

short her_resources_available(long maxnodes)
	{
	if(her_node_expanded>maxnodes) return NO;
	return YES;
	}

struct node *her_select_most_proving_node(struct node *node,struct info *info)
	{
	short i,flag,depth=0;

	while(node->expanded)
		{
		i=0;
		flag=FALSE;

		switch(node->type)
			{
			case OR_TYPE:
				do
					{
					if(node->child[nodeseq[i]] &&
						node->child[nodeseq[i]]->proof==node->proof)
							flag=TRUE;
					else i++;
					} while(i<BOARDX && !flag);

				if(!flag)
					fatal_error("Could not find a good OR child!");
				break;

			case AND_TYPE:
				do
					{
					if(node->child[nodeseq[i]] &&
						node->child[nodeseq[i]]->disproof==node->disproof)
							flag=TRUE;
					else i++;
					} while(i<BOARDX && !flag);

				if(!flag)
					fatal_error("Could not find a good AND child!");
				break;

			default:
				fatal_error("Unknown node type!");
				break;

			}
		if(!flag) fatal_error("Null node found!");
		else
			{
			if(depth==0) info->bestmove=nodeseq[i];
			node=node->child[nodeseq[i]];
			}

		depth++;
		}

	info->max_tree_depth=max(info->max_tree_depth,depth+1);
	return node;
	}


void her_set_pdv_according_to_children(struct node *node)
	{
	short x,children=0;

	for(x=0;x<BOARDX;x++)
		if(node->stack[x]<BOARDY) children++;

	if(children==0)
		fatal_error("Father without children but of value unknown");

	switch(node->type)
		{
		case AND_TYPE:
			node->proof=children;
			node->disproof=1;
			break;

		case OR_TYPE:
			node->proof=1;
			node->disproof=children;
			break;
		}
	}


void her_set_proof_and_disproof_numbers(struct node *node)
	{
	short x;

	if(!node) fatal_error("Invalid node choosen");
	else if(node->expanded)
		{
		switch(node->type)
			{
			case AND_TYPE:
				node->proof=0;
				node->disproof=MAXVALUE;
				for(x=0;x<BOARDX;x++)
					if(node->child[x])
						{
						node->proof+=node->child[x]->proof;
						node->disproof=min(node->disproof,node->child[x]->disproof);
						}
					if(node->disproof==0) node->proof=MAXVALUE;
				break;

			case OR_TYPE:
				node->proof=MAXVALUE;
				node->disproof=0;
				for(x=0;x<BOARDX;x++)
					if(node->child[x])
						{
						node->proof=min(node->proof,node->child[x]->proof);
						node->disproof+=node->child[x]->disproof;
						}
					if(node->proof==0) node->disproof=MAXVALUE;
				break;

			default:
				fatal_error("I don't know what to prove or disprove!");
				break;
			}

		if(node->proof<0 || node->disproof<0)
			fatal_error("Proof and disproof numbers cannot be lower than zero");

		}
	else if(node->evaluated)
		{
		switch(node->value)
			{
			case PROVED:
				node->proof=0;
				node->disproof=MAXVALUE;
				break;

			case DISPROVED:
				node->proof=MAXVALUE;
				node->disproof=0;
				break;

			case UNKNOWN:
				her_set_pdv_according_to_children(node);
				break;
			}
		}
	else fatal_error("Asked to set a node never evaluated!");
	}

void her_develop_node(struct node *node)
	{
	short i;

	node->expanded=YES;
	her_generate_all_children(node);

	for(i=0;i<BOARDX;i++)
		{
		if(node->child[i])
			{
			her_evaluate(node->child[i]);
			her_set_proof_and_disproof_numbers(node->child[i]);
			}
		}
	}

void her_update_ancestors(struct node *node)
	{
	struct node *previous_node;
	short x;

	if(node)
		{
		her_set_proof_and_disproof_numbers(node);

		for(x=0;x<BOARDX;x++)
			if(node->parent[x]) her_update_ancestors(node->parent[x]);
		}
	}

void her_pn_search(struct node *root,long maxnodes,struct info *info)
	{
	struct node *her_most_proving_node;
    short fl;

	info->max_tree_depth=1;
	info->bestmove=her_evaluate(root);
	her_set_proof_and_disproof_numbers(root);

	while(root->proof!=0 && root->disproof!=0 && her_resources_available(maxnodes))
		{
		her_most_proving_node=her_select_most_proving_node(root,info);
		her_develop_node(her_most_proving_node);
		her_update_ancestors(her_most_proving_node);
		}

	if(root->proof==0) root->value=PROVED;
	else if (root->disproof==0) root->value=DISPROVED;
	else root->value=UNKNOWN;
	}

short heuristic_search(struct node *mynode,long maxnodenum)
	{
	struct info info;
	short x;

	if(mynode->expanded || mynode->evaluated)
		fatal_error("Request to evaluate a node already evaluated or expanded!");

	mynode->evaluated=YES;

	rootnode=(struct node *)c4_malloc(sizeof(struct node));
	if(!rootnode) printf ("heuristic_search1\n");

	memcpy(rootnode,mynode,sizeof(struct node));

	her_node_expanded=0L;
	her_node_not_expanded=0L;

    for(x=0;x<BOARDX;x++)
		rootnode->parent[x]=NULL;

    streeroot=fast_init_bin_tree(rootnode);
	her_pn_search(rootnode,maxnodenum,&info);

    mynode->value=rootnode->value;
    mynode->proof=rootnode->proof;
    mynode->disproof=rootnode->disproof;

    her_free_whole_tree(streeroot);
    fast_free_bin_tree(streeroot);

	if(mynode->value!=UNKNOWN) return YES;
	return NO;
	}


/* Avoid tricks */

short heuristic_play_best(struct board *board,long maxnodenum)
	{
	struct board *tempboard;
    struct info info;
    short mymove,fl;
	struct node *symmetric;
	short x,y,issymm=NO;

	auxboard=board;
	tempboard=(struct board *)c4_malloc(sizeof(struct board));
	if(!tempboard) printf ("heuristic_play_best1\n");
	memcpy(tempboard,board,sizeof(struct board));

	rootnode=(struct node *)c4_malloc(sizeof(struct node));
	symmetric=(struct node *)c4_malloc(sizeof(struct node));
	if(!rootnode || !symmetric) printf ("heuristic_play_best2\n");

	for(y=0;y<BOARDY;y++)
		{
		rootnode->square[ELM(BOARDX,y)]=(unsigned char)(board->square[ELM(BOARDX,y)]&0xff);
		symmetric->square[ELM(BOARDX,y)]=(unsigned char)(board->square[ELM(BOARDX,y)]&0xff);
		for(x=0;x<BOARDX;x++)
			{
			rootnode->square[ELM(x,y)]=(unsigned char)(board->square[ELM(x,y)]&0xff);
			symmetric->square[ELM(x,y)]=(unsigned char)(board->square[ELM(BOARDX-x-1,y)]&0xff);
			}
		}

	rootnode->turn=board->turn;
	symmetric->turn=board->turn;

	for(x=0;x<BOARDX;x++)
		{
		rootnode->stack[x]=(unsigned char)(board->stack[x]&0xff);
		symmetric->stack[x]=(unsigned char)(board->stack[BOARDX-1-x]&0xff);
		}

	rootnode->stack[BOARDX]=(unsigned char)(board->stack[BOARDX]&&0xff);
	symmetric->stack[BOARDX]=(unsigned char)(board->stack[BOARDX]&&0xff);

	if(bin_compare(symmetric->square,rootnode->square)>0)
		{
		free(rootnode);
		rootnode=symmetric;
		issymm=YES;
		}
	else free(symmetric);

	her_node_expanded=0L;
	her_node_not_expanded=0L;

	for(x=0;x<BOARDX;x++)
		{
		rootnode->parent[x]=NULL;
		rootnode->child[x]=NULL;
		}

	rootnode->evaluated=NO;
	rootnode->expanded=NO;
	rootnode->value=UNKNOWN;
	rootnode->type=OR_TYPE;

    streeroot=fast_init_bin_tree(rootnode);
	her_pn_search(rootnode,maxnodenum,&info);
	mymove=info.bestmove;

    if(rootnode->value==UNKNOWN) mymove=-1;
    else if(rootnode->value==DISPROVED) mymove=-2;
	else if(issymm) mymove=BOARDX-1-mymove;

	her_free_whole_tree(streeroot);
    fast_free_bin_tree(streeroot);

	memcpy(board,tempboard,sizeof(struct board));
	free(tempboard);

	board->nodes_visited=her_node_expanded+her_node_not_expanded;
	board->maxtreedepth=info.max_tree_depth;
	return mymove;
	}