流星载月I have a dream,abeatiful dream that one day i can fly !!首页日志相册音乐收藏博友关于我日志fly_just永远不相信努力创造不了奇迹！加博友关注他最新日志http包截获并还原HTML与数据中华民族的好总理－周恩来中华民族的好总理－朱镕基网络共享拨号软件粗设计五子棋算法设计初探First ,Last 集构造首页推荐日本人喜欢用饺子配米饭劈腿女如何玩转俩'老公'台湾新片靠全裸女博出位石油双雄逼民营油企停产女星走红毯全靠透视装？灵肉交织的智力舞蹈(图)更多>>First ,Last 集构造网络共享拨号软件粗设计五子棋算法设计初探2008-11-08 21:12:38| 分类：默认分类|字号目录:标题一、设计概要1、图形界面设计2、算法设计概要二、具体算法实现1．计算放棋的相对物理坐标2．给着棋点周围加权3．计算棋局上成棋个数4．给特殊棋格附于特别权5．计算最大权值、最小权值6．根据最大、最小权值决定策略7．输赢的判断三、变量、数据结构与函数1.自定义的变量和消息2.类成员变量3.数据结构4.全局函数5.类主要成员函数三、人机对战流程图主题内容：、图形界面设计棋盘方格以背景图片的方式贴于对方框之上，其中的图片来自网络图片中剪切下来的一部分，格局大小非标准的国际五子棋大小，只是为了研究五子棋算法而作的一个模拟棋盘。
棋盘大小为16＊14，即横方向上16格，坚直方向上14格。
棋子仍MFC自带绘图ICON工具所绘制，大小31＊31像素，分为黑白两种棋子。
棋局可以自动保存于数据链表中，可自动重绘。
见图(1).图(1)、算法设计概要⑴关于落子点的计算在棋局上下棋时，不能以鼠标的点击位置为着棋点，所以必须找一个合适的或者用户最想要着棋的位置着棋。
所以关于着棋点的位置要经过特定的计算才能着棋。
我们棋盘的十字交叉点的间距横对都为35个像素，方格直经为53个像素，而起始坐标经计算为（33,37）像素处。
我们是这样计算的：坐棋盘的起始坐标（33，37）开始每隔35个像素间距后，通过与鼠标点击点的坐标求径直距离后，再与方格直径53的一半26.5作比较，如果两点的距离小于或等于26.5，那么该点极有可能是客户最想要的着棋点，扫描棋盘直到找到一个这样的点为止，除非用户点击的不在棋盘区域或已经着棋了的点，否着应该找到这样的一点。
⑵关于着棋后的输赢判断在判断输赢时，用到的一个巧妙的方法。
从所周知，无论谁下棋赢了以后总会成五子连线，而成五子连线时，第五颗棋总是会着落在棋盘上，所以我们在判断是否有五子连线时，并不是全盘扫描，而是在每着落一子后就扫描该棋子左右、上下、以及斜着的四个方向。
如果扫描出来了那个方向上的棋子首先到达五子，就返回给上级调用，由上级调用者作出相应判断。
如果是其它子，如果某个方向上成了六子或六子以上时，不能算作它赢得了棋，而必是五子才能赢得了棋。
如果是五子以下的棋子时，将要根局相应棋子成子情况，作出相应反应，如加权、减权等操作。
⑶关于加权搜索算法的实现该五子棋用到的算法命名为加权搜索算法。
我们将棋盘分解为了两个子棋盘，它们分别是一个16＊14大小的二维数组。
一个棋盘负现保存当前着棋点位置，比如1表示黑棋着了该棋格，2表示白棋着了该棋格，另一个棋盘负责记录下来每个棋格的权值。
权值有正负两种，其中正权值表示进攻分，而负权值表示防守分。
算法是这样设计的：每个棋子都有它的势力范围（想法来自于围棋），最大势力范围为5（加上自已的一格），影响到周围八个方向。
在此，我们将这个势力范围定义为深度，用它来设置电脑当前等级。
当某一个棋子着棋后，便会对它势力范围内的所有棋格权值分有所影响，靠得越近的自然影响越大，越远的影响等级呈递减速趋势。
在每着一棋后判断棋子输赢的同时，会记录下来当前棋子与其周围棋子的成棋个数，根据成棋的个数及棋局形势再设置各个棋格权值，通常会加上或减去N个Callful值（Callfull =100 ,N>=1），如果是电脑形成成棋个数，则加上N个Callful,如果是玩家，则减去N个Callfull,N由以下几种情况决定:注：要加权的格用＊表示①成四子时：电脑N=4，玩家N=3独立四子即：＊●●●●＊成被阻四子即：＿＊●●●●○或○●●●●＊＿②成三子时，电脑N=3，玩家N=2独立三子即：＿＊●●●＊＿加上中空后成四子即：＿＊●●●＊●加上中空后被阻即：＿＊●●●＊○（会减少一个Callfull权）③成被阻三子，N=2左被阻三子：○●●●＊＿＿右被阻三子：＿＊●●●○加上中空即后续一子成五子：○●●●＊●＿或＿●＊●●●○（再加一Callful权）加上中空即后续二子成六子：○●●●＊●●或●●＊●●●○(恢复原权值)④成两子，N=1成独立两子：＿＊●●＊＿加上中空后成六子：＿●●＊●●● (恢复原权值)加上中空后成五子：＿●●＊●●_或＿●●＊●●○（再加一Callful权）⑤成孤立一子：加上中空与其后续子成五子：＿●＊●●●＿或＿●＊●●●○（加上3倍Callful权）加上中空与其后续子成独立四子：＿●＊●●?＿（加上1倍Callful权）加上中空与其后续子时成被阻四子：＿●＊●●○（恢复原权值）⑥一般情况下任何子的处理：黑子时：n=1,白子时：n=-1;如果深度为depth=3，那么任何一个棋子只能影响到它附近的三个点，包含自身如图（2）图中黑子给它周围的这几个相对它来说深度为三的点加上权值，靠得越近的，比如说右边第一个点，将会加上权值depth,而右边第二个点，将会加上权值depth-1,呈显递减趋势如果是白棋，则相反，它会使它周围的棋权减小相应值。
图（2）⑦特殊权值处理：即：形成独立三子后，被对方一棋了所阻，那么对点就应该减少N倍权值：电脑N=3，玩家N=2图示：开始＿＊●●●＊＿被阻：○●●●＊＿无效：○●●●&＿&点权值应减小N倍，防止再次无意义的被阻: ○●●●○＿．计算放棋的相对物理坐标for(m=0;m<NumberSpaceX;m++)遍历整个棋盘，直到找到一个最近的未被占用的点{x=m*LengthSpaceX+StartPointX;for(n=0;n<NumberSpaceY;n++){y=n*LengthSpaceY+StartPointY;Length=sqrt(pow((myPoint.x-x),2)+pow((myPoint.y-y),2));if(Length<A V aribleWay&&m_CheeseArray[m][n]==0){A V ariblePoint.x=x;A V ariblePoint.y=y;m_CheeseArray[m][n]=WhoPlay;将找到的点放上棋子，表示占有了该点。
pointX=m;pointY=n;return A V ariblePoint;}}}．给着棋点周围加权k=Depth;水平方向for(i=a-1;i>=a-Depth&&i>=0;i--,k--){m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}for(i=a+1;i<=a+Depth&&i<MaxCheesePlace_X;i++,k--){m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}上下方向for(j=b-1;j>=b-Depth&&j>=0;j--,k--){m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}for (j=b+1;j<=b+Depth&&j<MaxCheesePlace_Y;j++,k--){m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}反斜方向for (i=a-1,j=b-1;i>=a-Depth&&j>=b-Depth&&i>=0&&j>=0;i--,j--,k--){m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}for (i=a+1,j=b+1;i<=a+Depth&&j<=b+Depth&&i<MaxCheesePlace_X&&j<MaxCheesePlace_Y;i++,j++,k--) {m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}正斜方向for (i=a+1,j=b-1;i<=a+Depth&&j>=b-Depth&&i<MaxCheesePlace_X&&j>=0;i++,j--,k--) {m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}for (i=a-1,j=b+1;i>=a-Depth&&j<=b+Depth&&i>=0&&j<MaxCheesePlace_Y;i--,j++,k--) {m_CheeseSGore[i][j]=m_CheeseSGore[i][j]+Way*k;}．计算棋局上成棋个数以坚直方向上为例：while(n<MaxCheesePlace_Y)向下{if(m_CheeseArray[m][n]==SomeOne){count++;k1++;}else{break;}n++;}n=j-1;while(n>=0)向上{if(m_CheeseArray[m][n]==SomeOne){count++;k2++;}else{break;}n--;}if(count==5)成五子棋子了。
{return 1;}else if(count<5)其它对应处理{…….}．给特殊棋格附于特别权仍以坚直方向为例：⑴成四子时：对下面的空子附对相应权if (j+k1+1<MaxCheesePlace_Y){m_CheeseSGore[i][j+k1+1]+=3*CareFull*Number;if (SomeOne==ComputerCheese) 如果是电脑，权优先一级{m_CheeseSGore[i][j+k1+1]+=CareFull*Number;}if (j+k1+2<MaxCheesePlace_Y如果成了六子，则恢复原值&&m_CheeseArray[i][j+k1+2]==SomeOne){m_CheeseSGore[i][j+k1+1]-=3*CareFull*Number;if (SomeOne==ComputerCheese){m_CheeseSGore[i][j+k1+1]-=CareFull*Number;}}}对上面的空子附对相应权if (j-k2-1>=0){m_CheeseSGore[i][j-k2-1]+=3*CareFull*Number;if (SomeOne==ComputerCheese) 如果是电脑，权优先一级{m_CheeseSGore[i][j-k2-1]+=2*CareFull*Number;}if (j-k2-2>=0&&m_CheeseArray[i][j-k2-2]==SomeOne) 如果成了六子，则恢复原值{m_CheeseSGore[i][j-k2-2]-=3*CareFull*Number;if (SomeOne==ComputerCheese){m_CheeseSGore[i][j-k2-2]-=2*CareFull*Number;}}}⑵成独立三子：if (count==3&&j-k2-1>=0&&j+k1+1<MaxCheesePlace_Y&&m_CheeseArray[i][j+k1+1]==0&&m_CheeseArray[i][j-k2-1]==0){m_CheeseSGore[i][j+k1+1]+=2*CareFull*Number;左右空子权值皆要增加m_CheeseSGore[i][j-k2-1]+=2*CareFull*Number;加上中空后如果成五子，则权值再增加一级if(j-k2-2>=0&&j+k1+2<MaxCheesePlace_Y){if (m_CheeseArray[i][j+k1+2]==SomeOne){m_CheeseSGore[i][j+k1+1]+=CareFull*Number;}if (j+k1+3<MaxCheesePlace_Y&&m_CheeseArray[i][j+k1+3]==SomeOne){m_CheeseSGore[i][j+k1+1]-=3*CareFull*Number;}if (m_CheeseArray[i][j-k2-2]==SomeOne){m_CheeseSGore[i][j-k2-1]+=CareFull*Number;}if (j-k2-3>=0&&m_CheeseArray[i][j-k2-3]==SomeOne){m_CheeseSGore[i][j-k2-1]-=3*CareFull*Number;}}}⑶成被阻三子或成独立二子左阻时：if((count==3&&j+k1+2<MaxCheesePlace_Y&&j-k2-1>=0&&m_CheeseArray[i][j+k1+1]==0&&m_CheeseArray[i][j-k2-1]!=SomeOne&&m_CheeseArray[i][j-k2-1]!=0&&m_CheeseArray[i][j+k1+2]==SomeOne)||(count==2&&j+k1+2<MaxCheesePlace_Y&&j-k2-1>=0&&m_CheeseArray[i][j+k1+1]==0&&m_CheeseArray[i][j-k2-1]==0&&m_CheeseArray[i][j+k1+2]==SomeOne)){m_CheeseSGore[i][j+k1+1]+=Q*CareFull*Number;加上中空后成六子时，加权无效if(j+k1+3<MaxCheesePlace_Y&&m_CheeseArray[i][j+k1+3]==SomeOne){if(count==3)m_CheeseSGore[i][j+k1+1]-=Q*CareFull*Number;else if(count==2){if(j+k1+4<MaxCheesePlace_Y&&m_CheeseArray[i][j+k1+4]==SomeOne){m_CheeseSGore[i][j+k1+1]-=Q*CareFull*Number;}}}}右阻时：else if(count==3&&j-k1-2>=0&&j+k1+1<MaxCheesePlace_Y&&m_CheeseArray[i][j-k2-1]==0&&m_CheeseArray[i][j+k1+1]!=SomeOne&&m_CheeseArray[i][j+k1+1]!=0&&m_CheeseArray[i][j-k2-2]==SomeOne||(count==2&&j-k1-2>=0&&j+k1+1<MaxCheesePlace_Y&&m_CheeseArray[i][j-k2-1]==0&&m_CheeseArray[i][j+k1+1]==0&&m_CheeseArray[i][j-k2-2]==SomeOne)){m_CheeseSGore[i][j-k2-1]+=Q*CareFull*Number;if(j-k2-3>=0&&m_CheeseArray[i][j-k2-3]==SomeOne){if(count==3)m_CheeseSGore[i][j-k2-1]-=Q*CareFull*Number;else if(count==2){if(j-k2-4>=0&&m_CheeseArray[i][j-k2-4]==SomeOne){m_CheeseSGore[i][j-k2-1]-=Q*CareFull*Number;}}}}⑷成一子时：ChangeStoreForOne(i,j,0,1,SomeOne);向下扫描成子个数，如果为三，则为本段处理if(i+m*k<MaxCheesePlace_X&&j+n*k<MaxCheesePlace_Y&&m_CheeseArray[i+m*k][j+n*k]==0) {k++;计算成子个数while(k<=3&&i+m*k<MaxCheesePlace_X&&j+n*k<MaxCheesePlace_Y){if(m_CheeseArray[i+m*k][j+n*k]!=self){break;}k++;}if(k==4&&i+m*k<MaxCheesePlace_X&&j+n*k<MaxCheesePlace_Y){if(m_CheeseArray[i+m*k][j+n*k]==self){m_CheeseSGore[i+m][j+n]+=3*CareFull*number;if(i+m*k+m<MaxCheesePlace_X&&j+n*k+n<MaxCheesePlace_Y&&m_CheeseArray[i+m*k+m][j+n*k+n]==self){m_CheeseSGore[i+m][j+n]-=3*CareFull*number;}}if(m_CheeseArray[i+m*k][j+n*k]==0){m_CheeseSGore[i+m][j+n]+=2*CareFull*number;}}}向上扫描成子个数，找到为三的成子点，并改变相应权值。