Reimplemented AI (old one was too slow)

git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@443 72836036-5685-4462-b002-a69064685172

1 files changed, 567 insertions, 325 deletions

diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java
index e736361..8318773 100644
--- a/src/jrummikub/ai/TurnLogic.java
+++ b/src/jrummikub/ai/TurnLogic.java
@@ -1,391 +1,633 @@
 package jrummikub.ai;
 
-import static jrummikub.ai.fdsolver.Constraints.constant;
-import static jrummikub.ai.fdsolver.Constraints.index;
-import static jrummikub.ai.fdsolver.Constraints.lessThan;
-import static jrummikub.ai.fdsolver.Constraints.lessThanEq;
-import static jrummikub.ai.fdsolver.Constraints.offset;
-import static jrummikub.ai.fdsolver.Constraints.same;
-import static jrummikub.ai.fdsolver.Constraints.sum;
-import static jrummikub.ai.fdsolver.Constraints.unless;
-import static jrummikub.ai.fdsolver.Constraints.when;
-
 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 java.util.Set;
 
-import jrummikub.ai.fdsolver.Constraint;
-import jrummikub.ai.fdsolver.Solver;
-import jrummikub.ai.fdsolver.Var;
 import jrummikub.model.GameSettings;
 import jrummikub.model.Stone;
 import jrummikub.model.StoneColor;
+import jrummikub.util.Pair;
 
-/**
- * Provides Humanlike Advanced Logic (HAL) that models the options given to a
- * player in a turn to the Solver MCP.
- */
 public class TurnLogic {
-	private Solver solver = new Solver();
-	private GameSettings settings;
-	private int stoneCount;
-	private int maxSetSize;
-	private int maxHandPoints;
+	GameSettings settings;
+	int stoneCount;
+	StoneColor maxColor;
+	StoneColor minColor;
+	ArrayList<StoneColor> stoneColors;
+
+	ArrayList<State> stack = new ArrayList<State>();
+	State top;
+	
+	int neededPoints = 0;
+	double neededScore = Double.NEGATIVE_INFINITY;
+	
+	@SuppressWarnings("serial")
+	private static class Contradiction extends Throwable {
 
-	private Var<Boolean> trueVar;
-	private Var<Integer> totalPoints;
+	}
 
-	private List<Var<Boolean>> onTable = new ArrayList<Var<Boolean>>();
+	private class State {
+		ArrayList<StoneState> stones = new ArrayList<StoneState>();
+		HashSet<Integer> changedStones = new HashSet<Integer>();
+		ArrayList<Integer> jokerIDs = new ArrayList<Integer>();
 
-	private List<Var<Integer>> pointsValue = new ArrayList<Var<Integer>>();
+		public State() {
+		}
 
-	private List<Var<Integer>> stoneValue = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> leftStoneValue = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> rightStoneValue = new ArrayList<Var<Integer>>();
+		public State(State state) {
+			for (StoneState stone : state.stones) {
+				stones.add(new StoneState(stone));
+			}
+			jokerIDs = state.jokerIDs;
+		}
 
-	private List<Var<StoneColor>> stoneColor = new ArrayList<Var<StoneColor>>();
-	private List<Var<StoneColor>> leftStoneColor = new ArrayList<Var<StoneColor>>();
-	private List<Var<StoneColor>> rightStoneColor = new ArrayList<Var<StoneColor>>();
+		public void add(StoneState stone) {
+			stones.add(stone);
+			changedStones.add(stones.size() - 1);
+			if (stone.joker) {
+				jokerIDs.add(stone.id);
+			}
+		}
 
-	private List<Var<Integer>> lowCount = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> leftLowCount = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> rightLowCount = new ArrayList<Var<Integer>>();
+		public void updateStones() throws Contradiction {
+			checkJokers();
+			for (int i : changedStones) {
+				stones.get(i).checkState();
+			}
+			checkScoreAndPoints();
+			while (!changedStones.isEmpty()) {
+				updateStonesStep();
+				checkScoreAndPoints();
+			}
+		}
 
-	private List<Var<Integer>> highCount = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> leftHighCount = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> rightHighCount = new ArrayList<Var<Integer>>();
+		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;
+		}
 
-	private List<Var<Integer>> setSize = new ArrayList<Var<Integer>>();
+		public boolean isSolved() {
+			for (StoneState stone : stones) {
+				if (!stone.isSolved())
+					return false;
+			}
+			return true;
+		}
 
-	private List<Var<Boolean>> isRun = new ArrayList<Var<Boolean>>();
+		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));
 
