penguin.cpp

#include "penguin.hpp"
#include <sstream>
#include <random>
#include <algorithm>
using namespace std;

namespace game
{
	/**
	 * Creates the game: load the state from standard input.
	 * Penguins in state can be composed of just their position: the moves will be updated automatically.
	**/
	penguin::penguin()
	{
		cout << "Enter penguin game state as JSON on one line" << endl;
		string line;
		getline(cin, line);
		json json_state = json::parse(line);
		//Charging every element of the state if it exists
		if(json_state.count("bitboards"))
		{
			if(json_state["bitboards"].count("onefish")) {state.one_fish = json_state["bitboards"]["onefish"];}
			if(json_state["bitboards"].count("twofish")) {state.two_fish = json_state["bitboards"]["twofish"];}
			if(json_state["bitboards"].count("threefish")) {state.three_fish = json_state["bitboards"]["threefish"];}
		}
		if(json_state.count("current_player"))
			state.current_player_red = json_state["current_player"] == "Red" ? true : false;
		if(json_state.count("penguins"))
		{
			if(json_state["penguins"].count("red"))
			{
				for(int i = 0; i < 4; i++)
					state.peng_red[i] = json_state["penguins"]["red"][i];
			}
			if(json_state["penguins"].count("blue"))
			{
				for(int i = 0; i < 4; i++)
					state.peng_blue[i] = json_state["penguins"]["blue"][i];
			}
		}
		if(json_state.count("score"))
		{
			if(json_state["score"].count("red")) { state.score_red = json_state["score"]["red"]; }
			if(json_state["score"].count("blue")) { state.score_blue = json_state["score"]["blue"]; }
		}
		// We compute the moves for all penguin
		uint64_t obstacles = create_obstacles_bitboard();
		state.nb_moves_red = 0;
		state.nb_moves_blue = 0;

		for(int i = 0; i < 4; i++)
		{
			state.nb_moves_red += update_penguin_moves(&state.peng_red[i], obstacles);
			state.nb_moves_blue += update_penguin_moves(&state.peng_blue[i], obstacles);
		}
		if (state.nb_moves_red == 0)
		{
			state.canPlay_red = false;
			state.nb_moves_red = 1; //We create an artificial move so that the mcts works
		}
		if (state.nb_moves_blue == 0)
		{
			state.canPlay_blue = false;
			state.nb_moves_blue = 1; //We create an artificial move so that the mcts works
		}

		//std::cout << penguin_board(BLUE) << std::endl;

		//std::cout << penguin_board(RED) << std::endl;
	}
	penguin::penguin(bool b)
	{
		if(b)
		{
			set_state(penguin::random_start_state());
		}
	}

	shared_ptr<game<penguin_state>> penguin::do_copy() const
	{
		return shared_ptr<penguin>(new penguin(*this));
	}

	penguin_state penguin::get_state()
	{
		return state;
	}

	void penguin::set_state(const penguin_state& s)
	{
		state = s;
	}

	bool penguin::end_of_game() const
	{
		return state.canPlay_red == false && state.canPlay_blue == false;
	}

	bool penguin::won(std::uint8_t player) const
	{
		if (player == RED) return state.score_red > state.score_blue;
		return state.score_blue > state.score_red;
	}

	bool penguin::lost(std::uint8_t player) const
	{
		if(player == RED) return state.score_red < state.score_blue;
		return state.score_blue < state.score_red;
	}

	bool penguin::draw(std::uint8_t player) const
	{
		return state.score_blue == state.score_red;
	}

	uint8_t penguin::current_player() const
	{
		return state.current_player_red ? RED : BLUE;
	}

	int penguin::value(uint8_t player) const
	{
		if (won(player))
			return 1;
		else if (lost(player))
			return -1;
		else
			return 0;
	}

	/* Number of moves that you can play */
	uint16_t penguin::number_of_moves() const
	{
		return state.current_player_red ? state.nb_moves_red : state.nb_moves_blue;
	}

