📄 tree.cpp
字号:
// Tree.cpp: implementation of the Tree class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "chess.h"
#include "Tree.h"
#include <math.h>
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
//#define LAYER nodes.GetAt(depth)
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Tree::Tree(int deep,MyChess* chess)
{
PS* psmember=new PS;
POSITION pos;
Node nd;
Deep=0;ActDeep=deep; //Deep is the acture depth
if(chess->BlackOrWhite==0)MyBW=1;
else MyBW=0;
if(SearchDeep==2){MAXNODE=100;MIDNODE=25;}
if(SearchDeep==3){MAXNODE=100;MIDNODE=25;}
if(SearchDeep==4){MAXNODE=70;MIDNODE=25;}
chess->checkme();//delete all the bad chain
chessSource=chess;
CloneChess(chess,chessSource,&(psmember->chessp));
nd.AndOr=FALSE;nd.Depth=0;nd.Leaf=FALSE;
nd.MePos=0;
nd.FatherPos=-1;nd.NextPos=-1;nd.SonPos=-1;
nd.p.x=-1;nd.p.y=-1;nd.v=0;
nodes.Add(nd);
NodeCount=0;
psmember->node=nd.MePos;
Stack.AddTail(*psmember);//Push the root of tree into stack
//del int t=Stack.GetCount();//t should be 1 now
//chess->fileout();
while(!Stack.IsEmpty()){ //when stack is not empty then do this
psmember=&(Stack.GetTail());
pos=Stack.GetTailPosition();
MakeAllPosible(psmember); //this function can generate all nodes of the tree
Stack.RemoveAt(pos);//pop from stack
// out();
}
}
Tree::~Tree()
{
}
MyChess Tree::CopyChess(MyChess * chess1)
{//this function is same as the ChessDoc
MyChess ReturnChess;
int i,j;
ReturnChess.BlackOrWhite=chess1->BlackOrWhite;
ReturnChess.ChainCount=chess1->ChainCount;
ReturnChess.ChessCount=chess1->ChessCount;
for(i=1;i<=chess1->ChessCount;i++)ReturnChess.ChessStep[i]=chess1->ChessStep[i];
for(i=0;i<chess1->ChainCount;i++)ReturnChess.chaintab[i]=chess1->chaintab[i];
for(i=0;i<15;i++){
for(j=0;j<15;j++)ReturnChess.State[i][j]=chess1->State[i][j];
}
return(ReturnChess);
}
void Tree::MakeAllPosible(PS * member)
{
//member is the latest value of the stack
int count;
int x,y,x1=-1,y1=-1;
int i,k;
int pos;
CPoint tp;
MyChess chess1; //this is the original chess
MyChess chess2; //this is the chess1's copy
BOOL End=FALSE; //mark the point whether is checked
CArray<CPoint,CPoint&> Checked; //Memerise all the checked point
PS newps;//The new member to be push the stack
Node node; //the next node of the tree
Node* nd; //the curren node of the stack
BOOL start;
chess1=CopyChess(chessSource);
int linshi=member->chessp.y;
if(linshi>member->chessp.x){
for(i=member->chessp.x;i<linshi;i++){
//CPoint tp=member->State[i];
chess1.PushChess(State[i].x,State[i].y);
}
}
nd=&(nodes.GetAt(member->node));
chess2=CopyChess(&chess1);//backup
count=chess1.ChainCount;
pos=-1;
i=-1;start=TRUE;
while(start){//try all the chain
i++;start=i<count-1;
for(k=1;k<=MAXSTEP;k++){//try all the points
switch(chess1.chaintab[i].EnaAdd){//chain's addable
case 1://left or up
x=chess1.chaintab[i].FirstP.x-k;
y=chess1.chaintab[i].FirstP.y-k;
switch(chess1.chaintab[i].VHState){
case 0://horisen
y=chess1.chaintab[i].FirstP.y;
break;
case 1://vertical
x=chess1.chaintab[i].FirstP.x;
break;
case 3://d-r
y=chess1.chaintab[i].FirstP.y+k;
break;
}
break;
case 2://right or down
x=chess1.chaintab[i].FirstP.x+chess1.chaintab[i].ChainLenth+k-1;
y=chess1.chaintab[i].FirstP.y+chess1.chaintab[i].ChainLenth+k-1;
switch(chess1.chaintab[i].VHState){
case 0://horisen
y=chess1.chaintab[i].FirstP.y;
break;
case 1://vertival
x=chess1.chaintab[i].FirstP.x;
break;
case 3://d-r
y=chess1.chaintab[i].FirstP.y-chess1.chaintab[i].ChainLenth-k+1;
break;
}
break;
case 3://Two sides
x=chess1.chaintab[i].FirstP.x-k;
y=chess1.chaintab[i].FirstP.y-k;
x1=chess1.chaintab[i].FirstP.x+chess1.chaintab[i].ChainLenth+k-1;//two points
y1=chess1.chaintab[i].FirstP.y+chess1.chaintab[i].ChainLenth+k-1;
switch(chess1.chaintab[i].VHState){
case 0:
y=chess1.chaintab[i].FirstP.y;
y1=y;
break;
case 1:
x=chess1.chaintab[i].FirstP.x;
x1=x;
break;
case 3:
y=chess1.chaintab[i].FirstP.y+k;
y1=chess1.chaintab[i].FirstP.y-chess1.chaintab[i].ChainLenth-k+1;
break;
}
break;
}
x--;y--,x1--;y1--;
int t=1;
if(y1>=0)t=2;//if two points
for(int j=0;j<t;j++){
NodeCount=nodes.GetSize();
if(j==t-1&&j!=0){y=y1;x=x1;}
int tc=Checked.GetSize();
for(int k1=0;k1<tc;k1++){//check whether the point is checked
tp=Checked.GetAt(k1);
if(tp.x==x&&tp.y==y)End=TRUE;
}
if(End){End=FALSE;continue;}//if checked the point the end the loop
tp.x=x;tp.y=y;
Checked.Add(tp);//add the point
if(chess2.PushChess(x,y)==1){//if can push here
start=start&&(NodeCount<MAXNODE||
(chess1.chaintab[i].ChainLenth>=2&&
chess1.chaintab[i].EnaAdd==3)||
chess1.chaintab[i].ChainLenth==4);
node.FatherPos=nd->MePos;
//DEL int tcount=nodes[nd->MeX].GetCount();
node.Depth=nd->Depth+1;
node.NextPos=-1;node.SonPos=-1;
if(pos==-1){
pos=NodeCount;
nodes[nd->MePos].SonPos=pos;
}
else{
pos=NodeCount;
nodes[pos-1].NextPos=pos;
}
node.MePos=pos;
node.p.x=x;node.p.y=y;
//del if(nd->Depth==0){//Remeber every cases when the first depth
//del CPoint tp;
//del tp.x=x;tp.y=y;
//del Deside.Add(tp);
//del }
node.v=Value(&chess2,node.Depth);//member's depth
if(chess2.BlackOrWhite!=MyBW)node.AndOr=FALSE;
else node.AndOr=TRUE;
double tv=fabs(node.v-nodes[member->node].v);
if(node.v>=MAXF-1||node.v<=MINF+1 //Can judge who win
||node.Depth==ActDeep //Get the depth of searching
||chess2.ChessCount==MAXCHESS
||(NodeCount>=MIDNODE&&tv<10)
||NodeCount>MAXNODE) //if chess full
node.Leaf=TRUE;//if is the leaf
else {node.Leaf=FALSE;}
nodes.Add(node);//generate a node of the tree
CloneChess(&chess1,&chess2,&(newps.chessp));
newps.node=node.MePos;
if(nodes[newps.node].Depth>Deep)Deep=nodes[newps.node].Depth;//Value the Deep
if(!node.Leaf)Stack.AddTail(newps);//Stack.AddTail(newps);//if node is not the leaf then push the stack
chess2=CopyChess(&chess1);//reutrn to the original
//int tc=Stack.GetCount();
}
}
}
}
// out();
}
float Tree::Value(MyChess * chess1, int depth)
{
int i;
BOOL t=FALSE;
float MeF=0,EnemyF=0,MeWeight=float(0.3),EnemyWeight=float(0.7);
float f=0;//the sub value
chess1->checkme();//del all bad chain
// chess1->fileout();
chess1->chiefchess();
// chess1->fileout();
t=0;
for(i=0;i<chess1->ChainCount;i++){
if(chess1->chaintab[i].ChainLenth==5&&chess1->chaintab[i].EnaAdd<10){//this step have 5
if(MyBW!=chess1->chaintab[i].BorW)return(float(MINF));
else return(float(MAXF));
}
else{
if(chess1->BlackOrWhite!=chess1->chaintab[i].BorW){
if(chess1->chaintab[i].ChainLenth==4){//next step have 4
if(MyBW==chess1->chaintab[i].BorW)return(float(MAXF-1));
else return(float(MINF+1));
}
}
if(chess1->chaintab[i].ChainLenth==4//own free 4
&&(chess1->chaintab[i].EnaAdd==3)){
if(MyBW==chess1->chaintab[i].BorW)f=float(MAXF-1);
else f=float(MINF+1);
t=TRUE;
continue;
}
}
if((chess1->chaintab[i].EnaAdd==1
||chess1->chaintab[i].EnaAdd==2
||chess1->chaintab[i].EnaAdd>=11)
&&(chess1->chaintab[i].ChainLenth==4)){
if(MyBW==chess1->chaintab[i].BorW)MeF+=200;
else EnemyF+=200;
}
if((chess1->chaintab[i].EnaAdd==3
||chess1->chaintab[i].EnaAdd==13)
&&chess1->chaintab[i].ChainLenth==3){
if(MyBW==chess1->chaintab[i].BorW)MeF+=100;
else EnemyF+=100;
}
if((chess1->chaintab[i].EnaAdd==1
||chess1->chaintab[i].EnaAdd==2
||chess1->chaintab[i].EnaAdd==11
||chess1->chaintab[i].EnaAdd==12)
&&chess1->chaintab[i].ChainLenth==3){
if(MyBW==chess1->chaintab[i].BorW)MeF+=5;
else EnemyF+=5;
}
if(chess1->chaintab[i].EnaAdd==3
&&chess1->chaintab[i].ChainLenth==2){
if(MyBW==chess1->chaintab[i].BorW)MeF+=4;
else EnemyF+=4;
}
if(((chess1->chaintab[i].EnaAdd==1
||chess1->chaintab[i].EnaAdd==2)
&&chess1->chaintab[i].ChainLenth==2)
||(chess1->chaintab[i].EnaAdd==3
&&chess1->chaintab[i].ChainLenth==1)){
if(MyBW==chess1->chaintab[i].BorW)MeF+=2;
else EnemyF+=2;
}
if((chess1->chaintab[i].EnaAdd==1
||chess1->chaintab[i].EnaAdd==2)
&&chess1->chaintab[i].ChainLenth==1){
if(MyBW==chess1->chaintab[i].BorW)MeF+=1;
else EnemyF+=1;
}
}
if(t)return(f);
f=MeWeight*MeF-EnemyWeight*EnemyF;
return(f);
}
CPoint Tree::Result()
{
CList<PSTWO,PSTWO> PsStatus;
PSTWO ps;
PSTWO pstemp;
PSTWO* ps1=new PSTWO;
int pos=0;
//POSITION postemp;
int postemp1;
float maxv;
Node* tempnode;
Node* tempnode1;
CPoint BestPoint;
//for(i=0;i<=ActDeep;i++)postemp[i]=nodes[i].GetHeadPosition();
//del BestPoint.x=Deside[0].x;BestPoint.y=Deside[0].y;
tempnode1=&(nodes.GetAt(pos));
pos++;
maxv=float(MINF);
do{
ps.nd=&(nodes.GetAt(pos));
pos++;
ps.open=TRUE;
ps.v=MAXF;
PsStatus.AddTail(ps);
do{
pstemp=PsStatus.GetTail();
ps1=&pstemp;
PsStatus.RemoveTail();
//int t=PsStatus.GetCount();
if(!ps1->open){
if(ps1->nd->Depth==1)break;
else if(ps1->nd->AndOr){
//tempnode=nodes[ps1->nd->FatherX].GetHead();
//postemp=nodes[tempnode->FatherX].GetHeadPosition();
//while(postemp!=NULL){
// tempnode=nodes[tempnode->FatherX].GetNext();
// if(tempnode->MeX==ps1->nd->FatherX)break;
//}
tempnode=&(nodes.GetAt(ps1->nd->FatherPos));
ps.nd=tempnode;
ps.open=FALSE;
ps.v=ps1->v;
PsStatus.AddTail(ps);
DelSubTree(ps1->nd,&PsStatus);
continue;
}
else{
postemp1=ps1->nd->NextPos;
if(postemp1!=-1)tempnode=&(nodes.GetAt(postemp1));
if(postemp1!=-1&&tempnode->FatherPos==ps1->nd->FatherPos){
ps.nd=tempnode;
ps.open=FALSE;
ps.v=ps1->v;
}
else{
tempnode=&(nodes.GetAt(ps1->nd->FatherPos));
ps.nd=tempnode;
ps.open=FALSE;ps.v=ps1->v;
}
PsStatus.AddTail(ps);
continue;
}
}
if(ps1->open){
if(ps1->nd->Leaf){
float fv;
fv=ps1->v;
if(fv>=ps1->nd->v)fv=ps1->nd->v;
Insert(ps1->nd,fv,&PsStatus);
continue;
}
else if(ps1->nd->AndOr){
tempnode=&(nodes.GetAt(ps1->nd->SonPos));
ps.nd=tempnode;
ps.open=TRUE;
ps.v=ps1->v;
PsStatus.AddTail(ps);
continue;
}
else{
postemp1=ps1->nd->SonPos;
if(postemp1!=-1)tempnode=&(nodes.GetAt(postemp1));
while(postemp1>=0){
tempnode=&(nodes.GetAt(postemp1));
postemp1=tempnode->NextPos;
ps.nd=tempnode;
ps.open=TRUE;
ps.v=ps1->v;
PsStatus.AddTail(ps);
}
continue;
}
}
}while(TRUE);
if(maxv<=ps1->nd->v){
BestPoint.x=ps1->nd->p.x;BestPoint.y=ps1->nd->p.y;
maxv=ps1->nd->v;
}
}while(ps.nd->NextPos!=-1);
return(BestPoint);
}
void Tree::DelSubTree(Node * nd,CList<PSTWO,PSTWO>* stack)
{
int i;
int pos;
POSITION pos1;
Node* tempnode;
Node* tempnode1;
PSTWO tempstack;
pos=nd->NextPos;
i=stack->GetCount();
pos1=stack->GetHeadPosition();
while(pos!=-1){
tempnode=&(nodes.GetAt(pos));
if(nd->SonPos!=-1)tempnode1=&(nodes.GetAt(nd->SonPos));
pos=tempnode->NextPos;
while(pos1!=NULL&&i>=0){
i--;
tempstack=stack->GetNext(pos1);
if(tempstack.nd->MePos!=tempnode->MePos){
stack->AddHead(tempstack);
}
else{
if(nd->Leaf)break;
else DelSubTree(tempnode1,stack);
}
}
}
}
void Tree::Insert(Node *nd, float v,CList<PSTWO,PSTWO>* ps)
{
POSITION pos;
PSTWO tempnd;
PSTWO pstemp;
pos=ps->GetHeadPosition();
int t=ps->GetCount();
if(t==0){
pstemp.nd=nd;
pstemp.open=FALSE;
pstemp.v=v;
ps->AddTail(pstemp);
}
while(pos!=NULL){
tempnd=ps->GetNext(pos);
if(tempnd.v>=v){
pstemp.nd=nd;
pstemp.open=FALSE;
pstemp.v=v;
ps->InsertBefore(pos,pstemp);
break;
}
}
}
//DEL void Tree::out()
//DEL {
//DEL FILE* fp;
//DEL POSITION pos;
//DEL int i=0;
//DEL PS* ps;
//DEL fp=fopen("stack.txt","w");
//DEL pos=Stack.GetHeadPosition();
//DEL while(pos!=NULL){
//DEL i++;
//DEL ps=&(Stack.GetNext(pos));
//DEL fprintf(fp,"%i: chaincount,chesscount,pointx-pointy\n",i);
//DEL // fprintf(fp,"%i,%i,%i-%i\n",ps->chessp->,ps->chessp->ChessCount,ps->chessp.chaintab[ps->chessp.ChainCount-1].FirstP.x,ps->chessp.chaintab[ps->chessp.ChainCount-1].FirstP.y);
//DEL fprintf(fp,"node.p.x,node.p.y,node.FatherX,node.MeX,node.v\n");
//DEL fprintf(fp,"%i,%i,%i,%i,%f\n",nodes[ps->node].p.x,nodes[ps->node].p.y,nodes[ps->node].FatherPos,nodes[ps->node].MePos,nodes[ps->node].v);
//DEL fprintf(fp,"\n");
//DEL }
//DEL fprintf(fp,"Nodes infos\n");
//DEL i=nodes.GetSize();
//DEL for(int j=0;j<i;j++){
//DEL fprintf(fp,"node:p.x,p.y,FatherX,MeX,next,son,AndOr,Depth,Leaf, V:%i\n",j);
//DEL fprintf(fp," %i, %i, %i, %i, %i, %i, %i, %i, %i, %f3\n",nodes[j].p.x,nodes[j].p.y,nodes[j].FatherPos,nodes[j].MePos,nodes[j].NextPos,nodes[j].SonPos,nodes[j].AndOr,nodes[j].Depth,nodes[j].Leaf,nodes[j].v);
//DEL }
//DEL fclose(fp);
//DEL }
void Tree::CloneChess(MyChess * BaseChess, MyChess * DestChess,CPoint* array)
{
int i;
int t=State.GetSize();
array->x=t;
for(i=BaseChess->ChessCount+1;i<=DestChess->ChessCount;i++){
State.Add(DestChess->ChessStep[i].p);
}
array->y=State.GetSize();
}
void Tree::PSInsert(PS ps,float v)
{
POSITION pos1;
//POSITION pos2;
PS* tempps;
v=float(fabs(v));
pos1=Stack.GetHeadPosition();
int t=Stack.GetCount();
int j=0;
if(t==0)Stack.AddTail(ps);
while(pos1!=NULL){
tempps=&(Stack.GetNext(pos1));
j++;
float v1=nodes[tempps->node].v;
if(v>=v1){
Stack.InsertAfter(pos1,ps);
break;
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -