idea.txt

围棋游戏

本程序用VC6.0编成,共有类9个,结构体4个.
在这九个类中,有本人自己独立设计的类3个(MyChess,chain和Tree类),其余类均为从MFC
中派生得来.


下面介绍主要实现步骤和思想:
系统建设分两步进行:
1.完成对棋局的判断,即由两个人互相对弈时,能够正确工作,判断出谁赢谁输.
2.完成人机对弈,用人工智能的方法让计算机进行决策.

思想:
1.模型:
    链(Chain):五子棋的主要操作对象就是链,即连成链,合并链,还有删除链. 用一个
数据结构模拟链,以及链的各种信息.
    下棋的过程就是各种链的形成组合,以及灭亡的过程.在人人对弈时能够正确建立
一个棋局的链.在搜索过程中无非是完成对所有链的有关位置的估计并进行链与链之间
关系的评价,并最后决策.
2.方法:
    有了抽象的模型就能够把下棋问题归结为一个人工智能中常见的搜索问题即对所有
可能进行有价值的搜索.


下面分别介绍各类的主要功能:
1.MyChess类:
    此类用于纪录每一局棋的主要信息.
    其中主要成员变量有chaintab(一个Chain类的数组),ChessStep,纪录每一步棋所
下的位置,State纪录当前棋局的状态(他是一个15*15的矩阵,用来纪录棋盘上每个点
的棋子信息).
    主要成员函数有:PushChess,每下一步棋时就调用一回此函数.另外她还会判断出
某点能否下棋.AddChain,CheAndCreChain,CheckChain,CreChain,UnionChain,DelChain
exchange都是用来对变量Chaintab的操作,包括对chain的检查,合并,建立,还有删除. 
他们都在PushChess函数发生后激发. 另外的一些成员函数还有:WhoWin(判断谁赢),
checkme,chiefchain这两个函数都是在人工智能搜索时用到,分别用来删去死链并按,
chain的长度和可扩展性(EnaAdd)排序,以及判断两个连的隔一个棋子的关联(即所谓
的假四和假五).

2.chain类:
    此类纪录每个链的信息,包括链的长度(chainlen),链的黑白属性(BorW),链的可
加性(EnaAdd),链的状态(VHState,有横,竖,左上斜,右下斜四种),链的位置(FirstP),
还有链的唯一标识(ChainID). 
    由于对链的大部分操作都在MyChess类中进行,所以chain类的函数仅有IfInMe(判
断一点是否在此链的延长线上),AddMember(在链中再加一个成员).

3.Tree类:
    此类纪录对棋局的搜索信息,以及完成搜索的主要功能.
    主要成员有:ChessSource(被搜索的原始棋局),Nodes(树的节点),Stack(搜索时
临时用的栈).
    函数主要有:MakeAllPossible(用来找出所有可能的对当前棋局的扩展,并生成搜
索树),Value(对每个从MakeAllPossible中生成的棋局进行评价,评价函数采用加权和
的形式),Result(用人工智能中的SSS搜索算法完成对树的搜索,并作出最后落子的决
策).
    值得提及的是在完成这部分功能中的几个关键技术:
    1.在MakeAllPossible中尽量对生成的结果采取限制,以免产生组合爆炸.所以作者
用了限制最大搜索节点数的方法.
    2.对树的构造是用一个动态链表和一个一维数组实现的,数组中纪录节点的信息,
包括儿子的指针,父亲的指针,节点的估价值还有所处的深度等信息,而链表中纪录的是
指向数组的指针.
    3.用堆栈完成树的生成.
    4.评价函数的计算是把所有的链的分数值加到一起,并对敌我双方进行加权计算,
有几种情况下,评价函数会达到最大值,如有一连成五个的链,还有活四等情况.



    下面讨论各类之间的关系: 由MyChess类建立基本信息,并构造一个存储Chain类的
表,然后由Tree类完成搜索,返回值. 所有下棋的控制工作都由CChessDoc类完成,显示工
作由CChessView类完成.


    下一版本的发展趋势:
    1.在界面上加入更多的多媒体功能.
    2.优化搜索算法,尽量使树的生成和搜索一次性完成,这样可以减少重复的工作.
    3.加入学习功能,让程序能从以往的棋局中学习.
    4.加入自调节功能,用神经元网络调节各参数.
    5.加入知识推理功能.

1999.12-2000.2完成.