	/*
		Moves the penguin p (modify its position value), making it do its rel_move move.
		At the end of the function the penguin will be composed of just its new position (every other bit is at 0)
	*/
	void penguin::move_penguin(uint32_t* p, uint16_t rel_move)
	{
		//Direction A
		if(PENGUIN_MOVES_A(*p) > rel_move) //If the penguin total moves in this direction are greater than the move we want to do for it (not equal because moves start at 0)
		{
			//Move direction A
			(*p) = (7 * (rel_move +1)) + ((*p) & 63);
			return;
		}
		rel_move -= PENGUIN_MOVES_A(*p);
		if(PENGUIN_MOVES_B(*p) > rel_move)
		{
			//Move direction B
			(*p) = (-1 * (rel_move +1)) + ((*p) & 63);
			return;
		}
		rel_move -= PENGUIN_MOVES_B(*p);
		if(PENGUIN_MOVES_C(*p) > rel_move)
		{
			//Move direction C
			(*p) = (-8 * (rel_move +1)) + ((*p) & 63);
			return;
		}
		rel_move -= PENGUIN_MOVES_C(*p);
		if(PENGUIN_MOVES_D(*p) > rel_move)
		{
			//Move direction D
			(*p) = (-7 * (rel_move +1)) + ((*p) & 63);
			return;
		}
		rel_move -= PENGUIN_MOVES_D(*p);
		if(PENGUIN_MOVES_E(*p) > rel_move)
		{
			//Move direction E
			(*p) = (1 * (rel_move +1)) + ((*p) & 63);
			return;
		}
		rel_move -= PENGUIN_MOVES_E(*p);
		//Move direction F
		(*p) = (8 * (rel_move +1)) + ((*p) & 63);
	}

	/* Create bitboard of obstacles: 1 if there is an obstacle, 0 if the penguin can
		move freely on the tile
	*/
	uint64_t penguin::create_obstacles_bitboard()
	{
		uint64_t obstacles = (~(state.one_fish | state.two_fish | state.three_fish));
		for(int i = 0; i < 4; i++)
		{
			obstacles |= ((uint64_t) 1) << PENGUIN_POS(state.peng_red[i]);
			obstacles |= ((uint64_t) 1) << PENGUIN_POS(state.peng_blue[i]);
		}
		return obstacles;
	}

