Создать умный Спекер игрок игры


Я создаю игру под названием Спекер на C++.

Правила просты:

Есть \$р\$ игроков \$\влево(0 \П - 1\Право)\$ и $\Н\$ завались \$\влево(0 \П - 1\право)\$.

Начиная с игрока$0\$ каждый игрок берет \$к > 0 монет\$ из кучи \х $\$ и помещает монеты \$м\$ \$\влево(0 \ЛЭ м < к право\)\ долларов \кучи$г\$.

Выигрыша игрока, который играет последним, когда все монеты из все кучи удаляются.

Поэтому я создал игру и несколько классов игрока (GreedyPlayer, SpartanPlayer и т. д.) но они все немного предсказуемо, что они будут делать. Они не умные.

У вас есть какие-либо идеи о том, как создать более умного игрока AI, который будет на самом деле стараться победить в каждой игре?

Вот мой код:

#include <iostream>
#include <stdexcept>

using namespace std;

class Move {
private:
    int source_heap, source_coins, target_heap, target_coins;

public:
    Move(int sh, int sc, int th, int tc) {
        source_heap = sh;
        source_coins = sc;
        target_heap = th;
        target_coins = tc;
    }

    int getSource() const {
        return source_heap;
    }
    int getSourceCoins() const {
        return source_coins;
    }
    int getTarget() const {
        return target_heap;
    }
    int getTargetCoins() const {
        return target_coins;
    }

    // Let's do some operator overloading
    friend ostream &operator<<(ostream &out, const Move &move) {
        if (move.getTargetCoins()) {
            out << "takes " << move.getSourceCoins() << " coins from heap "
                << move.getSource() << " and puts " << move.getTargetCoins()
                << " coins to heap " << move.getTarget();

        } else {
            out << "takes " << move.getSourceCoins() << " coins from heap "
                << move.getSource() << " and puts nothing";
        }
    }
};

class State {
    // State with h heaps, where the i-th heap starts with c[i] coins.
private:
    int heaps, *heap_coins;

public:
    State(int h, const int c[]) {
        heaps = h;
        heap_coins = new int[heaps];
        for (int i = 0; i < heaps; i++)
            heap_coins[i] = c[i];
    }

    ~State() {
        delete[] heap_coins;
        return;
    }

    int getCoins(int h) const throw(logic_error) {
        if (h < 0 || h > heaps) {
            throw logic_error(
                "Invalid heap number, enter a number between 1 and heaps!");
            return 1;
        } else {
            return heap_coins[h];
        }
    }
    void next(const Move &move) throw(logic_error) {
        if ((move.getSource() < 0) || (move.getSource() > heaps) ||
            (move.getTarget() < 0) || (move.getTarget() > heaps)) {
            throw logic_error("Invalid Heap!");
            return;
        } else if (
            (move.getSourceCoins() < 1) || (move.getTargetCoins() < 0) ||
            (move.getSourceCoins() <= move.getTargetCoins()) ||
            (move.getSourceCoins() > getCoins(move.getSource()))) {
            throw logic_error("Invalid Coin number!");
        } else {
            heap_coins[move.getSource()] -= move.getSourceCoins();
            heap_coins[move.getTarget()] += move.getTargetCoins();
        }
    }

    bool winning() const {
        int s = 0;
        for (int i = 0; i < heaps; i++)
            s += getCoins(i);
        return not s; // yeah i know how booleans work :P
    }

    int getHeaps() const {
        return heaps;
    }

    friend ostream &operator<<(ostream &out, const State &state) {
        for (int i = 0; i < state.getHeaps(); i++) {
            out << state.heap_coins[i];
            if (i != state.getHeaps() - 1)
                out << ", ";
        }
        return out;
    }
};

class Player {
public:
    Player(const string &n);
    virtual ~Player();

    virtual const string &getType() const = 0;
    virtual Move play(const State &s) = 0;

    friend ostream &operator<<(ostream &out, const Player &player);

protected:
    string player_name;
};

class GreedyPlayer : public Player {
private:
    string player_type;

public:
    GreedyPlayer(const string &n) : Player(n) {
        player_type = "Greedy";
    }
    virtual const string &getType() const override {
        return player_type;
    }
    virtual Move play(const State &s) override {
        int source_heap = 0;
        int source_coins = 0;
        for (int i = 0; i < s.getHeaps(); i++) {
            if (s.getCoins(i) > source_coins) {
                source_heap = i;
                source_coins = s.getCoins(i);
            }
        }
        Move GreedyObject(source_heap, source_coins, 0, 0);
        return GreedyObject;
    }
};

class SpartanPlayer : public Player {
public:
    SpartanPlayer(const string &n) : Player(n) {
        player_type = "Spartan";
    }
    virtual const string &getType() const override {
        return player_type;
    }

    virtual Move play(const State &s) override {
        int source_heap = 0;
        int source_coins = 0;
        for (int i = 0; i < s.getHeaps(); i++) {
            if (s.getCoins(i) > source_coins) {
                source_heap = i;
                source_coins = s.getCoins(i);
            }
        }
        Move SpartanObject(source_heap, 1, 0, 0);
        return SpartanObject;
    }

private:
    string player_type;
};

class SneakyPlayer : public Player {
public:
    SneakyPlayer(const string &n) : Player(n) {
        player_type = "Sneaky";
    }
    virtual const string &getType() const override {
        return player_type;
    }

