From 56dc0f99b1e912da9be32269ca44bb850635b879 Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Tue, 31 May 2011 21:29:27 +0200 Subject: Fixed metrics in AIUtil git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@361 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/control/AIUtil.java | 348 ++++++++++++++++++++------------------ 1 file changed, 186 insertions(+), 162 deletions(-) (limited to 'src/jrummikub/control') diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java index 1501483..2205318 100644 --- a/src/jrummikub/control/AIUtil.java +++ b/src/jrummikub/control/AIUtil.java @@ -27,12 +27,13 @@ public class AIUtil { * settings * * @param settings - * the underlying game settings + * the underlying game settings */ public AIUtil(GameSettings settings) { this.settings = settings; - stoneColors = new ArrayList(Arrays.asList(StoneColor.values())); + stoneColors = new ArrayList(Arrays.asList(StoneColor + .values())); stoneColors.retainAll(settings.getStoneColors()); } @@ -42,85 +43,112 @@ public class AIUtil { int jokerCount; SearchState(int pointsMissing, - TreeMap, Integer> stoneCounts, int jokerCount) { + TreeMap, Integer> stoneCounts, + int jokerCount) { this.pointsMissing = pointsMissing; this.stoneCounts = stoneCounts; this.jokerCount = jokerCount; } } + @SuppressWarnings("serial") + private static class EnoughPoints extends Throwable { + private Pair, Integer> result; + + public EnoughPoints(Pair, Integer> result) { + this.result = result; + } + + public Pair, Integer> getResult() { + return result; + } + } + /** - * 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. + * 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 + * the desired number of points * @param stoneCounts - * the number of each stone + * the number of each stone * @param jokerCount - * the total number of jokers in the game + * the total number of jokers in the game * @return the sets that have the desired point total or the highest found */ @SuppressWarnings("unchecked") public Pair, Integer> findSetsWithTotalPoints( int pointsMissing, - TreeMap, Integer> stoneCounts, int jokerCount) { - - if (pointsMissing <= 0) { - return new Pair, Integer>( - Collections. emptyList(), 0); - } + TreeMap, Integer> stoneCounts, + int jokerCount) { + Pair, Integer> emptyResult = new Pair, Integer>( + Collections. emptyList(), 0); + if (pointsMissing <= 0) + return emptyResult; stoneCounts = (TreeMap, Integer>) stoneCounts .clone(); - Pair, Integer> result, bestResult; - bestResult = new Pair, Integer>( - Collections. emptyList(), 0); - - for (int value = settings.getHighestValue(); value >= 1; value--) { - for (StoneColor color : stoneColors) { - Pair stone = new Pair(value, - color); - - if (stoneCounts.containsKey(stone)) { - decrementStoneCount(stoneCounts, stone); - 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) { - 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; + SearchHelper searchHelper = new SearchHelper(pointsMissing, + new Pair, Integer>( + Collections. emptyList(), 0)); + try { + for (int value = settings.getHighestValue(); value >= 1; value--) { + for (StoneColor color : stoneColors) { + Pair stone = new Pair( + value, color); + + if (stoneCounts.containsKey(stone)) { + SearchState searchState = new SearchState(pointsMissing + - value, stoneCounts, jokerCount); + decrementStoneCount(stoneCounts, stone); + searchHelper.checkResult(findRunsWithTotalPoints( + searchState, stone, 1)); + + searchHelper.checkResult(findGroupsWithTotalPoints( + searchState, value, + Collections.singletonList(color), color)); + } + + if (jokerCount > 0) { + SearchState searchState = new SearchState(pointsMissing + - value, stoneCounts, jokerCount - 1); + searchHelper.checkResult(findRunsWithTotalPoints( + searchState, stone, 1)); + + searchHelper.checkResult(findGroupsWithTotalPoints( + searchState, value, + Collections.singletonList(color), color)); + } } } + } catch (EnoughPoints enoughPoints) { + return enoughPoints.getResult(); } + return searchHelper.getBestResult(); + } + + private static class SearchHelper { + Pair, Integer> bestResult; + int pointsMissing; - return bestResult; + public SearchHelper(int pointsMissing, + Pair, Integer> bestResult) { + this.pointsMissing = pointsMissing; + this.bestResult = bestResult; + } + + public void checkResult(Pair, Integer> result) + throws EnoughPoints { + if (result.getSecond() >= pointsMissing) + throw new EnoughPoints(result); + if (result.getSecond() > bestResult.getSecond()) + bestResult = result; + } + + public Pair, Integer> getBestResult() { + return bestResult; + } } private Pair, Integer> findGroupsWithTotalPoints( @@ -128,129 +156,125 @@ public class AIUtil { StoneColor testedColor) { StoneColor nextColor = getNextColor(testedColor); - Pair nextStone = new Pair(value, - nextColor); - - Pair, Integer> result, bestResult; - bestResult = new Pair, Integer>( - Collections. emptyList(), 0); - - if (nextColor != null) { - if (searchState.stoneCounts.containsKey(nextStone)) { - decrementStoneCount(searchState.stoneCounts, nextStone); - List newColors = new ArrayList(chosenColors); + Pair nextStone = new Pair( + value, nextColor); + + SearchHelper searchHelper = new SearchHelper(searchState.pointsMissing, + new Pair, Integer>( + Collections. emptyList(), 0)); + try { + if (nextColor != null) { + 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 (searchState.stoneCounts.containsKey(nextStone)) { + decrementStoneCount(searchState.stoneCounts, nextStone); + searchHelper.checkResult(findGroupsWithTotalPoints( + searchState, value, newColors, nextColor)); + incrementStoneCount(searchState.stoneCounts, nextStone); + } + if (searchState.jokerCount > 0) { + searchHelper.checkResult(findGroupsWithTotalPoints( + new SearchState(searchState.pointsMissing, + searchState.stoneCounts, + searchState.jokerCount - 1), value, + newColors, nextColor)); + } + searchHelper.checkResult(findGroupsWithTotalPoints(searchState, + value, chosenColors, nextColor)); } - 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 (chosenColors.size() >= 3) { + searchHelper.checkResult(handleFoundGroup(searchState, value, + chosenColors)); } - 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; + } catch (EnoughPoints enoughPoints) { + return enoughPoints.getResult(); } + return searchHelper.getBestResult(); + } - 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; + private Pair, Integer> handleFoundGroup( + SearchState searchState, int value, List chosenColors) { + int groupPoints = chosenColors.size() * value; + Pair, Integer> result = findSetsWithTotalPoints( + searchState.pointsMissing - groupPoints, + searchState.stoneCounts, searchState.jokerCount); + List newStones = new ArrayList(); + for (StoneColor color : chosenColors) { + newStones.add(new Stone(value, color)); } - return bestResult; + List newResultList = new ArrayList( + result.getFirst()); + newResultList.add(new StoneSet(newStones)); + result = new Pair, Integer>(newResultList, + result.getSecond() + groupPoints); + return result; } private Pair, Integer> findRunsWithTotalPoints( SearchState searchState, Pair testedStone, int runLength) { - Pair, Integer> result, bestResult; - bestResult = new Pair, Integer>( - Collections. emptyList(), 0); + SearchHelper searchHelper = new SearchHelper(searchState.pointsMissing, + new Pair, Integer>( + Collections. emptyList(), 0)); + try { + Pair nextStone = null; + if (testedStone.getFirst() > 1) { + int nextValue = testedStone.getFirst() - 1; + nextStone = new Pair(nextValue, + testedStone.getSecond()); + + if (searchState.stoneCounts.containsKey(nextStone)) { + decrementStoneCount(searchState.stoneCounts, nextStone); + searchHelper.checkResult(findRunsWithTotalPoints( + searchState, nextStone, runLength + 1)); + incrementStoneCount(searchState.stoneCounts, nextStone); - Pair nextStone = null; - if (testedStone.getFirst() > 1) { - int nextValue = testedStone.getFirst() - 1; - nextStone = new Pair(nextValue, - testedStone.getSecond()); - - 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 (searchState.jokerCount > 0) { + searchHelper.checkResult(findRunsWithTotalPoints( + new SearchState(searchState.pointsMissing, + searchState.stoneCounts, + searchState.jokerCount - 1), nextStone, + runLength + 1)); + } } - 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) { - - 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())); + if (runLength >= 3) { + searchHelper.checkResult(handleFoundRun(searchState, + testedStone, runLength)); } - List newResultList = new ArrayList(result.getFirst()); - newResultList.add(new StoneSet(newStones)); - result = new Pair, Integer>(newResultList, - result.getSecond() + runPoints); + } catch (EnoughPoints enoughPoints) { + return enoughPoints.getResult(); + } + return searchHelper.getBestResult(); + } - if (result.getSecond() >= searchState.pointsMissing) - return result; - if (result.getSecond() > bestResult.getSecond()) - bestResult = result; + private Pair, Integer> handleFoundRun( + SearchState searchState, Pair testedStone, + int runLength) { + int below = testedStone.getFirst() - 1; + int high = below + runLength; + int runPoints = (high * (high + 1)) / 2 - (below * (below + 1)) / 2; + + Pair, Integer> 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())); } - return bestResult; + List newResultList = new ArrayList( + result.getFirst()); + newResultList.add(new StoneSet(newStones)); + result = new Pair, Integer>(newResultList, + result.getSecond() + runPoints); + return result; } static void incrementStoneCount( @@ -302,7 +326,7 @@ public class AIUtil { * Counts the numbers of stones * * @param stones - * the stones to count + * the stones to count * @return the numbers for all stones */ public static Pair, Integer>, Integer> countStones( -- cgit v1.2.3