Shogi

[Onno Garms]

What is the trick to handle the enormous number of moves (large branching factor) that are "drops", i.e. insertion of pieces from your hand? This problem arises in shogi, bughouse chess (in German: Tandem) and chessgi. If there is such a trick, Zillions seems to have missed it. At least it is extremely weak at bughouse, chessgi and even pocket knight chess (both players have one knight to drop, besides that normal chess).

[Tord Romstad]

What is the trick to handle the enormous number of moves (large branching factor) that are "drops", i.e. insertion of pieces from your hand? This problem arises in shogi, bughouse chess (in German: Tandem) and chessgi.

I'm still a beginner in computer shogi, but the way I handle it is to search drops to "obviously irrelevant" parts of the board with dramatically reduced depth. The shogi board is big, and most of the pieces are quite weak and slow-moving. If a non-sliding piece is dropped far from both kings and the promotion zone, does not defend any friendly piece or attack an enemy piece, and does not defend against some serious threat, the drop is very unlikely to be a good move.

So far, my impression is that the high branching factor isn't the biggest problem in shogi programming. A far bigger problem is to write a decent evaluation function. This is relatively easy in chess, because material is the overwhelmingly most important evaluation component, and very easy to quantify. In shogi, where factors like king safety, speed of attack and initiative (all of which are very difficult to quantify) can often compensate for a huge material disadvantage, evaluation is much more difficult.

I have very little experience with bughouse and chessgi, but I would expect them to be similar to shogi in this respect.

Tord

[mjlef]

Yes, Zillions does not do so well in games with huge branching factors, like Shogi with its piece drops, or Go with a large board. Coming up with pruning or depth reduction rules for a game when you do not even know the rules until it gets loaded is quite a challenge. Tord solution of limiting depth on most position drops is nice, but very game specific.

Overall, Zillions does OK with a large class of games, and I am always trying to come up with ways to improve it, so send me your suggestions.

Mark