2
\$\begingroup\$

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).

\$\endgroup\$

closed as too broad by Vaughan Hilts, Seth Battin, congusbongus, bummzack, MrCranky May 5 '15 at 9:03

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ This queston is way too broad to be answered on a Q&A site like this. \$\endgroup\$ – Almo Apr 22 '15 at 12:55
  • \$\begingroup\$ What do you mean too broad ? It's about heuristics for a specific rule of a specific game. It might be too specific rather than too broad. \$\endgroup\$ – user3301833 Apr 22 '15 at 12:59
  • \$\begingroup\$ "Heuristics" itself is really broad. There won't be one: this would cause a lengthy discussion, and so is not suited to Q&A. You're better off on a forum, or in our chat room. \$\endgroup\$ – Almo Apr 22 '15 at 13:53
  • \$\begingroup\$ I see, you do have a point. Cheers. \$\endgroup\$ – user3301833 Apr 22 '15 at 14:02
3
\$\begingroup\$

Shogi is well researched, so you should be able to find research papers detailing different methods of implementing pruning or reduction heuristics for Shogi.

I can't offer specific advice since I've never implemented a Shogi engine, but I did implement one for Bughouse/Crazyhouse, which has similar rules (captured pieces can be dropped). My advice would be to simply focus on optimizing the efficiency of the engine as much as possible - I don't only mean speed here, though raw speed shouldn't be neglected. Remember that with alpha-beta pruning the effective branching factor of your engine only goes up by sqrt(average_legal_moves), so the increase due to the drop rule is much less as you would naively think (from 6 to 9). Now notice that real chess engines have an effective branching factor of just ~2 because they use more heuristics than basic alpha-beta pruning.

If a high branching factor is making your engine weak, it's much more likely your basic alpha-beta + move ordering + iterative deepening + transposition table + nullmove + futility + LMR implementation isn't good enough and contains bugs. I would focus on those before doing more complicated things specifically for drop-moves.

\$\endgroup\$
  • \$\begingroup\$ For now my engine uses a multi-threaded negamax with transposition tables, iterative deepening, very basic move ordering MVV-LVA (history and killers), alpha-beta pruning, LMR and null move. I haven't found any problem with any of these procedures so I assumed that the branching is too large. Many other procedures for Shogi like bitboards, futility, more advanced move ordering, etc are over my level of comprehension and my time is very limited. Anyways, thanks for the answer. \$\endgroup\$ – user3301833 Apr 22 '15 at 16:14
  • \$\begingroup\$ Oh, and believe me that Shogi is not as well researched as you think compared to many many other games. Or at least the research is not accessible online. \$\endgroup\$ – user3301833 Apr 22 '15 at 16:23
  • \$\begingroup\$ Make sure you are using the transposition table to store the best move to help move ordering. As for resources, start here: chessprogramming.wikispaces.com/Shogi I guess much useful material might be in Japanese, though. \$\endgroup\$ – gcp Apr 22 '15 at 19:23
  • \$\begingroup\$ I've been searching and reading everything on that website xD. And yes probably many resources would be available if I would know Japanese, but I don't. Thanks for the TT best move tip though. \$\endgroup\$ – user3301833 Apr 22 '15 at 21:11
0
\$\begingroup\$

I have no direct experience with Shogi, but:

1) You should check that your implementation isn't unnecessarily slow - as noted in gcp's answer, it sounds like it should work. How many positions do you evaluate per second? In C++ for a simple game, you can get around 10^7 moves per second. If you have complex heuristics and/or complex game rules, you still should stay at least at 10^6. If you are significantly below, you are probably doing something wrong and should focus on optimizing your code.

2) If your implementation is fast, but branching factor too high, you can use Monte Carlo Tree Search, especially UCT as for example here: http://senseis.xmp.net/?UCT It is not that hard too implement (I did it in C++ in around 3 days) and has worked well for Go, so it should be good for you as well.

\$\endgroup\$
  • \$\begingroup\$ Wow 10^6... I'm barely close to 10^4, damn I have so much to learn but not enough time, oh well. Cheers for the benchmarks. \$\endgroup\$ – user3301833 Apr 25 '15 at 10:56
  • \$\begingroup\$ @user3301833 Then you really need to optimize. There is a lot info on the Internet on optimizing Java code, but most notably: a) use a profiler to determine what actually is slow instead of guessing what is slow and b) preallocate all memory - both object creation and garbage collection are extremely slow. \$\endgroup\$ – Martin Modrák Apr 27 '15 at 8:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.