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 ++++++++++++++++++++++ src/jrummikub/model/Hand.java | 37 +++++---- test/jrummikub/model/HandTest.java | 4 +- 6 files changed, 164 insertions(+), 26 deletions(-) create mode 100644 src/jrummikub/ai/fdsolver/constraint/ListSumConstraint.java 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; + } + +} diff --git a/src/jrummikub/model/Hand.java b/src/jrummikub/model/Hand.java index 681241a..c656afd 100644 --- a/src/jrummikub/model/Hand.java +++ b/src/jrummikub/model/Hand.java @@ -1,12 +1,15 @@ package jrummikub.model; -import static jrummikub.model.StoneTray.Direction.*; +import static jrummikub.model.StoneTray.Direction.LEFT; +import static jrummikub.model.StoneTray.Direction.RIGHT; import java.util.ArrayList; +import java.util.Collections; import java.util.Iterator; import java.util.List; import java.util.TreeMap; +import jrummikub.ai.TurnLogic; import jrummikub.control.AIUtil; import jrummikub.util.Pair; @@ -44,8 +47,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) { double x = pos.getX(); double y = pos.getY(); @@ -56,9 +59,11 @@ 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); } } } @@ -80,29 +85,23 @@ public class Hand extends StoneTray implements IHand { @Override public boolean isInitialMeldPossible(GameSettings settings) { - AIUtil aiUtil = new AIUtil(settings); + List handStones = new ArrayList(); - List stones = new ArrayList(); - - for (Iterator> iter = this.iterator(); iter.hasNext();) { - stones.add(iter.next().getFirst()); + for (Pair entry : this) { + handStones.add(entry.getFirst()); } - Pair, Integer>, Integer> stoneCounts = AIUtil - .countStones(stones); - - Pair, Integer> result = aiUtil.findSetsWithTotalPoints( - settings.getInitialMeldThreshold(), stoneCounts.getFirst(), - stoneCounts.getSecond()); - - return (result.getSecond() >= settings.getInitialMeldThreshold()); + TurnLogic turnLogic = new TurnLogic(settings, + Collections. emptyList(), handStones); + return turnLogic.solve(); } @Override public int getIdenticalStoneCount() { List stones = new ArrayList(); - for (Iterator> iter = this.iterator(); iter.hasNext();) { + for (Iterator> iter = this.iterator(); iter + .hasNext();) { stones.add(iter.next().getFirst()); } diff --git a/test/jrummikub/model/HandTest.java b/test/jrummikub/model/HandTest.java index fa780a5..18db753 100644 --- a/test/jrummikub/model/HandTest.java +++ b/test/jrummikub/model/HandTest.java @@ -221,7 +221,7 @@ public class HandTest { } /** */ - @Test + @Test(timeout = 1000) public void testValidHuge() { List stones = new ArrayList(); for (int i = 1; i <= 10; i++) { @@ -232,7 +232,7 @@ public class HandTest { } /** */ - @Test + @Test(timeout = 1000) public void testInvalidHuge() { testInitialMeld(false, Arrays.asList(new Stone(1, RED), new Stone(2, RED), new Stone(4, RED), new Stone(6, RED), new Stone(8, RED), new Stone(10, -- cgit v1.2.3