Generic Alpha Beta Search with C++

Question

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

Декларация этого шаблона функции выглядит следующим образом:

template<class GameState, class Move, 
     class EndGame, class Evaluate, class GetMoves, class MakeMove) 
int alphaBetaMax(GameState g, int alpha, int beta, int depthleft); 

Среди других вещей, функция должна:

• Определить, если игра закончилась: bool EndGame(g)
• Оценка состояния игра: int Evaluate(g)
• Получить возможные ходы: std::vector<Move> moves = GetMoves(g)
• Двигайся: Gamestate gnew = MakeMove(g, moves[i])

Как вы думаете, функция должна много аргументов шаблона? Есть ли способ, чтобы уменьшить количество аргументов? Одна из идей состоит в том, чтобы расширить класс GameState с помощью членов , которые оценивают игру gamestate или решают, закончилась ли игра. Но дерево поиска альфа-бета содержит много экземпляров Gamestate, что может привести к ненужным потребностям в памяти , поэтому мне нравится держать Gamestate маленьким. В общем, правильный ли шаблон функции?

Answer 1

Вы могли бы определить абстрактный интерфейс сказать game_traits и специализировался реализация game_traits для каждой игры:

template<typename Game> 
class game_traits { 
    ... 
}; 

class Chess { 
    ... 
}; 

template<> 
class game_traits<Chess> { 
    static bool endGame(Chess game); 
    ... 
}; 

template <typename Game, typename traits = game_traits<Game> > 
int alphaBetaMax(Game game, int alpha, int beta, int depthleft) { 
    ended = traits::endGame(game); 
    ... 
} 

См char_traits в стандартной библиотеке С ++, как она там используются.

В качестве альтернативы вы можете сделать их только методами классов игры, вам не нужно наследование здесь из какого-то абстрактного класса, поскольку вы предоставляете его как аргумент шаблона. Вы просто получите, возможно, не столь прозрачную ошибку компиляции, когда ваша функция шаблона пытается получить доступ, скажем, game.has_ended(), когда такой метод не существует. Такой механизм также широко используется в стандартной библиотеке шаблонов.

Кстати, для этого была запланирована новая функция; Концепции:

auto concept GameType<typename Game> 
{ 
    bool has_ended(Game&); 
    ... 
}; 

template<typename Game> requires GameType<Game> 
int alphaBetaMax(Game game, int alpha, int beta, int depthleft) { 
    bool ended = game.has_ended(); 
    ... 
} 

К сожалению понятия были отложены до будущей версии стандарта и пока не будут появляться в C++ 0x :(

Answer 2

Наивный вопрос: не следует оценка GameState и «игра закончилась» решение быть дополнительным методы (Вы писали членов) в классе GameState, и, таким образом, не занимают никакой дополнительной памяти в-случае? Просто спрашиваю ...

Answer 3

Лично я пишу это как:

int alphaBetaMax(GameState *g, Move *move, EndGame *endgame, 
    Evaluate *evaluate, GetMoves* getmoves, MakeMove* makemove, 
    int alpha, int beta, int depthleft); 

Вы назвали бы это так:

GameState gs; 
alphaBetaMax(&gs, new ChessMove(), new ChessEndGame(), new ChessEvaluate(), 
    new ChessGetMoves(), new ChessMakeMove(), a, b, 40); 

сама функция удалит все указатель, но GameState (I» m Предполагая, что ваша функция возвращает результат, все остальное временно?).

Теперь еще лучший способ сделать это - пройти только один класс, который может сделать все, так как «сделать ход», «получить ход», «оценить», они все являются частью одной и той же логики. Нет причин делать 5 разных классов, C++ позволяет переопределить несколько виртуальных функций в классе.

Answer 4

Насколько я могу понять эту идею, я бы агрегировать вещи немного:

• GameState, EndGame, GetMoves, Оценка - обертывание одиночные черты типа GameStateTraits
• MakeMove это ответственность отдельного алгоритма, так GameMovePolicy

Я намеренно различаю черты и политику как отдельный тип. Как объясняется в Boost's Generic Programming Techniques, черты обычно несут информацию о типе, описание свойств типа. Эта идея хорошо подходит для переноса статической информации, состояния игры. Политика обеспечивает поведение - MakeMove является частью динамичного поведенческого алгоритма игры.

template<typename GameStateTraits, typename GameMovePolicy> 
int alphaBetaMax(GameStateTraits const& state, int alpha, int beta, int depthleft); 

Answer 5

Добавление методов в класс не делает объекты этого класса более крупными. Методы хранятся один раз для всего класса и используются вызовами в любых случаях. Поэтому добавление функций в класс GameState не приведет к тому, что алгоритм потребует больше памяти.

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

Более гибкий подход был бы просто использовать свободные функции в алгоритме:

template<class GameState> 
int alphaBetaMax(GameState g, int alpha, int beta, int depthleft) { 
    if (endGame(g)) { 
    return 1; 
    } 
    std::vector<Move> moves = getMoves(g); 
    // ... 
} 

Здесь endGame и getMoves зависимые имена, они зависят от параметра шаблона (так как они принимают g в качестве параметра). Поэтому компилятор не будет искать фактические определения этих имен при объявлении шаблона (он еще не знает, какой тип эти функции должен иметь после GameState еще не указан).

Только когда шаблон конкретизируется Перегрузки для этих функций должны быть доступны, которые подходят так, как они используются в шаблоне:

struct MyGameState {}; 

bool endGame(const MyGameState &st) { 
    return false; 
} 

std::vector<Move> getMoves(const MyGameState &st) { 
    // ... 
} 

void tst() { 
    MyGameState s; 
    alphaBetaMax(s, 1, 1, 1); // uses the new functions 
} 

Таким образом, вы можете адаптировать любой объект GameState к вашему алгоритму без потребовать специальные методы для этих объектов. Чтобы избежать загрязнения глобального пространства имен этими новыми функциями, вы можете поместить их в собственное пространство имен или класс признаков.

Таким образом, вы можете просто оставить дополнительные параметры шаблона, если функции правильных имен и типов будут определены после создания экземпляра шаблона.

Answer 6

Слишком много? Почему это шаблон? Это как раз то, как «ударять ноготь с бесконечными молотками», вам нужно быть осторожным с шаблонами. Особенно что-то вроде AI, где большинство проблем в значительной степени трудноразрешимы, а производительность имеет решающее значение.