From d25a73167cd13a7da0cce97414455c210437ae2e Mon Sep 17 00:00:00 2001 From: Bennet Gerlach Date: Mon, 30 May 2011 21:01:48 +0200 Subject: Extracted a AIUtil class from several hand methods git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@330 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/control/AIUtil.java | 208 +++++++++++++++++++++++++++++++++++++ src/jrummikub/model/Hand.java | 209 +++++--------------------------------- 2 files changed, 234 insertions(+), 183 deletions(-) create mode 100644 src/jrummikub/control/AIUtil.java (limited to 'src') 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, Integer> stoneCounts, int jokerCount) { + + if (pointsMissing <= 0) { + return true; + } + + stoneCounts = (TreeMap, Integer>) stoneCounts + .clone(); + + for (int value = 13; value >= 1; value--) { + for (StoneColor color : StoneColor.values()) { + Pair stone = new Pair(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, Integer> stoneCounts, int jokerCount, + Pair stone, int groupSize) { + + StoneColor nextColor = getNextColor(stone.getSecond()); + Pair nextStone = new Pair( + 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, Integer> stoneCounts, int jokerCount, + Pair stone, int runLength) { + + Pair nextStone = null; + if (stone.getFirst() > 1) { + int nextValue = stone.getFirst() - 1; + nextStone = new Pair(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, Integer> stones, + Pair stone) { + if (stones.containsKey(stone)) { + stones.put(stone, stones.get(stone) + 1); + } else { + stones.put(stone, 1); + } + } + + static void decrementStoneCount( + TreeMap, Integer> stones, + Pair 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> comparator = new Comparator>() { + + @Override + public int compare(Pair o1, + Pair 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, Integer>, Integer> countStones( + List stones) { + int jokerCount = 0; + TreeMap, Integer> stoneCounts = new TreeMap, Integer>( + comparator); + + for (Stone stone : stones) { + if (stone.isJoker()) { + jokerCount++; + } else { + Pair key = new Pair( + stone.getValue(), stone.getColor()); + + incrementStoneCount(stoneCounts, key); + } + } + return new Pair, 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 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 implements IHand { } @Override - protected Pair fixInvalidDrop(Stone stone, - Position pos, Direction dir) { + protected Pair fixInvalidDrop(Stone stone, Position pos, + Direction dir) { float x = pos.getX(); float y = pos.getY(); @@ -65,11 +67,9 @@ public class Hand extends StoneTray implements IHand { return new Pair(new Position(0, y), RIGHT); } else { if (getFreeRowSpace((int) y) == 0) { - return new Pair(new Position(0, y + 1), - RIGHT); + return new Pair(new Position(0, y + 1), RIGHT); } else { - return new Pair( - new Position(WIDTH - 1, y), LEFT); + return new Pair(new Position(WIDTH - 1, y), LEFT); } } } @@ -88,195 +88,38 @@ public class Hand extends StoneTray implements IHand { return points; } - private final static Comparator> comparator = new Comparator>() { - - @Override - public int compare(Pair o1, - Pair 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, Integer>, Integer> stoneCounts = countStones(); - - return findSetsWithTotalPoints(settings.getInitialMeldThreshold(), - stoneCounts.getFirst(), stoneCounts.getSecond()); - } + List stones = new ArrayList(); - private Pair, Integer>, Integer> countStones() { - int jokerCount = 0; - TreeMap, Integer> stoneCounts = new TreeMap, Integer>( - comparator); - - - for (Pair entry : this) { - if (entry.getFirst().isJoker()) { - jokerCount++; - } else { - Pair key = new Pair( - entry.getFirst().getValue(), entry.getFirst() - .getColor()); - - incrementStoneCount(stoneCounts, key); - } + for (Iterator> iter = this.iterator(); iter.hasNext();) { + stones.add(iter.next().getFirst()); } - return new Pair, Integer>, Integer>(stoneCounts, jokerCount); - } - private void incrementStoneCount( - TreeMap, Integer> stones, - Pair stone) { - if (stones.containsKey(stone)) { - stones.put(stone, stones.get(stone) + 1); - } else { - stones.put(stone, 1); - } - } - - private void decrementStoneCount( - TreeMap, Integer> stones, - Pair 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, Integer> stoneCounts, - int jokerCount) { + Pair, Integer>, Integer> stoneCounts = AIUtil + .countStones(stones); - if (pointsMissing <= 0) { - return true; - } - - stoneCounts = (TreeMap, Integer>) stoneCounts - .clone(); - - for (int value = 13; value >= 1; value--) { - for (StoneColor color : StoneColor.values()) { - Pair stone = new Pair( - 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, Integer> stoneCounts, - int jokerCount, Pair stone, int groupSize) { - - StoneColor nextColor = getNextColor(stone.getSecond()); - Pair nextStone = new Pair( - 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, Integer> stoneCounts, - int jokerCount, Pair stone, int runLength) { - - Pair nextStone = null; - if (stone.getFirst() > 1) { - int nextValue = stone.getFirst() - 1; - nextStone = new Pair(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 stones = new ArrayList(); - } - if (jokerCount > 0) { - if (findRunsWithTotalPoints(pointsMissing - nextValue, - stoneCounts, jokerCount - 1, nextStone, runLength + 1)) - return true; - } + for (Iterator> iter = this.iterator(); iter.hasNext();) { + stones.add(iter.next().getFirst()); } - if (runLength >= 3) { - if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount)) - return true; - } - return false; - } + Pair, Integer>, Integer> stoneCounts = AIUtil + .countStones(stones); - @Override - public int getIdenticalStoneCount() { - Pair, Integer>, Integer> stoneCounts = countStones(); int pairCount = 0; - - for(int count : stoneCounts.getFirst().values()) { + + for (int count : stoneCounts.getFirst().values()) { pairCount += count / 2; } - + return pairCount; } } -- cgit v1.2.3