H. G. Muller wrote on Thu, Aug 21, 2008 05:34 PM UTC:
| So just in four turns, the number of possibilities is quite large.
| First player turn X Second player turn X First player turn X Second
| player turn. And this is still not sufficient for effective play.
| The depth-search would need to be at least eight plys just to offer
| a 'good' move.
Well, this is how it worked in the stone age, before they invented alpha-beta, null-move pruning and late-move reductions. I would be surprised if with these modern search techniques you would not reach 10 ply in a minute or so for this game. In normal Chess the top programs reach 20 ply in that time. That is in a game with on the average 40 moves per position, so according to your calculation, that should require them to search 40^20 or about 10^32 positions. Yet they can do it when searching about 1 million per second (so ~10^8 in total). They thus search about 4 times deeper than your equation suggests.
It is true that Zillions is rather inefficient in handling games with drops. It does not seem to reduce the search depth for them, as it should. But Zillions is of course hardly a standard to measure things by. Don't get me wrong, I think it is a miraculous product, and have great respect for its designers. But in being completely general, it is unavoidable that a lot of efficiency gets lost. A dedicated Chess program, even my 100-lines miniature micro-Max / Fairy-Max, totally crushes Zillions in the games that it is able to play (e.g. Capablanca Chess, Shatranj, Knightmate).
The reason I think HiveQueen would be easy to program is that most positions seem rather quiet to me: many pieces cannot capture at all. So it should be easy to evaluate by 'wood counting'.