path: root/src/jrummikub/ai/TurnLogic.java

package jrummikub.ai;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

import jrummikub.model.GameSettings;
import jrummikub.model.Stone;
import jrummikub.model.StoneColor;
import jrummikub.model.StoneSet;
import jrummikub.util.Pair;

/**
 * Logic behind the ai turns
 */
public class TurnLogic {
	private GameSettings settings;
	private int stoneCount;
	private List<Stone> inputStones;
	private StoneColor maxColor;
	private StoneColor minColor;
	private ArrayList<StoneColor> stoneColors;
	private volatile State bestState;

	private ArrayList<State> stack = new ArrayList<State>();
	private State top;

	private volatile boolean abort = false;
	private volatile boolean autoAbort = false;

	private int neededPoints = 0;
	private double neededScore = 0;

	@SuppressWarnings("serial")
	private static class Contradiction extends Throwable {

	}

	private class State {
		ArrayList<StoneState> stones = new ArrayList<StoneState>();
		HashSet<Integer> changedStones = new HashSet<Integer>();
		ArrayList<Integer> jokerIDs = new ArrayList<Integer>();

		public State() {
		}

		public State(State state) {
			for (StoneState stone : state.stones) {
				stones.add(new StoneState(stone));
			}
			jokerIDs = state.jokerIDs;
		}

		public void add(StoneState stone) {
			stones.add(stone);
			changedStones.add(stones.size() - 1);
			if (stone.joker) {
				jokerIDs.add(stone.id);
			}
		}

		public void updateStones() throws Contradiction {
			checkJokers();
			for (int i : changedStones) {
				stones.get(i).checkState();
			}
			checkScoreAndPoints();
			while (!changedStones.isEmpty()) {
				updateStonesStep();
				checkScoreAndPoints();
			}
		}

		public void updateStonesStep() throws Contradiction {
			HashSet<Integer> newChangedStones = new HashSet<Integer>();
			for (int i = 0; i < stoneCount; i++) {
				StoneState stone = stones.get(i);
				if (stone.isInterested(changedStones)) {
					if (stone.update(changedStones)) {
						newChangedStones.add(i);
					}
				}
			}
			changedStones = newChangedStones;
		}

		public boolean isSolved() {
			for (StoneState stone : stones) {
				if (!stone.isSolved()) {
					return false;
				}
			}
			return true;
		}

		public void checkJokers() throws Contradiction {
			for (int i = 0; i < jokerIDs.size(); i++) {
				StoneState left = stones.get(jokerIDs.get(i));

				HashSet<Integer> leftLeftGroup = new HashSet<Integer>(left.leftGroup);
				HashSet<Integer> leftLeftRun = new HashSet<Integer>(left.leftRun);
				leftLeftGroup.remove(null);
				leftLeftRun.remove(null);
				int runID, groupID;
				if (leftLeftGroup.isEmpty()) {
					groupID = -1;
				} else {
					groupID = Collections.min(leftLeftGroup);
				}
				if (leftLeftRun.isEmpty()) {
					runID = -1;
				} else {
					runID = Collections.min(leftLeftRun);
				}
				for (int j = i + 1; j < jokerIDs.size(); j++) {
					StoneState right = stones.get(jokerIDs.get(j));

					if (right.leftGroup.remove(groupID)) {
						changedStones.add(jokerIDs.get(j));
					}
					if (right.leftRun.remove(runID)) {
						changedStones.add(jokerIDs.get(j));
					}
				}
			}
		}

		public void checkScoreAndPoints() throws Contradiction {
			if (getPoints() < neededPoints) {
				throw new Contradiction();
			}
			if (getScore() <= neededScore) {
				throw new Contradiction();
			}
		}

		public int getPoints() {
			int sum = 0;
			for (StoneState stone : stones) {
				if (stone.onTable != Boolean.FALSE) {
					sum += stone.getPoints();
				}
			}
			return sum;
		}

		public double getScore() {
			double sum = 0;
			for (StoneState stone : stones) {
				if (stone.onTable != Boolean.FALSE) {
					sum += stone.getScore();
				}

			}
			return sum;
		}
	}

