I'm writing a Shogi program with a computer player in Java from scratch as my undergradute dissertation project. Due to the drop rule, when the computer player captures a few pieces, the branching factor increases a lot and the running time becomes infeasible. I haven't manage to find any research or information on drop reduction and my own selection is too slow and not "selective" enough (trying to remove drops that are not safe or not protected and don't have any use like defending or attacking). Does anyone know any heuristics that can be implemented with reasonable time complexity for selecting drops that are worth adding to the game tree ? Cheers.
So, like in (western) Chess a piece can be captured and when a piece is captured the capturing player holds on to it. Now this piece can be dropped on the board anywhere on a free tile in any of the next turns (instead of moving a piece from the board). There are a lot more rules to drops but they are irrelevant. Because of this rule, when a player makes a capture, instead of a decrease in the branching factor like in chess, an increase of the branching factor happens because of the large amount of possible drops that can be made on the next turn. This results in an average branching factor of 80 (much more than Chess which has a average branching factor of 35).