_gamer.cpp

利用c++编写的带人工智能的跳棋程序。屏幕的中央是棋盘

    
    /* 下面这个语句段用来对FarWin和NearWin进行判断和改变，以达到在不同情况下采取不同的搜索方法之目的*/
    //-----------------------开始－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
    for(i=0;i<10;i++)					// 搜寻是否有走到目的节点的棋子
    {
        if( tNodes[ 120-MyChessman[i] ].Chessman  == type )
            data[0].Score += ReachAim;			// 若本方有，则给评估函数值加ReachAim(10*27)
        else if( tNodes[ MyChessman[i] ].Chessman == enemy )
            data[1].Score += ReachAim;			// 若对手有，则给评估函数值加ReachAim(10*27)
    }
    if( FarWin == 1 )					// 若双方棋子还没有交锋，则FarWin为真（非零值）
    {
        if( MyChessman[0] == 0 )			// 若游戏者原来占据棋盘的正上方，则Pos[0][9]是最
            if( Pos[0][9] > Pos[1][0] )			// 前端的棋子，Pos[1][0]是对手最前端的棋子	
                FarWin = 0;				// 交锋，则FarWin为假（零值）
        else if( Pos[0][0] < Pos[1][9] )		// 若游戏者原来占据棋盘的正下方，则Pos[0][0]是最
           						// 前端的棋子，Pos[1][9]是对手最前端的棋子
                 FarWin = 0;				// 交锋，则FarWin为假（零值）
    }
    else						// 若双方棋子已经交锋
    if( NearWin!=1)
    {
        if( data[0].Score > 8*ReachAim )		// 若已有至少8个棋子到达目的地，即马上要结束
            NearWin = 1;				// 则NearWin 为真（非零值）
        if( MyChessman[0] == 0 )			// 若游戏者原来占据棋盘的正上方，则Pos[0][0]是最
            if( Pos[0][0] > Pos[1][9] )                 // 后端的棋子，Pos[1][9]是对手最后端的棋子	
                NearWin = 1;				// 双方的棋子已经离开，则NearWin 为真（非零值）
        else if( Pos[0][9] < Pos[1][0] )		// 若游戏者原来占据棋盘的正下方，则Pos[0][9]是最
        						// 后端的棋子，Pos[1][0]是对手最后端的棋子
                 NearWin = 1;				// 双方的棋子已经离开，则NearWin 为真（非零值）
    }
    
    if( data[0].Score == 10*ReachAim )    		// 若10个棋子全部到达目的地，则将评估值置为最大
    {							// 返回
            data[0].Score = 20000;
            return data[0];
    }
    
    data[0].Score = data[1].Score = 0 ;			// 最后将评估函数值重置为零，下面开始真正的评估
    //-----------------------------结束-----------------------------------------------------
    
    // 开始评估
    _Coodinate cood[2],iCood;
    k = 120-MyChessman[0];				// k为目的地中的最远节点的序号
    cood[0] = tNodes[k].cood;				// cood[0]存放最远目的节点的坐标
    cood[1] = tNodes[ MyChessman[0] ].cood;		// cood[1]存放本方初始最后面节点的坐标
    int t,m;
    for( j = 0;j<2;j++)
    {
        for(i=Sumdis=0;i<10;i++)			// 一次循环完成所有节点（本方或对手）与最远
        {						// 目的节点（或本方初始最后面节点）的距离评估值
            iCood = tNodes[ Pos[j][i] ].cood;
            t = abs(cood[j].x-iCood.x);			// 每个节点与最远目的节点（本方初始最后面节点）
            						// 的横坐标之差的绝对值
            m = abs(cood[j].y-iCood.y);			// 每个节点与最远目的节点（本方初始最后面节点）
            						// 的纵坐标之差的绝对值
            m *= 1.15;           			// 将纵坐标之差的绝对值乘1.15
            m += t;					// 将两个值相加
            m = m/10;					// 将这个和除以10
            Sumdis +=  m*m;				// 将上面得到的结果平方和累积
        }
        if( cood[j].y > 100 )    			// 若本方原来占据了正上方，则t=0
            t = 0;             		 		
        else t = 5;					// 若本方原来占据了正下方，则t=5
        for(i = t;i < t+4;i++)				// 若走后边的棋子则有加分
           if( (h = tNodes[ Pos[j][i+1] ].cood.y - tNodes[ Pos[j][i] ].cood.y ) > 50 )
               Sumdis += (h-1)*150/27;
        data[j].Score += DisStep*( 20000 - Sumdis ) ;	// 得到该游戏者的评估值
    }
    if( NearWin == 0 && FarWin == 0 )			// 若处于中盘阶段则需要从本方的评估值中
    							// 减掉对手的评估值与权重的乘积
        data[0].Score  -= data[1].Score*EnemyScoreQuotiety;
	return data[0];
}
//---------------------------------------------------------------------------------------------
void _Robot::GetAllMyPath(_Path *AllPath,_Nodes *tNodes,int type)	
{							// 取得所有可走路径的函数，参数分别为指向存放所有
							// 可走位置数组的指针，指向棋盘的指针，游戏者序号
							// 将结果记录在第一个参数中
    int n,i,k,j;
    int chess[10];  					// 记录当前10个棋子位置的数组
    for(i=k=0;i<121;i++)  				// 搜索10个指定棋子的位置
    {
        if( tNodes[i].Chessman == type )
             chess[k++] = i;
        tNodes[i].visited = 0;				// 所有的棋子目前都没有被访问
    }
    _Nodes Node;
    for(i=0;i<10;i++)					// 对10个棋子进行循环
    {
        n=0;
        AllPath[i].count = 0;				// 第i个棋子可走的位置有0个
        AllPath[i].start =chess[i];			// 记录第i个棋子起始点序号
        Node=tNodes[AllPath[i].start];			// 当前是棋盘上的第i个棋子的起始点
        for(j=0;j<6;j++)				// 判断相邻的位置是否可以走棋，若是，则记为可走节点
        	if( Node.pointers[j] != 0 )
                if(Node.pointers[j]->Chessman == 0)
	                Node.pointers[j]->visited =1;

        DFS2(AllPath[i].start,tNodes);			// 判断其他的位置是否能够走棋
        for(k=0;k<121;k++)				// 记录所有可以走棋的位置于Allpath数组中
            if(tNodes[k].visited ==1)
            {
                AllPath[i].path[n++]=k;
                tNodes[k].visited = 0;
            }
        AllPath[i].count=n;				// 所有可走的位置的总数
    }
}

