From 278edc37a9861078d5ea1527695ef12766c0fb87 Mon Sep 17 00:00:00 2001 From: Bennet Gerlach Date: Tue, 31 May 2011 03:45:21 +0200 Subject: findSetsWithTotalPoints now finds sets (and total points) git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@341 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/control/AIUtil.java | 223 ++++++++++++++++++++++++++++---------- 1 file changed, 164 insertions(+), 59 deletions(-) (limited to 'src/jrummikub/control/AIUtil.java') 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, Integer> stoneCounts; + int jokerCount; + + SearchState(int pointsMissing, + TreeMap, 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, Integer> findSetsWithTotalPoints( + int pointsMissing, TreeMap, Integer> stoneCounts, int jokerCount) { if (pointsMissing <= 0) { - return true; + return new Pair, Integer>( + Collections. emptyList(), 0); } stoneCounts = (TreeMap, Integer>) stoneCounts .clone(); + Pair, Integer> result, bestResult; + bestResult = new Pair, Integer>( + Collections. emptyList(), 0); + for (int value = 13; value >= 1; value--) { for (StoneColor color : StoneColor.values()) { Pair stone = new Pair(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, Integer> stoneCounts, int jokerCount, - Pair stone, int groupSize) { + private static Pair, Integer> findGroupsWithTotalPoints( + SearchState searchState, int value, List chosenColors, + StoneColor testedColor) { + + StoneColor nextColor = getNextColor(testedColor); + Pair nextStone = new Pair(value, + nextColor); - StoneColor nextColor = getNextColor(stone.getSecond()); - Pair nextStone = new Pair( - stone.getFirst(), nextColor); + Pair, Integer> result, bestResult; + bestResult = new Pair, Integer>( + Collections. 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 newColors = new ArrayList(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 newColors = new ArrayList(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 newStones = new ArrayList(); + for (StoneColor color : chosenColors) { + newStones.add(new Stone(value, color)); + } + List newResultList = new ArrayList(result.getFirst()); + newResultList.add(new StoneSet(newStones)); + result = new Pair, 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, Integer> stoneCounts, int jokerCount, - Pair stone, int runLength) { + private static Pair, Integer> findRunsWithTotalPoints( + SearchState searchState, Pair testedStone, + int runLength) { + + Pair, Integer> result, bestResult; + bestResult = new Pair, Integer>( + Collections. emptyList(), 0); Pair nextStone = null; - if (stone.getFirst() > 1) { - int nextValue = stone.getFirst() - 1; - nextStone = new Pair(nextValue, stone.getSecond()); + if (testedStone.getFirst() > 1) { + int nextValue = testedStone.getFirst() - 1; + nextStone = new Pair(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 newStones = new ArrayList(); + for (int i = 0; i < runLength; i++) { + newStones.add(new Stone(i + testedStone.getFirst(), testedStone + .getSecond())); + } + List newResultList = new ArrayList(result.getFirst()); + newResultList.add(new StoneSet(newStones)); + result = new Pair, 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( -- cgit v1.2.3