计算机桥牌双明手解的Hash表改进  

Improvement of Using Hash Table in Computer Bridge Double-dummy Solver

作　　者：程克非[1] 张聪[2] 沈一栋[3] 

机构地区：[1]重庆邮电学院计算机系 [2]重庆交通学院计算机系,重庆400074 [3]中国科学院软件研究所计算机科学重点实验室,北京100080

出　　处：《重庆大学学报（自然科学版）》2005年第12期45-47,共3页Journal of Chongqing University

基　　金：国家自然科学基金资助项目(69883009)

摘　　要：人工智能中关于牌类游戏的研究因为具有信息不完备的特点,在发展上落后于棋类游戏.牌类游戏研究的基础是在信息不完备条件下寻求一种快速的局面求解方法,虽然这个问题也非常困难.在采用Scout搜索的桥牌双明手算法基础上,提出根据牌局的特点对局面进行标准化编码的方案,从而提高了Scout搜索中Hash表的内存利用率和查询命中率,使得在剪枝过程中比原来的算法少展开5%的叶节点.Incomplete information of the poker games make the research progress lags behind the chess games in AI. Although it is still very difficult to find a fast algorithm to solve a poker game with complete information which is the foundation of some advance researches. This paper gives a standard way to encode and store a game state into hash table, so the memory of hash table can be used more effectively and higher hit rate can be gotten in Scout search meth od. With the new encoding method, the total expanding leaf nodes reduces by around 5%.

关 键 词：对策树搜索 HASH表 计算机桥牌 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]