-	private List<Var<Integer>> leftNeighbor = new ArrayList<Var<Integer>>();
-	private List<Var<Integer>> rightNeighbor = new ArrayList<Var<Integer>>();
+					if (right.leftGroup.remove(groupID)) {
+						changedStones.add(jokerIDs.get(j));
+					}
+					if (right.leftRun.remove(runID)) {
+						changedStones.add(jokerIDs.get(j));
+					}
+				}
+			}
+		}
 
-	private List<Var<Integer>> stoneID = new ArrayList<Var<Integer>>();
+		public void checkScoreAndPoints() throws Contradiction {
+			if (getPoints() < neededPoints) {
+				throw new Contradiction();
+			}
+			if (getScore() <= neededScore) {
+				throw new Contradiction();
+			}
+		}
 
-	private List<Var<Boolean>> hasLeftNeighbor = new ArrayList<Var<Boolean>>();
-	private List<Var<Boolean>> hasRightNeighbor = new ArrayList<Var<Boolean>>();
+		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 List<Boolean> isJoker = new ArrayList<Boolean>();
+	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 TurnLogic(GameSettings settings, Collection<Stone> tableStones,
-			Collection<Stone> handStones) {
-		this.settings = settings;
-		stoneCount = tableStones.size() + handStones.size();
-		maxSetSize = Math.max(settings.getHighestValue(), settings
-				.getStoneColors().size());
+		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;
+		}
 
-		trueVar = solver.makeVar(true);
+		public boolean isInterested(HashSet<Integer> changes) {
+			return !(Collections.disjoint(changes, leftRun)
+					&& Collections.disjoint(changes, rightRun)
+					&& Collections.disjoint(changes, leftGroup) && Collections
+					.disjoint(changes, rightGroup));
+		}
 
-		maxHandPoints = 0;
-		int i = 0;
-		for (Stone stone : tableStones) {
-			addStone(i, true, stone);
-			i++;
+		private boolean isNullSet(HashSet<Integer> i) {
+			return i.size() == 1 && i.contains(null);
 		}
-		for (Stone stone : handStones) {
-			addStone(i, false, stone);
-			i++;
+
+		private boolean isSingleNonNullSet(HashSet<Integer> i) {
+			return i.size() == 1 && !i.contains(null);
 		}
 
-		for (i = 0; i < stoneCount; i++) {
-			addConstraints(i);
+		public <T extends Comparable<T>> boolean lessThan(T a, T b) {
+			return a == null || b == null || a.compareTo(b) < 0;
 		}
 
-		totalPoints = solver.makeRangeVar(settings.getInitialMeldThreshold(),
-				maxHandPoints);
+		public <T> boolean same(T a, T b) {
+			return a == null || b == null || a.equals(b);
+		}
 
-		List<Var<Integer>> points = new ArrayList<Var<Integer>>();
+		public boolean step(Integer a, Integer b) {
+			return a == null || b == null || (int) a == b - 1;
+		}
 
-		for (Var<Integer> var : pointsValue) {
-			if (var != null) {
-				points.add(var);
-			}
+		public boolean cycleStep(Integer a, Integer b) {
+			return a == null || b == null || (int) a == b - 1
+					|| a == settings.getHighestValue() && b == 1;
 		}
 
-		add(sum(totalPoints, points));
-	}
+		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);
+		}
 
-	private void addStone(int i, boolean table, Stone stone) {
-		if (table) {
-			onTable.add(trueVar);
-		} else {
-			onTable.add(solver.makeBoolVar());
-		}
-		isJoker.add(stone.isJoker());
-		if (stone.isJoker()) {
-			stoneValue.add(solver.makeRangeVar(1, settings.getHighestValue()));
-			if (table) {
-				pointsValue.add(null);
-			} else {
-				pointsValue.add(solver.makeRangeVar(0,
-						settings.getHighestValue()));
-				maxHandPoints += settings.getHighestValue();
-			}
-			stoneColor.add(solver.makeVar(settings.getStoneColors()));
-		} else {
-			stoneValue.add(solver.makeVar(stone.getValue()));
-			if (table) {
-				pointsValue.add(null);
+		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 {
-				pointsValue.add(solver.makeVar(0, stone.getValue()));
-				maxHandPoints += stone.getValue();
+				if (((Integer) 1).equals(other.value)
+						|| ((Integer) settings.getHighestValue()).equals(value)) {
+					return false;
+				}
+				return step(value, other.value);
 			}
-			stoneColor.add(solver.makeVar(stone.getColor()));
 		}
 
-		leftStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue()));
-		rightStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue()));
-		leftStoneColor.add(solver.makeVar(settings.getStoneColors()));
-		rightStoneColor.add(solver.makeVar(settings.getStoneColors()));
+		public boolean update(HashSet<Integer> changes) throws Contradiction {
+			boolean changed = false;
+			changed |= updateRuns(changes);
+			changed |= updateGroups(changes);
+			changed |= checkState();
+			return changed;
+		}
 
