第４１卷第６期吉林大学学报（工学版）Ｖｏｌ．４１Ｎｏ．６２０１１年１１月ＪｏｕｒｎａｌｏｆＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ（ＥｎｇｉｎｅｅｒｉｎｇａｎｄＴｅｃｈｎｏｌｏｇｙＥｄｉｔｉｏｎ）Ｎｏｖ．２０１１基于形势判断和遗传算法的计算机围棋静态评估算法余磊１，３，魏君２，田丰３，刘锦高３（１．南昌航空大学信息工程学院，南昌３３００６３；２．吉林大学公共教学中心，长春１３００６２；３．华东师范大学信息科学技术学院，上海２０００６２）摘要：提出了一种计算静态评估值的数学模型，并结合遗传算法对模型参数进行了优化。利用此方法可以获得不同棋力下分别对应的不同静态评估算法模型。对比实验结果表明，该模型能将运算精度提升９３％，运算速度提升３５％；其运行能力可以应用于计算机围棋中盘、收官等模块中，对计算机博弈、人工智能以及游戏软件的研究具有重要意义。关键词：人工智能；静态评估；形势判断；遗传算法中图分类号：ＴＰ１８２文献标志码：Ａ文章编号：１６７１－５４９７（２０１１）０６－１６９４－０５ＣｏｍｐｕｔｅｒｓｏｌｕｔｉｏｎｏｆｓｔａｔｉｃｅｖａｌｕａｔｉｏｎｐｒｏｂｌｅｍｓｂａｓｅｄｏｎｐｏｓｉｔｉｏｎａｌａｎａｌｙｓｉｓａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍＹＵＬｅｉ１，３，ＷＥＩＪｕｎ２，ＴＩＡＮＦｅｎｇ３，ＬＩＵＪｉｎ－ｇａｏ３（１．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＮａｎｃｈａｎｇＨａｎｇｋｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ３３００６３，Ｃｈｉｎａ；２．ＴｅａｃｈｉｎｇＣｅｎｔｅｒｏｆＢａｓｉｃＣｏｕｒｓｅｓ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００６２，Ｃｈｉｎａ；３．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００６２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＡｎａｐｐｒｏａｃｈｂａｓｅｄｏｎＧｏｋｎｏｗｌｅｄｇｅｔｏｃａｌｃｕｌａｔｅｔｈｅｓｔａｔｉｃｅｖａｌｕａｔｉｏｎｖａｌｕｅｉｓｐｒｏｐｏｓｅｄ，ａｎｄｔｈｅｐａｒａｍｅｔｅｒｏｆｔｈｅｍｏｄｅｌｉｓｆｕｒｔｈｅｒｏｐｔｉｍｉｚｅｄｂｙｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．Ｔｈｒｏｕｇｈｔｈｉｓａｐｐｒｏａｃｈ，ｖａｒｉｏｕｓｓｔａｔｉｃｅｖａｌｕａｔｉｏｎｍｏｄｅｌｓｂａｓｅｄｏｎｄｉｆｆｅｒｅｎｔｌｅｖｅｌｓｃａｎｂｅｏｂｔａｉｎｅｄ．Ｔｈｅｒｅｓｕｌｔｓｏｆｔｅｘｔｓｈｏｗｔｈａｔ，ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｏｒｉｇｉｎａｌｍｏｄｅｌ，ｔｈｅａｃｃｕｒａｃｙａｎｄｏｐｅｒａｔｉｏｎｓｐｅｅｄｏｆｔｈｅｐｒｏｐｏｓｅｄａｐｐｒｏａｃｈａｒｅｐｒｏｍｏｔｅｄｂｙ９３％ａｎｄ３５％ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｗｅｅｘｐｅｃｔｔｈａｔ，ｗｉｔｈｓｕｃｈｏｐｅｒａｔｉｏｎｃａｐａｃｉｔｙ，ｔｈｉｓｍｏｄｅｌｃａｎｂｅａｐｐｌｉｅｄｉｎｔｈｅｍｏｄｕｌｅｏｆｔｈｅｍｉｄｄｌｅｇａｍｅａｎｄｅｎｄｇａｍｅｏｆｃｏｍｐｕｔｅｒＧｏ．Ｔｈｉｓｍｏｄｅｌｈａｓａｐｒａｃｔｉｃａｌｕｔｉｌｉｚａｔｉｏｎｉｎｒｅｓｅａｒｃｈｅｓｏｎｃｏｍｐｕｔｅｒｇａｍｅｓ，ａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅａｎｄｇａｍｅｓｏｆｔｗａｒｅ．Ｋｅｙｗｏｒｄｓ：ａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅ；ｓｔａｔｉｃｅｖａｌｕａｔｉｏｎ；ｐｏｓｉｔｉｏｎａｌａｎａｌｙｓｉｓ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ围棋是一门形象思维和逻辑思维兼备的艺强的围棋对弈程序大约２级左右，不及人类棋手术，也是人工智能领域的难题之一。由于围棋棋学棋一年的水平［１］。因此，借鉴人类棋手的思维局状态的搜索空间巨大，类似于国际象棋程序中特点设计相应的启发式算法是提高计算机围棋棋普遍采用的穷举式搜索难以奏效；目前世界上最力的可行途径之一［２］。收稿日期：２０１０－０１－０７．基金项目：国家自然科学基金项目（６０９７３０４８）；博士科研启动基金项目（ＥＡ２０１１０４１８３）；上海市科技攻关重点项目（０７５１１５００２）．作者简介：余磊（１９８４－），男，博士研究生．研究方向：计算机围棋，人工智能．Ｅ－ｍａｉｌ：ｃｈｅｎｓｈｉｙｕ１＠ｇｍａｉｌ．ｃｏｍ第６期余磊，等：基于形势判断和遗传算法的计算机围棋静态评估算法·５９６１·目前，围棋程序通常单纯以可成空目数最大凭借棋局已进行手数Ｔ和边界空点数，依然难以作为最佳棋步的评判标准［３］。然而，在围棋比赛准确描述棋局进展程度。因此，本文提出待定区中，输赢的结果与输赢多少目无关：除去贴目，即域的概念：棋盘上有待双方争夺的地域称为待定使比对方多一目，