From e06ba8ea1346e5045a34508648ac93150aacb01a Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Fri, 17 Jun 2011 17:41:52 +0200 Subject: Reimplemented AI (old one was too slow) git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@443 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/TurnLogic.java | 892 +++++++++++++++++++++++++--------------- 1 file changed, 567 insertions(+), 325 deletions(-) (limited to 'src/jrummikub/ai/TurnLogic.java') diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java index e736361..8318773 100644 --- a/src/jrummikub/ai/TurnLogic.java +++ b/src/jrummikub/ai/TurnLogic.java @@ -1,391 +1,633 @@ package jrummikub.ai; -import static jrummikub.ai.fdsolver.Constraints.constant; -import static jrummikub.ai.fdsolver.Constraints.index; -import static jrummikub.ai.fdsolver.Constraints.lessThan; -import static jrummikub.ai.fdsolver.Constraints.lessThanEq; -import static jrummikub.ai.fdsolver.Constraints.offset; -import static jrummikub.ai.fdsolver.Constraints.same; -import static jrummikub.ai.fdsolver.Constraints.sum; -import static jrummikub.ai.fdsolver.Constraints.unless; -import static jrummikub.ai.fdsolver.Constraints.when; - import java.util.ArrayList; +import java.util.Arrays; import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; import java.util.HashSet; import java.util.List; -import java.util.Set; -import jrummikub.ai.fdsolver.Constraint; -import jrummikub.ai.fdsolver.Solver; -import jrummikub.ai.fdsolver.Var; import jrummikub.model.GameSettings; import jrummikub.model.Stone; import jrummikub.model.StoneColor; +import jrummikub.util.Pair; -/** - * Provides Humanlike Advanced Logic (HAL) that models the options given to a - * player in a turn to the Solver MCP. - */ public class TurnLogic { - private Solver solver = new Solver(); - private GameSettings settings; - private int stoneCount; - private int maxSetSize; - private int maxHandPoints; + GameSettings settings; + int stoneCount; + StoneColor maxColor; + StoneColor minColor; + ArrayList stoneColors; + + ArrayList stack = new ArrayList(); + State top; + + int neededPoints = 0; + double neededScore = Double.NEGATIVE_INFINITY; + + @SuppressWarnings("serial") + private static class Contradiction extends Throwable { - private Var trueVar; - private Var totalPoints; + } - private List> onTable = new ArrayList>(); + private class State { + ArrayList stones = new ArrayList(); + HashSet changedStones = new HashSet(); + ArrayList jokerIDs = new ArrayList(); - private List> pointsValue = new ArrayList>(); + public State() { + } - private List> stoneValue = new ArrayList>(); - private List> leftStoneValue = new ArrayList>(); - private List> rightStoneValue = new ArrayList>(); + public State(State state) { + for (StoneState stone : state.stones) { + stones.add(new StoneState(stone)); + } + jokerIDs = state.jokerIDs; + } - private List> stoneColor = new ArrayList>(); - private List> leftStoneColor = new ArrayList>(); - private List> rightStoneColor = new ArrayList>(); + public void add(StoneState stone) { + stones.add(stone); + changedStones.add(stones.size() - 1); + if (stone.joker) { + jokerIDs.add(stone.id); + } + } - private List> lowCount = new ArrayList>(); - private List> leftLowCount = new ArrayList>(); - private List> rightLowCount = new ArrayList>(); + public void updateStones() throws Contradiction { + checkJokers(); + for (int i : changedStones) { + stones.get(i).checkState(); + } + checkScoreAndPoints(); + while (!changedStones.isEmpty()) { + updateStonesStep(); + checkScoreAndPoints(); + } + } - private List> highCount = new ArrayList>(); - private List> leftHighCount = new ArrayList>(); - private List> rightHighCount = new ArrayList>(); + public void updateStonesStep() throws Contradiction { + HashSet newChangedStones = new HashSet(); + for (int i = 0; i < stoneCount; i++) { + StoneState stone = stones.get(i); + if (stone.isInterested(changedStones)) { + if (stone.update(changedStones)) { + newChangedStones.add(i); + } + } + } + changedStones = newChangedStones; + } - private List> setSize = new ArrayList>(); + public boolean isSolved() { + for (StoneState stone : stones) { + if (!stone.isSolved()) + return false; + } + return true; + } - private List> isRun = new ArrayList>(); + public void checkJokers() throws Contradiction { + for (int i = 0; i < jokerIDs.size(); i++) { + StoneState left = stones.get(jokerIDs.get(i)); + + HashSet leftLeftGroup = new HashSet( + left.leftGroup); + HashSet leftLeftRun = new HashSet( + left.leftRun); + leftLeftGroup.remove(null); + leftLeftRun.remove(null); + int runID, groupID; + if (leftLeftGroup.isEmpty()) { + groupID = -1; + } else { + groupID = Collections.min(leftLeftGroup); + } + if (leftLeftRun.isEmpty()) { + runID = -1; + } else { + runID = Collections.min(leftLeftRun); + } + for (int j = i + 1; j < jokerIDs.size(); j++) { + StoneState right = stones.get(jokerIDs.get(j)); - private List> leftNeighbor = new ArrayList>(); - private List> rightNeighbor = new ArrayList>(); + if (right.leftGroup.remove(groupID)) { + changedStones.add(jokerIDs.get(j)); + } + if (right.leftRun.remove(runID)) { + changedStones.add(jokerIDs.get(j)); + } + } + } + } - private List> stoneID = new ArrayList>(); + public void checkScoreAndPoints() throws Contradiction { + if (getPoints() < neededPoints) { + throw new Contradiction(); + } + if (getScore() <= neededScore) { + throw new Contradiction(); + } + } - private List> hasLeftNeighbor = new ArrayList>(); - private List> hasRightNeighbor = new ArrayList>(); + public int getPoints() { + int sum = 0; + for (StoneState stone : stones) { + if (stone.onTable != Boolean.FALSE) { + sum += stone.getPoints(); + } + } + return sum; + } + + public double getScore() { + double sum = 0; + for (StoneState stone : stones) { + if (stone.onTable != Boolean.FALSE) { + sum += stone.getScore(); + } + + } + return sum; + } + } - private List isJoker = new ArrayList(); + private class StoneState { + int id; + boolean joker; + Integer value; + StoneColor color; + Boolean onTable; + boolean fromTable; + HashSet leftRun; + HashSet rightRun; + HashSet leftGroup; + HashSet rightGroup; + + public StoneState(int id, Stone stone, boolean table) { + this.id = id; + joker = stone.isJoker(); + if (!joker) { + this.value = stone.getValue(); + this.color = stone.getColor(); + } + onTable = table ? true : null; + fromTable = table; + leftRun = makeFullSet(); + rightRun = makeFullSet(); + leftGroup = makeFullSet(); + rightGroup = makeFullSet(); + } - public TurnLogic(GameSettings settings, Collection tableStones, - Collection handStones) { - this.settings = settings; - stoneCount = tableStones.size() + handStones.size(); - maxSetSize = Math.max(settings.getHighestValue(), settings - .getStoneColors().size()); + public StoneState(StoneState stone) { + this.id = stone.id; + this.joker = stone.joker; + this.value = stone.value; + this.color = stone.color; + this.onTable = stone.onTable; + this.fromTable = stone.fromTable; + this.leftRun = new HashSet(stone.leftRun); + this.rightRun = new HashSet(stone.rightRun); + this.leftGroup = new HashSet(stone.leftGroup); + this.rightGroup = new HashSet(stone.rightGroup); + } + + private HashSet makeFullSet() { + HashSet set = new HashSet(); + for (int i = 0; i < stoneCount; i++) { + if (i != id) { + set.add(i); + } + } + set.add(null); + return set; + } - trueVar = solver.makeVar(true); + public boolean isInterested(HashSet changes) { + return !(Collections.disjoint(changes, leftRun) + && Collections.disjoint(changes, rightRun) + && Collections.disjoint(changes, leftGroup) && Collections + .disjoint(changes, rightGroup)); + } - maxHandPoints = 0; - int i = 0; - for (Stone stone : tableStones) { - addStone(i, true, stone); - i++; + private boolean isNullSet(HashSet i) { + return i.size() == 1 && i.contains(null); } - for (Stone stone : handStones) { - addStone(i, false, stone); - i++; + + private boolean isSingleNonNullSet(HashSet i) { + return i.size() == 1 && !i.contains(null); } - for (i = 0; i < stoneCount; i++) { - addConstraints(i); + public > boolean lessThan(T a, T b) { + return a == null || b == null || a.compareTo(b) < 0; } - totalPoints = solver.makeRangeVar(settings.getInitialMeldThreshold(), - maxHandPoints); + public boolean same(T a, T b) { + return a == null || b == null || a.equals(b); + } - List> points = new ArrayList>(); + public boolean step(Integer a, Integer b) { + return a == null || b == null || (int) a == b - 1; + } - for (Var var : pointsValue) { - if (var != null) { - points.add(var); - } + public boolean cycleStep(Integer a, Integer b) { + return a == null || b == null || (int) a == b - 1 + || a == settings.getHighestValue() && b == 1; } - add(sum(totalPoints, points)); - } + public boolean groupNeighbor(StoneState other) { + if (isNullSet(leftGroup) && isNullSet(other.rightGroup)) { + return false; + } + if (other.color == minColor || color == maxColor) { + return false; + } + return lessThan(color, other.color) && same(value, other.value); + } - private void addStone(int i, boolean table, Stone stone) { - if (table) { - onTable.add(trueVar); - } else { - onTable.add(solver.makeBoolVar()); - } - isJoker.add(stone.isJoker()); - if (stone.isJoker()) { - stoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); - if (table) { - pointsValue.add(null); - } else { - pointsValue.add(solver.makeRangeVar(0, - settings.getHighestValue())); - maxHandPoints += settings.getHighestValue(); - } - stoneColor.add(solver.makeVar(settings.getStoneColors())); - } else { - stoneValue.add(solver.makeVar(stone.getValue())); - if (table) { - pointsValue.add(null); + public boolean runNeighbor(StoneState other) { + if (isNullSet(leftRun) && isNullSet(other.rightRun)) { + return false; + } + if (!same(color, other.color)) { + return false; + } + if (settings.isNoLimits()) { + return cycleStep(value, other.value); } else { - pointsValue.add(solver.makeVar(0, stone.getValue())); - maxHandPoints += stone.getValue(); + if (((Integer) 1).equals(other.value) + || ((Integer) settings.getHighestValue()).equals(value)) { + return false; + } + return step(value, other.value); } - stoneColor.add(solver.makeVar(stone.getColor())); } - leftStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); - rightStoneValue.add(solver.makeRangeVar(1, settings.getHighestValue())); - leftStoneColor.add(solver.makeVar(settings.getStoneColors())); - rightStoneColor.add(solver.makeVar(settings.getStoneColors())); + public boolean update(HashSet changes) throws Contradiction { + boolean changed = false; + changed |= updateRuns(changes); + changed |= updateGroups(changes); + changed |= checkState(); + return changed; + } - lowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); - leftLowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); - rightLowCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + public boolean updateRuns(HashSet changes) + throws Contradiction { + boolean changed = false; + HashSet relevantChanges = new HashSet(leftRun); + relevantChanges.retainAll(changes); + for (int i : relevantChanges) { + StoneState other = top.stones.get(i); + if (!other.runNeighbor(this) || !other.rightRun.contains(id)) { + leftRun.remove(i); + changed = true; + } else if (other.rightRun.size() == 1 + && other.onTable == Boolean.TRUE) { + changed |= leftRun.retainAll(Arrays.asList(i)); + changed |= onTable != Boolean.TRUE; + onTable = true; + break; + } + } + relevantChanges = new HashSet(rightRun); + relevantChanges.retainAll(changes); + for (int i : relevantChanges) { + StoneState other = top.stones.get(i); + if (!this.runNeighbor(other) || !other.leftRun.contains(id)) { + rightRun.remove(i); + changed = true; + } else if (other.leftRun.size() == 1 + && other.onTable == Boolean.TRUE) { + changed |= rightRun.retainAll(Arrays.asList(i)); + changed |= onTable != Boolean.TRUE; + onTable = true; + break; + } + } + return changed; + } - highCount.add(solver.makeRangeVar(0, maxSetSize - 1)); - leftHighCount.add(solver.makeRangeVar(0, maxSetSize - 1)); - rightHighCount.add(solver.makeRangeVar(0, maxSetSize - 1)); + public boolean updateGroups(HashSet changes) + throws Contradiction { + boolean changed = false; + HashSet relevantChanges = new HashSet(leftGroup); + relevantChanges.retainAll(changes); + for (int i : relevantChanges) { + StoneState other = top.stones.get(i); + if (!other.groupNeighbor(this) + || !other.rightGroup.contains(id)) { + leftGroup.remove(i); + changed = true; + } else if (other.rightGroup.size() == 1 + && other.onTable == Boolean.TRUE) { + changed |= leftGroup.retainAll(Arrays.asList(i)); + changed |= onTable != Boolean.TRUE; + onTable = true; + break; + } + } + relevantChanges = new HashSet(rightGroup); + relevantChanges.retainAll(changes); + for (int i : relevantChanges) { + StoneState other = top.stones.get(i); + if (!this.groupNeighbor(other) || !other.leftGroup.contains(id)) { + rightGroup.remove(i); + changed = true; + } else if (other.leftGroup.size() == 1 + && other.onTable == Boolean.TRUE) { + changed |= rightGroup.retainAll(Arrays.asList(i)); + changed |= onTable != Boolean.TRUE; + onTable = true; + break; + } + } + return changed; + } - setSize.add(solver.makeRangeVar(2, maxSetSize - 1)); + public boolean checkState() throws Contradiction { + boolean changed = false; + if (onTable == Boolean.FALSE) { + if (leftRun.size() + rightRun.size() + leftGroup.size() + + rightGroup.size() != 0) { + leftRun.clear(); + rightRun.clear(); + leftGroup.clear(); + rightGroup.clear(); + return true; + } + return false; + } - isRun.add(solver.makeBoolVar()); + if (!(leftGroup.contains(null) || rightGroup.contains(null))) { + changed |= leftRun.retainAll(Arrays.asList((Integer) null)) + | rightRun.retainAll(Arrays.asList((Integer) null)); + } + if (!(leftRun.contains(null) || rightRun.contains(null))) { + changed |= leftGroup.retainAll(Arrays.asList((Integer) null)) + | rightGroup.retainAll(Arrays.asList((Integer) null)); + } - leftNeighbor.add(solver.makeRangeVar(0, stoneCount - 1)); - rightNeighbor.add(solver.makeRangeVar(0, stoneCount - 1)); + @SuppressWarnings("unchecked") + List> sets = Arrays.> asList( + leftGroup, rightGroup, leftRun, rightRun, leftGroup, + rightGroup, leftRun); + for (int i = 0; i < 4; i++) { + if (isNullSet(sets.get(i)) && isNullSet(sets.get(i + 1)) + && isNullSet(sets.get(i + 2))) { + changed |= sets.get(i + 3).remove(null); + } + } - stoneID.add(solver.makeVar(i)); + if (leftGroup.isEmpty() || rightGroup.isEmpty() + || leftRun.isEmpty() || rightRun.isEmpty()) { + if (onTable == Boolean.TRUE) { + throw new Contradiction(); + } + if (onTable == null) { + onTable = false; + changed = true; + } + } + + if (isSingleNonNullSet(leftRun) + && isNullSet(top.stones.get(leftRun.iterator().next()).leftRun)) { + changed |= rightRun.remove(null); + } + if (isSingleNonNullSet(rightRun) + && isNullSet(top.stones.get(rightRun.iterator().next()).rightRun)) { + changed |= leftRun.remove(null); + } + + if (isSingleNonNullSet(leftGroup) + && isNullSet(top.stones.get(leftGroup.iterator().next()).leftGroup)) { + changed |= rightGroup.remove(null); + } + if (isSingleNonNullSet(rightGroup) + && isNullSet(top.stones.get(rightGroup.iterator().next()).rightGroup)) { + changed |= leftGroup.remove(null); + } + + changed |= checkJoker(); + + return changed; + } + + private boolean checkJoker() { + return false; + } + + public boolean isSolved() { + if (onTable == Boolean.FALSE) { + return true; + } + if (onTable == null || color == null || value == null) { + return false; + } + if (leftRun.size() > 1 || rightRun.size() > 1 + || leftGroup.size() > 1 || rightGroup.size() > 1) { + return false; + } + return true; + } + + public double getScore() { + if (fromTable) { + return 0; + } + return 1; + } + + public double getPoints() { + if (fromTable) { + return 0; + } + if (value == null) + return (double) settings.getHighestValue(); + else + return (double) value; + } + } + + public TurnLogic(GameSettings settings, Collection tableStones, + Collection handStones) { + this.settings = settings; + + stoneCount = tableStones.size() + handStones.size(); + + maxColor = Collections.max(settings.getStoneColors()); + minColor = Collections.min(settings.getStoneColors()); + + stoneColors = new ArrayList(settings.getStoneColors()); + Collections.sort(stoneColors); + + top = new State(); + stack.add(top); + + ArrayList> sortedStones = new ArrayList>(); + + for (Stone stone : tableStones) { + sortedStones.add(new Pair(stone, true)); + } + for (Stone stone : handStones) { + sortedStones.add(new Pair(stone, false)); + } + Collections.sort(sortedStones, new Comparator>() { + @Override + public int compare(Pair o1, Pair o2) { + int cmp; + cmp = ((Boolean) o1.getFirst().isJoker()).compareTo(o2 + .getFirst().isJoker()); + if (cmp != 0) { + return -cmp; + } + cmp = (o1.getFirst().getColor()).compareTo(o2.getFirst() + .getColor()); + if (cmp != 0) { + return cmp; + } + cmp = ((Integer) o1.getFirst().getValue()).compareTo(o2 + .getFirst().getValue()); + return cmp; + } + }); + + int i = 0; + for (Pair pair : sortedStones) { + top.add(new StoneState(i++, pair.getFirst(), pair.getSecond())); + } + } + + public void needIntialMeldThreshold() { + neededPoints = settings.getInitialMeldThreshold(); + } - hasLeftNeighbor.add(solver.makeBoolVar()); - hasRightNeighbor.add(solver.makeBoolVar()); + private void pop() { + stack.remove(stack.size() - 1); + if (!stack.isEmpty()) { + top = stack.get(stack.size() - 1); + } } - private void add(Constraint c) { - solver.addConstraint(c); + private void replace() { + stack.remove(stack.size() - 1); } - private void addConstraints(int i) { - // Linking of neighbors - add(when(hasLeftNeighbor.get(i), - index(stoneID.get(i), leftNeighbor.get(i), rightNeighbor))); - add(unless(hasLeftNeighbor.get(i), constant(leftNeighbor.get(i), 0))); - add(when(hasLeftNeighbor.get(i), - index(trueVar, leftNeighbor.get(i), hasRightNeighbor))); - add(when(hasRightNeighbor.get(i), - index(stoneID.get(i), rightNeighbor.get(i), leftNeighbor))); - add(unless(hasRightNeighbor.get(i), constant(rightNeighbor.get(i), 0))); - add(when(hasRightNeighbor.get(i), - index(trueVar, rightNeighbor.get(i), hasLeftNeighbor))); - // hand stones have no neighbors - add(unless(onTable.get(i), constant(hasLeftNeighbor.get(i), false))); - add(unless(onTable.get(i), constant(hasRightNeighbor.get(i), false))); - - // low/high counts and size - add(unless(hasLeftNeighbor.get(i), constant(lowCount.get(i), 0))); - add(unless(hasRightNeighbor.get(i), constant(highCount.get(i), 0))); - - add(when(hasLeftNeighbor.get(i), - index(leftLowCount.get(i), leftNeighbor.get(i), lowCount))); - add(unless(hasLeftNeighbor.get(i), constant(leftLowCount.get(i), 0))); - - add(when(hasRightNeighbor.get(i), - index(rightLowCount.get(i), rightNeighbor.get(i), lowCount))); - add(unless(hasRightNeighbor.get(i), constant(rightLowCount.get(i), 0))); - - add(when(hasLeftNeighbor.get(i), - index(leftHighCount.get(i), leftNeighbor.get(i), highCount))); - add(unless(hasLeftNeighbor.get(i), constant(leftHighCount.get(i), 0))); - - add(when(hasRightNeighbor.get(i), - index(rightHighCount.get(i), rightNeighbor.get(i), highCount))); - add(unless(hasRightNeighbor.get(i), constant(rightHighCount.get(i), 0))); - - add(when(hasLeftNeighbor.get(i), - index(setSize.get(i), leftNeighbor.get(i), setSize))); - - add(when(hasRightNeighbor.get(i), - index(setSize.get(i), rightNeighbor.get(i), setSize))); - - add(when(hasLeftNeighbor.get(i), - offset(1, leftLowCount.get(i), lowCount.get(i)))); - add(when(hasRightNeighbor.get(i), - offset(1, lowCount.get(i), rightLowCount.get(i)))); - - add(when(hasRightNeighbor.get(i), - offset(1, rightHighCount.get(i), highCount.get(i)))); - add(when(hasLeftNeighbor.get(i), - offset(1, highCount.get(i), leftHighCount.get(i)))); - - add(when(onTable.get(i), - sum(lowCount.get(i), highCount.get(i), setSize.get(i)))); - - add(unless(onTable.get(i), constant(setSize.get(i), 2))); - - // set same rules - add(when(hasLeftNeighbor.get(i), - index(isRun.get(i), leftNeighbor.get(i), isRun))); - add(when(hasRightNeighbor.get(i), - index(isRun.get(i), rightNeighbor.get(i), isRun))); - - add(unless(onTable.get(i), constant(isRun.get(i), false))); - - // rule neighbors - add(when(hasLeftNeighbor.get(i), - index(leftStoneColor.get(i), leftNeighbor.get(i), stoneColor))); - add(unless(hasLeftNeighbor.get(i), - constant(leftStoneColor.get(i), StoneColor.RED))); - add(when(hasRightNeighbor.get(i), - index(rightStoneColor.get(i), rightNeighbor.get(i), stoneColor))); - add(unless(hasRightNeighbor.get(i), - constant(rightStoneColor.get(i), StoneColor.RED))); - - add(when(hasLeftNeighbor.get(i), - index(leftStoneValue.get(i), leftNeighbor.get(i), stoneValue))); - add(unless(hasLeftNeighbor.get(i), constant(leftStoneValue.get(i), 1))); - add(when(hasRightNeighbor.get(i), - index(rightStoneValue.get(i), rightNeighbor.get(i), stoneValue))); - add(unless(hasRightNeighbor.get(i), constant(rightStoneValue.get(i), 1))); - // general rules - - add(when( - hasLeftNeighbor.get(i), - when(isRun.get(i), - lessThanEq(leftStoneValue.get(i), stoneValue.get(i))))); - add(when( - hasRightNeighbor.get(i), - when(isRun.get(i), - lessThanEq(stoneValue.get(i), rightStoneValue.get(i))))); - - add(when( - hasLeftNeighbor.get(i), - when(isRun.get(i), - lessThanEq(leftStoneColor.get(i), stoneColor.get(i))))); - add(when( - hasRightNeighbor.get(i), - when(isRun.get(i), - lessThanEq(stoneColor.get(i), rightStoneColor.get(i))))); - - // run rules - - add(when( - hasLeftNeighbor.get(i), - when(isRun.get(i), - offset(1, leftStoneValue.get(i), stoneValue.get(i))))); - add(when( - hasRightNeighbor.get(i), - when(isRun.get(i), - offset(1, stoneValue.get(i), rightStoneValue.get(i))))); - - add(when( - hasLeftNeighbor.get(i), - when(isRun.get(i), - same(leftStoneColor.get(i), stoneColor.get(i))))); - add(when( - hasRightNeighbor.get(i), - when(isRun.get(i), - same(stoneColor.get(i), rightStoneColor.get(i))))); - - // group rules - add(when( - hasLeftNeighbor.get(i), - unless(isRun.get(i), - same(leftStoneValue.get(i), stoneValue.get(i))))); - add(when( - hasRightNeighbor.get(i), - unless(isRun.get(i), - same(stoneValue.get(i), rightStoneValue.get(i))))); - - add(when( - hasLeftNeighbor.get(i), - unless(isRun.get(i), - lessThan(leftStoneColor.get(i), stoneColor.get(i))))); - add(when( - hasRightNeighbor.get(i), - unless(isRun.get(i), - lessThan(stoneColor.get(i), rightStoneColor.get(i))))); - - // joker defaulting - if (isJoker.get(i)) { - add(unless(onTable.get(i), constant(stoneValue.get(i), 1))); - add(unless(onTable.get(i), - constant(stoneColor.get(i), StoneColor.RED))); - } - - // initial meld points - if (pointsValue.get(i) != null) { - add(when(onTable.get(i), - same(stoneValue.get(i), pointsValue.get(i)))); - add(unless(onTable.get(i), constant(pointsValue.get(i), 0))); + private void pushes(State... states) { + for (State state : states) { + stack.add(state); } } + private void done() { + top = stack.get(stack.size() - 1); + } + public boolean solve() { - Set tableIDs = new HashSet(); - Set leftIDs = new HashSet(); - boolean res = solver.solve(); - if (!res) - return false; - System.out.println("== Hand =="); + if (top.isSolved()) { + pop(); + } + while (stack.size() != 0) { + try { + top.updateStones(); + if (top.isSolved()) { + return true; + } + branch(); + done(); + } catch (Contradiction c) { + pop(); + } + } + return false; + } + + public double optimize() { + while (solve()) { + neededScore = top.getScore(); + } + return neededScore; + } + + private void branch() throws Contradiction { for (int i = 0; i < stoneCount; i++) { - if (onTable.get(i).getValue()) { - tableIDs.add(i); - if (!hasLeftNeighbor.get(i).getValue()) { - leftIDs.add(i); + StoneState stone = top.stones.get(i); + if (stone.onTable == null) { + replace(); + State newState = new State(top); + newState.stones.get(i).onTable = false; + newState.changedStones.add(i); + State altState = new State(top); + altState.stones.get(i).onTable = true; + altState.changedStones.add(i); + pushes(altState, newState); + return; + } + if (stone.leftRun.size() > 1) { + replace(); + for (Integer id : stone.leftRun) { + State newState = new State(top); + newState.stones.get(i).leftRun.clear(); + newState.stones.get(i).leftRun.add(id); + newState.changedStones.add(i); + pushes(newState); } - } else { - outputStone(i); - } - } - System.out.println(""); - System.out.println("== Table =="); - boolean newLine = false; - boolean first = true; - int nextID = -1; // leftIDs.iterator().next(); - while (!tableIDs.isEmpty()) { - if (tableIDs.contains(nextID)) { - tableIDs.remove(nextID); - leftIDs.remove(nextID); - if (newLine) { - if (!first) { - System.out.println(""); - } - first = false; - newLine = false; + return; + } + if (stone.rightRun.size() > 1) { + replace(); + for (Integer id : stone.rightRun) { + State newState = new State(top); + newState.stones.get(i).rightRun.clear(); + newState.stones.get(i).rightRun.add(id); + newState.changedStones.add(i); + pushes(newState); } - outputStone(nextID); - if (!hasRightNeighbor.get(nextID).getValue()) { - newLine = true; - nextID = -1; - } else { - nextID = rightNeighbor.get(nextID).getValue(); + return; + } + if (stone.leftGroup.size() > 1) { + replace(); + for (Integer id : stone.leftGroup) { + State newState = new State(top); + newState.stones.get(i).leftGroup.clear(); + newState.stones.get(i).leftGroup.add(id); + newState.changedStones.add(i); + pushes(newState); } - } else { - if (leftIDs.isEmpty()) { - nextID = tableIDs.iterator().next(); - } else { - nextID = leftIDs.iterator().next(); + return; + } + if (stone.rightGroup.size() > 1) { + replace(); + for (Integer id : stone.rightGroup) { + State newState = new State(top); + newState.stones.get(i).rightGroup.clear(); + newState.stones.get(i).rightGroup.add(id); + newState.changedStones.add(i); + pushes(newState); + } + return; + } + if (stone.color == null) { + replace(); + for (StoneColor color : stoneColors) { + State newState = new State(top); + newState.stones.get(i).color = color; + newState.changedStones.add(i); + pushes(newState); } - newLine = true; + return; + } + if (stone.value == null) { + replace(); + for (int value = 1; value <= settings.getHighestValue(); value++) { + State newState = new State(top); + newState.stones.get(i).value = value; + newState.changedStones.add(i); + pushes(newState); + } + return; } } - System.out.println(""); - System.out.println(""); - return res; - } - - private void outputStone(int i) { - System.out.print("[" - + stoneColor.get(i).getValue().toString().substring(0, 1) - + stoneValue.get(i).getValue() + "]"); - /* - * + "," + leftNeighbor.get(i).getValue() + - * hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + "," - * + rightNeighbor.get(i).getValue() + - * hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() + - * "]"); - */ + // This should never happen + throw new Error("Internal AI error"); } } -- cgit v1.2.3