-		lowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
-		leftLowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
-		rightLowCount.add(solver.makeRangeVar(0, maxSetSize - 1));
+		public boolean updateRuns(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;
+				}
+			}
+			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;
+		}
 
-		highCount.add(solver.makeRangeVar(0, maxSetSize - 1));
-		leftHighCount.add(solver.makeRangeVar(0, maxSetSize - 1));
-		rightHighCount.add(solver.makeRangeVar(0, maxSetSize - 1));
+		public boolean updateGroups(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;
+				}
+			}
+			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;
+		}
 
-		setSize.add(solver.makeRangeVar(2, maxSetSize - 1));
+		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;
+			}
 
-		isRun.add(solver.makeBoolVar());
+			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));
+			}
 
-		leftNeighbor.add(solver.makeRangeVar(0, stoneCount - 1));
-		rightNeighbor.add(solver.makeRangeVar(0, stoneCount - 1));
+			@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);
+				}
+			}
 
-		stoneID.add(solver.makeVar(i));
+			if (leftGroup.isEmpty() || rightGroup.isEmpty()
+					|| leftRun.isEmpty() || rightRun.isEmpty()) {
+				if (onTable == Boolean.TRUE) {
+					throw new Contradiction();
+				}
+				if (onTable == null) {
+					onTable = false;
+					changed = true;
+				}
+			}
+
+			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);
+			}
+
+			changed |= checkJoker();
+
+			return changed;
+		}
+
+		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;
+		}
+	}
+
+	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>>();
+
+		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()));
+		}
+	}
+	
+	public void needIntialMeldThreshold() {
+		neededPoints = settings.getInitialMeldThreshold();
+	}
 
-		hasLeftNeighbor.add(solver.makeBoolVar());
-		hasRightNeighbor.add(solver.makeBoolVar());
+	private void pop() {
+		stack.remove(stack.size() - 1);
+		if (!stack.isEmpty()) {
+			top = stack.get(stack.size() - 1);
+		}
 	}
 
