diff options
Diffstat (limited to 'src/jrummikub/control')
| -rw-r--r-- | src/jrummikub/control/AIUtil.java | 223 |
1 files changed, 164 insertions, 59 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(
|