【摘要】 围棋有五种基本定式，将围棋定式与计算机技术结合以后，查询定式、学习定式将不再是麻烦事。文章介绍了基于C++技术的围棋定式管理系统制作原理并详细说明了制作该系统所用到的基本算法。
　　【关键词】 围棋定式；二叉树；前序遍历
　　【中图分类号】 G891.3
　　【文献标识码】 B
　　【文章编号】 1005-1074(2008)08-0058-02
　　
　　围棋定式就是在围棋活动中长久以来逐渐形成的各种进攻或防守的模式。围棋的基本定式有五种：小目定式、目外定式、高目定式、星定式、三三定式。采用面向对象方法编写围棋定式管理系统是很有实用性的，初学者学习围棋时辅以该系统学习一系列的定式、布局和攻防，不断地进行对战，在实战中增加对定式、布局的理解，强化攻防转换的能力，从而使自己的围棋水平更上一层楼。
　　
　　1 围棋棋子的显示
　　
　　每一个围棋定式都是由一个个的下棋步骤组成的，每一个下棋步骤在棋盘中显示。那么我们就应该先研究如何将棋盘以及棋子在计算机中显示出来。围棋棋盘的形状为正方形或略呈长方形的平面图，现在的棋盘为平面上画横竖各19条平行线，构成361个交叉点。棋盘上可分为9个部分，分别称为：左上角、左下角、右上角、右下角、上边、下边、左边、右边和中腹。棋盘上共有九个黑点称作“星”，棋心的黑点称作“天元”。_［1]
　　绘制可以利用C++ Builder强大的图形编程功能进行绘制。绘制围棋棋盘时要用到的组件有TImage,其中用到TCanvas对象。绘制棋盘时只要通过循环就可以画出横竖各十九条平行线的棋盘。
　　还应该考虑的一个问题是如何在用户点击棋盘时在点击处显示出一个棋子。棋子分为白色与黑色两种，利用TCanvas的画图功能同样可以画出棋子。棋盘的范围有限，绘制棋子时应该先判断点击的位置是否在棋盘的范围内，若在棋盘范围内则调用画图函数画出棋子；若超出棋盘范围，则不显示。_［4］
　　
　　2 主要算法分析
　　
　　2.1 建立二叉树实现定式的存储
　　


