Using Partial Order Bounding in Shogi
Grimbergen, R., Hadano, K. and Suetsugu, M. (2003)
in: The 8th Game Programming Workshop in Japan (GPW2002),
pp. 52--58, Kanagawa, Japan.
Abstract
Using a weighted sum of feature values as evaluation function has
some important drawbacks. If an evaluation function with a partial
order of features is used, information which is otherwise lost by using
a weighted sum can be preserved and better move decisions can be made.
Partial Order Bounding (POB) is a new search method that promises to
be more efficient than earlier attempts to search with partial order
evaluations. Thus far, POB has only be applied to Go endgames. In this
paper, we discuss the use of POB in shogi. We outline the implementation
decisions that have to made when using POB. These concern the choice
of the partial order evaluation, how to set the search targets in POB
and how to manage multiple iterations of POB. We compare the
results of a number of different implementation schemes of POB in
shogi. The best scheme is able to find the correct move in 27 out
of 50 next move shogi problems, using an average time of 48 seconds
per problem. We consider this a good starting point for
further research in Partial Order Bounding.