我想寻求五子棋的简单算法!!
有谁知道比较简单点的算法?
我不知道该怎么去找最重要的那点，怎么比较棋盘上最重要的点。
我现在烦恼了好几天,写来写去结果计算机很容易输.
我现在发现自己写程序的话是写不出来的，
毕业设计我不知道该怎么办才好了
能有点提示吗??
问题点数：100、回复次数：39Top
1 楼snoopy291（稻草）回复于 2005-05-03 22:36:06 得分 0
有些人的论文是抄书或搬网上的，我坚持自己做，但觉得自己太固执了。
根本做不出,技术不高.
算法也不会.
很想有高手的提示,比较简单的算法就好.Top
2 楼sun428（Born to Win）回复于 2005-05-03 22:43:39 得分 0
去google吧Top
3 楼snoopy291（稻草）回复于 2005-05-03 22:53:08 得分 0
我搜索过了，看来我问这个问题没有多大的意义的呢.
不过那些算法对我来说,我还觉得挺复杂的，又难懂.
所以我想找很简单的.
我现在写的出的一个五子棋程序实在是太简单了，
而且计算机是乱下了，从一开始就是从第一列开始下，不管人下了多少要赢了,
计算机还是对人下的棋子无动于衷,一列一列地下的.
^_^真是郁闷.
好希望能过关.
Top
4 楼ldwh（灰沙）回复于 2005-05-03 22:58:51 得分 0
我有个例子，不是我写的Top
5 楼snoopy291（稻草）回复于 2005-05-03 23:07:04 得分 0
你的例子简单吗?
那些网上的什么冲三活四,死四之类的名词我好难理解的.
不知道是什么样的棋型才是，那都是涉及到专业术语,
可是我的老师说不要去理解那些也可以的。
:(
快要崩溃了，每天都在想.做不出
放完假就要答辩了，我好急Top
6 楼ldwh（灰沙）回复于 2005-05-03 23:20:32 得分 0
没有说明，只有代码
Top
7 楼snoopy291（稻草）回复于 2005-05-04 11:38:39 得分 0
没有说明的代码肯定很难看得懂,我也搜索到，但因为没有注释,我看不下去了，
我现在还在自己做.就坚持下去吧,就算做不出，起码也学到了好多东西.
^_^
实在到逼不得已的那天，我再看.^_^Top
8 楼lw1a2（一刀 现在改六点下班了：（）回复于 2005-05-04 11:42:42 得分 0
不是吧，你连五子棋的那些术语都不懂，却要做五子棋的算法？Top
9 楼snoopy291（稻草）回复于 2005-05-04 12:12:09 得分 0
老师都说可以不用去理解了。
我懂得下一点棋啊，那是我的毕业设计论文的题目。
我现在都不知道当时怎么选了这个题目.
我确实是不懂冲三活四和死四,但我懂只要能连成五个就赢.
^_^Top
10 楼snoopy291（稻草）回复于 2005-05-04 12:15:15 得分 0
要是有谁懂的话，可以告诉我吗?至少可以了解一下.Top
11 楼kulongus（公司会计说：零钱太少了，你还是半年领一次工资吧）回复于 2005-05-04 13:50:13 得分 0
郁闷，我也是做五子棋
Top
12 楼diandian82（点点(nothing)）回复于 2005-05-04 14:06:57 得分 0
如果要让计算机会下棋那真的不简单啊，要用到些人工智能的东西！可惜我不会，帮不了你啊！Top
13 楼learner_baker（菜鸟看世界）回复于 2005-05-04 14:24:51 得分 30
设定三个数组，一个记录棋盘位置的代码，一个记录电脑下子的代码，一个记录人下子的代码。（如：0代表电脑，1代表人），通过循环扫描两个记录下子代码的表去查找你上面所说的活三，冲四等。。只要扫描到符合条件的就是胜利者了。我做过。这只是我的课程设计。如果想人机对战的电脑聪明点，多遍历几次数组，查找最适合的位置就行了。网上有很多这样的例子，你最好用自己的方法去实现。。毕竟算法很多，而且都是人想出来的。好好干吧。Top
14 楼snoopy291（稻草）回复于 2005-05-04 15:00:26 得分 0
呵呵，谢谢楼上,我也是自己想的，但好象都是凭下棋的一点经验的，所谓冲三活四死四死三那些我不知道是什么东西。我也很想了解,但我没有看到游戏里有关的定义到底是如何的。
在加油了。 也许不是很强，起码也能下一点吧.
我该去哪里了解活三冲四这些术语啊?Top
15 楼SaiRose（Learning......）回复于 2005-05-04 15:46:01 得分 0
有时间自己找找人工智能方面的资料吧
网上的带ＡＩ的程序也很多
www.vcok.com看看去
感觉带ＡＩ的都有点烦的也不是一两句能说清的
关键就是求当前棋盘上每个点的权值（叫法不记得了）
然后选最大的
楼主最好能问个下的很好的人
那样就容易知道下哪些点最可能赢，然后相应的应用到程序上Top
16 楼snoopy291（稻草）回复于 2005-05-04 15:58:32 得分 0
呵呵，我现在做出一点了，是凭经验做的，还没有用到人工智能,所以当我和它下的时候还是有胜它的情况的，所以就觉得情况不全面，要是去看书时间已经来不及了。我现在就想知道那些所谓冲三活四到底是什么东西，然后我把所有可能最会胜的情况都搜索.
但我还是觉得自己做的太简单了。人机对弈计算机聪明的话，是不会轻易让人战胜的吧?
我下的就有好几次还是赢了计算机.AI对我来说也是挺深奥的东西，所以只能采取简单的做法了，因为时间的关系我真的来不及了。Top
17 楼snoopy291（稻草）回复于 2005-05-04 16:02:49 得分 0
SaiRose(Learning......),你给的网站很不错,有好多知识和东西,谢谢你!!
激发我学习的兴趣了。^_^Top
18 楼snoopy291（稻草）回复于 2005-05-04 16:32:04 得分 0
不过，我现在的算法是太过简单了:先搜索连续成线的棋子数最多的，并且两边都各至少有一个空位,然后就选择这点下,但每一次搜索只考虑了一个点的一个方向,所以当出现两个方向都能连成五子连边也有空位的时候，计算机没有及时防守,所以失手了。^_^我现在还在想怎么去补充.
如果不补充还可以勉强上交吧,那可是个置命的弱点.:(
我就是不知道该怎么搜索多个方向都有连续子,特别是有不止一个空格的情况,而且重要程度如何，该放在哪里也不知道.我的程序是按照顺序下来的，前面的条件不满足就到下面的.连续棋子数越多的先放在前面，后面就是依次减少的。Top
19 楼corrupt（喜欢 睡在床板下 的思考）回复于 2005-05-04 20:22:57 得分 0
呵呵， 搞个人-人对战的不就可以了，Top
20 楼snoopy291（稻草）回复于 2005-05-05 01:23:51 得分 0
呵呵，人人对战那不是只需判断胜负就可以了吗?
要弄联机的话，恐怕更难吧.
My God.
我担心论文不过关.
程序运行不按照程序的去做，真不知道为什么.Top
21 楼km3（北落师门）回复于 2005-05-05 08:33:07 得分 30
楼主想做五子棋方面的程序，还不懂得规则，想做好的话不太可能。我建议你先到google里搜一下，
五子棋的规则，好好看一看。然后到联众里去下两天五子棋。
我以前拿delphi写过一个，算法的效率有点低下，不过电脑的AI可不菜，可惜电脑升级的时候不小心
硬盘上的东东全没了。
我说一下我的思路（我自己想的，可不是网上搜的），用一个二维数组(array1)来记录当前棋盘上的
情况（如：空0，黑1，白2）。再用一个二维数组（array2）来预测array1中的一个0变为1或2的情况。
在写N多个方法遍历数组来了解棋局的情况，返回int型，如一个方法来判断五连的个数，再有个方法来
判断冲四（冲四有多种情况：20222，22022，22202，2222）的个数，…………，这样方法越多越详细，电脑对棋局情况了解的越详细，电脑的AI越高。每一回电脑下棋的时候array1里的一个0变为1放到array2里，然后用你的N个方法去遍历,每个方法的返回值都乘个分数，比如五连的方法的返回值*30000，冲四的返回值*1000，当然也可以几个方法和在一起用来判断四三子类的棋局，然后你还点判断这个0变为2的情况，也可以得出一系列的分值，将这些分加在一起，就可以得出这点的分值了，将array1里的每一个0的分值都算出来，然后得出分值最高的一点，就是电脑要走的棋了。
你也可以建array3,array4…………的数组来预测以后2,3…………步的棋局.
我这么写效率有点低，不过可以判断禁手，我在网上看到的例子都是没有禁手的。
Top
22 楼SaiRose（Learning......）回复于 2005-05-05 11:03:58 得分 0
楼上的哥们是不是喜欢天文．．．
Top
23 楼graciexy（在程序的海洋里学游泳）回复于 2005-05-05 12:03:24 得分 0
是的，我学长做过这个课题，也是算横竖还有对角线上的权值（还是概率）大小的。Top
24 楼snoopy291（稻草）回复于 2005-05-05 13:00:58 得分 0
谢谢楼上km3(北落师门)给的思路!!还有learner_baker(菜鸟看世界)的思路!!
不过我现在做的却是只有一个数组存储棋盘的情况.然后等人每下一子之后就对当前的棋盘二维数组进行遍历,对每一个空位,
1.要是遇到计算机马上会赢的,即这个空位有连续四子的情况,则先下,
2.若第1条情况没有,若此空位是人马上会赢的位置,则下，阻止其胜利,
3.若前2条情况没有，就看这空位对计算机来说有没有活三的情况，若有(可以构成活四或冲四)，则下,以进攻
4.若前3条情况没有，就看这空位对人来说是不是有活三的情况，则下,以防守
5.若前4条情况也没有,就看对计算机来说是不是有连续两子的情况，若有(可以构成活三)，则下,继续进攻
6.要是前5条都没有，则看对人来说有没有连续两子的情况，若有，则下，也是为及早防守
7.要是前面的情况都没有，则看对计算机来说若有一子,空位可以和它构成两子的，则下，继续进攻.
8.要是还没有，则看人方,人要是有一子,空位可以和它连成两子,以防守.
每次都是人下子后，计算机都按照顺序遍历一遍,若是在第一条找到符合的空为，则下，然后轮到人下，人下后，计算机又重新遍历,要是第一条没有符合，又重新遍历，找找看有没有符合第2条，要是没有,又重新遍历,找符合第3条的，这样继续下去，直到找到其中一个符合的就下。上面的顺序我就认为是按重要程度来下了。
我的想发就这样，但我下了之后,计算机很容易输,因为我没有考虑一个空位上的多个方向一起结合，
只考虑一个方向.所以遇到双三,四四的时候,计算机没有办法识别，所以输了。可是我不知道怎么改进了。没有时间了，我的对话框还是有问题的，我画棋盘是在Onpain()函数里用.MoveTo()和LineTo();
画棋子是以TextOut()来输出不同的符号,比如"+"表示计算机下的棋子,"-"表示人下的棋子.
但这样做出来的对话框很奇怪，下棋之后的字符，要是我动了这个对话框以外的程序窗口或者什么,那些字符全都不见了!要是我猛地拖动对话框,上面下的字符全都不见了，好奇怪!!我都不知道原因，我传给别人下下看，别人一点击一下，字符马上消失!!
我好郁闷,不知道哪里出原因,算法不够聪明这不用说了，对话框出现这样的情况真是不可理解.
难道一定要用画图或粘贴图上去的，我都不会用.
我的知识水平太有限了!!!不知道该怎么解决.只勉强做到这一步. :(Top
25 楼snoopy291（稻草）回复于 2005-05-05 13:29:36 得分 0
而且，计算机有时候还没有按照上面的顺序来下的，明明有满足第四条的,它却执行第六条的.所以在该下的地方，计算机还什么样下，人就抓住了这一漏洞,计算机输了.但我的程序我还没有仔细查找过，但觉得程序不会这么出错的吧,就是按照顺序写下来的，满足条件的先执行不是吗?可是它却不这样.
有哪个高手清楚的话，或有什么想法,请提出,请指教.
分享一下你们的高见.
^_^Top
26 楼snoopy291（稻草）回复于 2005-05-05 13:38:53 得分 0
在前面的两位高手给出思路之前我已经这么做了。
我不知道我这样是否能合格了。
突然觉得什么都不知道了.
什么都不懂.:(
Top
27 楼SaiRose（Learning......）回复于 2005-05-05 14:23:19 得分 0
km3(北落师门) 已经说明的很清楚了
我觉得楼主没有理解他的意思
哪个点的重要程度当然可以按楼主那么说的判断，但我觉得很难全不考虑
而且很麻烦，太多判断语句
比较好的就是按 km3(北落师门) 的计算当前棋盘上的每个点的重要程度
用一个值来衡量，然后每次下这个值最大的那个点
另你说的画图的问题是 你没把棋子的位子保存下来
你是用数组来表示棋子的吧，０－没下 １－白 ２－黑，是么？
那么在OnPaint函数里写画图程序时就按你的这个数组来画棋子
数组哪个位子上值不为０则相应的画上白或者黑
windows程序是在每次重绘窗口时调用OnPaint函数
只要你在OnPaint里都画了就不会出现你说的情况Top
28 楼SaiRose（Learning......）回复于 2005-05-05 14:25:51 得分 0
画棋子可以不用TextOut来画
就直接CDC.Ellicpse()就可以了，画圆
不过不同颜色的话还要加上不同的画刷
如果还想好看点就用位图了，就看楼主有没这个时间了
呵呵，加油了Top
29 楼snoopy291（稻草）回复于 2005-05-05 16:14:42 得分 0
SaiRose(Learning......),你说得很对!!可是你怎么知道我是这样表示的呢?
我确实是用数组来表示棋子的，０－没下 １－白 ２－黑，
按km3(北落师门)的算法，好象我没有用我的算法之前试过，但因为出错，我不用了，我还以为是算法的问题.因为每次调试的时候,箭头都指向条件句,可能我的条件句也是太复杂了。那时候我用调用函数的方法,后来发现调用屡屡出错，索性直接不用调用了，就用最笨的办法,干脆一个一个来好了。
因为这样做的时候，我没有出错.之前一点击鼠标就是弹出一个对话框说XX.exe遇到问题要关闭,表示抱歉.用了最笨的方法后，这个问题不出现才得以解决，我现在也想不通自己的程序错在哪里.
但有一点,对km3(北落师门)的计算方法,我不是很明白,也许先按我这个笨方法写一下吧,完之后要是还有时间可以修改,我会尝试他的算法看看.他说的那个用一个方法来判断五连的情况,是说用一个函数来专门判断五连的，再有，用另一个函数来专门判断活四的，....,是这样吧,就是说一个空位,可能四个方向都各有一种棋型,每种棋型都有一个返回值,就把那个空位的四个方向的四个棋型对应值加起来,是这样吗?然后也计算这空位的若下的是另一方的，也计算一下,然后所有的点都有一个值,比较找最大的.是这样吧? 我曾经用过，可能是我程序错误而没有得到实现吧,后来就放弃了。
要是有时间我考虑用位图吧,这我还得自己去看点书.
但我有很多困惑的地方，看书的时候，好多地方出现什么CClientDC和CCpaintDC和
什么CDC,GetClientDC,我好混淆这些地方的.有时候也看到逻辑坐标和屏幕坐标之分,我都不知道它到底指什么,还有什么获取窗口客户区之类的,设备上下文到底和窗口、窗口客户区有什么区别？
CDC.Ellicpse()不是只能画椭圆吗？我该到底怎么画一个实心圆，有颜色的，但我不会用那些函数，到底用什么类的什么对象我也不知道，要是你知道能给个例子吗？
还有要是我没有用位图，就像我用的TextOut(),如果要保存到底该怎么保存？
棋盘纵横线我是在OnPaint里画的，你的意思是说，我画棋子即TextOut()也要放在OnPaint（）里？
可是一个OnPaint（）函数怎么知道我要画哪方的棋子啊？
....好多问题冒出来了...
还有执行文件的问题，我当时建立项目时，只是选择了基本对话框那一项，其它的都是默认的。
但当我想把执行文件独立脱离VC环境运行，我不知道该怎么弄，别人告诉我说要设置成静态编译，但我用之后，拿到别人的没有VC的机子上运行却出现状况：说没有找到MFC42D.DLL文件,所以应用程序未能启动.重新安装应用程序可能会修复此问题.
不知道是不是我安装VC不完全还是怎么样。
而且我的五子棋很不正规，棋子是画在格子而不是直线上,还是用不同的字符表示的。呵呵
今天按上面说的去搜索看了冲三活四的说法，现在才知道六个子连的时候不算胜，而我的那个程序连成六个也算五连在里面了，所以也算胜利。呵呵，觉得自己很搞笑，都没有想那么多呢。
觉得游戏里的规则还挺多的，我还没有用禁手，也没有到高级中级的程度，也没有悔棋的步骤，
那样更加复杂了。我只想能下一般的棋计算机不容易输就好了。
我们老师要求还没有那么复杂，但计算机容易输说明算法有漏洞。
^_^ 谢谢你!!!!Top
30 楼snoopy291（稻草）回复于 2005-05-05 16:25:51 得分 0
对了，我画棋子的函数都放在Onpaint()外面的.
但也没有在Onpaint()里面调用它们.我应该怎么做才能保存啊?
要放到里面去吗?也许我该多加一参数表示是哪方的.Top
31 楼snoopy291（稻草）回复于 2005-05-05 16:47:39 得分 0
哦，现在我想起来:
画两种棋子,我该怎么放到Onpaint()里啊，
我的画棋函数在Onpaint()外面定义是这样的:
DrawManChess(int i, int j)
DrawPcChess(int i, int j)
只要我该下在(i,j)的时候，我就调用它们,但我想,这样的函数放在Onpaint()里怎么区分怎么调用，而且参数该怎么传递啊?
我是用自定义的ChooseBestChess()选择要下的位置.在ChooseBestChess()里调用画棋的函数，但画棋的函数又要放到Onpaint()里面去的话，参数到底该怎么写啊?
哎，好乱哦Top
32 楼dzw2004（深蓝）回复于 2005-05-05 16:49:14 得分 0
up~Top
33 楼SaiRose（Learning......）回复于 2005-05-05 16:52:40 得分 40
不知道你还有多少时间，本来以前我就一直准备做一个五子棋的
不过当时很菜，是用tc编的，功能也只有判断输赢
这段时间准备一个课程设计，等做完了就准备做个五子棋的，作为最后的一个程序（然后就准备考研了，呵呵，准备痛苦了，不能继续学习program了）
如果你的时间允许，也许过几天（１星期内）可以一起探讨了．
关于算法，我断断续续的想过一点，说下，不知道好不好实现：
就是关于求最大权值的方法，举个例
先说明下，你另用一个２维数组保存每个点的权值
０００ 左边这表示下了一个白棋，它的周围都没下，那么可以将下了棋的那个点位子的权值设
０１０ 为０，而它周围８个都设为１０（这个自己定）
０００
００００ 左边表示下了２个连在一起的白棋，再次设置时就将a位置的点的权值设为１００（这个
a１１a 也是自己定，但记住一定要比１０＋１０大，为什么自己先想想）
００００
其他的类似了，每下一步棋就要将当前棋盘上的点的全部权值都扫描一遍，将需要改的权值都改了
这只是个基本的想法，实际实现时要考虑的还有很多
你有空先想想，我自己想的，也不知道对不对
最好可以下下五子棋，那样的话认识会提高的（我选五子棋就因为我自己蛮强，呵呵）
关于画图，那只是个架子，不要在那上面花时间，我一直认为程序的好坏是用你所用到的算法和数
据结构来评价，所以看到那些用华丽的界面来掩饰幼稚的算法的程序就很鄙视
鉴于你说的情况，你可以找本vc的书看看，市面上很多的，图书馆也应该有，很多都是手把手教你
怎么做的，你所需要知道就是对程序运行的基本了解，比如什么时候窗口重绘，什么时候调用什么
消息，知道这些就够了，你现在也没时间了解更多的，用MFC做个架子没你想像的那么复杂
MFC我了解的也不多，我是从SDK开始看的
你画棋子也要在OnPaint里画！！！记住，这是肯定的
也很简单，就把你以前怎么画的程序搬到OnPaint里来就可以了
画圆的函数我不记得了，你查查，应该很容易找到的
你所说的运行时弹出一个对话框说XX.exe遇到问题要关闭估计是数组越界了，仔细检查吧Top
34 楼SaiRose（Learning......）回复于 2005-05-05 16:54:44 得分 0
直接把函数放进去不就可以了么？Top
35 楼snoopy291（稻草）回复于 2005-05-05 17:25:38 得分 0
呵呵，谢谢你!!
我全都明白!!
你这么忙还这么耐心地解说.
有空我会想!!如果我不是放完假答辩,也许和你会同步的.
呵呵.
^_^
我们继续努力吧!!Top
36 楼snoopy291（稻草）回复于 2005-05-05 17:28:20 得分 0
说的也是，我觉得我的界面挺简单朴素的.但就是很怪，字符会无影无踪地消失,我现在听了你的解说,真的明白了!!我会改进!棋子下在格子里也没有问题吧?虽然现在都是下在直线上的。
但我想简单点.就像你说的，最主要体现算法和数据结构吧.
^_^Top
37 楼SaiRose（Learning......）回复于 2005-05-05 18:15:20 得分 0
呵呵
补充一下，也不能说的那么绝对，毕竟和用户打交道的还是界面
所以一个好的界面也是很重要的Top
38 楼snoopy291（稻草）回复于 2005-05-05 20:35:33 得分 0
^_^
先完成最本质的东西，如果时间允许,再完成外在的东西.
还是挺感激你的!!Top
39 楼snoopy291（稻草）回复于 2005-05-12 20:05:54 得分 0
今天答辩了，我都不知道怎么回答问题,很多问题我回答起来都是牛头不对马嘴的.
…………
我结帖了，感谢以上各位的热心帮助！！
^_^Top