　　上图是三三定式的一部分结构图。白1尖冲三三,是对三三的一种对策.利用三三位置偏低尽量的压扁它是一种取势的下法。黑方走后，轮到白方走。那么我们把黑方在棋盘上的坐标位置当作树的根，那么根据三三定式，白方有可能走的位置就是A、B、C、D、E。1长,也是出头的要点。如果在A位挡,就会被黑毫不犹豫的在1位扳。被黑扳起来的话,黑的出路宽阔，根据地也有了。倒是白的头被捂着,前面和左面和下面的出路都没有了，只有右边的出路还没有根据地，这样的棋很被动,很容易遭杀。所以,白1长必然,当然也有在C位跳的棋.长更坚实有利瞄着B位的拐头封锁和A位的挡。_［1]
　　这相当于树的父节点为1，1的孩子节点为A、B、C、D、E。将围棋中任何一个定式按步骤展开，我们会发现定式中每一步都是有序的，且每一步需要保存的信息为该步在棋盘中的坐标位置，整个定式展开与数据结构中树的遍历很相似。
　　将一种定式在围棋棋盘上记录下来相当于建立一棵二叉树。将树用孩子兄弟表示法进行存储，有利于对各种操作的实现。一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置，对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。
　　我们用如下结构体来记录棋子的信息。
　　typedef struct btnode
　　{float x1,y1;
　　AnsiString jieshou,dir;
　　AnsiString colour;
　　struct btnode *lchild,*rchild;
　　}bitnode,*bitree;
　　其中x1,y1为围棋棋子在棋盘中的坐标，jieshou为围棋定式中每一步的解说，dir为建立孩子兄弟表示法时每一个节点的方向，若为l，则为左孩子；若为r，则为右孩子，孩子兄弟表示法中，左为左孩子，右为右兄弟；colour记录的是棋子的颜色。
　　利用二叉树前序遍历的结果可以非常方便地生成给定的二叉树，具体做法是：将第一个输入的结点作为二叉树的根结点，后继输入的结点序列是二叉树左子树前序遍历的结果，由它们生成二叉树的左子树；再接下来输入的结点序列为二叉树右子树前序遍历的结果，应该由它们生成二叉树的右子树；而由二叉树左子树前序遍历的结果生成二叉树的左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同，只是所处理的对象范围不同，于是完全可以使用递归方式加以实现。_［5]
　　建立二叉树可以采用递归或者非递归的方法，在该程序中采用递归的方法，函数名为ins_node，函数的主要代码分析如下：_［2]
　　ins_node(bitree s,bitree t,String dir) //s、t为二叉树节点类型变量
　　{AnsiString aa=IntToStr(j)+"-("+FloatToStr(s->x1)+","+FloatToStr(s->y1)+")是否为左孩";
　　//aa为字符串类型变量
　　if(t＝＝NULL)//判断节点是否为空
　　{ t=s; //为空则插入
　　if(Table1->TableName!=NULL) //表格名称是否为空
　　{String command="insertinto"+Table1->TableName+"values('"+FloatToStr(s->x1)+"','"+FloatToStr(s->y1)+"','"+t->jieshou+"','"+_dir+"')";
　　//将坐标值等存入数据库的表中
　　Query1->SQL->Text=command;
　　Query1->ExecSQL( );
　　} elseShowMessage("没有建立该表!");
　　}
　　else if(MessageDlg(aa ,mtInformation, TMsgDlgButtons() << mbYes<　　//是否为左孩子
　　{ _dir=_dir+"l";
　　t->lchild=ins_node(s,t->lchild,_dir);
　　//递归建立左子树
　　}
　　else
　　{_dir=_dir+"r";
　　t->rchild=ins_node(s,t->rchild,_dir);
　　//递归建立右子树
　　}
　　return t;
　　}
　　2.2 遍历二叉树实现定式的输出
　　建立在存储结构为树形结构的基础上，对围棋中每一个定式的显示就相当于对所存储的二叉树进行遍历。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列。
　　二叉树的遍历有三种方法：前序遍历、中序遍历、后序遍历。由于每一个定式的特点，我们可以采用前序遍历的方法实现对围棋定式的显示。
　　_preorder( )函数的功能是通过递归调用对已经建立的二叉树进行右子树遍历。参数root为二叉树的根节点，biaoji是一个标记值，整形变量，返回值为空。
　　递归算法是遍历二叉树常采用的算法，用递归写的二叉树遍历程序简洁且通俗易懂。_preorder( )函数先判断当前结点是否为空，若不为空，则设置要显示的画布颜色以及字体颜色，并输出标记符号，递归遍历该结点的右子树；若为空则退出。_［3]
　　该函数的流程图见图1。
　　_preorder(bitree root,int biaoji) //root为二叉树的根节点
　　{
　　int k=0;
　　if(root!=NULL)
　　{Image1->Canvas->TextOutA(root->x1,root->y1,IntToStr(biaoji));
　　//根據遍历树的值在画布上显示标记符号，即指明下一步该走哪一个位置
　　biaoji++;
　　_preorder(root->rchild,biaoji);
　　//遍历右兄弟节点
　　}
　　}
　　


　　本文将数据结构中树的算法应用于围棋定式管理系统，详尽论述了开发围棋定式管理系统各部分主要程序算法的具体思路和方法。应用该系统可以随时进入研究模式自己再琢磨新的走法，研究时进退自如，免除在传统棋盘上反复移挪棋子之苦。围棋是检验人工智能发展水平的良好环境，如何提高围棋程序的棋力是人工智能领域的一大难题。同时，开发出与人类棋手水平相当的围棋程序也有助于对人类认知能力的理解，计算机围棋研究具有重要的理论意义和实用价值。
　　
　　3 参考文献
　　
　　1 西 丁.围棋基本定式100例[M].四川：署蓉棋艺出版社,1999
　　2 肖正南.C++ Builder 6编程实用指南[M].湖北：华中科技大学出版社,2004
　　3 严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社，1997