Create a clever Specker game player

Question

I am creating a game called Specker in c++.

The rules are simple:

There are \$p\$ players \$\left(0 \to p - 1\right)\$ and \$n\$ heaps \$\left(0 \to n - 1\right)\$.

Starting with player \$0\$ each player takes \$k > 0\$ coins from a heap \$x\$ and places \$m\$ coins \$\left(0 \le m < k\right)\$ on heap \$y\$.

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

So I have created the game and some player classes (GreedyPlayer, SpartanPlayer etc.) but they all are a little bit predictable on what they will do. They aren't clever.

Have you got any ideas on how to create a more clever AI player that will actually try to beat every game?

Here is my code:

#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);

}

Answer 1

Several things that can be improved.

• According to GDB the line << players_list[i % game_players]->play(currentState) << endl; causes a segmentation fault.

• If you compile with more warnings such as -Weffc++ -pedantic you will get lots of hints about things that can be improved.
  You should always enable as many warnings as possible and fix all of them. Some people even treat warnings as errors to enforce this.

• Don't use using namespace std

• Avoid declaring more than one variable per line. There is no need to be stingy with your vertical space.
  Also in C++ * and & are generally seen as part of the type so you should prefer int* foo over int *foo.

• Prefer smart pointers over raw pointers. Manual memory managment is hard to get right even for pros. As of C++11 and higher you should almost never have a reason to use new.

• Unless you want to flush the output buffer prefer \n over endl. If you do want to flush it prefer using flush() to make your intent clear.

• Some of your variable names can be improved. Try to always use names that describe what the variable is being used for.

• Your comments don't really add anything to the code as of now so you might as well drop them.

Answer 2

Have you got any ideas on how to create a more clever AI player that will actually try to beat every game?

That's a vast question, of which I'm not certain it belongs here. I won't offer an implementation, but the general idea of many game AI algorithm is what is called min-maxing: you know you'll pick the best move, and that your opponents will do the same. So you'll rely on this assumption to explore the outcome of the possible moves.

What would an implementation look like?

You'll need a function to build a game tree, where each node is a valid state of the game, and the children of each node are its possible outcomes.

You'll also need a function to evaluate a state.

Then you decide on an analysis depth: you'll decide on the merit of a move based on the state it will lead to x turns ahead, which you can guess by applying the min-max hypothesis.

The challenge is then to optimize exploration (see, for instance, alpha-beta pruning), and to avoid the horizon effect.

Answer 3

You could try to make an Agent who will use a more abstract method which does not use characteristic (evaluation) function. A method as such could be a Monte Carlo Tree Search. You only need to provide your agent all the available moves and through random sampling the agent will expand the tree and give a reward to each action set.

I think you could find sufficient documentation here.