	/* Updates the moves of a signle penguin.
		This computes the moves in every direction according to the penguin position and the obstacles.
		Parameters:
			- p: a penguin that will be updated. Only his position is used and the rest is computed
			- obstacles: a bitboard of obstacles: 1 means an obstacle in that tile
		Returns:
			Total moves of this penguin.
	*/
	int penguin::update_penguin_moves(uint32_t* p, uint64_t obstacles)
	{
		#define IsFree(i) (((obstacles >> (i)) & 1) == 0)
		int pos = PENGUIN_POS(*p);
		(*p) = pos; //Reset the penguin to all zeros except the position
		int i = pos;
		uint32_t nbmoves = 0; //Nb of moves in one direction
		uint32_t total_moves = 0;

		//Direction A
		while(((i+7) < 60) && (i%15 != 0) && IsFree(i+7))
		{
			i += 7;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 12;
		//Direction B
		nbmoves = 0;
		i = pos;
		while((i%15 != 0) && (i%15 != 8) && IsFree(i-1))
		{
			i --;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 15;
		//Direction C
		nbmoves = 0;
		i = pos;
		while((i-8 >= 0) && (i%15 != 0) && IsFree(i-8))
		{
			i -= 8;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 18;
		//Direction D
		nbmoves = 0;
		i = pos;
		while((i-7 > 0) && (i%15 != 7) && IsFree(i-7))
		{
			i -= 7;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 21;
		//Direction E
		nbmoves = 0;
		i = pos;
		while((i%15 != 7) && (i%15 != 14) && IsFree(i+1))
		{
			i ++;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 24;
		//Direction F
		nbmoves = 0;
		i = pos;
		while((i+8 < 60) && (i%15 != 7) && IsFree(i+8))
		{
			i += 8;
			nbmoves++; total_moves++;
		}
		(*p) = (*p) | nbmoves << 27;

		(*p) = (*p) | total_moves << 6;
		return total_moves;
	}

	//Play the mth move in the possible moves list.
	void penguin::play(uint16_t m)
	{
		//CAN WE PLAY?
		// We check if we can effectively play: if yes, the move is parsed and player, otherwise we do nothing (the move can be whatever, we won't look at it, so the player actually skip the turn)
		if ((state.current_player_red == true && state.canPlay_red) || ((state.current_player_red == false) && state.canPlay_blue))
		{
			//WHICH PENGUIN WILL MOVE?
			uint32_t* peng; // The penguin that will move
			uint16_t rel_move = m; // Move number relative to this penguin
			int i = 0;
			if(state.current_player_red)
			{
				/* We search for the first penguin that can make the move. If a penguin can't, we will decrese the move number
				by the number of moves that he can do */
				for(i = 0; (i < 3) && (PENGUIN_TOT_MOVES(state.peng_red[i]) <= rel_move); i ++) //While we didn't find the penguin
					rel_move -= PENGUIN_TOT_MOVES(state.peng_red[i]);
				// Now i is the number of the penguin that will move and rel_move is the move relative to this penguin (because we decreased it)
				peng = &state.peng_red[i];
			}
			else //If blue
			{
				for(i = 0; (i < 3) && (PENGUIN_TOT_MOVES(state.peng_blue[i]) <= rel_move); i ++) //While we didn't find the penguin
					rel_move -= PENGUIN_TOT_MOVES(state.peng_blue[i]);
				peng = &state.peng_blue[i];
			}

			// ADD PENGUIN TILE TO THE SCORE
			if((state.one_fish >> PENGUIN_POS(*peng)) & 1) //If there is a one fish on this position
			{
				if(state.current_player_red)
					state.score_red += 1;
				else
					state.score_blue += 1;
				//We replace this tile with an empty one (0 in the bitboard)
				state.one_fish = state.one_fish & ~(((uint64_t) 1) << PENGUIN_POS(*peng));
			}
			else if((state.two_fish >> PENGUIN_POS(*peng)) & 1)
			{
				if(state.current_player_red)
					state.score_red += 2;
				else
					state.score_blue += 2;
				//We replace this tile with an empty one (0 in the bitboard)
				state.two_fish = state.two_fish & ~(((uint64_t) 1) << PENGUIN_POS(*peng));
			}
			else
			{
				if(state.current_player_red)
					state.score_red += 3;
				else
					state.score_blue += 3;
				//We replace this tile with an empty one (0 in the bitboard)
				state.three_fish = state.three_fish & ~(((uint64_t) 1) << PENGUIN_POS(*peng));
			}

			// MOVE THE PENGUIN
			move_penguin(peng, rel_move);
		}
		// END CAN_WE PLAY. We will now compute the moves for every penguin and for the player.
		uint64_t obstacles = create_obstacles_bitboard();

		state.nb_moves_red = 0;
		state.nb_moves_blue = 0;

		if (state.current_player_red) //Red just played
		{
			if(state.canPlay_blue) //If blue couldn't play last turn there is no way he could play this new turn
			{
				for(int i = 0; i < 4; i++)
					state.nb_moves_blue += update_penguin_moves(&state.peng_blue[i], obstacles);
				if (state.nb_moves_blue == 0)
				{
					state.canPlay_blue = false;
					state.nb_moves_blue = 1; //We create an artificial move so that the mcts works
				}
			}
			else
			{
				state.nb_moves_blue = 1; //We create an artificial move so that the mcts works
			}
			state.current_player_red = false;
		}
		else //Blue just played
		{
			if(state.canPlay_red)
			{
				for(int i = 0; i < 4; i++)
					state.nb_moves_red += update_penguin_moves(&state.peng_red[i], obstacles);
				if (state.nb_moves_red == 0)
				{
					state.canPlay_red = false;
					state.nb_moves_red = 1;
				}
			}
			else
			{
				state.nb_moves_red = 1;
			}
			state.current_player_red = true;
		}
	}
	const tile_content penguin::get_tile(std::uint8_t tile_index) const
	{
		for(int k = 0; k < 4; k++) {
			if(PENGUIN_POS(state.peng_blue[k]) == tile_index)
				return BLUE_PENGUIN;
			if(PENGUIN_POS(state.peng_red[k]) == tile_index)
				return RED_PENGUIN;
		}
		if(((state.one_fish >> (tile_index)) & 1) > 0) 
			return ONE_FISH;
		if(((state.two_fish >> (tile_index)) & 1) > 0) 
			return TWO_FISH;
		if(((state.three_fish >> tile_index) & 1) > 0) 
			return THREE_FISH;		
		return OBSTACLE;
		

	}

	string penguin::player_to_string(uint8_t player) const
	{
		return player == RED ? "Red" : "Blue";
	}


	string penguin::move_to_string(uint16_t m) const
	{
		return std::to_string(m);
	}

	set<int> penguin::to_input_vector() const
	{
		return set<int>();
	}

	void penguin::from_input_vector(const std::set<int>& input)
	{
	}

	json penguin::to_JSON() const
	{
		json json_state;
		json_state["bitboards"]["onefish"] = state.one_fish;
		json_state["bitboards"]["twofish"] = state.two_fish;
		json_state["bitboards"]["threefish"] = state.three_fish;

		for(int i = 0; i < 4; i++)
		{
			json_state["penguins"]["red"][i] = state.peng_red[i];
			json_state["penguins"]["blue"][i] = state.peng_blue[i];
		}

		json_state["score"]["red"] = state.score_red;
		json_state["score"]["blue"] = state.score_blue;

		json_state["possible_moves"]["red"] = state.nb_moves_red;
		json_state["possible_moves"]["blue"] = state.nb_moves_blue;

		json_state["current_player"] = state.current_player_red ? "Red" : "Blue";

		json_state["can_play"]["red"] = state.canPlay_red;
		json_state["can_play"]["blue"] = state.canPlay_blue;

		return json_state;
	}

	string penguin::to_string() const
	{
		ostringstream os;
		os << to_JSON() << endl;
		return os.str();
	}

	std::uint64_t penguin::hash() const
	{
		return 0;
	}

	std::uint64_t penguin::hash(std::uint16_t m) const
	{
		return 0;
	}

	ostream& operator<<(ostream& os, const penguin& pen)
	{
		os << pen.to_string();
		return os;
	}
	penguin_state penguin::random_start_state()
    {
		std::random_device rd;
        std::default_random_engine generator(rd());
        std::uniform_int_distribution<int> distribution(0,59);
        std::vector<int> free;
        free.resize(60);
        for(int i = 0; i < 60; i++)
        {
         free[i] = i;   
        }
        int max1Fish = 30, max2Fish = 20;
        penguin_state s = {};
        s.current_player_red = true;
        s.score_red = 0;
        s.score_blue = 0;
        s.one_fish = 0;
        s.two_fish = 0;
        s.three_fish = 0;
        for(int i = 0; i < 60; i++) 
        {
            distribution = std::uniform_int_distribution<int>(0,free.size() -1 );
            int rand = distribution(generator);
            int tile =free[rand];
            free.erase(std::remove(free.begin(),free.end(),tile),free.end());
            if(i < max1Fish) {
                s.one_fish |= (long) 1 << tile;
            } else if( i < max1Fish + max2Fish) {
                s.two_fish |= (long) 1 << tile;
            } else {
                s.three_fish |= (long) 1 << tile;
            }
            
        }
        uint32_t* tab_peng = s.peng_red;
        std::vector<int> pengPos;
        pengPos.reserve(8);
        
        distribution = std::uniform_int_distribution<int>(0,59);
        for(int i = 0; i < 8; i++)
        {
                if(i == 4) tab_peng = s.peng_blue;
                
                int pos = distribution(generator);
                while(std::find(pengPos.begin(),pengPos.end(),pos) != pengPos.end())
                {
                        pos = distribution(generator);
                }
                pengPos.push_back(pos);
                tab_peng[i%4] = pos;
        }
        
        return s;
        
    }

    uint64_t penguin::penguin_board(bool color) const
    {
    	//A penguin alone on the case 0 correspond to a bitboard which value is 1
    	uint64_t board = 0ULL;
        const uint32_t* tab = color ? state.peng_blue : state.peng_red;
    	
        for (int i = 0; i<4 ; i++){
            board |=  (uint64_t) 1 << (tab[i] & 63 );
        }
    	return board;
    }

    uint64_t penguin::penguin_move_board(const uint32_t& pen) const
    {
    	uint64_t board = 0;
    	//Direction A
    	for(uint i=1; i<= PENGUIN_MOVES_A(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*7));
    	}
    	//Direction B
    	for(uint i=1; i<= PENGUIN_MOVES_B(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*(-1)));
    	}
    	//Direction C
    	for(uint i=1; i<= PENGUIN_MOVES_C(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*(-8)));
    	}
    	//Direction D
    	for(uint i=1; i<= PENGUIN_MOVES_D(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*(-7)));
    	}
    	//Direction E
    	for(uint i=1; i<= PENGUIN_MOVES_E(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*1));
    	}
    	//Direction F
    	for(uint i=1; i<= PENGUIN_MOVES_A(pen); i++){
    		board |= ((uint64_t)1 << (PENGUIN_POS(pen) + i*8));
    	}
    	return board;
    }

    uint8_t penguin::turns_played() const
    {
        uint8_t played = 0;
        uint64_t obstacles = (~(state.one_fish | state.two_fish | state.three_fish));
        while(obstacles > 0) {
            if(obstacles % 2 == 1) ++played;
            obstacles /= 2;
        }
        return played;
        
    }

	uint32_t penguin::move_to_pos(uint16_t m)
	{
		uint32_t result = 0;
		uint32_t* peng;
		uint16_t rel_move = m;
		int i = 0;

		if(state.current_player_red) {
			for(i = 0; (i < 3) && (PENGUIN_TOT_MOVES(state.peng_red[i]) <= rel_move); i ++) //While we didn't find the penguin
				rel_move -= PENGUIN_TOT_MOVES(state.peng_red[i]);
			peng = &state.peng_red[i];
		}
		else {
			for(i = 0; (i < 3) && (PENGUIN_TOT_MOVES(state.peng_blue[i]) <= rel_move); i ++) //While we didn't find the penguin
				rel_move -= PENGUIN_TOT_MOVES(state.peng_blue[i]);
			peng = &state.peng_blue[i];
		}

		result = PENGUIN_POS(*peng) << 16;
		play(m);
		result |= PENGUIN_POS(*peng);

		return result;
	}
}