计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (16): 54-55.

• 理论研究 • 上一篇    下一篇

博弈树启发式搜索的α-β茁剪枝技术研究

张聪品,刘春红,徐久成   

  1. 河南师范大学 计算机与信息技术学院 智能信息处理实验室,河南 新乡 453007
  • 收稿日期:2007-12-12 修回日期:2008-03-24 出版日期:2008-06-01 发布日期:2008-06-01
  • 通讯作者: 张聪品

Research on alpha-beta pruning of heuristic search in game-playing tree

ZHANG Cong-pin,LIU Chun-hong,XU Jiu-cheng   

  1. Key Laboratory for Intelligent Information Processing,College of Computer and Information Technology,Henan Normal University,Xinxiang,Henan 453007,China
  • Received:2007-12-12 Revised:2008-03-24 Online:2008-06-01 Published:2008-06-01
  • Contact: ZHANG Cong-pin

摘要: 博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。

Abstract: The game playing is an important domain of heuristic search,and its procedure is represented by a special and/or tree.Alpha-beta pruning is always used for problem solving by searching the game-playing-tree.In this paper,the plan which child nodes are inserted into game-playing-tree from large value of estimation function to small one when the node of no receiving fixed ply depth is expanded is proposed based on alpha-beta pruning.It improves the effect of search.