Fixed metrics in AIUtil

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

1 files changed, 186 insertions, 162 deletions

diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java
index 1501483..2205318 100644
--- a/src/jrummikub/control/AIUtil.java
+++ b/src/jrummikub/control/AIUtil.java
@@ -27,12 +27,13 @@ public class AIUtil {
 	 * settings

 	 * 

 	 * @param settings

-	 *          the underlying game settings

+	 *            the underlying game settings

 	 */

 	public AIUtil(GameSettings settings) {

 		this.settings = settings;

 

-		stoneColors = new ArrayList<StoneColor>(Arrays.asList(StoneColor.values()));

+		stoneColors = new ArrayList<StoneColor>(Arrays.asList(StoneColor

+				.values()));

 		stoneColors.retainAll(settings.getStoneColors());

 	}

 

@@ -42,85 +43,112 @@ public class AIUtil {
 		int jokerCount;

 

 		SearchState(int pointsMissing,

-				TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {

+				TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts,

+				int jokerCount) {

 			this.pointsMissing = pointsMissing;

 			this.stoneCounts = stoneCounts;

 			this.jokerCount = jokerCount;

 		}

 	}

 

+	@SuppressWarnings("serial")

+	private static class EnoughPoints extends Throwable {

+		private Pair<List<StoneSet>, Integer> result;

+

+		public EnoughPoints(Pair<List<StoneSet>, Integer> result) {

+			this.result = result;

+		}

+

+		public Pair<List<StoneSet>, Integer> getResult() {

+			return result;

+		}

+	}

+

 	/**

-	 * Tries to find sets with a certain total of points. If only lower totals are

-	 * found, returns the sets with the highest cumulated point total.

+	 * Tries to find sets with a certain total of points. If only lower totals

+	 * are found, returns the sets with the highest cumulated point total.

 	 * 

 	 * @param pointsMissing

-	 *          the desired number of points

+	 *            the desired number of points

 	 * @param stoneCounts

-	 *          the number of each stone

+	 *            the number of each stone

 	 * @param jokerCount

-	 *          the total number of jokers in the game

+	 *            the total number of jokers in the game

 	 * @return the sets that have the desired point total or the highest found

 	 */

 	@SuppressWarnings("unchecked")

 	public Pair<List<StoneSet>, Integer> findSetsWithTotalPoints(

 			int pointsMissing,

-			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {

-

-		if (pointsMissing <= 0) {

-			return new Pair<List<StoneSet>, Integer>(

-					Collections.<StoneSet> emptyList(), 0);

-		}

+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts,

+			int jokerCount) {

+		Pair<List<StoneSet>, Integer> emptyResult = new Pair<List<StoneSet>, Integer>(

+				Collections.<StoneSet> emptyList(), 0);

+		if (pointsMissing <= 0)

+			return emptyResult;

 

 		stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts

 				.clone();

 

-		Pair<List<StoneSet>, Integer> result, bestResult;

-		bestResult = new Pair<List<StoneSet>, Integer>(

-				Collections.<StoneSet> emptyList(), 0);

-

-		for (int value = settings.getHighestValue(); value >= 1; value--) {

-			for (StoneColor color : stoneColors) {

-				Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(value,

-						color);

-

-				if (stoneCounts.containsKey(stone)) {

-					decrementStoneCount(stoneCounts, stone);

-					result = findRunsWithTotalPoints(new SearchState(pointsMissing

-							- value, stoneCounts, jokerCount), stone, 1);

-					if (result.getSecond() >= pointsMissing)

-						return result;

-					if (result.getSecond() > bestResult.getSecond())

-						bestResult = result;

-

-					result = findGroupsWithTotalPoints(new SearchState(pointsMissing

-							- value, stoneCounts, jokerCount), value,

-							Collections.singletonList(color), color);

-					if (result.getSecond() >= pointsMissing)

-						return result;

-					if (result.getSecond() > bestResult.getSecond())

-						bestResult = result;

-				}

-

-				if (jokerCount > 0) {

-					result = findRunsWithTotalPoints(new SearchState(pointsMissing

-							- value, stoneCounts, jokerCount - 1), stone, 1);

-					if (result.getSecond() >= pointsMissing)

-						return result;

-					if (result.getSecond() > bestResult.getSecond())

-						bestResult = result;

-

-					result = findGroupsWithTotalPoints(new SearchState(pointsMissing

-							- value, stoneCounts, jokerCount - 1), value,

-							Collections.singletonList(color), color);

-					if (result.getSecond() >= pointsMissing)

-						return result;

-					if (result.getSecond() > bestResult.getSecond())

-						bestResult = result;

+		SearchHelper searchHelper = new SearchHelper(pointsMissing,

+				new Pair<List<StoneSet>, Integer>(

+						Collections.<StoneSet> emptyList(), 0));

+		try {

+			for (int value = settings.getHighestValue(); value >= 1; value--) {

+				for (StoneColor color : stoneColors) {

+					Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(

+							value, color);

+

+					if (stoneCounts.containsKey(stone)) {

+						SearchState searchState = new SearchState(pointsMissing

+								- value, stoneCounts, jokerCount);

+						decrementStoneCount(stoneCounts, stone);

+						searchHelper.checkResult(findRunsWithTotalPoints(

+								searchState, stone, 1));

+

+						searchHelper.checkResult(findGroupsWithTotalPoints(

+								searchState, value,

+								Collections.singletonList(color), color));

+					}

+

+					if (jokerCount > 0) {

+						SearchState searchState = new SearchState(pointsMissing

+								- value, stoneCounts, jokerCount - 1);

+						searchHelper.checkResult(findRunsWithTotalPoints(

+								searchState, stone, 1));

+

+						searchHelper.checkResult(findGroupsWithTotalPoints(

+								searchState, value,

+								Collections.singletonList(color), color));

+					}

 				}

 			}

+		} catch (EnoughPoints enoughPoints) {

+			return enoughPoints.getResult();

 		}

+		return searchHelper.getBestResult();

+	}

+

+	private static class SearchHelper {

+		Pair<List<StoneSet>, Integer> bestResult;

+		int pointsMissing;

 

-		return bestResult;

+		public SearchHelper(int pointsMissing,

+				Pair<List<StoneSet>, Integer> bestResult) {

+			this.pointsMissing = pointsMissing;

+			this.bestResult = bestResult;

+		}

+

+		public void checkResult(Pair<List<StoneSet>, Integer> result)

+				throws EnoughPoints {

+			if (result.getSecond() >= pointsMissing)

+				throw new EnoughPoints(result);

+			if (result.getSecond() > bestResult.getSecond())

+				bestResult = result;

+		}

+

+		public Pair<List<StoneSet>, Integer> getBestResult() {

+			return bestResult;

+		}

 	}

 

 	private Pair<List<StoneSet>, Integer> findGroupsWithTotalPoints(

@@ -128,129 +156,125 @@ public class AIUtil {
 			StoneColor testedColor) {

 

 		StoneColor nextColor = getNextColor(testedColor);

-		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(value,

-				nextColor);

-

-		Pair<List<StoneSet>, Integer> result, bestResult;

-		bestResult = new Pair<List<StoneSet>, Integer>(

-				Collections.<StoneSet> emptyList(), 0);

-

-		if (nextColor != null) {

-			if (searchState.stoneCounts.containsKey(nextStone)) {

-				decrementStoneCount(searchState.stoneCounts, nextStone);

-				List<StoneColor> newColors = new ArrayList<StoneColor>(chosenColors);

+		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(

+				value, nextColor);

+

+		SearchHelper searchHelper = new SearchHelper(searchState.pointsMissing,

+				new Pair<List<StoneSet>, Integer>(

+						Collections.<StoneSet> emptyList(), 0));

+		try {

+			if (nextColor != null) {

+				List<StoneColor> newColors = new ArrayList<StoneColor>(

+						chosenColors);

 				newColors.add(nextColor);

-				result = findGroupsWithTotalPoints(new SearchState(

-						searchState.pointsMissing, searchState.stoneCounts,

-						searchState.jokerCount), value, newColors, nextColor);

-				if (result.getSecond() >= searchState.pointsMissing)

-					return result;

-				if (result.getSecond() > bestResult.getSecond())

-					bestResult = result;

-				incrementStoneCount(searchState.stoneCounts, nextStone);

+				if (searchState.stoneCounts.containsKey(nextStone)) {

+					decrementStoneCount(searchState.stoneCounts, nextStone);

+					searchHelper.checkResult(findGroupsWithTotalPoints(

+							searchState, value, newColors, nextColor));

+					incrementStoneCount(searchState.stoneCounts, nextStone);

+				}

+				if (searchState.jokerCount > 0) {

+					searchHelper.checkResult(findGroupsWithTotalPoints(

+							new SearchState(searchState.pointsMissing,

+									searchState.stoneCounts,

+									searchState.jokerCount - 1), value,

+							newColors, nextColor));

+				}

+				searchHelper.checkResult(findGroupsWithTotalPoints(searchState,

+						value, chosenColors, nextColor));

 			}

-			if (searchState.jokerCount > 0) {

-				List<StoneColor> newColors = new ArrayList<StoneColor>(chosenColors);

-				newColors.add(nextColor);

-				result = findGroupsWithTotalPoints(new SearchState(

-						searchState.pointsMissing, searchState.stoneCounts,

-						searchState.jokerCount - 1), value, newColors, nextColor);

-				if (result.getSecond() >= searchState.pointsMissing)

-					return result;

-				if (result.getSecond() > bestResult.getSecond())

-					bestResult = result;

+

+			if (chosenColors.size() >= 3) {

+				searchHelper.checkResult(handleFoundGroup(searchState, value,

+						chosenColors));

 			}

-			result = findGroupsWithTotalPoints(new SearchState(

-					searchState.pointsMissing, searchState.stoneCounts,

-					searchState.jokerCount), value, chosenColors, nextColor);

-			if (result.getSecond() >= searchState.pointsMissing)

-				return result;

-			if (result.getSecond() > bestResult.getSecond())

-				bestResult = result;

+		} catch (EnoughPoints enoughPoints) {

+			return enoughPoints.getResult();

 		}

+		return searchHelper.getBestResult();

+	}

 

-		if (chosenColors.size() >= 3) {

-			int groupPoints = chosenColors.size() * value;

-			result = findSetsWithTotalPoints(searchState.pointsMissing - groupPoints,

-					searchState.stoneCounts, searchState.jokerCount);

-			List<Stone> newStones = new ArrayList<Stone>();

-			for (StoneColor color : chosenColors) {

-				newStones.add(new Stone(value, color));

-			}

-			List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());

-			newResultList.add(new StoneSet(newStones));

-			result = new Pair<List<StoneSet>, Integer>(newResultList,

-					result.getSecond() + groupPoints);

-			if (result.getSecond() >= searchState.pointsMissing)

-				return result;

-			if (result.getSecond() > bestResult.getSecond())

-				bestResult = result;

+	private Pair<List<StoneSet>, Integer> handleFoundGroup(

+			SearchState searchState, int value, List<StoneColor> chosenColors) {

+		int groupPoints = chosenColors.size() * value;

+		Pair<List<StoneSet>, Integer> result = findSetsWithTotalPoints(

+				searchState.pointsMissing - groupPoints,

+				searchState.stoneCounts, searchState.jokerCount);

+		List<Stone> newStones = new ArrayList<Stone>();

+		for (StoneColor color : chosenColors) {

+			newStones.add(new Stone(value, color));

 		}

-		return bestResult;

+		List<StoneSet> newResultList = new ArrayList<StoneSet>(

+				result.getFirst());

+		newResultList.add(new StoneSet(newStones));

+		result = new Pair<List<StoneSet>, Integer>(newResultList,

+				result.getSecond() + groupPoints);

+		return result;

 	}

 

 	private Pair<List<StoneSet>, Integer> findRunsWithTotalPoints(

 			SearchState searchState, Pair<Integer, StoneColor> testedStone,

 			int runLength) {

 

-		Pair<List<StoneSet>, Integer> result, bestResult;

-		bestResult = new Pair<List<StoneSet>, Integer>(

-				Collections.<StoneSet> emptyList(), 0);

+		SearchHelper searchHelper = new SearchHelper(searchState.pointsMissing,

+				new Pair<List<StoneSet>, Integer>(

+						Collections.<StoneSet> emptyList(), 0));

+		try {

+			Pair<Integer, StoneColor> nextStone = null;

+			if (testedStone.getFirst() > 1) {

+				int nextValue = testedStone.getFirst() - 1;

+				nextStone = new Pair<Integer, StoneColor>(nextValue,

+						testedStone.getSecond());

+

+				if (searchState.stoneCounts.containsKey(nextStone)) {

+					decrementStoneCount(searchState.stoneCounts, nextStone);

+					searchHelper.checkResult(findRunsWithTotalPoints(

+							searchState, nextStone, runLength + 1));

+					incrementStoneCount(searchState.stoneCounts, nextStone);

 

-		Pair<Integer, StoneColor> nextStone = null;

-		if (testedStone.getFirst() > 1) {

-			int nextValue = testedStone.getFirst() - 1;

-			nextStone = new Pair<Integer, StoneColor>(nextValue,

-					testedStone.getSecond());

-

-			if (searchState.stoneCounts.containsKey(nextStone)) {

-				decrementStoneCount(searchState.stoneCounts, nextStone);

-				result = findRunsWithTotalPoints(new SearchState(

-						searchState.pointsMissing, searchState.stoneCounts,

-						searchState.jokerCount), nextStone, runLength + 1);

-				if (result.getSecond() >= searchState.pointsMissing)

-					return result;

-				if (result.getSecond() > bestResult.getSecond())

-					bestResult = result;

-				incrementStoneCount(searchState.stoneCounts, nextStone);

+				}

+				if (searchState.jokerCount > 0) {

+					searchHelper.checkResult(findRunsWithTotalPoints(

+							new SearchState(searchState.pointsMissing,

+									searchState.stoneCounts,

+									searchState.jokerCount - 1), nextStone,

+							runLength + 1));

 

+				}

 			}

-			if (searchState.jokerCount > 0) {

-				result = findRunsWithTotalPoints(new SearchState(

-						searchState.pointsMissing, searchState.stoneCounts,

-						searchState.jokerCount - 1), nextStone, runLength + 1);

-				if (result.getSecond() >= searchState.pointsMissing)

-					return result;

-				if (result.getSecond() > bestResult.getSecond())

-					bestResult = result;

-			}

-		}

-

-		if (runLength >= 3) {

-

-			int below = testedStone.getFirst() - 1;

-			int high = below + runLength;

-			int runPoints = (high * (high + 1)) / 2 - (below * (below + 1)) / 2;

-

-			result = findSetsWithTotalPoints(searchState.pointsMissing - runPoints,

-					searchState.stoneCounts, searchState.jokerCount);

 

-			List<Stone> newStones = new ArrayList<Stone>();

-			for (int i = 0; i < runLength; i++) {

-				newStones.add(new Stone(i + testedStone.getFirst(), testedStone

-						.getSecond()));

+			if (runLength >= 3) {

+				searchHelper.checkResult(handleFoundRun(searchState,

+						testedStone, runLength));

 			}

-			List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());

-			newResultList.add(new StoneSet(newStones));

-			result = new Pair<List<StoneSet>, Integer>(newResultList,

-					result.getSecond() + runPoints);

+		} catch (EnoughPoints enoughPoints) {

+			return enoughPoints.getResult();

+		}

+		return searchHelper.getBestResult();

+	}

 

-			if (result.getSecond() >= searchState.pointsMissing)

-				return result;

-			if (result.getSecond() > bestResult.getSecond())

-				bestResult = result;

+	private Pair<List<StoneSet>, Integer> handleFoundRun(

+			SearchState searchState, Pair<Integer, StoneColor> testedStone,

+			int runLength) {

+		int below = testedStone.getFirst() - 1;

+		int high = below + runLength;

+		int runPoints = (high * (high + 1)) / 2 - (below * (below + 1)) / 2;

+

+		Pair<List<StoneSet>, Integer> result = findSetsWithTotalPoints(

+				searchState.pointsMissing - runPoints, searchState.stoneCounts,

+				searchState.jokerCount);

+

+		List<Stone> newStones = new ArrayList<Stone>();

+		for (int i = 0; i < runLength; i++) {

+			newStones.add(new Stone(i + testedStone.getFirst(), testedStone

+					.getSecond()));

 		}

-		return bestResult;

+		List<StoneSet> newResultList = new ArrayList<StoneSet>(

+				result.getFirst());

+		newResultList.add(new StoneSet(newStones));

+		result = new Pair<List<StoneSet>, Integer>(newResultList,

+				result.getSecond() + runPoints);

+		return result;

 	}

 

 	static void incrementStoneCount(

@@ -302,7 +326,7 @@ public class AIUtil {
 	 * Counts the numbers of stones

 	 * 

 	 * @param stones

-	 *          the stones to count

+	 *            the stones to count

 	 * @return the numbers for all stones

 	 */

 	public static Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> countStones(