www.pudn.com > fivesource.zip > Game.cpp
/////////////////////////////////////////////////////////////////////////////////////
// 五子棋分析程序:
// 1996.4-1997.11 刘国辉
/////////////////////////////////////////////////////////////////////////////////////
// 说明：
// ~~~~~~~
// 约定：
// ~~~~~~~
// ‘W' 代表白棋
// 'B' 代表黑棋
// 'N' 代表空地
//（1）平分函数:
// ~~~~~~~~~~~~~~
// int Dump( int x,int Wf )
// X 在一条线上的子数
// WF = 1 两边都没有被堵住 例如 NNWWWNB..
// = 0 一边被堵住 BWWWNNW..
// = 2 跨越式的 WWWNW..
// 返回一个分数
//（2）线扫描函数:
// ~~~~~~~~~~~~~~~~
// int SreachLine( char *FLine,int M,int MF )
// FLine 线指针,指向一个字符串 NNNWWWBWWWN...
// M 字符个数
// WF ='W'或'B'表示对黑或白进行平分
// 返回一个分数
// (3)面扫描函数:
// ~~~~~~~~~~~~~~~
// long SreachArea( char *Area[15],int M,char WF )
// ....
/////////////////////////////////////////////////////////////////////////////////////
#include "game.h"
#include // For rand()
/////////////////////////////////////////////////////////////////////////////////////
// 静态成员初始化
// ~~~~~~~~~~~~~~~
int CFive::WF1_1;
int CFive::WF1_2;
int CFive::WF1_3;
int CFive::WF1_4;
int CFive::WF0_1;
int CFive::WF0_2;
int CFive::WF0_3;
int CFive::WF0_4;
int CFive::WF2_3;
int CFive::WF2_4;
int CFive::WF5;
int CFive::DeepMax;
int CFive::BreadthMax;
int CFive::Delta;
int CFive::ThreadDeepMax;
char CFive::Side;
BOOL CFive::PlayStateFlags;
int CFive::PlayIndex;
char CFive::FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
CList CFive::StepList;
CList CFive::OneCountList;
CArray CFive::ImpList;
CEvent CFive::KillWzqRun(FALSE,TRUE);
CStatusBar* CFive::pInfo;
long CFive::MemoryCount;
int CFive::ThreadCount;
long CFive::JingDuCount;
Count CFive::PiShen;
/////////////////////////////////////////////////////////////////////////////////////
// 顺序化
// ~~~~~~
IMPLEMENT_SERIAL( CFive, CWinThread, 1 )
/////////////////////////////////////////////////////////////////////////////////////
// 构造与析构
// ~~~~~~~~~~~
CFive::CFive():EndEvent( FALSE,TRUE )
{
m_bAutoDelete = FALSE; // 不自动删除CWinThread对象
CurDeep = DeepMax;
CurBreadth = BreadthMax;
CurThreadDeep = ThreadDeepMax;
CurSide = Side;
CurCount = 0;
PlayStateFlags= FALSE;
}
CFive::CFive( char side,int deep,int breadth,int threaddeep ):EndEvent( FALSE,TRUE )
{
m_bAutoDelete = FALSE; // 不自动删除CWinThread对象
CurSide = (side == 'B'?'W':'B');
CurDeep = deep - 1;
if( CurDeep < 0 )
CurDeep = -1;
CurThreadDeep = threaddeep - 1;
if( CurThreadDeep < 0 )
CurThreadDeep = -1;
if( CurSide == Side )
CurBreadth = BreadthMax - (DeepMax-CurDeep)*Delta;
else
CurBreadth = 1;
if( CurBreadth < 0 )
CurBreadth = -1;
if( CurThreadDeep < 0 )
CurThreadDeep = -1;
CurCount = 0;
}
CFive::~CFive()
{
}
////////////////////////////////////////////////////////////////////////////////////
// 初始化
// ~~~~~~
void CFive::WzqInit( char side,BOOL flags )
{
int i,j;
Side = side;
CurSide = side;
CurDeep = DeepMax;
CurBreadth = BreadthMax;
CurThreadDeep = ThreadDeepMax;
PlayStateFlags= FALSE;
PiShen.count = WZQ_YOU;
StepList.RemoveAll();
for( i = 0;i < FIVE_MAX_LINE;i++ )
for( j = 0;j < FIVE_MAX_LINE;j++ )
FiveArea[i][j] = 'N';
if( flags == FALSE )
{
Step temp;
int mx,my;
mx = FIVE_MAX_LINE/2 -2;
my = mx;
mx += rand()%4;
my += rand()%4;
FiveArea[mx][my] = Side;
temp.side = Side;
temp.m = mx;
temp.n = my;
StepList.AddTail(temp);
}
}
void CFive::SetInfo( CStatusBar*p)
{
pInfo = p;
}
void CFive::SetParam( int breadth,int deep,int thread,int delta )
{
BreadthMax = breadth;
DeepMax = deep;
ThreadDeepMax = thread;
Delta = delta;
}
void CFive::GetParam( int& breadth,int& deep,int& thread,int& delta )
{
breadth = BreadthMax;
deep = DeepMax;
thread = ThreadDeepMax;
delta = Delta;
}
char CFive::GetSide()
{
return Side;
}
char CFive::GetSubPosition( int m,int n )
{
if( m >=0&&n>=0&&m= StepList.GetCount() )
return FALSE;
PlayIndex = StepList.GetCount();
UpdatePlay();
return TRUE;
}
BOOL CFive::BackOneStep()
{
PlayStateFlags = TRUE;
if( PlayIndex > 0 )
{
PlayIndex--;
UpdatePlay();
return TRUE;
}
return FALSE;
}
BOOL CFive::FowardOneStep()
{
PlayStateFlags = TRUE;
if( PlayIndex < StepList.GetCount() )
{
PlayIndex++;
UpdatePlay();
return TRUE;
}
return FALSE;
}
void CFive::UpdatePlay()
{
int i,j;
POSITION pos;
Step step;
for( i = 0;i= 5 )
{
while( Fline[ i+j ] != Wf && i+j < M )
i++;
if( i > 4 )
{
for( k = 0; k < i; k++ )
{
n = 0;
while( Fline[ j+k ] == Nf && k < i )
{
n++;
k++;
}
if( n )
{
if( n > 4 )
return -1; //发现5子
if( n == k || k == i )
Wf = 0;
else
Wf = 1;
if( n == 2 && Wf == 1 )
if((k+13&&Fline[ j+k-4 ]==Nf))
{
n++;
Wf = 2;
}
if( n == 3 && Wf == 0 )
if((k+14&&Fline[ j+k-5 ]==Nf))
{
n++;
Wf = 2;
}
count = count + Dump( n , Wf );
}
}
}
j = j + i + 1;
i = 0;
}
return count;
}
long CFive::SreachArea( char Area[][FIVE_MAX_LINE],char Nf )
{
int i,j,cbak;
long count = 0;
char Fline[FIVE_MAX_LINE];
for( i = 0; i < FIVE_MAX_LINE; i++ )
{
for( j = 0; j < FIVE_MAX_LINE; j++ )
Fline[j] = Area[i][j];
cbak = SreachLine( Fline,FIVE_MAX_LINE,Nf );
if( cbak == -1 )
return -1;
else
count = count + (long)cbak;
}
for( i = 0; i < FIVE_MAX_LINE; i++ )
{
for( j = 0; j < FIVE_MAX_LINE; j++ )
Fline[j] = Area[j][i];
cbak = SreachLine( Fline,FIVE_MAX_LINE,Nf );
if( cbak == -1 )
return -1;
else
count = count + (long)cbak;
}
for( i = 0; i < FIVE_MAX_LINE - 4; i++ )
{
for( j = 0; j < FIVE_MAX_LINE - i; j++ )
Fline[j] = Area[i+j][j];
cbak = SreachLine( Fline, FIVE_MAX_LINE-i, Nf );
if( cbak == -1 )
return -1;
else count = count + (long)cbak;
}
for( i = FIVE_MAX_LINE-1; i > 3; i-- )
{
for( j = 0; j < i+1; j++ )
Fline[j] = Area[i-j][j];
cbak = SreachLine( Fline, i+1, Nf );
if( cbak == -1 )
return -1;
else
count = count + (long)cbak;
}
for( i = 0; i < FIVE_MAX_LINE - 5; i++ )
{
for( j = 0; j < FIVE_MAX_LINE - i; j++ )
Fline[j] = Area[i+j][FIVE_MAX_LINE-j];
cbak = SreachLine( Fline, FIVE_MAX_LINE-i, Nf );
if( cbak == -1 )
return -1;
else
count = count + (long)cbak;
}
for( i = FIVE_MAX_LINE-1; i > 4; i-- )
{
for( j = 0; j < i+1; j++ )
Fline[j] = Area[i-j][FIVE_MAX_LINE-j];
cbak = SreachLine( Fline, i+1, Nf );
if( cbak == -1 )
return -1;
else
count = count + (long)cbak;
}
return count;
}
////////////////////////////////////////////////////////////////////////////////////////////
// 在Call WzqRun前Call WzqTest以测试当前情况
int CFive::WzqTest( int m,int n )
{
char Nf,Mf;
int i,j;
Step step_temp;
Nf = Side;
MemoryCount = 0;
ThreadCount = 0;
JingDuCount = 0;
if( PlayStateFlags == TRUE )
{
PlayStateFlags= FALSE;
ResumePlayState();
return WZQ_HAVE;
}
if( Nf == 'B' )
Mf = 'W';
else if( Nf == 'W' )
Mf = 'B';
else
return WZQ_ERROR;
for( i = 0;i= FIVE_MAX_LINE||n < 0||n >= FIVE_MAX_LINE )
return WZQ_HAVE;
if( FiveArea[m][n] != 'N' )
return WZQ_HAVE;
if( SreachArea( FiveArea,Nf ) == -1 )
return WZQ_I;
if( SreachArea( FiveArea,Mf ) == -1 )
return WZQ_YOU;
FiveArea[m][n] = (Side == 'W'?'B':'W');
step_temp.side = (Side == 'W'?'B':'W');
step_temp.m = m;
step_temp.n = n;
StepList.AddTail( step_temp );
PlayIndex = StepList.GetCount();
if( SreachArea( FiveArea,Nf ) == -1 )
return WZQ_I;
if( SreachArea( FiveArea,Mf ) == -1 )
return WZQ_YOU;
return WZQ_RUN;
}
int CFive::WzqEndTest()
{
char Nf,Mf;
int i,j;
Nf = Side;
MemoryCount = 0;
ThreadCount = 0;
JingDuCount = 0;
if( Nf == 'B' )
Mf = 'W';
else if( Nf == 'W' )
Mf = 'B';
else
return WZQ_ERROR;
if( SreachArea( FiveArea,Nf ) == -1 )
return WZQ_I;
if( SreachArea( FiveArea,Mf ) == -1 )
return WZQ_YOU;
for( i = 0;i= FIVE_MAX_LINE||n < 0||n >= FIVE_MAX_LINE )
return WZQ_HAVE;
// if( FiveArea[m][n] != 'N' )
// return WZQ_HAVE;
if( BiTest( mm,nn ) == FALSE )
{
OneCountList.RemoveAll();
CreateThread();
//------------------------------------------------
// EndEvent.Lock();
// WaitForSingleObject( m_hThread,INFINITE );
// if( OneCountList.IsEmpty() )
// return WZQ_ERROR;
//
// temp = OneCountList.GetHead();
// max_count = temp.count;
// mm = temp.step.m;
// nn = temp.step.n;
//
// pos = OneCountList.GetHeadPosition();
// while( pos != NULL )
// {
// temp = OneCountList.GetNext( pos );
// if( temp.count > max_count )
// {
// max_count = temp.count;
// mm = temp.step.m;
// nn = temp.step.n;
// }
// }
//----------------------------------------------------
}
else
return WZQ_NOTHREAD;
//----------------------------------------------------
// if( mm == m&&nn == n )
// return WZQ_ERROR;
// FiveArea[mm][nn] = Side;
// step_temp.side = Side;
// step_temp.m = mm;
// step_temp.n = nn;
// StepList.AddTail( step_temp );
// PlayIndex = StepList.GetCount();
//-----------------------------------------------------
return WZQ_RUN;
}
int CFive::GetCurStep(int &mm,int &nn)
{
int m,n;
POSITION pos;
double max_count;
Count temp;
Step step_temp;
if( PiShen.count == WZQ_I )
{
step_temp = PiShen.step;
mm = PiShen.step.m;
nn = PiShen.step.n;
step_temp.side = Side;
FiveArea[mm][nn] = Side;
StepList.AddTail( step_temp );
PlayIndex = StepList.GetCount();
return WZQ_RUN;
}
////////////////////////////////////////////////////////////////////////////////
// if( OneCountList.IsEmpty() )
// return WZQ_ERROR;
////////////////////////////////////////////////////////////////////////////////
if( CountList.IsEmpty() )
return WZQ_ERROR;
// temp = OneCountList.GetHead();
temp = CountList.GetHead();
max_count = temp.count;
mm = temp.step.m;
nn = temp.step.n;
///////////////////////////////////////////////////////////////////////////////
// pos = OneCountList.GetHeadPosition();
// while( pos != NULL )
// {
// temp = OneCountList.GetNext( pos );
// if( temp.count > max_count )
// {
// max_count = temp.count;
// mm = temp.step.m;
// nn = temp.step.n;
// }
// }
//////////////////////////////////////////////////////////////////////////////
pos = CountList.GetHeadPosition();
while( pos != NULL )
{
temp = CountList.GetNext( pos );
if( temp.count > max_count )
{
max_count = temp.count;
mm = temp.step.m;
nn = temp.step.n;
}
}
if( mm == m&&nn == n )
return WZQ_ERROR;
FiveArea[mm][nn] = Side;
step_temp.side = Side;
step_temp.m = mm;
step_temp.n = nn;
StepList.AddTail( step_temp );
PlayIndex = StepList.GetCount();
return WZQ_RUN;
}
void CFive::Serialize( CArchive& ar )
{
int i,j;
BYTE flags0,flags1;
if (ar.IsStoring())
{
// TODO: add storing code here
ar<<(BYTE)0xfa;
ar<<(BYTE)0x5e;
ar<>flags0;
ar>>flags1;
if( flags0!=0xfa||flags1!=0x5e)
AfxThrowFileException(CFileException::accessDenied);
StepList.RemoveAll();
ar>>WF0_1;
ar>>WF0_2;
ar>>WF0_3;
ar>>WF0_4;
ar>>WF1_1;
ar>>WF1_2;
ar>>WF1_3;
ar>>WF1_4;
ar>>WF2_3;
ar>>WF2_4;
ar>>WF5;
ar>>BreadthMax;
ar>>DeepMax;
ar>>ThreadDeepMax;
ar>>Delta;
ar>>Side;
for( i = 0;i>FiveArea[i][j];
StepList.Serialize( ar );
ImpList.Serialize( ar );
ar>>PlayStateFlags;
ar>>PlayIndex;
if( PlayStateFlags == TRUE )
UpdatePlay();
}
}
////////////////////////////////////////////////////////////////////////////////////////////
// 抽象平分函数
// ~~~~~~~~~~~~~
// Nf ----------对那一方平分'B'或'W'
// level--------方法COUNT_INC,COUNT_SUB,COUNT_MID
///////////////////////////////////////////////////////////////////////////////////////////
void CFive::CalRun( char Nf,LEVE leve )
{
if( CurBreadth <= 0 )
return;
MemoryCount++;
JingDuCount++;
char Mf;
int i,j,num;
double Ncount,Mcount,TempCount,TempCount1,wf5temp;
Count *pCount,temp;
char Area[FIVE_MAX_LINE][FIVE_MAX_LINE];
POSITION pos;
Step steptemp;
Mf = ( Nf == 'B'?'W':'B');
pCount = new Count[CurBreadth];
for( i = 0;i < CurBreadth;i++ )
{
pCount[i].count = -9999999;
pCount[i].step.side = 'E';
}
for( i = 0;i < FIVE_MAX_LINE;i++ )
for( j = 0;j < FIVE_MAX_LINE;j++ )
Area[i][j] = FiveArea[i][j]; //复制FiveArea数组
pos = DeepList.GetHeadPosition( );
while(pos != NULL)
{
steptemp = DeepList.GetNext(pos);
Area[steptemp.m][steptemp.n] = steptemp.side;
}
switch( leve )
{
case COUNT_INC:
Ncount = SreachArea( Area,Nf );
for( i = 0;i < FIVE_MAX_LINE;i++ )
{
for( j = 0;j < FIVE_MAX_LINE;j++ )
{
if( Area[i][j] == 'N' )
{
Area[i][j] = Nf;
wf5temp = SreachArea( Area,Nf );
if( wf5temp == -1 )
wf5temp = 2*Dump( 5,10 ) + Ncount;
TempCount = wf5temp - Ncount;
if( TempCount > pCount[0].count )
{
pCount[0].count = TempCount;
pCount[0].step.side = Nf;
pCount[0].step.m = i;
pCount[0].step.n = j;
for( num = 1;num < CurBreadth;num++ )
if( pCount[0].count > pCount[num].count )
{
temp = pCount[num];
pCount[num] = pCount[0];
pCount[0] = temp;
}
}
Area[i][j] = 'N';
}
}
}
break;
case COUNT_SUB:
Mcount = SreachArea( Area,Mf );
for( i = 0;i < FIVE_MAX_LINE;i++ )
{
for( j = 0;j < FIVE_MAX_LINE;j++ )
{
if( Area[i][j] == 'N' )
{
Area[i][j] = Nf;
TempCount = Mcount - SreachArea( Area,Mf );
if( TempCount > pCount[0].count )
{
pCount[0].count = TempCount;
pCount[0].step.side = Nf;
pCount[0].step.m = i;
pCount[0].step.n = j;
for( num = 1;num < CurBreadth;num++ )
if( pCount[0].count > pCount[num].count )
{
temp = pCount[num];
pCount[num] = pCount[0];
pCount[0] = temp;
}
}
Area[i][j] = 'N';
}
}
}
break;
case COUNT_MID:
Mcount = SreachArea( Area,Mf );
Ncount = SreachArea( Area,Nf );
for( i = 0;i < FIVE_MAX_LINE;i++ )
{
for( j = 0;j < FIVE_MAX_LINE;j++ )
{
if( Area[i][j] == 'N' )
{
Area[i][j] = Nf;
wf5temp = SreachArea( Area,Nf );
if( wf5temp == -1 )
wf5temp = Ncount + 2*Dump( 5,10 );
TempCount1 = wf5temp - Ncount;
TempCount = Mcount - SreachArea( Area,Mf );
TempCount = TempCount + TempCount1;
if( TempCount > pCount[0].count )
{
pCount[0].count = TempCount;
pCount[0].step.side = Nf;
pCount[0].step.m = i;
pCount[0].step.n = j;
for( num = 1;num < CurBreadth;num++ )
if( pCount[0].count > pCount[num].count )
{
temp = pCount[num];
pCount[num] = pCount[0];
pCount[0] = temp;
}
}
Area[i][j] = 'N';
}
}
}
break;
case COUNT_ALPHA:
Mcount = SreachArea( Area,Mf );
Ncount = SreachArea( Area,Nf );
for( i = 0;i pCount[0].count )
{
pCount[0].count = TempCount;
pCount[0].step.side = Nf;
pCount[0].step.m = i;
pCount[0].step.n = j;
for( num = 1;num < CurBreadth;num++ )
if( pCount[0].count > pCount[num].count )
{
temp = pCount[num];
pCount[num] = pCount[0];
pCount[0] = temp;
}
}
Area[i][j] = 'N';
}
}
break;
case COUNT_DELTA:
Mcount = SreachArea( Area,Mf );
Ncount = SreachArea( Area,Nf );
for( i = 0;i TempCount )
TempCount = TempCount1;
if( TempCount > pCount[0].count )
{
pCount[0].count = TempCount;
pCount[0].step.side = Nf;
pCount[0].step.m = i;
pCount[0].step.n = j;
for( num = 1;num < CurBreadth;num++ )
if( pCount[0].count > pCount[num].count )
{
temp = pCount[num];
pCount[num] = pCount[0];
pCount[0] = temp;
}
}
Area[i][j] = 'N';
}
}
break;
}
for( num = 0;num < CurBreadth;num++ )
if( pCount[num].step.side != 'E' )
CountList.AddTail( pCount[num] );
delete pCount;
MemoryCount--;
}
/////////////////////////////////////////////////////////////////////////////////////////////
// 给下一层次加入深度列表
// ~~~~~~~~~~~~~~~~~~~~~~~
void CFive::AddDeepList( Step step )
{
DeepList.AddTail( step );
}
Step CFive::GetLastDeepList()
{
return DeepList.GetTail();
}
double CFive::GetStepCount()
{
POSITION pos;
double temp;
Count steptemp;
temp = 0;
pos = CountList.GetHeadPosition();
while(pos != NULL)
{
steptemp = CountList.GetNext(pos);
temp = steptemp.count + temp;
}
if( CurCount == Side )
return (temp+CurCount);
else
return (-temp+CurCount);
}
/////////////////////////////////////////////////////////////////////////////////////////////
// 搜索安排函数
// ~~~~~~~~~~~~~
void CFive::ThreadRun()
{
if( WaitForSingleObject( KillWzqRun,0 ) == WAIT_OBJECT_0 )
return;
if( CurDeep <= 0 || CurBreadth <= 0 )
{
return;
}
/////////////////////////////////////////////////////////////////////////////////
// 显示信息
// ~~~~~~~~~
// {
// TCHAR Buf[50];
// wsprintf( Buf,"%d",ThreadCount );
// pInfo->SetPaneText(2,Buf );
// wsprintf( Buf,"%2fMb",MemoryCount*600/1024/1024 );
// pInfo->SetPaneText(3,Buf );
// }
/////////////////////////////////////////////////////////////////////////////////
if( CurThreadDeep > 0 )
{
POSITION pos,postemp;
CFive **pFive;
int i,num;
i = 0;
//...........................................................................................
CalRun( CurSide, COUNT_ALPHA );
num = CountList.GetCount();
pFive = (CFive**)new BYTE[sizeof(CFive*)*num];
pos = CountList.GetHeadPosition();
while(pos)
{
pFive[i] = new CFive( CurSide,CurDeep,CurBreadth,CurThreadDeep );
postemp = DeepList.GetHeadPosition();
while( postemp )
{
pFive[i] -> AddDeepList( DeepList.GetNext( postemp ));
}
pFive[i] -> AddDeepList( CountList.GetNext( pos ).step );
pFive[i] -> CreateThread(); //Create thread
i++;
}
for( i=0;i < num;i++ )
{
pFive[i]->EndEvent.Lock();
WaitForSingleObject( pFive[i] -> m_hThread,INFINITE );
CurCount += pFive[i] -> GetStepCount();
if( CurDeep == DeepMax )
{
Count count_temp;
count_temp.step = pFive[i] -> GetLastDeepList();
count_temp.count = pFive[i] -> GetStepCount();
OneCountList.AddTail( count_temp );
}
delete pFive[i];
}
delete pFive;
}
else
{
int i,num;
POSITION pos,postemp;
//...........................................................................................
CalRun( CurSide,COUNT_ALPHA );
num = CountList.GetCount();
pos = CountList.GetHeadPosition();
while( pos )
{
if( WaitForSingleObject( KillWzqRun,0 ) == WAIT_OBJECT_0 )
return;
{
postemp = DeepList.GetHeadPosition();
if( CurSide == Side )
{
CFive five( CurSide,CurDeep,CurBreadth,CurThreadDeep );
while( postemp )
{
five.AddDeepList( DeepList.GetNext( postemp ));
}
five.AddDeepList( CountList.GetNext( pos ).step );
i++;
five.ThreadRun();
CurCount += five.GetStepCount();
if( CurDeep == DeepMax )
{
Count count_temp;
count_temp.step = five.GetLastDeepList();
count_temp.count = five.GetStepCount();
OneCountList.AddTail( count_temp );
}
}else
{
CFive five( CurSide,CurDeep,CurBreadth,CurThreadDeep );
while( postemp )
{
five.AddDeepList( DeepList.GetNext( postemp ));
}
five.AddDeepList( CountList.GetNext( pos ).step );
i++;
five.ThreadRun();
CurCount += five.GetStepCount();
if( CurDeep == DeepMax )
{
Count count_temp;
count_temp.step = five.GetLastDeepList();
count_temp.count = five.GetStepCount();
OneCountList.AddTail( count_temp );
}
}
}
}
}
}
BOOL CFive::InitInstance()
{
ThreadCount++;
ThreadRun();
return FALSE;
}
int CFive::ExitInstance()
{
ThreadCount--;
EndEvent.SetEvent();
return CWinThread::ExitInstance();
}