public interface DeterminizationSampler{

	/**
	 * Samples one observable state from the current belief.
	 * @param factory the game factory that contains the current belief and the game configuration.
	 * @param the current game description to provide access to the state array
	 * @return a fully-observable game object
	 */
	public GameSample sampleObservableState(Game currentGame, GameFactory factory);
	
	/**
	 * Creates nSamples fully-observable games
	 * @param nSamples the number of samples
	 * @param belief current belief
	 * @param currentGame current game that contains the current state
	 * @param factory game factory to create new games
	 * @return
	 */
	public default GameSample[] sampleObservableStates(int nSamples, Game currentGame, GameFactory factory) {
		GameSample[] samples = new GameSample[nSamples];
		for(int i = 0; i < nSamples; i++) {
			samples[i] = sampleObservableState(currentGame, factory);
		}
		return samples;
	}

} public interface Game {

	/**
	 * @return a clone of the game state
	 */
	public int[] getState();

	public int getWinner();

	public boolean isTerminal();

	public int getCurrentPlayer();

	/**
	 * Updates the state description based on the chosen action
	 * 
	 * @param a
	 *            the chosen action
	 * @param sample
	 *            if this action was sampled according to an efficient game specific
	 *            method or not. A simple rule of thumb is if the options were
	 *            listed with sample true this should also be true and vice-versa.
	 */
	public void performAction(int[] a, boolean sample);

	/**
	 * @param sample
	 *            flag for deciding if should include all actions or just sample
	 *            from the legal ones. (e.g. usage: set to true if this is called
	 *            while performing rollouts)
	 * @return a list of all the legal actions given the current state
	 */
	public Options listPossiblities(boolean sample);

	/**
	 * @return a clone of the game
	 */
	public Game copy();

	/**
	 * Method for sampling the next action at random or based on the chances built
	 * into the game logic;
	 * 
	 * @return the next action description
	 */
	public int[] sampleNextAction();

	/**
	 * Method for sampling the next action at random or based on the chances built
	 * into the game logic;
	 * 
	 * @return the index of the next legal action
	 */
	public int sampleNextActionIndex();

	public TreeNode generateNode();

	/**
	 * Executes one random action.
	 * 
	 * @param belief
	 */
	public void gameTick();
} public class GameFactory {
	public static final int TICTACTOE = 0;
	public static final int CATAN = 1;
	
	private GameConfig gameConfig;
	private Belief belief;
	
	public GameFactory(GameConfig gameConfig, Belief belief) {
		this.gameConfig = gameConfig;
		this.belief = belief;
	}
	
	public Game getNewGame(){
		if(gameConfig.id == CATAN){
			if(belief != null) {
				if(!CatanWithBelief.board.init)
					 CatanWithBelief.initBoard();//we can safely create a new board here as this means that we don't need to use a specific board.
				return new CatanWithBelief(((CatanConfig) gameConfig), (CatanFactoredBelief) belief);
			}else {
				if(!Catan.board.init)
					 Catan.initBoard();
				return new Catan(((CatanConfig) gameConfig));
			}
		}else
			return new TicTacToe();
	} 
	
	public Game getGame(int[] state){
		if(gameConfig.id == CATAN){
			if(belief != null)
				return new CatanWithBelief(state, ((CatanConfig) gameConfig), (CatanFactoredBelief) belief);
			else
				return new Catan(state, ((CatanConfig) gameConfig));
		}else
			return new TicTacToe(state);
	} 

	public GameConfig getConfig(){
		return gameConfig;
	}
	
	public Belief getBelief() {
		return belief;
	}
	
	public DeterminizationSampler getDeterminizationSampler() {
		if(gameConfig.id == CATAN && belief != null)
			return new CatanDeterminizationSampler();
		return new NullDeterminizationSampler();
	}
	
	/**
	 * @return
	 */
	public static int nMaxPlayers(){
		return 4;
	}
	
	public GameFactory copy() {
		Belief clone = null;
		if(belief != null)
			 clone = belief.copy();
		GameFactory factory = new GameFactory(gameConfig.copy(), clone);
		return factory;
	}
	
} public interface SearchListener {
	
	public boolean hasFinished();
	
	public void waitForFinish();
	
	public void increment();
	
	public int getNSimulations();
} public class ExpansionPolicy {

	/**
	 * Expands a node and adds all the children to the tree data structure. It
	 * also selects the next one at random. If seeding is used it adds the newly
	 * expanded node to the seed trigger.
	 * 
	 * @param tree
	 * @param node
	 * @param trigger
	 * @param gameFactory
	 * @return
	 */
	public static Selection expand(Tree tree, TreeNode node, SeedTrigger trigger, GameFactory gameFactory, Game obsGame, int nRootActLeg) {
		Game game = gameFactory.getGame(node.getState());
		Options options = game.listPossiblities(false);//always list all options when expanding
		ArrayList<int[]> actions = options.getOptions();
		int[] act;
		Game gameClone;
		TreeNode child;
		ArrayList<Key> children = new ArrayList<Key>();
		ArrayList<Double> mask = new ArrayList<Double>(Collections.nCopies(actions.size(), 1.0));
		Options obsOptions = null;
		if(obsGame != null) {//POMCP and ISMCTS, list actions here so we can compute the mask for initialising parent visits
			obsOptions = obsGame.listPossiblities(false);
			mask = Utils.createActMask(obsOptions.getOptions(), actions);
		}
		for (int i = 0; i < actions.size(); i++) {
			gameClone = game.copy();
			act = actions.get(i);
			gameClone.performAction(act, false);
			child = gameClone.generateNode();
			children.add(child.getKey());
			tree.putNodeIfAbsent(child);
			if(mask.get(i) == 1.0)//update parent visits for ISMCTS
				tree.getNode(child.getKey()).incrementParentVisits();
		}
		if(nRootActLeg > 1 && options.getProbabilities() != null) {//smooth out action legality prob
			ArrayList<Double> probs = options.getProbabilities();
			for(int i =0; i < probs.size(); i++) {
				probs.set(i, Math.pow(probs.get(i), 1.0/nRootActLeg));
			}
		}
		((StandardNode) node).addChildren(children, options.getOptions(), options.getProbabilities());
		if(children.size() > 1)// there is nothing to seed if there is a single option.
			trigger.addNode(node, gameFactory.copy());
		int[] action;
		ThreadLocalRandom rnd = ThreadLocalRandom.current();
		//pick one action at random and execute it so we can update the results of one of the new nodes also.
		double actProb = 1.0;
		int idx = 0;
		if(obsGame != null) {//POMCP
			idx = rnd.nextInt(obsOptions.size());
			action = obsOptions.getOptions().get(idx);
			//get action idx from the whole set of options
			idx = options.indexOfAction(action);
			actProb = options.getProbabilities().get(idx);//we don't actually need this	
			obsGame.performAction(action, false);
		}else {
			idx = rnd.nextInt(options.size());
			action = options.getOptions().get(idx);
			ArrayList<Double> probs = options.getProbabilities();
			if(probs != null)//handling the MCTS version on observable games
				actProb = probs.get(idx);
		}
		game.performAction(action, false);
		return new Selection(false, tree.getNode(children.get(idx)), actProb);
	}
} public class SimulationPolicy {
	private static int maxDepth = 100000;
	/**
	 * Run the rollout policy to the end of the game
	 * @param state
	 * @return the game in the final state
	 */
	public static Game simulate(Game game){
		int depth = 0;
		while(!game.isTerminal()){
			depth++;
			game.gameTick();
			if(depth > maxDepth){
				System.err.println("WARNING: rollout reached max depth!!!");
				break;
			}
		}
		return game;
	}
} public class Tree {
	private ConcurrentHashMap<Key, TreeNode> nodes;
	private TreeNode root;
	private int maxTreeSize = 500000;
	
	public boolean maxSizeReached(){
		return nodes.size() > maxTreeSize;
	}
	
	public Tree(Game currentState, int maxSize) {
		maxTreeSize = maxSize;
		nodes = new ConcurrentHashMap<Key, TreeNode>(maxTreeSize);
		root = currentState.generateNode();
		nodes.put(root.getKey(), root);
	}
	
	public TreeNode getNode(Key k){
		return nodes.get(k);
	}
	
	public void putNodeIfAbsent(TreeNode node){
		nodes.putIfAbsent(node.getKey(),node);
	}
	
	public TreeNode getRoot(){
		return root;
	}
	
	public int getTreeSize(){
		return nodes.size();
	}
		
} public abstract class TreeNode {

	private final int[] state;
	private final int[] belief;
	
	int nVisits;
    double[] wins;
	int vLoss;
	private final int currentPlayer;
	private boolean leaf = true;
	private final boolean terminal;
	/**
	 * Field required for ISMCTS way of computing parentVisits when this node was legal
	 */
	private int parentVisits;
	
	/**
	 * Flag set when an external evaluation metric is used for seeding.
	 */
	private boolean evaluated = false;
	
	public TreeNode(int[] state, int[] belief, boolean terminal, int cpn) {
	    this.state = state;
	    this.belief = belief;
		this.terminal = terminal;
		currentPlayer = cpn;
		vLoss = 0;
		nVisits = 0;
		parentVisits = 0;
	    wins = new double[GameFactory.nMaxPlayers()]; //TODO: find a way to set this value depending on the current game
	}
	
	public int getCurrentPlayer(){
		return currentPlayer;
	}
	
	/**
	 * @return a clone of the state
	 */
	public int[] getState(){
		return state.clone();
	}
	
	public boolean isLeaf(){
		return leaf;
	}
	
	public void setLeaf(boolean leaf){
		this.leaf = leaf;
	}

	public boolean isTerminal(){
		return terminal;
	}
	
	public Key getKey(){
		return new Key(state, belief);
	}
	
	/**
	 * Update this node and remove the virtual loss.
	 * 
	 * TODO: it remains to be seen if synchronising makes this too slow...
	 * initial tests indicate this is a negligible increase, while it is
	 * beneficial to synchronise the updates so that no results are lost
	 */
	public synchronized void update(double[] reward, int nRollouts) {
		for(int i = 0; i < wins.length; i++)	
			wins[i]+=reward[i];
		nVisits+=nRollouts;
		vLoss = 0;
	}
	
	public int getParentVisits() {
		return parentVisits;
	}
	
	public void incrementParentVisits() {
		parentVisits++;
	}
	
	public double getWins(int pn) {
		return wins[pn];
	}
	
	public int getnVisits() {
		return nVisits;
	}
	
	public int getvLoss() {
		return vLoss;
	}
	
	public void setEvaluated(boolean evaluated){
		this.evaluated = evaluated;
	}
	
	public boolean isEvaluated(){
		return evaluated;
	}
	
	public void incrementVLoss(){
		this.vLoss++;
	}
	
	/**
	 * Can this node be expanded?
	 * 
	 * @return
	 */
	public abstract boolean canExpand();
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof TreeNode){
			return Arrays.equals(state, ((TreeNode) obj).state);
		}
		return false;
	}
	
	@Override
	public int hashCode() {
		return Arrays.hashCode(state);
	}
	
} public class GameSample {
	private Game game;
	private double prob;
	
	public GameSample(Game g, double p) {
		game = g;
		prob = p;
	}
	
	public Game getGame() {
		return game;
	}
	
	public double getProb() {
		return prob;
	}
} public enum Priority {
	  HIGHEST(0),
	  HIGH(1),
	  MEDIUM(2),
	  LOW(3),
	  LOWEST(4);

	  int value;

	  Priority(int val) {
	    this.value = val;
	  }

	  public int getValue(){
	    return value;
	  }
} public interface PriorityRunnable {
	
	int getPriority();
	
} public class Selection {

	private boolean b = false;
	private TreeNode node;
	private double actProb;

	public Selection(boolean b, TreeNode node, double prob) {
		this.b = b;
		this.node = node;
		this.actProb = prob;
	}

	public boolean getBoolean() {
		return b;
	}

	public TreeNode getNode() {
		return node;
	}
	
	public double getActProb() {
		return actProb;
	}
}
import java.util.ArrayList;
import mcts.game.DeterminizationSampler;
import mcts.game.Game;
import mcts.game.GameFactory;
import mcts.listeners.SearchListener;
import mcts.tree.ExpansionPolicy;
import mcts.tree.SimulationPolicy;
import mcts.tree.Tree;
import mcts.tree.node.TreeNode;
import mcts.utils.GameSample;
import mcts.utils.Priority;
import mcts.utils.PriorityRunnable;
import mcts.utils.Selection;
package mcts;


public class POMCPAgent implements Runnable,PriorityRunnable{
	private Tree tree;
	private SearchListener listener;
	private MCTSConfig config;
	private GameFactory gameFactory;
	private static Priority priority = Priority.LOW;
	
	public POMCPAgent(Tree tree, SearchListener listener, MCTSConfig config,  GameFactory gameFactory) {
		this.tree = tree;
		this.listener = listener;
		this.gameFactory = gameFactory;
		this.config = config;
	}
	@Override
	public void run() {
		try {
			GameFactory factory = gameFactory.copy();
			ArrayList<Selection> visited = new ArrayList<Selection>();
			TreeNode node = tree.getRoot();
			Selection selection = new Selection(false, node, 1.0);
			visited.add(selection); 
			
			/*
			 * Sample one state that is followed through the algorithm to provide observations for POMCP
			 * NOTE: that the sampler may return null if there is no belief and pomcp flag doesn't make a difference.
			 */
			Game obsGame = null;