	private class StoneState {
		int id;
		boolean joker;
		Integer value;
		StoneColor color;
		Boolean onTable;
		boolean fromTable;
		HashSet<Integer> leftRun;
		HashSet<Integer> rightRun;
		HashSet<Integer> leftGroup;
		HashSet<Integer> rightGroup;

		public StoneState(int id, Stone stone, boolean table) {
			this.id = id;
			joker = stone.isJoker();
			if (!joker) {
				this.value = stone.getValue();
				this.color = stone.getColor();
			}
			onTable = table ? true : null;
			fromTable = table;
			leftRun = makeFullSet();
			rightRun = makeFullSet();
			leftGroup = makeFullSet();
			rightGroup = makeFullSet();
		}

		public StoneState(StoneState stone) {
			this.id = stone.id;
			this.joker = stone.joker;
			this.value = stone.value;
			this.color = stone.color;
			this.onTable = stone.onTable;
			this.fromTable = stone.fromTable;
			this.leftRun = new HashSet<Integer>(stone.leftRun);
			this.rightRun = new HashSet<Integer>(stone.rightRun);
			this.leftGroup = new HashSet<Integer>(stone.leftGroup);
			this.rightGroup = new HashSet<Integer>(stone.rightGroup);
		}

		private HashSet<Integer> makeFullSet() {
			HashSet<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < stoneCount; i++) {
				if (i != id) {
					set.add(i);
				}
			}
			set.add(null);
			return set;
		}

		public boolean isInterested(HashSet<Integer> changes) {
			return !(Collections.disjoint(changes, leftRun)
					&& Collections.disjoint(changes, rightRun)
					&& Collections.disjoint(changes, leftGroup) && Collections.disjoint(
					changes, rightGroup));
		}

		public <T extends Comparable<T>> boolean lessThan(T a, T b) {
			return a == null || b == null || a.compareTo(b) < 0;
		}

		public <T> boolean same(T a, T b) {
			return a == null || b == null || a.equals(b);
		}

		public boolean step(Integer a, Integer b) {
			return a == null || b == null || (int) a == b - 1;
		}

		public boolean cycleStep(Integer a, Integer b) {
			return a == null || b == null || (int) a == b - 1
					|| a == settings.getHighestValue() && b == 1;
		}