-	private void add(Constraint c) {
-		solver.addConstraint(c);
+	private void replace() {
+		stack.remove(stack.size() - 1);
 	}
 
-	private void addConstraints(int i) {
-		// Linking of neighbors
-		add(when(hasLeftNeighbor.get(i),
-				index(stoneID.get(i), leftNeighbor.get(i), rightNeighbor)));
-		add(unless(hasLeftNeighbor.get(i), constant(leftNeighbor.get(i), 0)));
-		add(when(hasLeftNeighbor.get(i),
-				index(trueVar, leftNeighbor.get(i), hasRightNeighbor)));
-		add(when(hasRightNeighbor.get(i),
-				index(stoneID.get(i), rightNeighbor.get(i), leftNeighbor)));
-		add(unless(hasRightNeighbor.get(i), constant(rightNeighbor.get(i), 0)));
-		add(when(hasRightNeighbor.get(i),
-				index(trueVar, rightNeighbor.get(i), hasLeftNeighbor)));
-		// hand stones have no neighbors
-		add(unless(onTable.get(i), constant(hasLeftNeighbor.get(i), false)));
-		add(unless(onTable.get(i), constant(hasRightNeighbor.get(i), false)));
-
-		// low/high counts and size
-		add(unless(hasLeftNeighbor.get(i), constant(lowCount.get(i), 0)));
-		add(unless(hasRightNeighbor.get(i), constant(highCount.get(i), 0)));
-
-		add(when(hasLeftNeighbor.get(i),
-				index(leftLowCount.get(i), leftNeighbor.get(i), lowCount)));
-		add(unless(hasLeftNeighbor.get(i), constant(leftLowCount.get(i), 0)));
-
-		add(when(hasRightNeighbor.get(i),
-				index(rightLowCount.get(i), rightNeighbor.get(i), lowCount)));
-		add(unless(hasRightNeighbor.get(i), constant(rightLowCount.get(i), 0)));
-
-		add(when(hasLeftNeighbor.get(i),
-				index(leftHighCount.get(i), leftNeighbor.get(i), highCount)));
-		add(unless(hasLeftNeighbor.get(i), constant(leftHighCount.get(i), 0)));
-
-		add(when(hasRightNeighbor.get(i),
-				index(rightHighCount.get(i), rightNeighbor.get(i), highCount)));
-		add(unless(hasRightNeighbor.get(i), constant(rightHighCount.get(i), 0)));
-
-		add(when(hasLeftNeighbor.get(i),
-				index(setSize.get(i), leftNeighbor.get(i), setSize)));
-
-		add(when(hasRightNeighbor.get(i),
-				index(setSize.get(i), rightNeighbor.get(i), setSize)));
-
-		add(when(hasLeftNeighbor.get(i),
-				offset(1, leftLowCount.get(i), lowCount.get(i))));
-		add(when(hasRightNeighbor.get(i),
-				offset(1, lowCount.get(i), rightLowCount.get(i))));
-
-		add(when(hasRightNeighbor.get(i),
-				offset(1, rightHighCount.get(i), highCount.get(i))));
-		add(when(hasLeftNeighbor.get(i),
-				offset(1, highCount.get(i), leftHighCount.get(i))));
-
-		add(when(onTable.get(i),
-				sum(lowCount.get(i), highCount.get(i), setSize.get(i))));
-
-		add(unless(onTable.get(i), constant(setSize.get(i), 2)));
-
-		// set same rules
-		add(when(hasLeftNeighbor.get(i),
-				index(isRun.get(i), leftNeighbor.get(i), isRun)));
-		add(when(hasRightNeighbor.get(i),
-				index(isRun.get(i), rightNeighbor.get(i), isRun)));
-
-		add(unless(onTable.get(i), constant(isRun.get(i), false)));
-
-		// rule neighbors
-		add(when(hasLeftNeighbor.get(i),
-				index(leftStoneColor.get(i), leftNeighbor.get(i), stoneColor)));
-		add(unless(hasLeftNeighbor.get(i),
-				constant(leftStoneColor.get(i), StoneColor.RED)));
-		add(when(hasRightNeighbor.get(i),
-				index(rightStoneColor.get(i), rightNeighbor.get(i), stoneColor)));
-		add(unless(hasRightNeighbor.get(i),
-				constant(rightStoneColor.get(i), StoneColor.RED)));
-
-		add(when(hasLeftNeighbor.get(i),
-				index(leftStoneValue.get(i), leftNeighbor.get(i), stoneValue)));
-		add(unless(hasLeftNeighbor.get(i), constant(leftStoneValue.get(i), 1)));
-		add(when(hasRightNeighbor.get(i),
-				index(rightStoneValue.get(i), rightNeighbor.get(i), stoneValue)));
-		add(unless(hasRightNeighbor.get(i), constant(rightStoneValue.get(i), 1)));
-		// general rules
-
-		add(when(
-				hasLeftNeighbor.get(i),
-				when(isRun.get(i),
-						lessThanEq(leftStoneValue.get(i), stoneValue.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				when(isRun.get(i),
-						lessThanEq(stoneValue.get(i), rightStoneValue.get(i)))));
-
-		add(when(
-				hasLeftNeighbor.get(i),
-				when(isRun.get(i),
-						lessThanEq(leftStoneColor.get(i), stoneColor.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				when(isRun.get(i),
-						lessThanEq(stoneColor.get(i), rightStoneColor.get(i)))));
-
-		// run rules
-
-		add(when(
-				hasLeftNeighbor.get(i),
-				when(isRun.get(i),
-						offset(1, leftStoneValue.get(i), stoneValue.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				when(isRun.get(i),
-						offset(1, stoneValue.get(i), rightStoneValue.get(i)))));
-
-		add(when(
-				hasLeftNeighbor.get(i),
-				when(isRun.get(i),
-						same(leftStoneColor.get(i), stoneColor.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				when(isRun.get(i),
-						same(stoneColor.get(i), rightStoneColor.get(i)))));
-
-		// group rules
-		add(when(
-				hasLeftNeighbor.get(i),
-				unless(isRun.get(i),
-						same(leftStoneValue.get(i), stoneValue.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				unless(isRun.get(i),
-						same(stoneValue.get(i), rightStoneValue.get(i)))));
-
-		add(when(
-				hasLeftNeighbor.get(i),
-				unless(isRun.get(i),
-						lessThan(leftStoneColor.get(i), stoneColor.get(i)))));
-		add(when(
-				hasRightNeighbor.get(i),
-				unless(isRun.get(i),
-						lessThan(stoneColor.get(i), rightStoneColor.get(i)))));
-
-		// joker defaulting
-		if (isJoker.get(i)) {
-			add(unless(onTable.get(i), constant(stoneValue.get(i), 1)));
-			add(unless(onTable.get(i),
-					constant(stoneColor.get(i), StoneColor.RED)));
-		}
-
-		// initial meld points
-		if (pointsValue.get(i) != null) {
-			add(when(onTable.get(i),
-					same(stoneValue.get(i), pointsValue.get(i))));
-			add(unless(onTable.get(i), constant(pointsValue.get(i), 0)));
+	private void pushes(State... states) {
+		for (State state : states) {
+			stack.add(state);
 		}
 	}
 
+	private void done() {
+		top = stack.get(stack.size() - 1);
+	}
+
 	public boolean solve() {
-		Set<Integer> tableIDs = new HashSet<Integer>();
-		Set<Integer> leftIDs = new HashSet<Integer>();
-		boolean res = solver.solve();
-		if (!res)
-			return false;
-		System.out.println("== Hand ==");
+		if (top.isSolved()) {
+			pop();
+		}
+		while (stack.size() != 0) {
+			try {
+				top.updateStones();
+				if (top.isSolved()) {
+					return true;
+				}
+				branch();
+				done();
+			} catch (Contradiction c) {
+				pop();
+			}
+		}
+		return false;
+	}
+
+	public double optimize() {
+		while (solve()) {
+			neededScore = top.getScore();
+		}
+		return neededScore;
+	}
+
+	private void branch() throws Contradiction {
 		for (int i = 0; i < stoneCount; i++) {
-			if (onTable.get(i).getValue()) {
-				tableIDs.add(i);
-				if (!hasLeftNeighbor.get(i).getValue()) {
-					leftIDs.add(i);
+			StoneState stone = top.stones.get(i);
+			if (stone.onTable == null) {
+				replace();
+				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);
+				return;
+			}
+			if (stone.leftRun.size() > 1) {
+				replace();
+				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);
 				}
-			} else {
-				outputStone(i);
-			}
-		}
-		System.out.println("");
-		System.out.println("== Table ==");
-		boolean newLine = false;
-		boolean first = true;
-		int nextID = -1; // leftIDs.iterator().next();
-		while (!tableIDs.isEmpty()) {
-			if (tableIDs.contains(nextID)) {
-				tableIDs.remove(nextID);
-				leftIDs.remove(nextID);
-				if (newLine) {
-					if (!first) {
-						System.out.println("");
-					}
-					first = false;
-					newLine = false;
+				return;
+			}
+			if (stone.rightRun.size() > 1) {
+				replace();
+				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);
 				}
-				outputStone(nextID);
-				if (!hasRightNeighbor.get(nextID).getValue()) {
-					newLine = true;
-					nextID = -1;
-				} else {
-					nextID = rightNeighbor.get(nextID).getValue();
+				return;
+			}
+			if (stone.leftGroup.size() > 1) {
+				replace();
+				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);
 				}
-			} else {
-				if (leftIDs.isEmpty()) {
-					nextID = tableIDs.iterator().next();
-				} else {
-					nextID = leftIDs.iterator().next();
+				return;
+			}
+			if (stone.rightGroup.size() > 1) {
+				replace();
+				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);
+				}
+				return;
+			}
+			if (stone.color == null) {
+				replace();
+				for (StoneColor color : stoneColors) {
+					State newState = new State(top);
+					newState.stones.get(i).color = color;
+					newState.changedStones.add(i);
+					pushes(newState);
 				}
-				newLine = true;
+				return;
+			}
+			if (stone.value == null) {
+				replace();
+				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);
+				}
+				return;
 			}
 		}
-		System.out.println("");
-		System.out.println("");
-		return res;
-	}
-
-	private void outputStone(int i) {
-		System.out.print("["
-				+ stoneColor.get(i).getValue().toString().substring(0, 1)
-				+ stoneValue.get(i).getValue() + "]");
-		/*
-		 * + "," + leftNeighbor.get(i).getValue() +
-		 * hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + ","
-		 * + rightNeighbor.get(i).getValue() +
-		 * hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() +
-		 * "]");
-		 */
+		// This should never happen
+		throw new Error("Internal AI error");
 	}
 }