search.cpp

有全屏显示的一个很优秀的中国象棋软件.用VC6.0开发

// Search.cpp: implementation of the Search class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "chess.h"
#include "Search.h"
#include "chessDlg.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CChessDlg* pwnd;
Search::Search(CDialog * p)
{
   pWnd=p;
   pwnd=(CChessDlg*)p;
}


int depthend,AutoTime=30000;
int progress[15][2];


Search::~Search()
{

}

void Move(CHESSMOVE&move,BYTE p[][9])
{
	if (p[move.to.x][move.to.y]==5) pwnd->king [0]=FALSE;else if (p[move.to.x][move.to.y]==12) pwnd->king[1]=FALSE;
	p[move.to.x][move.to.y]=p[move.from .x][move.from .y];
	p[move.from .x][move.from .y]=0;

}
void UnMove(CHESSMOVE & move, BYTE p[][9],BYTE thefrom)
{
    p[move.from .x][move.from .y]=p[move.to .x][move.to .y];
	p[move.to .x][move.to .y]=thefrom;
    if (p[move.to.x][move.to.y]==5) pwnd->king [0]=TRUE;else if (p[move.to.x][move.to.y]==12) pwnd->king[1]=TRUE;

}
void Search::EnterLishi(CHESSMOVE & move,int depth)
{
	Lishi[move.from .x*9+move.from .y][move.to.x*9+move.to.y]+=2<<depth;
}
void Search::Sort(CHESSMOVE move[],MOVE mm[],int n)
{
	CHESSMOVE chessmove;
	MOVE chess;
	for (int x=0;x<n-1;x++)
		for (int y=n-1;y>x;y--)
		    if (Lishi[mm[y].from ][mm[y].to ]>Lishi[mm[y-1].from][mm[y-1].to])
			{
				chessmove.from=move[y].from ;
				chessmove.to=move[y].to ;
				move[y].from =move[y-1].from;
				move[y].to =move[y-1].to ;
				move[y-1].from=chessmove.from;
				move[y-1].to=chessmove.to;
				chess.from=mm[y].from ;
				chess.to=mm[y].to ;
				mm[y].to=mm[y-1].to;
				mm[y].from=mm[y-1].from;
				mm[y-1].from=chess.from;
				mm[y-1].to=chess.to;
			}
}

int Search::AB(int depth,int a,int b,BYTE p[][9])
{
	if (depth==0)
		return -pwnd->m_pv->GetValue(p,0);
    if (MaxDepth%2==1) if (!pwnd->king[(depth)%2]) return 10000+(2<<depth);
	if (MaxDepth%2==0) if (!pwnd->king[(depth+1)%2]) 
	{
		return 10000+(2<<depth);
	}
//    if (depth==0)
//		return -pwnd->m_pv->GetValue(p);
    CHESSMOVE move[100];
	MOVE mm[100];
	int n=0,bestmove=-1;
    pwnd->m_ppm->Product(move,mm,n,p,(depth+1)%2,0);
//	ASSERT(depth!=3);
	if (depth==MaxDepth)
	{
		pwnd->m_progress .SetRange (0,n-1);pwnd->m_progress .SetPos(1);

		int maxdepth=MaxDepth;
		MaxDepth=MaxDepth-2;
		int vv[100],top=0;
		ab(MaxDepth,-20000,20000,p,move,vv,top);
		MaxDepth=maxdepth;

	}
	else
	      Sort(move,mm,n);
    if (n==0)
			if (a>0) return a-1;else return a+1;
	for (int x=0;x<n;x++)
	{
		BYTE pp=p[move[x].to.x][move[x].to .y];
		Move(move[x],p);
		int v=-AB(depth-1,-b,-a,p);
//		ASSERT(!(move[x].to.x==3&&move[x].to.y==6));
        if (depth==MaxDepth) {
			pwnd->m_progress .SetPos (x+1);
//			pwnd->message .Format ("%d",v);
//			pwnd->Draw();
//			Sleep(500);
		}
		UnMove(move[x],p,pp);
        if (v>a) {a=v;bestmove=x;if (depth==MaxDepth) {BestMove.from =move[x].from ;BestMove.to =move[x].to ;}}
		if (a>=b) {bestmove=x; break;}
	}
    if (bestmove!=-1)
		EnterLishi(move[bestmove],depth);
	return a;
}
DWORD lasttime;
int lastpos,range;

