Application of the killer-tree heuristic and the lambda-search method to lines of action
This paper investigates the application of the the killer-tree heuristic (KTH) and the ?1-search method to the endgame of lines of action. Both techniques are developed to be used in the endgame of shogi. They are incorporated into two depth-first searches: iterative deepening ?? and PDS. ?1-Search, in which the move generation is limited to ?1-moves, shows a poor ability to find winning solutions. When using ?1-sorting, in which ?1-moves are put at the front of the move list, the number of nodes searched is reduced considerably, but the solving ability is diminished because of the inefficiency of the move generation. Using the KTH, the number of nodes searched and the solving time are reduced by 5% in iterative deepening ?? and by 20% in PDS. Consequently, the solving ability has been enhanced.
killer-tree heuristic lambda-search lines of action endgame search