From 3ffad8597290f91d21c2a2ba7657bbbc16ab1582 Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Tue, 14 Jun 2011 21:05:15 +0200 Subject: Implemented initial meld test using new AI git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@441 72836036-5685-4462-b002-a69064685172 --- src/jrummikub/ai/TurnLogic.java | 50 ++++++++++-- src/jrummikub/ai/fdsolver/Constraints.java | 5 ++ src/jrummikub/ai/fdsolver/Var.java | 3 + .../ai/fdsolver/constraint/ListSumConstraint.java | 91 ++++++++++++++++++++++ 4 files changed, 144 insertions(+), 5 deletions(-) create mode 100644 src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java (limited to 'src/jrummikub/ai') diff --git a/src/jrummikub/ai/TurnLogic.java b/src/jrummikub/ai/TurnLogic.java index 1ce752c..e736361 100644 --- a/src/jrummikub/ai/TurnLogic.java +++ b/src/jrummikub/ai/TurnLogic.java @@ -32,11 +32,15 @@ public class TurnLogic { private GameSettings settings; private int stoneCount; private int maxSetSize; + private int maxHandPoints; private Var trueVar; + private Var totalPoints; private List> onTable = new ArrayList>(); + private List> pointsValue = new ArrayList>(); + private List> stoneValue = new ArrayList>(); private List> leftStoneValue = new ArrayList>(); private List> rightStoneValue = new ArrayList>(); @@ -76,6 +80,7 @@ public class TurnLogic { trueVar = solver.makeVar(true); + maxHandPoints = 0; int i = 0; for (Stone stone : tableStones) { addStone(i, true, stone); @@ -89,6 +94,19 @@ public class TurnLogic { for (i = 0; i < stoneCount; i++) { addConstraints(i); } + + totalPoints = solver.makeRangeVar(settings.getInitialMeldThreshold(), + maxHandPoints); + + List> points = new ArrayList>(); + + for (Var var : pointsValue) { + if (var != null) { + points.add(var); + } + } + + add(sum(totalPoints, points)); } private void addStone(int i, boolean table, Stone stone) { @@ -100,9 +118,22 @@ public class TurnLogic { 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); + } else { + pointsValue.add(solver.makeVar(0, stone.getValue())); + maxHandPoints += stone.getValue(); + } stoneColor.add(solver.makeVar(stone.getColor())); } @@ -282,6 +313,13 @@ public class TurnLogic { 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))); + } } public boolean solve() { @@ -342,10 +380,12 @@ public class TurnLogic { 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() + - // "]"); + /* + * + "," + leftNeighbor.get(i).getValue() + + * hasLeftNeighbor.get(i).getValue() + lowCount.get(i).getValue() + "," + * + rightNeighbor.get(i).getValue() + + * hasRightNeighbor.get(i).getValue() + highCount.get(i).getValue() + + * "]"); + */ } } diff --git a/src/jrummikub/ai/fdsolver/Constraints.java b/src/jrummikub/ai/fdsolver/Constraints.java index 0885d2a..caa8cfa 100644 --- a/src/jrummikub/ai/fdsolver/Constraints.java +++ b/src/jrummikub/ai/fdsolver/Constraints.java @@ -7,6 +7,7 @@ import jrummikub.ai.fdsolver.constraint.FilterConstraint; import jrummikub.ai.fdsolver.constraint.IfConstraint; import jrummikub.ai.fdsolver.constraint.IndexConstraint; import jrummikub.ai.fdsolver.constraint.LessThan; +import jrummikub.ai.fdsolver.constraint.ListSumConstraint; import jrummikub.ai.fdsolver.constraint.OffsetConstraint; import jrummikub.ai.fdsolver.constraint.SameConstraint; import jrummikub.ai.fdsolver.constraint.SumConstraint; @@ -46,6 +47,10 @@ public class Constraints { return new SumConstraint(x, y, z); } + public static Constraint sum(Var sum, List> list) { + return new ListSumConstraint(sum, list); + } + public static > Constraint lessThan(Var x, Var y) { return new LessThan(false, x, y); } diff --git a/src/jrummikub/ai/fdsolver/Var.java b/src/jrummikub/ai/fdsolver/Var.java index a454487..e885cef 100644 --- a/src/jrummikub/ai/fdsolver/Var.java +++ b/src/jrummikub/ai/fdsolver/Var.java @@ -42,6 +42,9 @@ public class Var implements Comparable> { range.remove(value); solver.logInvalidation(this, value); makeDirty(); + if (range.size() == 0) { + solver.contradiction = true; + } } HashSet getConstraints() { diff --git a/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java new file mode 100644 index 0000000..22f480f --- /dev/null +++ b/src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java @@ -0,0 +1,91 @@ +package jrummikub.ai.fdsolver.constraint; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import jrummikub.ai.fdsolver.Constraint; +import jrummikub.ai.fdsolver.Propagator; +import jrummikub.ai.fdsolver.Satisfiability; +import jrummikub.ai.fdsolver.Var; + +public class ListSumConstraint extends Constraint { + Var sum; + List> list; + List> vars = new ArrayList>(); + + public ListSumConstraint(Var sum, List> list) { + this.sum = sum; + this.list = list; + vars.add(sum); + vars.addAll(list); + } + + @Override + public Collection> getWatchedVars() { + return vars; + } + + @Override + public Collection getPropagators(boolean negate) { + return Collections.emptyList(); + } + + @Override + public Satisfiability getSatisfiability() { + List values = new ArrayList(); + int valueSum = 0; + boolean isTaut = sum.getRange().size()==1; + for (Var var : list) { + Iterator it = var.getRange().iterator(); + int value = it.next(); + if (it.hasNext()) + isTaut = false; + values.add(value); + valueSum += value; + } + if (isTaut) { + if (valueSum == sum.getValue()) { + return Satisfiability.TAUT; + } else { + return Satisfiability.UNSAT; + } + } + + Set reachableValues = new HashSet(); + Set newValues = new HashSet(); + reachableValues.add(valueSum); + + if (sum.getRange().contains(valueSum)) { + return Satisfiability.SAT; + } + + for (int i = 0; i < values.size(); i++) { + Var var = list.get(i); + int offset = values.get(i); + for (int x : var.getRange()) { + if (x == offset) + continue; + newValues.clear(); + for (int y : reachableValues) { + int newValue = x + y - offset; + if (!reachableValues.contains(newValue)) { + newValues.add(x + y - offset); + } + } + if (!Collections.disjoint(sum.getRange(), newValues)) { + return Satisfiability.SAT; + } + reachableValues.addAll(newValues); + } + } + + return Satisfiability.UNSAT; + } + +} -- cgit v1.2.3