test/loops/Microscope.java

/*
 * 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/licenses/publicdomain
 */

import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.awt.event.*;
import javax.swing.event.*;
import java.util.concurrent.*;


/**
 * Microscope implements a version of the 7th Guest
 * game found looking in the Microscope in the laboratory.
 * See <a href="http://gee.cs.oswego.edu/dl/applets/micro.html">
 * Microscope</a> version for instructions.
 * <p>
 * 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 <threads> [<level>]");
            return;
        }
        group = nprocs == 0 ? new ForkJoinPool() : new ForkJoinPool(nprocs);
        startTime = System.currentTimeMillis();
        System.out.print("Score: ");
        oneRun();
        cd.await();
        long now = System.currentTimeMillis();
        System.out.println();
        System.out.println("time: " + (now - startTime) + "ms");
        System.out.println(group.toString());
        System.exit(0);
    }

    static void onExit() {
        long now = System.currentTimeMillis();
        System.out.println("time: " + (now - startTime) + "ms");
        System.out.println(group.toString());
        System.exit(0);
    }

    static void oneRun() {
        if (java.awt.GraphicsEnvironment.isHeadless()) {
            headless = true;
            Microscope t = new Microscope();
            t.init();
        }
        else {
            JFrame frame = new JFrame();
            frame.addWindowListener(new WindowAdapter() {
                    public void windowClosing(WindowEvent e) {onExit();}});

            Microscope t = new Microscope();
            frame.setSize(new Dimension(400, 400));
            frame.getContentPane().add(t);
            //        frame.pack();
            frame.setVisible(true);
            t.init();
        }
    }

    // representations:

    Board board = new Board();        // The current board representation

    synchronized Board getBoard() { return board; }
    synchronized void  setBoard(Board b) {
        board = b;
        System.out.print(b.score(player) + " ");
        if (boardPanel != null)
            boardPanel.repaint();
    }

    Player player = Player.Blue;      // current player (BLUE, GREEN)

    synchronized Player getPlayer() { return player; }
    synchronized void setPlayer(Player p) { player = p; }


    final AutoMover auto;                  // The move finder.
    final User user;                       // Mover for user moves
    Mover mover = null;    // the current Mover (always == auto or user or null)

    synchronized Mover getMover() { return mover; }
    synchronized void setMover(Mover m) { mover = m; }
    synchronized boolean isMoving() { return mover != null; }

    Vector<Move> history = new Vector<Move>();    // List of completed moves;

    boolean demoMode = true;
    synchronized boolean getDemoMode() { return demoMode; }
    synchronized void setDemoMode(boolean b) { demoMode = b; }
    synchronized boolean toggleDemoMode() { return demoMode = !demoMode; }

    final BoardPanel boardPanel;

    JLabel scoreLabel;
    JButton autoButton;
    JButton undoButton;
    JButton modeButton;
    JSlider levelSlider;

    public Microscope() {
        if (headless) {
            boardPanel = null;
            auto = new AutoMover(this);
            user = new User(this);
            return;
        }
        boardPanel = new BoardPanel();
        scoreLabel = new JLabel("Score:     0");
        autoButton = new JButton(" Start ");
        undoButton = new JButton("Undo");
        modeButton = new JButton("Demo mode");
        levelSlider = new JSlider(JSlider.VERTICAL, 2, 6, lookAheads);

        auto = new AutoMover(this);
        user = new User(this);

        JPanel topPanel = new JPanel();
        autoButton.addActionListener(new ActionListener() {
                public void actionPerformed(ActionEvent e) {
                    if (!isMoving()) {
                        startMover(auto);
                        autoButton.setText("Cancel");
                    }
                    else {
                        stopMover();
                        if (getDemoMode())
                            autoButton.setText(" Start ");
                        else
                            autoButton.setText(" Find ");
                    }
                }});

        modeButton.addActionListener(new ActionListener() {
                public synchronized void actionPerformed(ActionEvent e) {
                    toggleDemoMode();
                    updateStatus();

                }});

        undoButton.addActionListener(new ActionListener() {
                public void actionPerformed(ActionEvent e) {
                    undo();
                }});

        levelSlider.addChangeListener(new ChangeListener() {
                public void stateChanged(ChangeEvent e) {
                    setLevel(((JSlider)(e.getSource())).getValue());
                }});

        //        Dimension labDim = new Dimension(40, 16);
        //        Dimension labDim = new Dimension(72, 24);
        //        scoreLabel.setMinimumSize(labDim);
        //        scoreLabel.setPreferredSize(labDim);


        topPanel.add(autoButton);
        topPanel.add(modeButton);
        topPanel.add(undoButton);
        topPanel.add(scoreLabel);
        add(topPanel);


        levelSlider.setLabelTable(levelSlider.createStandardLabels(1));
        levelSlider.setPaintLabels(true);

        JPanel botPanel = new JPanel();

        botPanel.add(boardPanel);
        JPanel sliderPanel = new JPanel();
        sliderPanel.setLayout(new BoxLayout(sliderPanel, BoxLayout.Y_AXIS));
        sliderPanel.add(levelSlider);
        sliderPanel.add(new JLabel("Level"));

        botPanel.add(sliderPanel);

        add(botPanel);
    }

    void initializeBoard() {
        board.reset();
        board.occupy(Player.Blue,   0,             0);
        board.occupy(Player.Blue,   Board.RANKS-1, Board.RANKS-1);
        board.occupy(Player.Green,  0,             Board.RANKS-1);
        board.occupy(Player.Green,  Board.RANKS-1, 0);
        setPlayer(Player.Blue);
        if (boardPanel != null)
            boardPanel.repaint();
    }

    public void init() {
        initializeBoard();
        if (autostart) {
            startMover(auto);
        }
    }


    synchronized void setLevel(int l) {
        lookAheads = l;
        if (lookAheads <= 1) lookAheads = 2;
    }

    public int level () { return Microscope.lookAheads; }


    // process a move (called only from mover)

    public void move(Move m, Mover mvr) {
        if (mvr != mover ||
            m == null ||
            (mvr == user && !m.isLegal())) {
            setMover(null);
            if (mvr == auto && autostart) {
                cd.countDown();
                return; // System.exit(0);
            }
        }
        else {
            m.commit();
            setBoard(m.board());
            setPlayer(m.player().opponent());

            history.addElement(m);

            if (mvr == auto &&
                getDemoMode() &&
                !m.isPass()) {
                if (getBoard().gameOver()) {
                    if (autostart) {
                        cd.countDown();
                        return; // System.exit(0);
                    }
                    else
                        setMover(null);
                }
                else {
                    auto.startTurn(new Board(getBoard()), getPlayer());
                }
            }
            else {
                setMover(null);
            }
        }
    }

    // start up a Mover
    void startMover(Mover m) {
        Mover mvr = getMover();
        if (mvr == null) {
            setMover(m);
            m.startTurn(new Board(getBoard()), player);
        }
    }

    // stop current Mover
    void stopMover() {
        Mover mvr = getMover();
        if (mvr != null) {
            setMover(null);
            mvr.cancel();
        }
    }


    // handle Undo button
    synchronized void undo() {
        if (mover == null) {
            if (history.size() > 1) {
                history.removeElementAt(history.size()-1);
                Move m = history.lastElement();
                setPlayer(m.player().opponent());
                setBoard(m.board());
            }
            else if (history.size() == 1) {
                history.removeAllElements();
                initializeBoard();
            }
        }
    }

    // handle click on tile
    void userMove(int row, int col) {
        startMover(user);
        user.choose(row, col);
    }

    void updateStatus() { // normally called from board update
        Player p = getPlayer();
        int s = getBoard().score(p);
        if (scoreLabel == null) {
            System.out.print(s + " ");
            return;
        }

        scoreLabel.setForeground(displayColor(p));
        scoreLabel.setText("Score: " +  s);

        if (getDemoMode())
            modeButton.setText("Demo  mode");
        else {
            if (getPlayer().isBlue())
                modeButton.setText("Blue  turn");
            else
                modeButton.setText("Green turn");
        }

    }


    static final int CELL_SIZE = 40; // size of a tile/cell

    static final Color paleGreen = new Color(152, 251, 152);
    static final Color darkGreen = new Color(60, 179, 113);

    static final Color possibleMoveColor = Color.yellow;


    public static Color displayColor(Player pl) {
        if (pl.isBlue()) return Color.blue;
        else if (pl.isGreen()) return darkGreen;
        else return Color.white;
    }

    public static Color lightDisplayColor(Player pl) {
        if (pl.isBlue()) return Color.cyan;
        else if (pl.isGreen()) return paleGreen;
        else return Color.gray;
    }


    class BoardPanel extends Canvas implements MouseListener {

        BoardPanel() {
            setSize(new Dimension(Board.RANKS * CELL_SIZE + 5,
                                  Board.RANKS * CELL_SIZE + 5));
            addMouseListener(BoardPanel.this);
        }

        public void paint(Graphics g) {

            Board b = getBoard();
            Player p = getPlayer();

            // the cells
            for (int row = 0; row < Board.RANKS; row++) {
                for (int col = 0; col < Board.RANKS; col++) {

                    // Highlight selected tile and legal destinations
                    if (user.placing()) {
                        if (user.hasMovedFrom(row, col))
                            g.setColor(lightDisplayColor(p));
                        else if (user.canMoveTo(row, col))
                            g.setColor(possibleMoveColor);
                        else
                            g.setColor(displayColor(b.occupant(row, col)));
                    }

                    else
                        g.setColor(displayColor(b.occupant(row, col)));

                    // tiles are just filled rectangles
                    g.fillRect(row * CELL_SIZE, col * CELL_SIZE, CELL_SIZE, CELL_SIZE);
                }
            }

            // the grid over the cells
            g.setColor(Color.black);
            for ( int i = 0; i <= Board.RANKS; i++) {
                g.drawLine(0, i * CELL_SIZE, Board.RANKS * CELL_SIZE, i * CELL_SIZE);
                g.drawLine(i * CELL_SIZE, 0, i * CELL_SIZE, Board.RANKS * CELL_SIZE);
            }

            updateStatus();
        }

        public void mouseReleased(MouseEvent evt) {

            int x = evt.getX();
            int y = evt.getY();

            int row = x / CELL_SIZE;
            int col = y / CELL_SIZE;

            if (Board.inBounds(row, col)) { // cell selection
                userMove(row, col);
                repaint();
            }
        }

        public void mouseClicked(MouseEvent e) {}
        public void mousePressed(MouseEvent e) {}
        public void mouseEntered(MouseEvent e) {}
        public void mouseExited(MouseEvent e) {}
    }

    /**
     *  Player is just a glorified enumeration
     */
    static final class Player {

        public static final int EMPTY = 0;
        public static final int BLUE = 1;
        public static final int GREEN = 2;
        public static final int ILLEGAL_PLAYER_VALUE = 3;

        public static final Player Empty   = new Player(EMPTY);
        public static final Player Blue    = new Player(BLUE);
        public static final Player Green   = new Player(GREEN);
        public static final Player Illegal = new Player(ILLEGAL_PLAYER_VALUE);

        /* private */ int code_;

        public Player(int code)       { code_ = code; }
        public Player(Player p)       { code_ = p.code_; }

        public boolean same(Player p) { return code_ == p.code_; }

        public boolean isEmpty()      { return code_ == EMPTY; }
        public boolean isBlue()       { return code_ == BLUE; }
        public boolean isGreen()      { return code_ == GREEN; }
        public boolean isLegal()      { return code_ <= GREEN; }

        public Player opponent() {
            if (code_ == GREEN) return Blue;
            else if (code_ == BLUE) return Green;
            else return Illegal;
        }

    }

    /**
     *   Board configurations are represented by bit vectors.
     *   Since there are only 49 cells, the bits can be held in `longs',
     *   one for each player.
     * <p>
     * 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;                 // travserse 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);
        }
    }


}
Revision:	1.5
Committed:	Fri Oct 22 05:18:31 2010 UTC (13 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.4:	+4 -4 lines
Log Message:	whitespace