    virtual Move play(const State &s) override {
        int j = 0;
        while (s.getCoins(j) == 0) {
            j++;
        }
        int source_heap = j;
        int source_coins = s.getCoins(j);
        for (int i = j + 1; i < s.getHeaps(); i++) {
            if ((s.getCoins(i) < source_coins) && (s.getCoins(i) > 0)) {
                source_heap = i;
                source_coins = s.getCoins(i);
            }
        }
        Move SneakyObject(source_heap, source_coins, 0, 0);
        return SneakyObject;
    }

private:
    string player_type;
};

class RighteousPlayer : public Player {
public:
    RighteousPlayer(const string &n) : Player(n) {
        player_type = "Righteous";
    }
    virtual const string &getType() const override {
        return player_type;
    }

    virtual Move play(const State &s) override {
        int target_heap = 0;
        int source_heap = 0;
        int source_coins = s.getCoins(0);
        int target_coins = source_coins;

        for (int i = 1; i < s.getHeaps(); i++) {
            if (s.getCoins(i) > source_coins) {
                source_heap = i;
                source_coins = s.getCoins(i);
            } else if (s.getCoins(i) < target_coins) {
                target_heap = i;
                target_coins = s.getCoins(i);
            }
        }
        source_coins -= source_coins / 2;
        Move RighteousObject(
            source_heap, source_coins, target_heap, source_coins - 1);
        return RighteousObject;
    }

private:
    string player_type;
};

Player::Player(const string &n) {
    player_name = n;
}

Player::~Player() {
    player_name.clear();
}

ostream &operator<<(ostream &out, const Player &player) {
    out << player.getType() << " player " << player.player_name;
    return out;
}

class Game {
private:
    int game_heaps, game_players, current_heap, current_player;
    int *heap_coins;
    Player **players_list;

public:
    Game(int heaps, int players) {
        heap_coins= new int [heaps];
        game_heaps = heaps;
        game_players = players;
        current_heap = 0;
        current_player = 0;
        players_list = new Player*[players];
    }
    ~Game() {
        delete[] heap_coins;
        delete[] players_list;
    }
    void addHeap(int coins) throw(logic_error) {
        if (current_heap > game_heaps)
            throw logic_error("All heaps are full with coins!");
        else if (coins < 0)
            throw logic_error("Coins must be a positive number!"); 
        else {
                heap_coins[current_heap++] = coins;
            }
    }
    void addPlayer(Player *player) throw(logic_error) {
        if (current_player > game_players)
            throw logic_error("All players are added!");
        else {
            players_list[current_player++] = player;
        }
    }
    void play(ostream &out) throw(logic_error) {
        if ((current_player != game_players) && (current_heap != game_heaps)) {
            throw logic_error("Have you added all heaps and players?");
        } else {
            int i = 0;
            State currentState(game_heaps, heap_coins);
            while (!currentState.winning()) {
                out << "State: " << currentState << endl;
                out << *players_list[i % game_players] << " "
                    << players_list[i % game_players]->play(currentState) << endl;
                currentState.next(
                    players_list[i % game_players]->play(currentState));

                i++;
            }
            out << "State: " << currentState << endl;
            i--;
            out << *players_list[i % game_players] << " wins" << endl;
        }
    }
};


int main() {
 Game specker(3, 4);
 specker.addHeap(10);
 specker.addHeap(20);
 specker.addHeap(17);
 specker.addPlayer(new SneakyPlayer("Tom"));
 specker.addPlayer(new SpartanPlayer("Mary"));
 specker.addPlayer(new GreedyPlayer("Alan"));
 specker.addPlayer(new RighteousPlayer("Robin"));
 specker.play(cout);

}


Комментарии
3 ответа

Несколько вещей, которые могут быть улучшены.


  • По данным БГД линии << players_list[i % game_players]->play(currentState) << endl; вызывает ошибку сегментации.

  • Если вы компилируете с более предупреждений, таких как -Weffc++ -pedantic вы получите много подсказок о том, что можно улучшить.
    Вы всегда должны дать как можно больше предупреждений и исправить их все. Некоторые люди даже рассматривать предупреждения как ошибки, чтобы осуществить это.

  • Не использовать using namespace std

  • Избежать декларирования более чем одной переменной в строке. Не нужно быть скупым с вашими вертикальное пространство.
    Также в C++ * и & обычно рассматривается как часть тип поэтому следует отдавать предпочтение int* foo за int *foo.

  • Предпочитаю умные указатели на сырые указатели. Ручное управление памятью-это трудно сделать даже для профессионалов. Как из C++11 и выше, вы должны почти никогда не есть причина, чтобы использовать new.

  • Если вы хотите очистить выходной буфер предпочитают \n за endl. Если вы хотите, чтобы смыть его предпочитают использовать flush() чтобы сделать ваши намерения ясны.

  • Некоторые из ваших имен переменных могут быть улучшены. Старайтесь всегда использовать имена, которые описывают, что переменная используется для.

  • Ваши комментарии не очень что-то добавить в код, как сейчас, так что вы могли бы также бросить их.

8
ответ дан 14 марта 2018 в 12:03 Источник Поделиться


У вас есть какие-либо идеи о том, как создать более умного игрока AI, который будет на самом деле стараться победить в каждой игре?

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

Что бы реализация выглядит?

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

Вам также понадобится функция, чтобы оценить состояние.

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

Задача состоит в то, чтобы оптимизировать исследования (см., например, Альфа-Бета обрезка), и, чтобы избежать эффекта горизонта.

6
ответ дан 14 марта 2018 в 10:03 Источник Поделиться

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

Я думаю, вы могли бы найти достаточную документацию здесь.

-2
ответ дан 14 марта 2018 в 03:03 Источник Поделиться