		public boolean groupNeighbor(StoneState other) {
			if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) {
				return false;
			}
			if (other.color == minColor || color == maxColor) {
				return false;
			}
			return lessThan(color, other.color) && same(value, other.value);
		}

		public boolean runNeighbor(StoneState other) {
			if (isNullSet(leftRun) && isNullSet(other.rightRun)) {
				return false;
			}
			if (!same(color, other.color)) {
				return false;
			}
			if (settings.isNoLimits()) {
				return cycleStep(value, other.value);
			} else {
				if (((Integer) 1).equals(other.value)
						|| ((Integer) settings.getHighestValue()).equals(value)) {
					return false;
				}
				return step(value, other.value);
			}
		}

		public boolean update(HashSet<Integer> changes) throws Contradiction {
			boolean changed = false;
			changed |= updateRightRuns(changes);
			changed |= updateLeftRuns(changes);
			changed |= updateRightGroups(changes);
			changed |= updateLeftGroups(changes);
			changed |= checkState();
			return changed;
		}

		public boolean updateRightRuns(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftRun);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!other.runNeighbor(this) || !other.rightRun.contains(id)) {
					leftRun.remove(i);
					changed = true;
				} else if (other.rightRun.size() == 1 && other.onTable == Boolean.TRUE) {
					changed |= leftRun.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		public boolean updateLeftRuns(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(rightRun);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!this.runNeighbor(other) || !other.leftRun.contains(id)) {
					rightRun.remove(i);
					changed = true;
				} else if (other.leftRun.size() == 1 && other.onTable == Boolean.TRUE) {
					changed |= rightRun.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		public boolean updateRightGroups(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftGroup);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!other.groupNeighbor(this) || !other.rightGroup.contains(id)) {
					leftGroup.remove(i);
					changed = true;
				} else if (other.rightGroup.size() == 1
						&& other.onTable == Boolean.TRUE) {
					changed |= leftGroup.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		public boolean updateLeftGroups(HashSet<Integer> changes)
				throws Contradiction {
			boolean changed = false;
			HashSet<Integer> relevantChanges = new HashSet<Integer>(leftGroup);
			relevantChanges = new HashSet<Integer>(rightGroup);
			relevantChanges.retainAll(changes);
			for (int i : relevantChanges) {
				StoneState other = top.stones.get(i);
				if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) {
					rightGroup.remove(i);
					changed = true;
				} else if (other.leftGroup.size() == 1 && other.onTable == Boolean.TRUE) {
					changed |= rightGroup.retainAll(Arrays.asList(i));
					changed |= onTable != Boolean.TRUE;
					onTable = true;
					break;
				}
			}
			return changed;
		}

		public boolean checkState() throws Contradiction {
			boolean changed = false;

			if (onTable == Boolean.FALSE) {
				if (leftRun.size() + rightRun.size() + leftGroup.size()
						+ rightGroup.size() != 0) {
					leftRun.clear();
					rightRun.clear();
					leftGroup.clear();
					rightGroup.clear();
					return true;
				}
				return false;
			}

			changed |= checkSetTypeKnown();

			changed |= checkLonelyStone();

			changed |= checkNeighborStoneNeeded();

			changed |= checkStoneCanBeOnTable();

			checkGroupRunExclusive();

			changed |= checkJoker();

			return changed;
		}

		private boolean checkSetTypeKnown() {
			boolean changed = false;
			if (!(leftGroup.contains(null) || rightGroup.contains(null))) {
				changed |= leftRun.retainAll(Arrays.asList((Integer) null))
						| rightRun.retainAll(Arrays.asList((Integer) null));
			}
			if (!(leftRun.contains(null) || rightRun.contains(null))) {
				changed |= leftGroup.retainAll(Arrays.asList((Integer) null))
						| rightGroup.retainAll(Arrays.asList((Integer) null));
			}
			return changed;
		}

		private boolean checkLonelyStone() {
			boolean changed = false;
			@SuppressWarnings("unchecked")
			List<HashSet<Integer>> sets = Arrays.<HashSet<Integer>> asList(leftGroup,
					rightGroup, leftRun, rightRun, leftGroup, rightGroup, leftRun);
			for (int i = 0; i < 4; i++) {
				if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1))
						&& isNullSet(sets.get(i + 2))) {
					changed |= sets.get(i + 3).remove(null);
				}
			}
			return changed;
		}

		private boolean checkNeighborStoneNeeded() {
			boolean changed = false;
			if (isSingleNonNullSet(leftRun)
					&& isNullSet(top.stones.get(leftRun.iterator().next()).leftRun)) {
				changed |= rightRun.remove(null);
			}
			if (isSingleNonNullSet(rightRun)
					&& isNullSet(top.stones.get(rightRun.iterator().next()).rightRun)) {
				changed |= leftRun.remove(null);
			}

			if (isSingleNonNullSet(leftGroup)
					&& isNullSet(top.stones.get(leftGroup.iterator().next()).leftGroup)) {
				changed |= rightGroup.remove(null);
			}
			if (isSingleNonNullSet(rightGroup)
					&& isNullSet(top.stones.get(rightGroup.iterator().next()).rightGroup)) {
				changed |= leftGroup.remove(null);
			}
			return changed;
		}

		private boolean checkStoneCanBeOnTable() throws Contradiction {
			boolean changed = false;
			if (leftGroup.isEmpty() || rightGroup.isEmpty() || leftRun.isEmpty()
					|| rightRun.isEmpty()) {
				if (onTable == Boolean.TRUE) {
					throw new Contradiction();
				}
				if (onTable == null) {
					onTable = false;
					leftRun.clear();
					rightRun.clear();
					leftGroup.clear();
					rightGroup.clear();
					changed = true;
				}
			}
			return changed;
		}

		private void checkGroupRunExclusive() throws Contradiction {
			if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup))
					&& (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) {
				throw new Contradiction();
			}
		}

		private boolean checkJoker() {
			return false;
		}

		public boolean isSolved() {
			if (onTable == Boolean.FALSE) {
				return true;
			}
			if (onTable == null || color == null || value == null) {
				return false;
			}
			if (leftRun.size() > 1 || rightRun.size() > 1 || leftGroup.size() > 1
					|| rightGroup.size() > 1) {
				return false;
			}
			return true;
		}

		public double getScore() {
			if (fromTable) {
				return 0;
			}
			return 1;
		}

		public double getPoints() {
			if (fromTable) {
				return 0;
			}
			if (value == null)
				return (double) settings.getHighestValue();
			else
				return (double) value;
		}
	}

	private static boolean isNullSet(HashSet<Integer> i) {
		return i.size() == 1 && i.contains(null);
	}

	private static boolean isSingleNonNullSet(HashSet<Integer> i) {
		return i.size() == 1 && !i.contains(null);
	}

	/**
	 * Creates new turn logic
	 * 
	 * @param settings
	 *          the game settings
	 * @param tableStones
	 *          all stones on the table
	 * @param handStones
	 *          all stones on the hand
	 */
	public TurnLogic(GameSettings settings, Collection<Stone> tableStones,
			Collection<Stone> handStones) {
		this.settings = settings;

		stoneCount = tableStones.size() + handStones.size();

		maxColor = Collections.max(settings.getStoneColors());
		minColor = Collections.min(settings.getStoneColors());

		stoneColors = new ArrayList<StoneColor>(settings.getStoneColors());
		Collections.sort(stoneColors);

		top = new State();
		stack.add(top);

		ArrayList<Pair<Stone, Boolean>> sortedStones = new ArrayList<Pair<Stone, Boolean>>();
		inputStones = new ArrayList<Stone>();
		for (Stone stone : tableStones) {
			sortedStones.add(new Pair<Stone, Boolean>(stone, true));
		}
		for (Stone stone : handStones) {
			sortedStones.add(new Pair<Stone, Boolean>(stone, false));
		}
		Collections.sort(sortedStones, new Comparator<Pair<Stone, Boolean>>() {
			@Override
			public int compare(Pair<Stone, Boolean> o1, Pair<Stone, Boolean> o2) {
				int cmp;
				cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2.getFirst()
						.isJoker());
				if (cmp != 0) {
					return -cmp;
				}
				cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst().getColor());
				if (cmp != 0) {
					return cmp;
				}
				cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2.getFirst()
						.getValue());
				return cmp;
			}
		});

		int i = 0;
		for (Pair<Stone, Boolean> pair : sortedStones) {
			top.add(new StoneState(i++, pair.getFirst(), pair.getSecond()));
			inputStones.add(pair.getFirst());
		}
	}

	/**
	 * Include initial meld threshold into turn logic
	 */
	public void needIntialMeldThreshold() {
		neededPoints = settings.getInitialMeldThreshold();
	}

	private void pop() {
		stack.remove(stack.size() - 1);
		if (!stack.isEmpty()) {
			top = stack.get(stack.size() - 1);
		}
	}

	private void replace() {
		stack.remove(stack.size() - 1);
	}

	private void pushes(State... states) {
		for (State state : states) {
			stack.add(state);
		}
	}

	private void done() {
		top = stack.get(stack.size() - 1);
	}

	/**
	 * Aborts currently running solve call
	 */
	public void abort() {
		abort = true;
	}

	/**
	 * Get the found stones and create output sets
	 * 
	 * @return output sets to put on table
	 */
	public List<StoneSet> getResult() {
		State result = bestState;

		if (result == null) {
			return null;
		}

		ArrayList<StoneSet> outputSets = new ArrayList<StoneSet>();

		for (int i = 0; i < stoneCount; i++) {
			StoneState stone = result.stones.get(i);
			if (isNullSet(stone.leftRun) && isNullSet(stone.leftGroup)) {
				ArrayList<Stone> setStones = new ArrayList<Stone>();
				while (true) {
					setStones.add(inputStones.get(stone.id));
					if (isNullSet(stone.rightRun) && isNullSet(stone.rightGroup)) {
						break;
					}
					Integer rightRunID = stone.rightRun.iterator().next();
					Integer rightGroupID = stone.rightGroup.iterator().next();

					stone = result.stones.get(rightRunID == null ? rightGroupID
							: rightRunID);
				}
				outputSets.add(new StoneSet(setStones));
			}
		}
		return outputSets;
	}

	/**
	 * Solves next state on stack while not aborted
	 * 
	 * @return solved
	 */
	public boolean solve() {
		if (top.isSolved()) {
			pop();
		}
		while (stack.size() != 0) {
			if (abort) {
				return false;
			}
			try {
				top.updateStones();
				if (top.isSolved()) {
					bestState = top;
					return true;
				}
				branch();
				done();
			} catch (Contradiction c) {
				pop();
			}
		}
		return false;
	}

	/**
	 * Optimizes the solution found as long as stopped from control
	 * 
	 * @return score of found solution
	 */
	public double optimize() {
		while (!autoAbort && solve()) {
			neededScore = top.getScore();
		}
		return neededScore;
	}

	private void branch() throws Contradiction {
		for (int i = 0; i < stoneCount; i++) {
			StoneState stone = top.stones.get(i);
			if (stone.onTable == null) {
				replace();
				branchOnHand(i);
				return;
			}
			if (stone.leftRun.size() > 1) {
				replace();
				branchLeftRun(i, stone);
				return;
			}
			if (stone.rightRun.size() > 1) {
				replace();
				branchRightRun(i, stone);
				return;
			}
			if (stone.leftGroup.size() > 1) {
				replace();
				branchLeftGroup(i, stone);
				return;
			}
			if (stone.rightGroup.size() > 1) {
				replace();
				branchRightGroup(i, stone);
				return;
			}
			if (stone.color == null) {
				replace();
				branchColor(i);
				return;
			}
			if (stone.value == null) {
				replace();
				branchValue(i);
				return;
			}
		}
		// This should never happen
		throw new Error("Internal AI error");
	}

	private void branchValue(int i) {
		for (int value = 1; value <= settings.getHighestValue(); value++) {
			State newState = new State(top);
			newState.stones.get(i).value = value;
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchColor(int i) {
		for (StoneColor color : stoneColors) {
			State newState = new State(top);
			newState.stones.get(i).color = color;
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchRightGroup(int i, StoneState stone) {
		for (Integer id : stone.rightGroup) {
			State newState = new State(top);
			newState.stones.get(i).rightGroup.clear();
			newState.stones.get(i).rightGroup.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchLeftGroup(int i, StoneState stone) {
		for (Integer id : stone.leftGroup) {
			State newState = new State(top);
			newState.stones.get(i).leftGroup.clear();
			newState.stones.get(i).leftGroup.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchRightRun(int i, StoneState stone) {
		for (Integer id : stone.rightRun) {
			State newState = new State(top);
			newState.stones.get(i).rightRun.clear();
			newState.stones.get(i).rightRun.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchLeftRun(int i, StoneState stone) {
		for (Integer id : stone.leftRun) {
			State newState = new State(top);
			newState.stones.get(i).leftRun.clear();
			newState.stones.get(i).leftRun.add(id);
			newState.changedStones.add(i);
			pushes(newState);
		}
	}

	private void branchOnHand(int i) {
		State newState = new State(top);
		newState.stones.get(i).onTable = false;
		newState.changedStones.add(i);
		State altState = new State(top);
		altState.stones.get(i).onTable = true;
		altState.changedStones.add(i);
		pushes(altState, newState);
	}

	/**
	 * Abort as soon as a solution is found
	 */
	public void autoAbort() {
		if (bestState != null) {
			abort = true;
		}
		autoAbort = true;
	}
}