Варианты разработки шахматного движка на основе C ++ - PullRequest
Новая
       7

Варианты разработки шахматного движка на основе C ++

5 голосов
/ 12 сентября 2010

У меня есть механизм вариантов шахмат, который играет шахматы-самоубийцы и шахматы неудачников наряду с обычными шахматами. Со временем я мог бы добавить больше вариантов в мой двигатель. Движок полностью реализован на C ++ с правильным использованием ООП. Мой вопрос связан с дизайном такого варианта двигателя.

Первоначально проект начинался как самоубийственный движок, а со временем я добавил другие варианты. Для добавления новых вариантов я сначала экспериментировал с использованием полиморфизма в C ++. Например, у абстрактного класса MoveGenerator есть два подкласса SuicideMoveGenerator и NormalMoveGenerator, и в зависимости от типа игры, выбранного пользователем, фабрика будет создавать правильный подкласс. Но я обнаружил, что это намного медленнее - очевидно, потому что создание экземпляров классов, содержащих виртуальные функции, и вызов виртуальных функций в узких циклах - оба совершенно неэффективны.

Но потом мне пришло в голову использовать шаблоны C ++ с шаблонной специализацией для разделения логики для разных вариантов с максимальным повторным использованием кода. Это также казалось очень логичным, потому что динамическое связывание на самом деле не является необходимым в контексте, поскольку, выбрав тип игры, вы в основном придерживаетесь его до конца игры. Специализация шаблонов C ++ обеспечивает именно это - статический полиморфизм. Параметр шаблона: либо SUICIDE, либо LOSERS, либо NORMAL. 

enum GameType { LOSERS, NORMAL, SUICIDE };

Таким образом, как только пользователь выбирает тип игры, создается соответствующий игровой объект, и все, что там вызывается, будет соответствующим образом шаблонизировано. Например, если пользователь выбирает шахматы-самоубийцы, скажем: 

ComputerPlayer<SUICIDE>

объект создается, и это создание в основном статически связано со всем потоком управления. Функции в ComputerPlayer<SUICIDE> будут работать с MoveGenerator<SUICIDE>, Board<SUICIDE> и т. Д., В то время как соответствующая NORMAL будет работать соответствующим образом.

В целом, это позволяет мне создавать правильный шаблонизированный специализированный класс в начале и без каких-либо других условий if в любом месте, все работает отлично. Лучше всего то, что производительности вообще не будет!

Однако основным недостатком этого подхода является то, что использование шаблонов делает ваш код немного сложнее для чтения. Кроме того, специализация шаблона, если она не обрабатывается надлежащим образом, может привести к серьезным ошибкам.

Интересно, что обычно делают другие разработчики движков для разделения логики (с хорошим повторным использованием кода) ?? Я нашел подходящее программирование на C ++, но если есть что-то лучшее, я был бы рад принять. В частности, я проверил движок Fairymax доктора Г. Г. Мюллера, но он использует файлы конфигурации для определения правил игры. Я не хочу этого делать, потому что многие из моих вариантов имеют разные расширения и, делая его общим для уровня config-файлов, движок может не стать сильным. Другой популярный движок Sjeng везде окружен if условиями, и я лично считаю, что это не очень хороший дизайн.

Любые идеи нового дизайна были бы очень полезны.

Ответы [ 2 ]

6 голосов
/ 12 сентября 2010

"Вызов виртуальных функций в узких циклах неэффективен"

Я был бы очень удивлен, если бы это вызвало реальное раздувание, если все переменные цикла имеют одинаковый динамический типтогда я ожидал бы, что компилятор извлечет соответствующую инструкцию из своего кэша L1 и, таким образом, не сильно пострадает.

Однако есть одна часть, которая меня беспокоит:

"очевидно, потому что создание экземпляраклассы, содержащие виртуальные функции [это] совершенно неэффективно "

Теперь ... Я действительно удивлен.

Стоимость создания класса с виртуальными функциями почти неотличима от стоимостисоздание экземпляра класса без каких-либо виртуальных функций: это еще один указатель, и это все (на популярных компиляторах, что соответствует _vptr).

Я предполагаю, что ваша проблема кроется в другом месте.Итак, я собираюсь сделать дикое предположение:

  • У вас, случайно, много динамических инстанциаций происходит?(звонит new)

Если это так, вы бы много выиграли, удалив их.

Существует шаблон проектирования под названием Strategy, который в высшей степени подходит дляваша точная ситуация.Идея этого шаблона на самом деле сродни использованию виртуальных функций, но на самом деле она экстернализует эти функции.

Вот простой пример: 

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

После реализации вынужна функция, чтобы получить правильную стратегию: 

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

И, наконец, вы можете делегировать работу без использования наследования для других структур: 

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

private:
  GameType gt;
};

Стоимость в значительной степени похожа наиспользуя виртуальные функции, однако вам больше не требуется динамически выделенная память для основных объектов вашей игры, а выделение стека происходит НАМНОГО быстрее.

0 голосов
/ 12 сентября 2010

Я не совсем уверен, подходит ли это, но вы можете достичь статического полиморфизма через CRTP с некоторыми небольшими изменениями в вашем первоначальном дизайне.

...