int Search::AutoAB(int depth,int a,int b,BYTE p[][9])
{
	if (depth==depthend)
		return -pwnd->m_pv->GetValue(p,depthend);
    if ((MaxDepth-depthend)%2==1) if (!pwnd->king[(depth-depthend)%2]) return 10000+(2<<depth);
	if ((MaxDepth-depthend)%2==0) if (!pwnd->king[(depth-depthend+1)%2]) 
	{   
		return 10000+(2<<depth);
	}
//    if (depth==0)
//		return -pwnd->m_pv->GetValue(p);
    CHESSMOVE move[100];
	MOVE mm[100];
	int n=0,bestmove=-1;
    pwnd->m_ppm->Product(move,mm,n,p,(depth-depthend+1)%2,depthend);
//	ASSERT(depth!=3);
	if (depth==MaxDepth)
	{

		int maxdepth=MaxDepth;
		MaxDepth=MaxDepth-2-depthend;
		int vv[100],top=0;
		ab(MaxDepth,-20000,20000,p,move,vv,top);
		MaxDepth=maxdepth;
		lasttime=pwnd->start=GetTickCount();
	    lastpos=0;
		range=n;
		
	}
	else
	      Sort(move,mm,n);
	progress[depth][1]=n;
	progress[depth][0]=progress[depth-1][0];
	if (depth==MaxDepth-2)
	{
		pwnd->m_progress .SetRange (0,progress[MaxDepth][1]*progress[MaxDepth-1][1]*progress[MaxDepth-2][1]);pwnd->m_progress .SetPos(progress[MaxDepth][0]*progress[MaxDepth-1][0]*progress[MaxDepth-2][0]);
	}
    if (n==0)
			if (a>0) return a-1;else return a+1;
	for (int x=0;x<n;x++)
	{
		BYTE pp=p[move[x].to.x][move[x].to .y];
		Move(move[x],p);
		int v=-AutoAB(depth-1,-b,-a,p);
		DWORD t;
		progress[depth][0]=x;
		pwnd->m_progress .SetPos(progress[MaxDepth][0]*progress[MaxDepth-1][0]*progress[MaxDepth-2][0]);
//		ASSERT(!(move[x].to.x==3&&move[x].to.y==6));
		if (depth==depthend+4)
		{
		    t=GetTickCount();
			int pos=pwnd->m_progress.GetPos();
			if (pos!=lastpos)
			{	
			if ((float)(t-lasttime)/AutoTime-(float)(pos-lastpos)/range<-0.0005) 
					{if (depthend>0) depthend--;}
			else if ((float)(t-lasttime)/AutoTime-(float)(pos-lastpos)/range>0.005) 
					{if (depthend<6) depthend++;}
			pwnd->message .Format ("%f,%f,%d       ",(float)(t-lasttime)/AutoTime,(float)(pos-lastpos)/range,depthend);
			pwnd->Draw();
			lastpos=pos;
			lasttime=t;

			}
		}
//        if (depth==MaxDepth) {
//			pwnd->m_progress .SetPos (x);
//			pwnd->message .Format ("%d,%d       ",t-pwnd->start,depthend);
//			pwnd->Draw();
//			Sleep(500);
//		}
		UnMove(move[x],p,pp);
        if (v>a) {a=v;bestmove=x;if (depth==MaxDepth) {BestMove.from =move[x].from ;BestMove.to =move[x].to ;}}
		if (a>=b) {bestmove=x; break;}
	}
    if (bestmove!=-1)
		EnterLishi(move[bestmove],depth);
	return a;
}

