8
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ I’m not sure this question fits the mould of “code review” very well: it’s asking about an algorithm. That said, it’s a very well-asked question and the code does benefit from review (it’s generally good but not beyond improvement). \$\endgroup\$ – Konrad Rudolph Mar 14 '18 at 10:32
  • \$\begingroup\$ @KonradRudolph Thanks for your answer . I was looking for more for suggestions than algorithms , but algorithm inspirations are kindly accepted :P \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 10:37
  • \$\begingroup\$ You might be right i might betterpost my question to StackOverflow \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 11:42
  • \$\begingroup\$ I should also point out that i can know how many players play in a game either my turn count. \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 12:50
  • \$\begingroup\$ Ok so ask the prof. and it agreed to include player count \$\endgroup\$ – Stavros Avramidis Mar 17 '18 at 6:39
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your points. Any thoughts on how i will make a "good" player?? \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 12:51
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. I thought about minmax but I think it will be vary process hungry even if the players are very few \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 10:58
  • \$\begingroup\$ i just thought minmax is not possible because i cannot know the number of players \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 12:59
-2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. \$\endgroup\$ – Dannnno Mar 14 '18 at 16:59
  • \$\begingroup\$ It cannot be be done cause my class don't know how much players are in the game neither in which turn it plays. \$\endgroup\$ – Stavros Avramidis Mar 14 '18 at 17:34
  • \$\begingroup\$ @Dannnno I just provided some different approach to the problem. I do not thing that including the analysis of the algorithm would help. Instead I did provide a reference where sufficient documentation and even actual code exists. \$\endgroup\$ – Emmanouil Karamalegos Mar 15 '18 at 7:45
  • \$\begingroup\$ @StavrosAvramidis There is no need to priory knowledge of the players. In each turn the algorithm just needs to know how many players are currently playing to make the proper simulations. \$\endgroup\$ – Emmanouil Karamalegos Mar 15 '18 at 7:48
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Dannnno Mar 15 '18 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.