findSetsWithTotalPoints now finds sets (and total points)

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

2 files changed, 171 insertions, 61 deletions

diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java
index 66a3442..bf6a078 100644
--- a/src/jrummikub/control/AIUtil.java
+++ b/src/jrummikub/control/AIUtil.java
@@ -1,12 +1,15 @@
 package jrummikub.control;

 

+import java.util.ArrayList;

 import java.util.Arrays;

+import java.util.Collections;

 import java.util.Comparator;

 import java.util.List;

 import java.util.TreeMap;

 

 import jrummikub.model.Stone;

 import jrummikub.model.StoneColor;

+import jrummikub.model.StoneSet;

 import jrummikub.util.Pair;

 

 /**

@@ -18,8 +21,22 @@ public class AIUtil {
 	private AIUtil() {

 	}

 

+	private static class SearchState {

+		int pointsMissing;

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

+		int jokerCount;

+

+		SearchState(int pointsMissing,

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

+			this.pointsMissing = pointsMissing;

+			this.stoneCounts = stoneCounts;

+			this.jokerCount = jokerCount;

+		}

+	}

+

 	/**

-	 * Finds sets with a certain total of points

+	 * 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

@@ -27,19 +44,25 @@ public class AIUtil {
 	 *          the number of each stone

 	 * @param jokerCount

 	 *          the total number of jokers in the game

-	 * @return whether such sets exist

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

 	 */

 	@SuppressWarnings("unchecked")

-	public static boolean findSetsWithTotalPoints(int pointsMissing,

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

+			int pointsMissing,

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

 

 		if (pointsMissing <= 0) {

-			return true;

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

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

 		}

 

 		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 = 13; value >= 1; value--) {

 			for (StoneColor color : StoneColor.values()) {

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

@@ -48,90 +71,172 @@ public class AIUtil {
 				if (stoneCounts.containsKey(stone)) {

 					decrementStoneCount(stoneCounts, stone);

 

-					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,

-							jokerCount, stone, 1))

-						return true;

-					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,

-							jokerCount, stone, 1))

-						return true;

+					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) {

-					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,

-							jokerCount - 1, stone, 1))

-						return true;

-					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,

-							jokerCount - 1, stone, 1))

-						return true;

+					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;

 				}

 			}

 		}

 

-		return false;

+		return bestResult;

 	}

 

-	static boolean findGroupsWithTotalPoints(int pointsMissing,

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

-			Pair<Integer, StoneColor> stone, int groupSize) {

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

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

+			StoneColor testedColor) {

+

+		StoneColor nextColor = getNextColor(testedColor);

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

+				nextColor);

 

-		StoneColor nextColor = getNextColor(stone.getSecond());

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

-				stone.getFirst(), nextColor);

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

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

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

 

 		if (nextColor != null) {

-			if (stoneCounts.containsKey(nextStone)) {

-				decrementStoneCount(stoneCounts, nextStone);

-				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),

-						stoneCounts, jokerCount, nextStone, groupSize + 1))

-					return true;

-				incrementStoneCount(stoneCounts, nextStone);

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

+				decrementStoneCount(searchState.stoneCounts, nextStone);

+				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 (jokerCount > 0) {

-				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),

-						stoneCounts, jokerCount - 1, nextStone, groupSize + 1))

-					return true;

+			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 (findGroupsWithTotalPoints(pointsMissing, stoneCounts, jokerCount,

-					nextStone, groupSize))

-				return true;

+			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;

 		}

 

-		if (groupSize >= 3) {

-			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))

-				return true;

+		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;

 		}

-		return false;

+		return bestResult;

 	}

 

-	static boolean findRunsWithTotalPoints(int pointsMissing,

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

-			Pair<Integer, StoneColor> stone, int runLength) {

+	private static 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);

 

 		Pair<Integer, StoneColor> nextStone = null;

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

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

-			nextStone = new Pair<Integer, StoneColor>(nextValue, stone.getSecond());

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

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

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

+					testedStone.getSecond());

 

-			if (stoneCounts.containsKey(nextStone)) {

-				decrementStoneCount(stoneCounts, nextStone);

-				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,

-						jokerCount, nextStone, runLength + 1))

-					return true;

-				incrementStoneCount(stoneCounts, nextStone);

+			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 (jokerCount > 0) {

-				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,

-						jokerCount - 1, nextStone, runLength + 1))

-					return true;

+			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) {

-			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))

-				return true;

+

+			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()));

+			}

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

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

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

+					result.getSecond() + runPoints);

+

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

+				return result;

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

+				bestResult = result;

 		}

-		return false;

+		return bestResult;

 	}

 

 	static void incrementStoneCount(

diff --git a/src/jrummikub/model/Hand.java b/src/jrummikub/model/Hand.java
index 0f8b050..344855d 100644
--- a/src/jrummikub/model/Hand.java
+++ b/src/jrummikub/model/Hand.java
@@ -99,8 +99,13 @@ public class Hand extends StoneTray<Stone> implements IHand {
 		Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = AIUtil
 				.countStones(stones);
 
-		return AIUtil.findSetsWithTotalPoints(settings.getInitialMeldThreshold(),
-				stoneCounts.getFirst(), stoneCounts.getSecond());
+		Pair<List<StoneSet>, Integer> result = AIUtil.findSetsWithTotalPoints(
+				settings.getInitialMeldThreshold(), stoneCounts.getFirst(),
+				stoneCounts.getSecond());
+		
+		System.out.println(result);
+
+		return (result.getSecond() >= settings.getInitialMeldThreshold());
 	}
 
 	@Override