int Search::ab(int depth,int a,int b,BYTE p[][9],CHESSMOVE Move1[],int value[],int & top)
{
	if (depth==0)
		return -pwnd->m_pv->GetValue(p,0);
    if (MaxDepth%2==1) if (!pwnd->king[depth%2]) return 10000+(2<<depth);
	if (MaxDepth%2==0) if (!pwnd->king[(depth+1)%2]) 
	{
		return 10000+(2<<depth);
	}
    CHESSMOVE move[100];
	int n=0,bestmove=-1;
	MOVE mm[100];
    pwnd->m_ppm->Product(move,mm,n,p,(depth+1)%2,0);
//	ASSERT(depth!=3);
	if (depth==MaxDepth)
	{
		pwnd->m_p.SetRange (0,n-1);pwnd->m_p.SetPos(0);
	}
	Sort(move,mm,n);
    if (n==0)
			if (a>0) return a-1;else return a+1;
	for (int x=0;x<n;x++)
	{
		BYTE pp=p[move[x].to.x][move[x].to .y];
		Move(move[x],p);
		int v=-ab(depth-1,-b,-a,p,Move1,value,top);
//		ASSERT(!(move[x].to.x==3&&move[x].to.y==6));
		UnMove(move[x],p,pp);
		if (depth==MaxDepth) {
			pwnd->m_p.SetPos (x);
		}
        if (v>a) {a=v;bestmove=x;}
		if (a>=b) {bestmove=x; if (MaxDepth<=4) {if (depth!=MaxDepth-2) break;}else if (depth!=MaxDepth-2&&depth!=MaxDepth-3) {/*if (MaxDepth<=6) break;if (depth!=MaxDepth-3) */break;}}
		
		if (depth==MaxDepth)
		{
        int i=0;
		while (i<top&&v<=value[i+1])i++;
        for (int j=top;j>i;j--)
		{
			value[j]=value[j-1];
			Move1[j].from=Move1[j-1].from;
			Move1[j].to=Move1[j-1].to;
		}
		value[i]=v;
		Move1[i].from=move[x].from;
		Move1[i].to=move[x].to;
		top++;
		}
	}
    if (bestmove!=-1)
		EnterLishi(move[bestmove],depth);
	return a;
}

/*

int Search::ab(int depth,BYTE p[][9],CHESSMOVE Move1[],int value[],int & top)
{
	int a;
	if (depth==0)
		return -pwnd->m_pv->GetValue(p);
//    if (depth==0)
//		return -pwnd->m_pv->GetValue(p);
    CHESSMOVE move[100];
	MOVE mm[100];
	int n=0,bestmove=-1;
    pwnd->m_ppm->Product(move,mm,n,p,(depth+1)%2);
//	ASSERT(depth!=3);
	for (int x=0;x<n;x++)
	{
		BYTE pp=p[move[x].to.x][move[x].to .y];
		Move(move[x],p);
		int v=-ab(depth-1,p,Move1,value,top);
//		ASSERT(!(move[x].to.x==3&&move[x].to.y==6));
		UnMove(move[x],p,pp);
        if (x==0) a=v;
        if (v>a) {a=v;}
		if (depth==MaxDepth)
		{
        int i=0;
		while (i<top&&v<=value[i+1])i++;
        for (int j=top;j>i;j--)
		{
			value[j]=value[j-1];
			Move1[j].from=Move1[j-1].from;
			Move1[j].to=Move1[j-1].to;
		}
		value[i]=v;
		Move1[i].from=move[x].from;
		Move1[i].to=move[x].to;
		top++;
		}

	}
	return a;
}
*/
void Search::Reset ()
{
	memset(Lishi,0,8100*sizeof(long));
}

CHESSMOVE * Search::GetBestMove()
{
    Reset();
	depthend=0;
	memset(progress,0,15*2*4);
	int x;
	if (MaxDepth>7) {depthend=5;x=AutoAB(MaxDepth,-20000,20000,pwnd->Current );}
	else x=AB(MaxDepth,-20000,20000,pwnd->Current );
	pwnd->message .Format ("%d",x);
	return &BestMove;
}