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

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

人工智能中关于牌类游戏的研究因为具有信息不完备的特点,在发展上落后于棋类游戏.牌类游戏研究的基础是在信息不完备条件下寻求一种快速的局面求解方法,虽然这个问题也非常困难.在采用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%.