// PCN1.cpp     Last Modified: 23/10/96   Probabilistic Conspiracy Numbers.
// (c) Robin Upton 1996
// Available from www.RobinUpton.com/research/phd/pcn1.cpp
class CPVector {
	double _CP[NoDiscreteValues];
public:
	double CP(int) const;			
	void Set_Cell(int, double);                             
	CPVector();
};        
class Node {
	unsigned long _seed;		/* Used to generate determined pseudo-random descendants. */
	BoardPosn* _position;	
	long _depth;                                                 
	int _score;
	CPVector* _CPV;
	Node* _parent;	                                           
	int _childno;			/* How this node is ordered in parent's child[ ] array. */
	Node* _child[MaxNoChildren];	/* Children ordered by score. */
	long depth() const;
 	int childno() const;
	void Add_child(Node*); 		/* used in Expand(). */
	void Number_children();		/* used in Expand(). */
	void Recalculate_CPvector();
	void Updated_child(int); 	/* Percolates changes up the tree. */
	int isbetter(int, int) const; 	/* > for MAX nodes, < for MIN nodes. */
	int ispreferable_to(Node*) const; /* Compares score, and if necessary CPV().*/
public:
	unsigned long seed() const;
	BoardPosn* position() const;
	int score() const;
	CPVector* CPV() const;
	double CP(int) const;
	Node* up() const;
	Node* child(int) const;
	Node(BoardPosn*,  Node*, unsigned long);
	void Con_search(int);	/* Search and try to change score to (int) or more. */
	void Expand();		/* Expands node with simple 1-ply search. */
	void PCN_Expand();	/* PCN updating that follows a call to Expand(). */
	int player() const;
};	

extern long Search_Time=DefaultSearchTime;
extern unsigned long No_Nodes_Searched=0;
 
void main(int argc, char *argv[] ){
 unsigned root_seed=1;           /* Game tree variables. */
 Node *best_kid, *pcn_root;      /* PCN* variables.*/
 long Last_Search_Time;		
 double cons_prob, most_likely_cp;
 int best_nmrv, new_minrootvalue, overall_best_cn, best_cn_this_child, child_no;
	pcn_root=new Node(new BoardPosn(ROOTSCORE),0,root_seed);/*Initialise the pcn search tree.*/
	if (argc>1) Search_Time= atoi(argv[1]);   /* Read the command line argument. */
	Last_Search_Time= Search_Time;
	pcn_root->PCN_Expand();
        do {/* Select the most likely strategy, S.*/
	   best_kid=pcn_root->child(0);
	   most_likely_cp=best_cn_this_child=0;
	   for (new_minrootvalue=pcn_root->child(1)->score();
		new_minrootvalue<=1+pcn_root->score(); new_minrootvalue++)
	        {/* Look at all new_minrootvalues between 1st & 2nd best node's scores. */
	          cons_prob=child_no=0;
		  /* Search through the children other than the best one. */
                  while (pcn_root->child(++child_no)!=0)
		if (pcn_root->child(child_no)->CP(new_minrootvalue)>cons_prob) /* Pick the best CP. */
	          		{ best_cn_this_child=child_no; 
	          		   cons_prob=pcn_root->child(child_no)->CP(new_minrootvalue); };
	          cons_prob*=best_kid->CP(new_minrootvalue-1);/* Root must also be degraded. */
	          if (cons_prob>most_likely_cp) 
	          		{/* Update the details of the best conspiracy. */
	          		  overall_best_cn=best_cn_this_child;
	          		  best_nmrv=new_minrootvalue;
	          		  most_likely_cp= cons_prob; }
                 }/* We now know that the best conspiracy is one in which                       */
  /*  pcn_root->child(0)               conspires to worse than `best_nmrv`              */
  /*  pcn_root->child(overall_best_cn) conspires to better than or equal to `best_nmrv` */
	   if (most_likely_cp > 0)  
	   		{pcn_root->child(overall_best_cn)->Con_search(best_nmrv);
	          best_kid->Con_search(best_nmrv-pcn_root->player());}
			/* Use 'best_kid', in case the children have been reordered. */
	   else  {FILE* DebugF=fopen(DEBUGFILE,"a");
                  fprintf(DebugF,"Search ended due to impossibility of conspiracy.\n");
                  fclose(DebugF); break; /* Exit if the game is over. */ }
	}             
	while (Search_Time>0);
}

void Node::Number_children()
 {int c=0; for (c=0; c<MaxNoChildren && child(c)!=0; c++) child(c)->_childno=c; }
void Node::Recalculate_CPvector() {
double best_prob_yet, prob_so_far;
int childno, cellscore;
	/* Calculate the CPV cells for the 'desired' changes. */
	for (cellscore=MINVALUE+(player()==MAX)*(NoDiscreteValues-1);
		cellscore!=score(); cellscore-=player())
		{best_prob_yet=0; childno=0;
		  do best_prob_yet=__max(best_prob_yet, child(childno)->CP(cellscore));
		  while (child(++childno)!=0);
		  CPV()->Set_Cell(cellscore,best_prob_yet);}
	/* Calculate the CPV cells for the 'undesired' changes. */
	for (cellscore=MINVALUE+(player()==MIN)*(NoDiscreteValues-1);
		cellscore!=score(); cellscore+=player())
		{prob_so_far=1; childno=0;
		  do prob_so_far*= child(childno)->CP(cellscore); 
		  while (child(++childno)!=0  && isbetter(child(childno)->score(),cellscore));
		 CPV()->Set_Cell(cellscore, prob_so_far);}
	CPV()->Set_Cell(score(),1); /* Set CPV cell for the null change.*/
}