//---------------------------------------------------------------------------------------------
_EvalueData _Robot::Search(_Nodes *tNodes,int Depth)	// 全搜索法，参数分别为指向棋盘的指针和搜索深度
{
    int i,j,Enemy;
    _EvalueData MaxData,NowData;			// 存放最大评估值和当前评估值的评估结构体
    _Path AllPath[10];   				// 存放十个棋子的可走位置
    MaxData.Score = -1000;				// 最大评估值初始化为-1000
    _GamerQuen *tQuen;					// 游戏者顺序的链表
    Depth--;                         			// 深度减1many !turns!
    GetAllMyPath(AllPath,tNodes,gamerID);         	// 取得所有可以走的位置
    if( gamerID == 1 )					// 确定对手的序号
        Enemy = 2;
    else Enemy = 1;
    for(i=j=0;i<10;i++)          			// 对10个棋子进行循环
	for(j=0;j<AllPath[i].count;j++)   		// 对该棋子的所有可走节点进行循环
		{
							// 走到某个节点
		tNodes[ AllPath[i].path[j] ].Chessman = tNodes[ AllPath[i].start ].Chessman;
		tNodes[ AllPath[i].start ].Chessman = 0;
            	if(Depth == 0)				// 若搜索深度为0，评估当前的棋局
                	NowData = Evalue(tNodes,gamerID,Enemy);	
            	else 					// 若搜索深度不为0，则递归调用Search
            		NowData = Search(tNodes,Depth); 
		if( NowData.Score > MaxData.Score )  	// 若当前的棋局比较好，则替换最大评估函数值
			{
                 	MaxData.Score = NowData.Score;
                 	MaxData.start = AllPath[i].start ;
                 	MaxData.end = AllPath[i].path[j];
            		}
							// 将这一步走回去，回到原来的状态
		tNodes[ AllPath[i].start ].Chessman = tNodes[ AllPath[i].path[j] ].Chessman;
		tNodes[ AllPath[i].path[j] ].Chessman = 0;
		}
    return MaxData;					// 返回最大的评估值
}

