Алгоритм Minimax для игры Specker

Я создаю минимаксный плеер для игры Specker на C++.

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

There are p players (0 to p - 1) and n heaps (0 to n - 1)

Starting with player 0 each player takes k > 0 coins from a heap x and places m coins (0 <= m < k) on heap y

The winning player is the one which plays last when all coins from all heaps are removed

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

поэтому я создаю игрока, который играет в соответствии с минимаксным (pt18a038) кодом, компилируется нормально, но программа перестает отвечать на выполнение. класс умных игроков:

class pt18a038 : public Player {
private:
    string player_type;

public:
    pt18a038(const string &n) : Player(n) {
        player_type = "Asder aka theRunner";
    }

    virtual const string &getType() const override {
        return player_type;
    }

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

        for (source_heap = 0; source_heap < s.getHeaps(); source_heap++) {
            for (source_coins = 1; source_coins <= s.getCoins(source_heap); source_coins++) {
                for (target_heap = 0; target_heap < s.getHeaps(); target_heap++) {
                    for (target_coins = 0; target_coins <= source_coins; target_coins++) {
                        Move m(source_heap, source_coins, target_heap, target_coins);
                        sum = minimax(s, 3, 0, m);
                        cout << "Play:" << source_heap << "," << source_coins << "," << target_heap << ","
                             << target_coins << ":" << sum << endl;
                    }
                }
            }
        }
        cout << sum << endl;

        // ///////////// for debbuging only until minimax is working...
        source_heap = 0;
        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;
        // /////////////

    }

    static int minimax(State s, const int &players, int depth, const Move move) {


        if (s.winning()) {
            cout << "game end!" << endl;
            return 1000;
            if (depth % players == 0) return 1000; //Maximazing player
            else return -1000; //Minimazing player
        }
        if (depth > 4) {
            //cout<<"optimazing"<<endl;
            return 0;
        }
        //cout << s << endl;
        s.next(move);


        int source_heap = 0;
        int target_heap = 0;
        int source_coins = 0;
        int target_coins = 0;
        int max = -100000;
        int min = 100000;
        int result;

        for (source_heap = 0; source_heap < s.getHeaps(); source_heap++) {
            for (source_coins = 1; source_coins <= s.getCoins(source_heap); source_coins++) {
                for (target_heap = 0; target_heap < s.getHeaps(); target_heap++) {
                    for (target_coins = 0; target_coins <= source_coins; target_coins++) {
                        //cout << "Move:" << source_heap << "," << source_coins << "," << target_heap << ","<< target_coins << endl;
                        Move m(source_heap, source_coins, target_heap, target_coins);
                        result = minimax(s, players, depth + 1, m);
                        if (depth % players == 0) {
                            max = result ? (result > max) : result;
                        } else {
                            min = result ? (result < min) : result;
                        }

                    }
                }
            }
        }

        return max ? (depth % players == 0) : min;

    }

};

Вот мой код для остальной части игры (он протестирован и отлично работает)

#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(6, 5);
    specker.addHeap(10);
    specker.addHeap(20);
    specker.addHeap(17);
    specker.addHeap(17);
    specker.addHeap(17);
    specker.addHeap(17);

    specker.addPlayer(new GreedyPlayer("Alan"));
    specker.addPlayer(new SneakyPlayer("Tom"));
    specker.addPlayer(new SpartanPlayer("Mary"));
    specker.addPlayer(new RighteousPlayer("Robin"));

    specker.addPlayer(new pt18a038("Stavros"));
    specker.play(cout);

}

Обновлено