diff options
Diffstat (limited to 'src/jrummikub/control')
| -rw-r--r-- | src/jrummikub/control/AIUtil.java | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java new file mode 100644 index 0000000..66a3442 --- /dev/null +++ b/src/jrummikub/control/AIUtil.java @@ -0,0 +1,208 @@ +package jrummikub.control;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.TreeMap;
+
+import jrummikub.model.Stone;
+import jrummikub.model.StoneColor;
+import jrummikub.util.Pair;
+
+/**
+ * A collection of several AI utility methods
+ *
+ */
+public class AIUtil {
+
+ private AIUtil() {
+ }
+
+ /**
+ * Finds sets with a certain total of points
+ *
+ * @param pointsMissing
+ * the desired number of points
+ * @param stoneCounts
+ * the number of each stone
+ * @param jokerCount
+ * the total number of jokers in the game
+ * @return whether such sets exist
+ */
+ @SuppressWarnings("unchecked")
+ public static boolean findSetsWithTotalPoints(int pointsMissing,
+ TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {
+
+ if (pointsMissing <= 0) {
+ return true;
+ }
+
+ stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts
+ .clone();
+
+ for (int value = 13; value >= 1; value--) {
+ for (StoneColor color : StoneColor.values()) {
+ Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(value,
+ color);
+
+ 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;
+ }
+
+ 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;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ static boolean findGroupsWithTotalPoints(int pointsMissing,
+ TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,
+ Pair<Integer, StoneColor> stone, int groupSize) {
+
+ StoneColor nextColor = getNextColor(stone.getSecond());
+ Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(
+ stone.getFirst(), nextColor);
+
+ 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 (jokerCount > 0) {
+ if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),
+ stoneCounts, jokerCount - 1, nextStone, groupSize + 1))
+ return true;
+ }
+ if (findGroupsWithTotalPoints(pointsMissing, stoneCounts, jokerCount,
+ nextStone, groupSize))
+ return true;
+ }
+
+ if (groupSize >= 3) {
+ if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))
+ return true;
+ }
+ return false;
+ }
+
+ static boolean findRunsWithTotalPoints(int pointsMissing,
+ TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,
+ Pair<Integer, StoneColor> stone, int runLength) {
+
+ Pair<Integer, StoneColor> nextStone = null;
+ if (stone.getFirst() > 1) {
+ int nextValue = stone.getFirst() - 1;
+ nextStone = new Pair<Integer, StoneColor>(nextValue, stone.getSecond());
+
+ if (stoneCounts.containsKey(nextStone)) {
+ decrementStoneCount(stoneCounts, nextStone);
+ if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,
+ jokerCount, nextStone, runLength + 1))
+ return true;
+ incrementStoneCount(stoneCounts, nextStone);
+
+ }
+ if (jokerCount > 0) {
+ if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,
+ jokerCount - 1, nextStone, runLength + 1))
+ return true;
+ }
+ }
+
+ if (runLength >= 3) {
+ if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))
+ return true;
+ }
+ return false;
+ }
+
+ static void incrementStoneCount(
+ TreeMap<Pair<Integer, StoneColor>, Integer> stones,
+ Pair<Integer, StoneColor> stone) {
+ if (stones.containsKey(stone)) {
+ stones.put(stone, stones.get(stone) + 1);
+ } else {
+ stones.put(stone, 1);
+ }
+ }
+
+ static void decrementStoneCount(
+ TreeMap<Pair<Integer, StoneColor>, Integer> stones,
+ Pair<Integer, StoneColor> stone) {
+ int count = stones.get(stone);
+ count--;
+
+ if (count == 0) {
+ stones.remove(stone);
+ } else {
+ stones.put(stone, count);
+ }
+ }
+
+ static StoneColor getNextColor(StoneColor color) {
+ int index = Arrays.binarySearch(StoneColor.values(), color) + 1;
+ if (index >= StoneColor.values().length) {
+ return null;
+ }
+ return StoneColor.values()[index];
+ }
+
+ private final static Comparator<Pair<Integer, StoneColor>> comparator = new Comparator<Pair<Integer, StoneColor>>() {
+
+ @Override
+ public int compare(Pair<Integer, StoneColor> o1,
+ Pair<Integer, StoneColor> o2) {
+ int firstComparison = o1.getFirst().compareTo(o2.getFirst());
+ if (firstComparison != 0) {
+ return -firstComparison;
+ } else {
+ return o1.getSecond().compareTo(o2.getSecond());
+ }
+ }
+ };
+
+ /**
+ * Counts the numbers of stones
+ *
+ * @param stones
+ * the stones to count
+ * @return the numbers for all stones
+ */
+ public static Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> countStones(
+ List<Stone> stones) {
+ int jokerCount = 0;
+ TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts = new TreeMap<Pair<Integer, StoneColor>, Integer>(
+ comparator);
+
+ for (Stone stone : stones) {
+ if (stone.isJoker()) {
+ jokerCount++;
+ } else {
+ Pair<Integer, StoneColor> key = new Pair<Integer, StoneColor>(
+ stone.getValue(), stone.getColor());
+
+ incrementStoneCount(stoneCounts, key);
+ }
+ }
+ return new Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer>(
+ stoneCounts, jokerCount);
+ }
+}
|