diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/jrummikub/control/AIUtil.java | 208 | ||||
| -rw-r--r-- | src/jrummikub/model/Hand.java | 209 |
2 files changed, 234 insertions, 183 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);
+ }
+}
diff --git a/src/jrummikub/model/Hand.java b/src/jrummikub/model/Hand.java index 6e30a32..0f8b050 100644 --- a/src/jrummikub/model/Hand.java +++ b/src/jrummikub/model/Hand.java @@ -3,10 +3,12 @@ package jrummikub.model; import static jrummikub.model.StoneTray.Direction.LEFT; import static jrummikub.model.StoneTray.Direction.RIGHT; -import java.util.Arrays; -import java.util.Comparator; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; import java.util.TreeMap; +import jrummikub.control.AIUtil; import jrummikub.util.Pair; /** Class managing a {@link Player}'s {@link Stone}s */ @@ -22,7 +24,7 @@ public class Hand extends StoneTray<Stone> implements IHand { * Create a new empty hand with given game settings * * @param settings - * the game settings + * the game settings */ public Hand(GameSettings settings) { this.settings = settings; @@ -53,8 +55,8 @@ public class Hand extends StoneTray<Stone> implements IHand { } @Override - protected Pair<Position, Direction> fixInvalidDrop(Stone stone, - Position pos, Direction dir) { + protected Pair<Position, Direction> fixInvalidDrop(Stone stone, Position pos, + Direction dir) { float x = pos.getX(); float y = pos.getY(); @@ -65,11 +67,9 @@ public class Hand extends StoneTray<Stone> implements IHand { return new Pair<Position, Direction>(new Position(0, y), RIGHT); } else { if (getFreeRowSpace((int) y) == 0) { - return new Pair<Position, Direction>(new Position(0, y + 1), - RIGHT); + return new Pair<Position, Direction>(new Position(0, y + 1), RIGHT); } else { - return new Pair<Position, Direction>( - new Position(WIDTH - 1, y), LEFT); + return new Pair<Position, Direction>(new Position(WIDTH - 1, y), LEFT); } } } @@ -88,195 +88,38 @@ public class Hand extends StoneTray<Stone> implements IHand { return points; } - 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()); - } - } - }; - @Override public boolean isInitialMeldPossible() { - Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = countStones(); - - return findSetsWithTotalPoints(settings.getInitialMeldThreshold(), - stoneCounts.getFirst(), stoneCounts.getSecond()); - } + List<Stone> stones = new ArrayList<Stone>(); - private Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> countStones() { - int jokerCount = 0; - TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts = new TreeMap<Pair<Integer, StoneColor>, Integer>( - comparator); - - - for (Pair<Stone, Position> entry : this) { - if (entry.getFirst().isJoker()) { - jokerCount++; - } else { - Pair<Integer, StoneColor> key = new Pair<Integer, StoneColor>( - entry.getFirst().getValue(), entry.getFirst() - .getColor()); - - incrementStoneCount(stoneCounts, key); - } + for (Iterator<Pair<Stone, Position>> iter = this.iterator(); iter.hasNext();) { + stones.add(iter.next().getFirst()); } - return new Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer>(stoneCounts, jokerCount); - } - private 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); - } - } - - private 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); - } - } - - @SuppressWarnings("unchecked") - private boolean findSetsWithTotalPoints(int pointsMissing, - TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, - int jokerCount) { + Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = AIUtil + .countStones(stones); - 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; - } - - private StoneColor getNextColor(StoneColor color) { - int index = Arrays.binarySearch(StoneColor.values(), color) + 1; - if (index >= StoneColor.values().length) { - return null; - } - return StoneColor.values()[index]; - } - - private 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; + return AIUtil.findSetsWithTotalPoints(settings.getInitialMeldThreshold(), + stoneCounts.getFirst(), stoneCounts.getSecond()); } - private 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); + @Override + public int getIdenticalStoneCount() { + List<Stone> stones = new ArrayList<Stone>(); - } - if (jokerCount > 0) { - if (findRunsWithTotalPoints(pointsMissing - nextValue, - stoneCounts, jokerCount - 1, nextStone, runLength + 1)) - return true; - } + for (Iterator<Pair<Stone, Position>> iter = this.iterator(); iter.hasNext();) { + stones.add(iter.next().getFirst()); } - if (runLength >= 3) { - if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount)) - return true; - } - return false; - } + Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = AIUtil + .countStones(stones); - @Override - public int getIdenticalStoneCount() { - Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> stoneCounts = countStones(); int pairCount = 0; - - for(int count : stoneCounts.getFirst().values()) { + + for (int count : stoneCounts.getFirst().values()) { pairCount += count / 2; } - + return pairCount; } } |