/* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ import java.awt.*; import java.awt.event.*; import java.util.*; import java.util.concurrent.*; import javax.swing.*; import javax.swing.event.*; /** * Microscope implements a version of the 7th Guest * game found looking in the Microscope in the laboratory. * See * Microscope version for instructions. *
* The code has been mangled beyond recognition
* as a test of ForkJoin.
*/
public class Microscope extends JPanel {
static final CountDownLatch cd = new CountDownLatch(1);
/*
* If true, the move finder uses a repeatable evaluation
* strategy, so all self-play games at same level have same outcome.
* This is useful for testing purposes, but much less fun to watch.
*/
static boolean DETERMINISTIC = false;
static boolean headless = false;
// Command-line parameters
static int nprocs;
static int lookAheads = 4;
static boolean autostart = true;
static ForkJoinPool group;
static long startTime;
public static void main(String[] args) throws Exception {
nprocs = 0;
try {
if (args.length > 0) {
nprocs = Integer.parseInt(args[0]);
autostart = false;
if (args.length > 1) {
autostart = true;
lookAheads = Integer.parseInt(args[1]);
DETERMINISTIC = true;
}
}
}
catch (Exception e) {
System.out.println("Usage: java Microscope
* Boards are not immutable, but are never passed around across
* threads (instead new ones are constructed), so don't
* need any synch.
*/
static final class Board {
/*
First, some Constants and utilities that might as well be here
*/
public static final int RANKS = 7;
public static final int CELLS = RANKS * RANKS;
static final long FULL = (1L << CELLS) - 1;
// The finder uses a spare bit to remember whose move it is.
static final long BLUEBIT = (1L << CELLS);
// Bits representing the adjacent cells for every position
static final long[] adjacentMasks = new long[CELLS];
// bit pattern associated with each tile
static final long[] cellBits = new long[CELLS];
// locations of all cells reachable by a jump for every position
static final byte[][] jumpDestinations = new byte[CELLS][];
// initialize tables
static {
byte[] dests = new byte[CELLS];
for (int j = 0; j < RANKS; ++j) {
for (int i = 0; i < RANKS; ++i) {
int k = i + j * RANKS;
long nmask = 0;
int jumpCount = 0;
for (int c = j-2; c <= j+2; ++c) {
for (int r = i-2; r <= i+2; ++r) {
if (c >= 0 && c < RANKS &&
r >= 0 && r < RANKS) {
int cellIndex = r + c * RANKS;
if (r == i-2 || r == i+2 || c == j-2 || c == j+2) {
dests[jumpCount++] = (byte)cellIndex;
}
else if (!(r == i && c == j)) {
nmask |= 1L << cellIndex;
}
}
}
}
adjacentMasks[k] = nmask;
cellBits[k] = 1L << k;
jumpDestinations[k] = new byte[jumpCount];
for (int l = 0; l < jumpCount; ++l)
jumpDestinations[k][l] = dests[l];
}
}
}
public static boolean inBounds(int row, int col) {
return (0 <= row) && (row < RANKS) && (0 <= col) && (col < RANKS);
}
// The representation
long blue_; // bit vector; true if occupied by blue
long green_; // same for green;
// constructors and intializers:
public Board() { blue_ = 0L; green_ = 0L; }
public Board(Board b) { blue_ = b.blue_; green_ = b.green_; }
public Board(long b, long g) { blue_ = b; green_ = g; }
public void copyState(Board b) {
blue_ = b.blue_;
green_ = b.green_;
}
void reset() {
blue_ = 0L; green_ = 0L;
}
long getBlue() { return blue_; }
long getGreen() { return green_; }
public Player occupant(int row, int col) {
if ((0 <= row) && (row < RANKS) && (0 <= col) && (col < RANKS)) {
long m = 1L << (row + col * RANKS);
if ((blue_ & m) != 0L) return Player.Blue;
else if ((green_ &m) != 0L) return Player.Green;
else return Player.Empty;
}
else
return Player.Illegal;
}
// place a tile without taking opponent tiles
public void occupy(Player player, int row, int col) {
long m = 1L << (row + col * RANKS);
long nm = ~m;
if (player.code_ == Player.BLUE) {
blue_ |= m;
green_ &= nm;
}
else if (player.code_ == Player.GREEN) {
blue_ &= nm;
green_ |= m;
}
else {
blue_ &= nm;
green_ &= nm;
}
}
public void unoccupy(int row, int col) {
long nm = ~(1L << (row + col * RANKS));
blue_ &= nm;
green_ &= nm;
}
// place a tile, taking all adjacent tiles of opponent
public void take(Player player, int row, int col) {
int k = row + col * RANKS;
long dest = 1L << k;
long nbrMask = adjacentMasks[k];
long sourceBlue = blue_;
long sourceGreen = green_;
if (player.code_ == Player.BLUE) {
blue_ = sourceBlue | dest | (sourceGreen & nbrMask);
green_ = sourceGreen & ~(sourceGreen & nbrMask);
}
else {
blue_ = sourceBlue & ~(sourceBlue & nbrMask);
green_ = sourceGreen | dest | (sourceBlue & nbrMask);
}
}
public boolean gameOver() {
return
(((blue_ | green_) & FULL) == FULL) ||
((blue_ & ~BLUEBIT) == 0) ||
((green_ & ~BLUEBIT) == 0);
}
public int score(Player player) {
if (player.isBlue()) {
return score(blue_, green_);
}
else {
return score(green_, blue_);
}
}
static int score(long b, long g) {
// much faster by splitting into ints
// and using clever shift-based bit counter
int lb = (int)(b & ((1L << 32) - 1));
int hb = ((int)(b >>> 32)) & ((1 << (CELLS - 32)) - 1);
lb -= (0xaaaaaaaa & lb) >>> 1;
lb = (lb & 0x33333333) + ((lb >>> 2) & 0x33333333);
lb = lb + (lb >>> 4) & 0x0f0f0f0f;
lb += lb >>> 8;
lb += lb >>> 16;
hb -= (0xaaaaaaaa & hb) >>> 1;
hb = (hb & 0x33333333) + ((hb >>> 2) & 0x33333333);
hb = hb + (hb >>> 4) & 0x0f0f0f0f;
hb += hb >>> 8;
hb += hb >>> 16;
hb = ((lb + hb) & 0xff);
int lg = (int)(g & ((1L << 32) - 1));
int hg = ((int)(g >>> 32)) & ((1 << (CELLS - 32)) - 1);
lg -= (0xaaaaaaaa & lg) >>> 1;
lg = (lg & 0x33333333) + ((lg >>> 2) & 0x33333333);
lg = lg + (lg >>> 4) & 0x0f0f0f0f;
lg += lg >>> 8;
lg += lg >>> 16;
hg -= (0xaaaaaaaa & hg) >>> 1;
hg = (hg & 0x33333333) + ((hg >>> 2) & 0x33333333);
hg = hg + (hg >>> 4) & 0x0f0f0f0f;
hg += hg >>> 8;
hg += hg >>> 16;
return hb - ((lg + hg) & 0xff);
}
static int slowscore(long b, long g) {
int score = 0;
for (int l = 0; l < CELLS; ++l) {
score += (int)(b & 1);
b >>>= 1;
score -= (int)(g & 1);
g >>>= 1;
}
return score;
}
}
/**
* Moves represent transitions across Board states
*/
static final class Move {
static final int NO_VALUE = -1; // row/col value if not yet set
static final int PASS_VALUE = -2; // special value for pass moves
// utilities for classifying moves
public static boolean twoFrom(int a, int b) {
return (a - b == 2) || (b - a == 2);
}
public static boolean withinTwo(int a, int b) {
int diff = a - b; return -2 <= diff && diff <= 2;
}
// representations
int fromRow;
int fromCol;
int toRow;
int toCol;
Player player_;
Board board_;
boolean committed = false; // true if board reflects move
// constructors and intializers
public Move(Player turn, Board board) {
fromRow = NO_VALUE; fromCol = NO_VALUE;
toRow = NO_VALUE; toCol = NO_VALUE;
player_ = turn;
board_ = board;
}
public Move(Player turn, Board board, boolean isCommitted) {
fromRow = NO_VALUE; fromCol = NO_VALUE;
toRow = NO_VALUE; toCol = NO_VALUE;
player_ = turn;
board_ = board;
committed = isCommitted;
}
synchronized void reset() {
fromRow = NO_VALUE;
fromCol = NO_VALUE;
toRow = NO_VALUE;
toCol = NO_VALUE;
}
// setters:
synchronized void player(Player p) { player_ = p; }
synchronized void board(Board b) { board_ = b; }
synchronized void from(int sr, int sc) { fromRow = sr; fromCol = sc; }
synchronized void to(int dr, int dc) { toRow = dr; toCol = dc; }
// accessors:
synchronized boolean isFrom(int r, int c) {
return fromRow== r && fromCol == c;
}
synchronized boolean isTo(int r, int c) {
return toRow == r && toCol == c;
}
synchronized Board board() {
return board_;
}
synchronized Player player() {
return player_;
}
// status checks:
synchronized boolean isPass() { // is this a `pass' move?
return (toRow == PASS_VALUE || fromRow == PASS_VALUE);
}
synchronized boolean isJump() {
return
(fromRow - toRow == 2) || (toRow - fromRow == 2) ||
(fromCol - toCol == 2) || (toCol - fromCol == 2);
}
synchronized boolean hasFrom() { // is from set?
return fromRow != NO_VALUE && fromCol != NO_VALUE;
}
synchronized boolean hasTo() { // is to set?
return toRow != NO_VALUE && toCol != NO_VALUE;
}
synchronized boolean possibleTo(int r, int c) { // is (r, c) a legal `to'?
return hasFrom() &&
withinTwo(fromRow, r) &&
withinTwo(fromCol, c) &&
board_.occupant(r, c).isEmpty();
}
synchronized boolean isLegal() {
if (isPass())
return true;
else if (!board_.occupant(toRow, toCol).isEmpty())
return false;
else if (!board_.occupant(fromRow, fromCol).same(player_))
return false;
else if (!(withinTwo(fromRow, toRow) && withinTwo(fromCol, toCol)))
return false;
else
return true;
}
synchronized void commit() { // update board to reflect move
if (!committed) {
committed = true;
if (isLegal() && !isPass()) {
if (isJump()) board_.occupy(Player.Empty, fromRow, fromCol);
board_.take(player_, toRow, toCol);
}
}
}
}
/**
* Mover is an abstract class to simplify code dealing with
* either user moves or auto moves.
*/
abstract static class Mover {
// caller for move callbacks
protected Microscope game;
protected Mover(Microscope ap) { game = ap; }
// start a turn as player on given board
public abstract void startTurn(Board b, Player p);
// cancel current partial move
public abstract void cancel();
// return true if move not yet ready
public abstract boolean placing();
}
/**
* User builds moves via instructions/clicks by users
*/
static class User extends Mover {
private Move current;
public User(Microscope ap) { super(ap); current = null; }
public synchronized void startTurn(Board b, Player p) {
current = new Move(p, b);
}
public boolean placing() {
return current != null && current.hasFrom() && !current.hasTo();
}
public synchronized void cancel() {
if (current != null) {
current.reset();
current = null;
}
}
public synchronized void choose(int row, int col) {
if (current != null) {
if (row == Move.PASS_VALUE) {
current.from(row, col);
game.move(current, this);
current = null;
}
else if (!current.hasFrom()) {
if (current.board().occupant(row, col).same(current.player())) {
current.from(row, col);
}
}
else {
current.to(row, col);
game.move(current, this);
current = null;
}
}
}
public synchronized boolean canMoveTo(int row, int col) {
return placing() && current.possibleTo(row, col);
}
public synchronized boolean hasMovedFrom(int row, int col) {
return current != null && current.isFrom(row, col);
}
}
/**
* AutoMover constructs Finders that compute actual moves
*/
static class AutoMover extends Mover {
boolean cancelled = false;
RootFinder currentFinder = null;
public AutoMover(Microscope ap) {
super(ap);
}
public synchronized boolean placing() {
return currentFinder != null;
}
synchronized void stopPlacing() {
currentFinder = null;
}
public synchronized void cancel() {
if (placing()) {
currentFinder.cancel(false);
stopPlacing();
}
}
public synchronized void startTurn(Board board, Player player) {
if (!placing()) {
currentFinder = new RootFinder(board, player,
Microscope.lookAheads, this);
group.execute(currentFinder);
}
}
synchronized void relay(Move move) { // relay callback from finder
if (placing()) {
stopPlacing();
game.move(move, this);
}
}
}
/**
* Implements a classic all-possible-move search algorith using
* ForkJoinTasks. The move finder is not all that smart. Among
* other possible improvements, it could keep a cache of explored
* moves and avoid repeating them. This would likely speed it up
* since most expansions are duplicates of others. It could also
* be changed to prune moves, although this is unlikely to work
* well without better partial evaluation functions.
*/
static class Finder extends RecursiveAction {
static final int NOMOVE = Integer.MIN_VALUE;
static final int LOSE = NOMOVE+1;
static final int WIN = -LOSE;
final long ours; // bits for our tiles
final long theirs; // bits for opponent tiles
final int level; // current number of lookAheads
final Finder next; // Each Finder is placed in a linked list by parent
// Assigned once; must be volatile since accessed by parents
volatile int bestScore;
Finder(long ours, long theirs, int level, Finder next) {
this.ours = ours;
this.theirs = theirs;
this.level = level;
this.next = next;
}
protected final void compute() {
// Handle sure wins and losses here
if ((ours & ~Board.BLUEBIT) == 0)
bestScore = LOSE;
else if ((theirs & ~Board.BLUEBIT) == 0)
bestScore = WIN;
else if (((ours | theirs) & Board.FULL) == Board.FULL) {
int score = Board.score(ours, theirs);
if (score > 0) bestScore = WIN;
else if (score < 0) bestScore = LOSE;
else bestScore = 0;
}
else
search();
}
final void search() {
int best = NOMOVE; // For direct evaluation when level == 1
Finder forked = null; // list of forked subtasks when level > 1
long open = ~(ours | theirs); // currently empty cells
long here = 1; // traverse through bits
for (int k = 0; k < Board.CELLS; ++k, here <<= 1) {
if ((here & ours) != 0) {
/*
* Step through possible destinations to find
* jumps for this tile
*/
byte[] dests = Board.jumpDestinations[k];
for (int j = 0; j < dests.length; ++j) {
byte d = dests[j];
long dest = 1L << d;
if ( (dest & open) != 0) {
long adjacent = Board.adjacentMasks[d];
long nTheirs = theirs & ~adjacent;
long nOurs = (ours & ~here) | dest | (theirs & adjacent);
if (level > 1)
(forked =
new Finder(nTheirs, nOurs, level-1, forked)).fork();
else {
int sc = Board.score(nOurs, nTheirs);
if (sc > best) best = sc;
}
}
}
}
else if ((here & open) != 0) {
/*
* If this cell is open, and is within 1 of one of
* our tiles, it can be taken in some copy move.
* It doesn't matter which of the adjacent cells
* is considered to be source of copy move
*/
long adjacent = Board.adjacentMasks[k];
if ((ours & adjacent) != 0) {
long nTheirs = theirs & ~adjacent;
long nOurs = ours | here | (theirs & adjacent);
if (level > 1)
(forked = new Finder(nTheirs, nOurs, level-1, forked)).fork();
else {
int sc = Board.score(nOurs, nTheirs);
if (sc > best) best = sc;
}
}
}
}
if (level > 1)
collect(forked);
else
bestScore = best;
}
/**
* Join all subtasks and evaluate moves. Default is sub-finder version.
* Overridden in RootFinder.
*/
void collect(Finder forked) {
int best = NOMOVE;
while (forked != null) {
while (!forked.isDone()) {
// interleave joins with status checks
if (isDone()) {
cancelAll(forked);
return;
}
else {
ForkJoinTask> t = pollTask();
if (t != null)
t.quietlyInvoke();
}
}
int score = -forked.bestScore; // negate opponent score
if (score > best) {
best = score;
if (score >= WIN) {
cancelAll(forked.next);
break;
}
}
forked = forked.next;
}
bestScore = best;
}
/**
* Cancels all forked subtasks in list.
*/
void cancelAll(Finder forked) {
while (forked != null) {
forked.cancel(false);
forked = forked.next;
}
}
}
/**
* Root Finder class -- wait out other finders and issue callback to game.
*/
static class RootFinder extends Finder {
final AutoMover automover;
final Player player;
RootFinder(Board board, Player p, int level, AutoMover automover) {
super( (p.isBlue() ? (board.getBlue()| Board.BLUEBIT) : board.getGreen()),
(p.isBlue() ? board.getGreen() : (board.getBlue()| Board.BLUEBIT)),
level,
null);
this.player = p;
this.automover = automover;
}
/**
* This differs from default version by recording
* and calling back with best move
*/
void collect(Finder forked) {
int best = NOMOVE;
Finder bestFinder = null;
while (forked != null) {
while (!forked.isDone()) {
if (isDone()) {
cancelAll(forked);
return;
}
else {
ForkJoinTask> t = pollTask();
if (t != null)
t.quietlyInvoke();
}
}
int score = -forked.bestScore; // negate opponent score
if (bestFinder == null || score > best) {
best = score;
bestFinder = forked;
if (score >= WIN) {
cancelAll(forked.next);
break;
}
}
// Just for fun, introduce a little randomness via hashcodes
else if (score == best &&
!Microscope.DETERMINISTIC &&
(System.identityHashCode(forked) >
System.identityHashCode(bestFinder))) {
bestFinder = forked;
}
forked = forked.next;
}
Move move = null;
if (bestFinder != null) {
/*
Even though accessed here,
the ours and theirs vars of Finders do not
need to be volatile because they are immutably
established in constructors.
*/
long nextOurs = bestFinder.theirs;
long nextTheirs = bestFinder.ours;
long blue = player.isBlue() ? nextOurs : nextTheirs;
long green = player.isBlue() ? nextTheirs : nextOurs;
move = new Move(player, new Board(blue, green), true);
}
automover.relay(move);
}
}
}