//---------------------------------------------------------------------------------------------
_EvalueData _Robot::aBSearch(_Nodes *tNodes,int Depth,int ParentScore)
{							// 剪枝搜索法，参数分别为指向棋盘的指针，
							// 搜索深度，上一层的评估值
    int i,j,Enemy;
    _EvalueData MaxData,NowData;			// 存放最优评估值和当前评估值的评估结构体
    _Path AllPath[10];   				// 存放10个棋子可走位置的数组
    _GamerQuen *tQuen;					// 指向游戏者顺序的链表
    Depth--;						// 搜索深度减1
    if( GamerQuen->GamerId == gamerID) 			// 根据当前节点的归属决定它的初值
        MaxData.Score = -20000;          		
    else
        MaxData.Score = 20000;
    GetAllMyPath(AllPath,tNodes,GamerQuen->GamerId);   	// 取得所有可以走的位置
    for(i=j=0;i<10;i++)          			// 对10个棋子进行循环
	for(j=0;j<AllPath[i].count;j++)   		// 对每个可走的位置进行循环
		{
							// 走到某个可走的位置
		tNodes[ AllPath[i].path[j] ].Chessman = tNodes[ AllPath[i].start ].Chessman;
		tNodes[ AllPath[i].start ].Chessman = 0;
            						// 转到下一个游戏者
            	tQuen = GamerQuen,GamerQuen = GamerQuen->Next;
	        if(Depth == 0)				// 若搜索的深度已经为0
            		{				// 确定对手的序号
                	if( GamerQuen->GamerId == gamerID) 
                    		Enemy = GamerQuen->EnemyId ;
                	else Enemy = GamerQuen->GamerId ;
                					// 评估当前的棋局
                	NowData = Evalue(tNodes,gamerID,Enemy);
            		}
            	else 					// 若搜索的深度不为0，则递归搜索
            		NowData = aBSearch(tNodes,Depth,MaxData.Score); 

            	if( GamerQuen->GamerId == gamerID ) 	// 若当前游戏者正是原来的游戏者
            	{					
                	if( NowData.Score <= ParentScore ) 	
                	{				// 若当前评估函数值小于初值，则减掉这一支
                    					// 将初值赋给最优评估值
                    		MaxData.Score = ParentScore;
                    					// 将这一步再走回去
                    		tNodes[ AllPath[i].start ].Chessman = tNodes[ AllPath[i].path[j] ].Chessman;
		    		tNodes[ AllPath[i].path[j] ].Chessman = 0;
		        	GamerQuen = tQuen;	// 将游戏者转回去
                    		return MaxData;
                	}
                	else if( NowData.Score < MaxData.Score )
	    		{				// 若当前评估函数值优于（大于等于）初值，保留
	    						// 将当前值赋给最优评估值
                     		MaxData.Score = NowData.Score;	
                     		MaxData.start = AllPath[i].start ;
                     		MaxData.end = AllPath[i].path[j];
                	}
             	}
             	else					// 若当前的游戏者已经是原来游戏者的对手
             	{
                	if( NowData.Score >= ParentScore ) 	
                	{				// 若当前的评估值大于等于初值，则减掉这一支
                					// 将初值赋给最优评估值
                    		MaxData.Score = ParentScore;	
                    		tNodes[ AllPath[i].start ].Chessman = tNodes[ AllPath[i].path[j] ].Chessman;
	            		tNodes[ AllPath[i].path[j] ].Chessman = 0;
                    		GamerQuen = tQuen;	// 将游戏者转回去
                    		return MaxData;
                	}
                	else if( NowData.Score > MaxData.Score )
                	{				// 若当前评估值优于（小于）初值，保留
                					// 将当前值赋给最优评估值
                     		MaxData.Score = NowData.Score;	
                     		MaxData.start = AllPath[i].start ;
                     		MaxData.end = AllPath[i].path[j];
                	}
             	}

							// 将这一步走回去，得到最初的状态		
    		tNodes[ AllPath[i].start ].Chessman = tNodes[ AllPath[i].path[j] ].Chessman;
    		tNodes[ AllPath[i].path[j] ].Chessman = 0;
                GamerQuen = tQuen;			// 将游戏者转回去
		}
    return MaxData;					// 返回最优的评估值结构体
}
void  _Robot::DFS2(int start,_Nodes *tNodes)
{
    _Nodes *pNode=NULL;

    for(int i=0;i<6;i++)				//遍历一个节点的周围六个节点
		{
			pNode=tNodes[start].pointers[i];
			if( pNode!=NULL )
				if( pNode->pointers[i]!=NULL )
					if(pNode->Chessman!=0&&pNode->pointers[i]->Chessman==0&&pNode->pointers[i]->visited==0)
					{
            	    	pNode->pointers[i]->visited = 1;
						DFS2(pNode->pointers[i]->index,tNodes);
					}
		}
}

//---------------------------------------------------------------------------------------------
void _Robot::GetCondition(int **ids,int count)          //_Robot初始化中将会用到
{
    _GamerQuen *t;					// 指向游戏者链表的指针
    int i;
    GamerQuen = new _GamerQuen();               	// 创建新的游戏者列表
    GamerQuen->GamerId = ids[0][0];             	// 赋值第一个游戏者
    if( GamerQuen->GamerId % 2 == 0 )			// 若游戏者序号为奇数，则该游戏者对手序号为本序号+1
            GamerQuen->EnemyId = GamerQuen->GamerId - 1;
    else 						// 若游戏者序号为偶数，则该游戏者对手序号为本话号-1
    	    GamerQuen->EnemyId = GamerQuen->GamerId + 1;
    t = GamerQuen;                              	// t指向游戏者列表的第一个游戏者
    for( i=1;i<count;i++)                       	// 将游戏者的顺序输入到列表中
    {						
        GamerQuen->Next = new _GamerQuen();		// 创建新的游戏者链表元素
        GamerQuen = GamerQuen->Next;			// 为新的游戏者链表元素赋值
        GamerQuen->GamerId = ids[i][0];			// 确定这个元素的对手是谁
        if( GamerQuen->GamerId % 2 == 0 )
            GamerQuen->EnemyId = GamerQuen->GamerId - 1;
        else GamerQuen->EnemyId = GamerQuen->GamerId + 1;
    }
    GamerQuen->Next = t;                     		// 将最后一个链表元素next指针指向第一个元素
    for( i=0;i<count;i++)                    		// 使gamerquen指向当前游戏者
        if(GamerQuen->GamerId == gamerID)
            break;
        else GamerQuen = GamerQuen->Next;
}