void Node::Updated_child(int child_no){/*called when _child[child_no] is updated.*/
Node* temp;
int newscore=child(child_no)->score();
 while (child_no>0 && (isbetter(newscore, child(child_no-1)->score())))
   /* Promote child(child_no).*/
   { temp=child(child_no-1);
     _child[child_no-1]=child(child_no);
     _child[child_no]=temp; /* Swap the two node pointers around. */
     child(child_no-1)->_childno--;
     child(child_no)->_childno++; /* Update the _childno records. */
     child_no--; };
     while ((child(child_no+1)!=0)&&(isbetter(child(child_no+1)->score(),newscore)))
	/*  Demote child(child_no).*/
	{temp=child(child_no+1);
	_child[child_no+1]=child(child_no);
	_child[child_no]=temp; /* Swap the two node pointers around. */
	child(child_no)->_childno--;
	child(child_no+1)->_childno++; /* Update the _childno records. */
	child_no++; };
     _score=child(0)->score(); /* Update the new score. */
     Recalculate_CPvector(); 
     // It is possible to reduce the complexity of Recalculate_CPVector()
     // here, by making use of the parameter passed. 					
     if(up()!=0)up()->Updated_child(childno());/* Percolate changes up the tree. */
}

int Node::isbetter(int i1, int i2) const { return player()*i1 > player()*i2; }
int Node::ispreferable_to(Node* N) const {
double margin=0; /* How much better "this" is than 'N'.*/
int celldiff=0;
	if (isbetter(score(), N->score())) return 0;
	if (isbetter(N->score(), score())) return 1;
	do /* Scores equal, so we compare the cells of the CPV... */
		{celldiff++;
		  if (score()+celldiff<=MAXVALUE)
			margin-=player()*(CP(score()+celldiff)-N->CP(score()+celldiff));
		  if (score()-celldiff>=MINVALUE)
			margin+=player()*(CP(score()-celldiff)-N->CP(score()-celldiff));
		  if (margin>0) return 1;else if (margin<0) return 0;}
	while (score()+celldiff>MAXVALUE && score()-celldiff<MINVALUE);
	return 1;/* Arbitrarily break ties against 'N' if we've no more cells to compare.*/
}
                         
unsigned long Node::seed() const { return _seed; }
BoardPosn* Node::position() const { return _position; }
int Node::score() const {return _score; }
CPVector* Node::CPV() const { return _CPV; }
double Node::CP(int cell) const { return CPV()->CP(cell); }
Node* Node::up() const { return _parent; }
Node* Node::child(int childno) const { return _child[childno]; }
Node::Node(BoardPosn* b, Node* parent, unsigned long newseed ) {
int i;
	No_Nodes_Searched++; /* Keep track of #nodes expanded. */
        Search_Time--; /* Keep track of amount of time used. */
        _seed=newseed;
	_position=b;
	_score=b->evaluate();
	_parent=parent;
	if (up()==0) _depth=0; else _depth=1+up()->depth();
        _CPV=b->get_ppd(player());
	for (i=0; i<MaxNoChildren; i++) _child[i]=0;
}

void Node::Con_search(int target) {
/* Picks conspiracy most likely to achieve score 'target' or more. */
int child_no=0;
 if (score()!=target) /* The target is not achieved - so conspire... */
   {if (child(0)==0) PCN_Expand();  /* We are at a leaf - expand. */                                        
   else if (isbetter(target, score()))
   /* Desirable change. Pick the node with the highest consp. prob. */
   {while (CP(target) > child(child_no)->CP(target))   child_no++;
   child(child_no)->Con_search(target);}
   else /* Undesirable change. */
   {do child(child_no)->Con_search(target);
   /* All nodes with a score > target need to conspire. */
   while (isbetter(child(child_no)->score(), target) && child(++child_no)!=0);};
   }
}
                                                                                                                                                                                  
void Node::PCN_Expand(){/* Expands node and recalculates CPVector as appropriate. */
 Expand();                                     /* First expand the node. */
 Number_children();                            /* Order them appropriately. */
 _score=child(0)->score();                     /* Get the new score first... */
 Recalculate_CPvector();                       /* then the new CPVector. */
 if (up()!=0) up()->Updated_child(childno());  /* Percolate stuff up the tree. */
}

void Node::Expand() { /* Expands node, with a 1-ply search. */
int child_no=0;       
BoardPosnArray* childboards=position()->get_kids(BRANCHINGFACTOR, seed());
	while (child_no<MaxNoChildren && childboards->posn(child_no)!=0)
{Node* new_child=new Node(childboards->posn(child_no),this,next_seed(seed(),child_no));
	  Add_child(new_child); /* Add the extra child.*/
	  child_no++; }
}

int Node::player() const { return 1-(int)(2*(depth()%2));}
double CPVector::CP(int cellscore) const { return _CP[cellscore-(MINVALUE)];}
void CPVector::Set_Cell(int cellscore,double value){_CP[cellscore-(MINVALUE)]=value;}
CPVector::CPVector() {int i; for (i=0; i<NoDiscreteValues; i++)	_CP[i]=0; }