Create a clever Specker game player

[asder]

I am creating a game called Specker in c++.
The rules are simple:

> 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

.

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

[jonnin]

I think when its 'your' turn (AI turn, that is) the AI needs to determine some things..
1) can it win now?
2) if it can't win, can it force a win next turn, by leaving 1 coin in each heap such that next turn it takes the last one?
3) if it can't win or force in 1 turn, what move can it make that does not lose (applying 1 and 2 rules to all other players to look for things to avoid) and drives the remaining piles towards #1 and #2?

#1 is easy.
#2 is easy.
#3 is fairly hard, and depends on how much depth (number of turns ahead) you want to study etc. There may be a clever way to do #3 simply and it may be that more than 2 turns ahead is not useful to study due to # of possible moves (if each pile had 100 coins for 10 piles, the number of possible next moves is staggering). Figuring out an approach will take some effort.

[asder]

Yes but 9ne issue is that my ai cannot onow how many players play and which turns it plays

[jonnin]

in a given game session, you don't know how many players you have and the order of turns?
That makes it intractable. What information DO you have? Without more information, all you can do is
1) can I win?
and
2) how can I not lose (which is almost always going to be removal of 1 or 2 coins from one of the piles with some algorithm to pick which and how many). If you knew more, you would know when to empty a pile and when not to... but I don't see that without information.

you can randomize the predictable algorithms to make them less predictable, and also less skilled. One way to do this is for every turn, pick the top 3 possible best moves and randomly select one, but this will result is less good play than picking the strictly best move each time. And, at a guess, in this game being predictable means losing.

[asder]

Ok so i contacted the prof. and he agreed to give the players count

[jonnin]

Sounds better. With the # of players and presumably the # of piles and # of coins in each pile, you can do the checks I suggested... 'can i win' 'can i force a win next round' and 'how can I not lose'.

the not-lose choices are very high in the early and mid game, so that is where you should randomize it a bit to mix it up.