package jrummikub.ai; 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 jrummikub.model.GameSettings; import jrummikub.model.Stone; import jrummikub.model.StoneColor; import jrummikub.model.StoneSet; import jrummikub.util.Pair; public class TurnLogic { private GameSettings settings; private int stoneCount; private List inputStones; private StoneColor maxColor; private StoneColor minColor; private ArrayList stoneColors; private volatile State bestState; private ArrayList stack = new ArrayList(); private State top; private volatile boolean abort = false; private volatile boolean autoAbort = false; private int neededPoints = 0; private double neededScore = 0; @SuppressWarnings("serial") private static class Contradiction extends Throwable { } private class State { ArrayList stones = new ArrayList(); HashSet changedStones = new HashSet(); ArrayList jokerIDs = new ArrayList(); public State() { } public State(State state) { for (StoneState stone : state.stones) { stones.add(new StoneState(stone)); } jokerIDs = state.jokerIDs; } public void add(StoneState stone) { stones.add(stone); changedStones.add(stones.size() - 1); if (stone.joker) { jokerIDs.add(stone.id); } } public void updateStones() throws Contradiction { checkJokers(); for (int i : changedStones) { stones.get(i).checkState(); } checkScoreAndPoints(); while (!changedStones.isEmpty()) { updateStonesStep(); checkScoreAndPoints(); } } 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; } public boolean isSolved() { for (StoneState stone : stones) { if (!stone.isSolved()) { return false; } } return true; } 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)); if (right.leftGroup.remove(groupID)) { changedStones.add(jokerIDs.get(j)); } if (right.leftRun.remove(runID)) { changedStones.add(jokerIDs.get(j)); } } } } public void checkScoreAndPoints() throws Contradiction { if (getPoints() < neededPoints) { throw new Contradiction(); } if (getScore() <= neededScore) { throw new Contradiction(); } } 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 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 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; } public boolean isInterested(HashSet changes) { return !(Collections.disjoint(changes, leftRun) && Collections.disjoint(changes, rightRun) && Collections.disjoint(changes, leftGroup) && Collections .disjoint(changes, rightGroup)); } public > boolean lessThan(T a, T b) { return a == null || b == null || a.compareTo(b) < 0; } public boolean same(T a, T b) { return a == null || b == null || a.equals(b); } public boolean step(Integer a, Integer b) { return a == null || b == null || (int) a == b - 1; } public boolean cycleStep(Integer a, Integer b) { return a == null || b == null || (int) a == b - 1 || a == settings.getHighestValue() && b == 1; } 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); } 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 { if (((Integer) 1).equals(other.value) || ((Integer) settings.getHighestValue()).equals(value)) { return false; } return step(value, other.value); } } public boolean update(HashSet changes) throws Contradiction { boolean changed = false; changed |= updateRuns(changes); changed |= updateGroups(changes); changed |= checkState(); return changed; } 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; } 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; } 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; } 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)); } @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); } } 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); } if (leftGroup.isEmpty() || rightGroup.isEmpty() || leftRun.isEmpty() || rightRun.isEmpty()) { if (onTable == Boolean.TRUE) { throw new Contradiction(); } if (onTable == null) { onTable = false; leftRun.clear(); rightRun.clear(); leftGroup.clear(); rightGroup.clear(); changed = true; } } if ((isSingleNonNullSet(leftGroup) || isSingleNonNullSet(rightGroup)) && (isSingleNonNullSet(leftRun) || isSingleNonNullSet(rightRun))) { throw new Contradiction(); } 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; } if (!((isNullSet(leftRun) && isNullSet(rightRun)) || (isNullSet(leftGroup) && isNullSet(rightGroup)))) { 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; } } private static boolean isNullSet(HashSet i) { return i.size() == 1 && i.contains(null); } private static boolean isSingleNonNullSet(HashSet i) { return i.size() == 1 && !i.contains(null); } 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>(); inputStones = 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())); inputStones.add(pair.getFirst()); } } public void needIntialMeldThreshold() { neededPoints = settings.getInitialMeldThreshold(); } private void pop() { stack.remove(stack.size() - 1); if (!stack.isEmpty()) { top = stack.get(stack.size() - 1); } } private void replace() { stack.remove(stack.size() - 1); } private void pushes(State... states) { for (State state : states) { stack.add(state); } } private void done() { top = stack.get(stack.size() - 1); } public void abort() { abort = true; } public List getResult() { State result = bestState; if (result == null) { return null; } ArrayList outputSets = new ArrayList(); for (int i = 0; i < stoneCount; i++) { StoneState stone = result.stones.get(i); if (isNullSet(stone.leftRun) && isNullSet(stone.leftGroup)) { ArrayList setStones = new ArrayList(); while (true) { setStones.add(inputStones.get(stone.id)); if (isNullSet(stone.rightRun) && isNullSet(stone.rightGroup)) { break; } Integer rightRunID = stone.rightRun.iterator().next(); Integer rightGroupID = stone.rightGroup.iterator().next(); stone = result.stones.get(rightRunID == null ? rightGroupID : rightRunID); } outputSets.add(new StoneSet(setStones)); } } return outputSets; } public boolean solve() { if (top.isSolved()) { pop(); } while (stack.size() != 0) { if (abort) { return false; } try { top.updateStones(); if (top.isSolved()) { bestState = top; return true; } branch(); done(); } catch (Contradiction c) { pop(); } } return false; } public double optimize() { while (!autoAbort && solve()) { neededScore = top.getScore(); } return neededScore; } private void branch() throws Contradiction { for (int i = 0; i < stoneCount; 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); } 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); } 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); } 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); } 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; } } // This should never happen throw new Error("Internal AI error"); } public void autoAbort() { if (bestState != null) { abort = true; } autoAbort = true; } }