A C++ based variants chess engine design question

Question

I have a chess variants engine that plays suicide chess and losers chess along with normal chess. I might, over time, add more variants to my engine. The engine is implemented completely in C++ with proper usage of OOP. My question is related to design of such a variant engine.

Initially the project started as a suicide-only engine while over time I added other flavors. For adding new variants, I experimented using polymorphism in C++ first. For instance, a MoveGenerator abstract class had two subclasses SuicideMoveGenerator and NormalMoveGenerator and depending on the type of game chosen by user, a factory would instantiate the right subclass. But I found this to be much slower - obviously because instantiating classes containing virtual functions and calling virtual functions in tight loops are both quite inefficient.

But then it occurred to me to use C++ templates with template specialization for separating logic for different variants with maximum reuse of code. This also seemed very logical because dynamic linking is not really necessary in the context as once you choose the type of game, you basically stick with it until the end of the game. C++ template specialization provides exactly this - static polymorphism. The template parameter is either SUICIDE or LOSERS or NORMAL.

enum GameType { LOSERS, NORMAL, SUICIDE };

So once user selects a game type, appropriate game object is instantiated and everything called from there will be appropriately templatized. For instance if user selects suicide chess, lets say:

ComputerPlayer<SUICIDE>

object is instantiated and that instantiation basically is linked to the whole control flow statically. Functions in ComputerPlayer<SUICIDE> would work with MoveGenerator<SUICIDE>, Board<SUICIDE> and so on while corresponding NORMAL one will appropriately work.

On a whole, this lets me instantiate the right templatize specialized class at the beginning and without any other if conditions anywhere, the whole thing works perfectly. The best thing is there is no performance penalty at all!

The main downside with this approach however is that using templates makes your code a bit harder to read. Also template specialization if not appropriately handled can lead to major bugs.

I wonder what do other variant engine authors normally do for separation of logic (with good reuse of code)?? I found C++ template programming quite suitable but if there's anything better out there, I would be glad to embrace. In particular, I checked Fairymax engine by Dr. H G Muller but that uses config files for defining game rules. I don't want to do that because many of my variants have different extensions and by making it generic to the level of config-files the engine might not grow strong. Another popular engine Sjeng is littered with if conditions everywhere and I personally feel thats not a good design.

Any new design insights would be very useful.

Answer 1

I'm not quite sure if this is a fit but you may be able to achieve static polymorphism via the CRTP with some slight modifications to your original design.

Answer 2

"Calling virtual functions in tight loops are inefficient"

I would be pretty surprised actually if this caused any real bloat, if all the variables of the loop have the same dynamic type, then I would expect the compiler to fetch the corresponding instruction from its L1 cache and thus not suffer much.

However there is one part that worries me:

"obviously because instantiating classes containing virtual functions [is] quite inefficient"

Now... I am really surprised.

The cost of instantiating a class with virtual functions is near undistinguishable from the cost of instantiating a class without any virtual functions: it's one more pointer, and that's all (on popular compilers, which corresponds to the _vptr).

I surmise that your problem lies elsewhere. So I am going to take a wild guess:

• do you, by any chance, have a lot of dynamic instantiation going on ? (calling new)

If that is the case, you would gain much by removing them.

There is a Design Pattern called Strategy which would be eminently suitable for your precise situation. The idea of this pattern is akin, in fact, to the use of virtual functions, but it actually externalize those functions.

Here is a simple example:

class StrategyInterface
{
public:
  Move GenerateMove(Player const& player) const;
private:
  virtual Move GenerateMoveImpl(Player const& player) const = 0;
};

class SuicideChessStrategy: public StrategyInterface
{
  virtual Move GenerateMoveImpl(Player const& player) const = 0;
};

// Others

Once implemented, you need a function to get the right strategy:

StrategyInterface& GetStrategy(GameType gt)
{
  static std::array<StrategyInterface*,3> strategies
    = { new SuicideChessStrategy(), .... };
  return *(strategies[gt]);
}

And finally, you can delegate the work without using inheritance for the other structures:

class Player
{
public:
  Move GenerateMove() const { return GetStrategy(gt).GenerateMove(*this); }

private:
  GameType gt;
};

The cost is pretty much similar to using virtual functions, however you do not need dynamically allocated memory for the basic objects of your game any longer, and stack allocation is a LOT faster.