注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

象棋程序,着法排序中相关的“杀手启发” 和 “历史表启发” 算法  

2008-06-25 18:42:17|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

下面这个解释的真是非常清楚啊,很多关键地方都说了了,来自http://en.wikipedia.org/wiki/Killer_heuristic

真不明白为什么国家要封 wiki这个东西,很多有用的资料啊。

Killer heuristic

From Wikipedia, the free encyclopedia

Jump to: navigation, search
象棋程序,着法排序中相关的“杀手启发” 和 “历史表启发” 算法 - widebright - widebright的个人空间
This article does not cite any references or sources. (October 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In competitive two-player games, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning, which in turn improves the efficiency of the minimax algorithm. This algorithm has an exponential search time to find the optimal next move, so general methods for speeding it up are very useful.

Alpha-beta pruning works best when the best moves are considered first. This is because the best moves are the ones most likely to produce a cutoff, a condition where the game playing program probably knows that the position it is presently considering could not possibly have resulted from best play by both sides and so need not be considered further.

The killer heuristic attempts to produce a cutoff by assuming that a move that produced a cutoff in another branch of the game tree at the same depth is likely to produce a cutoff in the present position, that is to say that a move that was a very good move from a different (but possibly similar) position might also be a good move in the present position. By trying the killer move before other moves, a game playing program can often produce an early cutoff, saving itself the effort of considering or even generating all legal moves from a position.

In practical implementation, game playing programs frequently keep track of two killer moves for each depth of the game tree and see if either of these moves, if legal, produces a cutoff before the program generates and considers the rest of the possible moves. If a non-killer move produces a cutoff, it replaces one of the two killer moves at its depth.

A generalization of the killer heuristic is the history heuristic. The history heuristic can be implemented as a table that is indexed by some characteristic of the move, for example "from" and "to" squares or piece moving and the "to" square. When there is a cutoff, the appropriate entry in the table is incremented, such as by adding or 2d where d is the current search depth. This information is used when ordering moves.

  评论这张
 
阅读(549)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017