alpha beta search iterative deepening refutation table
I've implemented an alpha beta search with iterative deepening and i've read several techniques to further optimize the algorithm by searching for the best move first that came up from previous depth search.
as far as i understand, can i just store the principal variation from the previous depth search in dynamic length list? for example, suppose i have searched until depth 4 with PV : [1, 0, 2, 3] means that at depth 1, choose move number 1, at depth 2 choose move number 0, at depth 3 choose move number 2 , etc..., and then for depth 5 search, the algorithm will first search the child of the node from that previous depth PV.
is that what you call the refutation tables?
description of refutation table from this link : For each iteration, the search yields a path for each move from the root to a leaf node that results in either the correct minimax score or an upper bound on its value. This path from the d - 1 ply search can be used as the basis for the search to d ply. Often, searching the previous iteration's path or refutation for a move as the initial path examined for the current iteration will prove sufficient to refute the move one ply deeper.
if it's not the same, can you explain what is refutation table really is(because to me, both seems equal, but im not sure) and what is the advantage of using the refutation tables instead of the way i mentioned first?
From the description provided from your link, I assume that refutation tables more or less extend the concept of Triangular PV-Table to all root moves. In other words, not only the best root moves but all root moves are associated with a triangular PV-Table.
I may be mistaken, though, as I never used or even heard of that technique before. In todays world, where it is no problem to allocate a sufficiently big transposition tables, I don't see any advantages of refutation tables compared to the standard techniques of transposition tables, killer moves and maybe history tables (though many engines no longer use the latter).
My advice: If you haven't implemented transposition tables and killer moves yet, I would strongly recommend to start there to improve the move ordering.
链接地址: http://www.djcxy.com/p/84686.html上一篇: 跳棋中的Alpha beta修剪（用于证明效率的测试用例）
下一篇: alpha beta搜索迭代加深反驳表