diff options
Diffstat (limited to 'src/jrummikub')
| -rw-r--r-- | src/jrummikub/control/AIUtil.java | 348 |
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(
|