Microscope


1   
2   import java.awt.*;
3   import javax.swing.*;
4   import java.util.*;
5   import java.awt.event.*;
6   import javax.swing.event.*;
7   import EDU.oswego.cs.dl.util.concurrent.*;
8   
9   
10  /**
11   * Microscope implements a version of the 7th Guest
12   * game found looking in the Microscope in the laboratory.
13   * See <a HREF="http://gee.cs.oswego.edu/dl/applets/micro.html">
14   * Microscope</a> version for instructions.
15   * <p>
16   * The code has been mangled beyond recognition 
17   * as a test of the FJTasks package.
18   **/
19  
20  public class Microscope extends JPanel {
21  
22    /*
23     * If true, the move finder uses a repeatable evaluation
24     * strategy, so all self-play games at same level have same outcome.
25     * This is useful for testing purposes, but much less fun to watch.
26     */
27  
28    static boolean DETERMINISTIC = false;
29  
30    // Command-line parameters
31  
32    static int nprocs;
33    static int lookAheads = 3;
34    static boolean autostart = false;
35  
36  
37    public static void main(String  [] args) {
38      try {
39        nprocs = Integer.parseInt(args[0]);
40        if (args.length > 1) {
41          autostart = true;
42          lookAheads = Integer.parseInt(args[1]);
43          DETERMINISTIC = true;
44        }
45      }
46      catch (Exception   e) {
47        System.out.println("Usage: java Microscope <threads> [<level>]");
48        return;
49      }
50  
51      JFrame frame = new JFrame();
52      frame.addWindowListener(new WindowAdapter() {
53        public void windowClosing(WindowEvent e) {System.exit(0);}});
54  
55      Microscope t = new Microscope();
56      frame.setSize(new Dimension(400, 400));
57      frame.getContentPane().add(t);
58      frame.setVisible(true);
59      t.init();
60    }
61  
62    // representations:
63  
64    Board board = new Board();        // The current board representation
65  
66    synchronized Board getBoard() { return board; }
67    synchronized void  setBoard(Board b) { board = b; boardPanel.repaint(); }
68  
69    Player player = Player.Blue;      // current player (BLUE, GREEN)
70  
71    synchronized Player getPlayer() { return player; }
72    synchronized void setPlayer(Player p) { player = p; }
73  
74  
75    final AutoMover auto;                  // The move finder.
76    final User user;                       // Mover for user moves
77    Mover mover = null;    // the current Mover (always == auto or user or null)
78  
79    synchronized Mover getMover() { return mover; }
80    synchronized void setMover(Mover m) { mover = m; }
81    synchronized boolean isMoving() { return mover != null; }
82  
83    Vector history = new Vector();    // List of completed moves;
84  
85    boolean demoMode = true;
86    synchronized boolean getDemoMode() { return demoMode; }
87    synchronized void setDemoMode(boolean b) { demoMode = b; }
88    synchronized boolean toggleDemoMode() { return demoMode = !demoMode; }
89  
90    final BoardPanel boardPanel = new BoardPanel();
91  
92    JLabel scoreLabel = new JLabel("Score:   0 ");
93    JButton autoButton = new JButton(" Start ");
94    JButton undoButton = new JButton("Undo");
95    JButton modeButton = new JButton("Demo mode");
96    JSlider levelSlider = new JSlider(JSlider.VERTICAL, 2, 6, lookAheads);
97  
98    public Microscope() {  
99      auto = new AutoMover(this);
100     user = new User(this);
101 
102     JPanel topPanel = new JPanel();
103     autoButton.addActionListener(new ActionListener() {
104       public void actionPerformed(ActionEvent e) {
105         if (!isMoving()) {
106           startMover(auto);
107           autoButton.setText("Cancel");
108         }
109         else {
110           stopMover();
111           if (getDemoMode()) 
112             autoButton.setText(" Start ");
113           else
114             autoButton.setText(" Find ");
115         }
116       }});
117 
118     modeButton.addActionListener(new ActionListener() {
119       public synchronized void actionPerformed(ActionEvent e) {
120         toggleDemoMode();
121         updateStatus();
122 
123       }});
124 
125     undoButton.addActionListener(new ActionListener() {
126       public void actionPerformed(ActionEvent e) {
127         undo();
128       }});
129  
130     levelSlider.addChangeListener(new ChangeListener() {
131       public void stateChanged(ChangeEvent e) {
132         setLevel(((JSlider)(e.getSource())).getValue());
133       }});
134 
135     //    Dimension labDim = new Dimension(40, 16);
136     Dimension labDim = new Dimension(72, 24);
137     scoreLabel.setMinimumSize(labDim);
138     scoreLabel.setPreferredSize(labDim);
139     
140 
141     topPanel.add(autoButton);
142     topPanel.add(modeButton);
143     topPanel.add(undoButton);
144     topPanel.add(scoreLabel);
145 
146     add(topPanel);
147     
148 
149     levelSlider.setLabelTable(levelSlider.createStandardLabels(1));
150     levelSlider.setPaintLabels(true);
151 
152     JPanel botPanel = new JPanel();
153 
154     botPanel.add(boardPanel);
155     JPanel sliderPanel = new JPanel();
156     sliderPanel.setLayout(new BoxLayout(sliderPanel, BoxLayout.Y_AXIS));
157     sliderPanel.add(levelSlider);
158     sliderPanel.add(new JLabel("Level"));
159 
160     botPanel.add(sliderPanel);
161     
162     add(botPanel);
163   }
164 
165   void initializeBoard() {
166     board.reset();
167     board.occupy(Player.Blue,   0,             0);
168     board.occupy(Player.Blue,   Board.RANKS-1, Board.RANKS-1);
169     board.occupy(Player.Green,  0,             Board.RANKS-1);
170     board.occupy(Player.Green,  Board.RANKS-1, 0);
171     setPlayer(Player.Blue);
172     boardPanel.repaint();
173   }
174 
175   public void init()  {
176     initializeBoard();
177     if (autostart) {
178       try { Thread.sleep(1000); } catch(InterruptedException   ex) { return; }
179       startMover(auto);
180     }
181   }
182 
183 
184   synchronized void setLevel(int l) {
185     lookAheads = l;
186     if (lookAheads <= 1) lookAheads = 2;
187   }
188     
189     public int level () { return Microscope.lookAheads; }
190     
191 
192   // process a move (called only from mover)
193 
194   public void move(Move m, Mover mvr) {
195     if (mvr != mover || 
196         m == null ||
197         (mvr == user && !m.isLegal())) {
198       setMover(null);
199       if (mvr == auto && autostart) {
200         auto.stats();        
201         System.exit(0);
202       }
203     }
204     else {
205       m.commit();
206       setBoard(m.board());
207       setPlayer(m.player().opponent());
208 
209       history.addElement(m);
210 
211       if (mvr == auto && 
212           getDemoMode() && 
213           !m.isPass()) {
214         if (getBoard().gameOver()) {
215           if (autostart) {
216             auto.stats();        
217             System.exit(0);
218           }
219           else
220             setMover(null);
221         }
222         else
223           auto.startTurn(new Board(getBoard()), getPlayer());
224       }
225       else
226         setMover(null);
227     }
228   }
229 
230   // start up a Mover
231   void startMover(Mover m) {
232     Mover mvr = getMover();
233     if (mvr == null) {
234       setMover(m);
235       m.startTurn(new Board(getBoard()), player);
236     }
237   }
238 
239   // stop current Mover
240   void stopMover() {
241     Mover mvr = getMover();
242     if (mvr != null) {
243       setMover(null);
244       mvr.cancel();
245     }
246   }
247  
248 
249   // handle Undo button
250   synchronized void undo() {
251     if (mover == null) {
252       if (history.size() > 1) {
253         history.removeElementAt(history.size()-1);
254         Move m = (Move)(history.lastElement());
255         setPlayer(m.player().opponent());
256         setBoard(m.board());
257       }
258       else if (history.size() == 1) {
259         history.removeAllElements();
260         initializeBoard();
261       }
262     }
263   }
264 
265   // handle click on tile
266   void userMove(int row, int col) {
267     startMover(user);
268     user.choose(row, col);
269   }
270   
271   void updateStatus() { // normally called from board update
272     Player p = getPlayer();
273     int s = getBoard().score(p);
274     scoreLabel.setForeground(displayColor(p));
275     scoreLabel.setText("Score: " +  s);
276 
277     if (getDemoMode()) 
278       modeButton.setText("Demo  mode");
279     else {
280       if (getPlayer().isBlue())
281         modeButton.setText("Blue  turn");
282       else
283         modeButton.setText("Green turn");
284     }
285 
286     if (!autostart) auto.stats();
287 
288   }
289 
290 
291   static final int CELL_SIZE = 40; // size of a tile/cell 
292   
293   static final Color paleGreen = new Color(152, 251, 152);
294   static final Color darkGreen = new Color(60, 179, 113);
295     
296   static final Color possibleMoveColor = Color.yellow;
297     
298 
299   public static Color displayColor(Player pl) {
300     if (pl.isBlue()) return Color.blue;
301     else if (pl.isGreen()) return darkGreen;
302     else return Color.white;
303   }
304 
305   public static Color lightDisplayColor(Player pl) {
306     if (pl.isBlue()) return Color.cyan;
307     else if (pl.isGreen()) return paleGreen;
308     else return Color.gray;
309   }
310 
311 
312   class BoardPanel extends Canvas implements MouseListener {
313     
314     BoardPanel() { 
315       setSize(new Dimension(Board.RANKS * CELL_SIZE + 5, 
316                             Board.RANKS * CELL_SIZE + 5));
317       addMouseListener(BoardPanel.this);
318     }
319     
320     public void paint(Graphics g) {
321       
322       Board b = getBoard();
323       Player p = getPlayer();
324       
325       // the cells
326       for (int row = 0; row < Board.RANKS; row++) {
327         for (int col = 0; col < Board.RANKS; col++) {
328           
329           // Highlight selected tile and legal destinations
330           if (user.placing()) {
331             if (user.hasMovedFrom(row, col)) 
332               g.setColor(lightDisplayColor(p));
333             else if (user.canMoveTo(row, col))
334               g.setColor(possibleMoveColor);
335             else
336               g.setColor(displayColor(b.occupant(row, col)));
337           }
338           
339           else
340             g.setColor(displayColor(b.occupant(row, col)));
341           
342           // tiles are just filled rectangles
343           g.fillRect(row * CELL_SIZE, col * CELL_SIZE, CELL_SIZE, CELL_SIZE);
344         }
345       }
346       
347       // the grid over the cells
348       g.setColor(Color.black);
349       for ( int i = 0; i <= Board.RANKS; i++) {
350         g.drawLine(0, i * CELL_SIZE, Board.RANKS * CELL_SIZE, i * CELL_SIZE);
351         g.drawLine(i * CELL_SIZE, 0, i * CELL_SIZE, Board.RANKS * CELL_SIZE);
352       }
353       
354       updateStatus();
355     }
356     
357     public void mouseReleased(MouseEvent evt) {
358       
359       int x = evt.getX();
360       int y = evt.getY();
361       
362       int row = x / CELL_SIZE;
363       int col = y / CELL_SIZE;
364       
365       if (Board.inBounds(row, col)) { // cell selection
366         userMove(row, col);
367         repaint();
368       }
369     }
370     
371     public void mouseClicked(MouseEvent e) {}
372     public void mousePressed(MouseEvent e) {}
373     public void mouseEntered(MouseEvent e) {}
374     public void mouseExited(MouseEvent e) {}
375   }
376 
377   /**
378    *  Player is just a glorified enumeration
379    **/
380 
381   static final class Player {
382 
383     public static final int EMPTY = 0;
384     public static final int BLUE = 1;
385     public static final int GREEN = 2;
386     public static final int ILLEGAL_PLAYER_VALUE = 3;
387     
388     public static final Player Empty   = new Player(EMPTY);
389     public static final Player Blue    = new Player(BLUE);
390     public static final Player Green   = new Player(GREEN);
391     public static final Player Illegal = new Player(ILLEGAL_PLAYER_VALUE);
392     
393     /* private */ int code_;
394     
395     public Player(int code)       { code_ = code; }
396     public Player(Player p)       { code_ = p.code_; }
397     
398     public boolean same(Player p) { return code_ == p.code_; }
399     
400     public boolean isEmpty()      { return code_ == EMPTY; }
401     public boolean isBlue()       { return code_ == BLUE; }
402     public boolean isGreen()      { return code_ == GREEN; }
403     public boolean isLegal()      { return code_ <= GREEN; }
404     
405     public Player opponent() { 
406       if (code_ == GREEN) return Blue;
407       else if (code_ == BLUE) return Green;
408       else return Illegal;
409     }
410     
411   }
412   
413   /**
414    *   Board configurations are represented by bit vectors.
415    *   Since there are only 49 cells, the bits can be held in `longs',
416    *   one for each player.
417    * <p>
418    * Boards are not immutable, but are never passed around across
419    * threads (instead new ones are constructed), so don't
420    * need any synch.
421    **/
422   
423   static final class Board   {
424 
425     /* 
426        First, some Constants and utilities that might as well be here
427     */
428     
429     public static final int RANKS = 7;
430     public static final int CELLS = RANKS * RANKS;
431     
432     static final long FULL = (1L << CELLS) - 1;
433     
434     // The finder uses a spare bit to remember whose move it is.
435     static final long BLUEBIT = (1L << CELLS);
436     
437     // Bits representing the adjacent cells for every position
438     static final long[] adjacentMasks = new long[CELLS];
439     
440     // bit pattern associated with each tile
441     static final long[] cellBits = new long[CELLS];
442 
443     // locations of all cells reachable by a jump for every position
444     static final byte[][] jumpDestinations = new byte[CELLS][];
445 
446     // initialize tables
447     static {
448       byte[] dests = new byte[CELLS];
449       for (int j = 0; j < RANKS; ++j) {
450         for (int i = 0; i < RANKS; ++i) {
451           int k = i + j * RANKS;
452           long nmask = 0;
453           int jumpCount = 0;
454           for (int c = j-2; c <= j+2; ++c) {
455             for (int r = i-2; r <= i+2; ++r) {
456               if (c >= 0 && c < RANKS &&
457                   r >= 0 && r < RANKS) {
458                 int cellIndex = r + c * RANKS;
459                 if (r == i-2 || r == i+2 || c == j-2 || c == j+2) {
460                   dests[jumpCount++] = (byte)cellIndex;
461                 }
462                 else if (!(r == i && c == j)) {
463                   nmask |= 1L << cellIndex;
464                 }
465               }
466             }
467           }
468           adjacentMasks[k] = nmask;
469           cellBits[k] = 1L << k;
470           jumpDestinations[k] = new byte[jumpCount];
471           for (int l = 0; l < jumpCount; ++l)
472             jumpDestinations[k][l] = dests[l];
473 
474         }
475       }
476 
477     }
478     
479     
480     public static boolean inBounds(int row, int col) {
481       return (0 <= row)  && (row < RANKS) && (0 <= col) && (col < RANKS);
482     }
483     
484     // The representation
485     
486     long blue_;      // bit vector; true if occupied by blue
487     long green_;     // same for green;
488     
489     // constructors and intializers:
490     
491     public Board()               { blue_ = 0L; green_ = 0L; }
492     public Board(Board b)        { blue_ = b.blue_; green_ = b.green_; }
493     public Board(long b, long g) { blue_ = b; green_ = g; }
494     
495     public void copyState(Board b) {
496       blue_ = b.blue_; 
497       green_ = b.green_; 
498     }
499 
500     void reset() { 
501       blue_ = 0L; green_ = 0L; 
502     }
503     
504     long getBlue() { return blue_; }
505     long getGreen() { return green_; }
506 
507 
508     public Player occupant(int row, int col) {
509       if ((0 <= row)  && (row < RANKS) && (0 <= col) && (col < RANKS)) {
510         long m = 1L << (row + col * RANKS);
511         if ((blue_ & m) != 0L) return Player.Blue;
512         else if ((green_ &m) != 0L) return Player.Green;
513         else return Player.Empty;
514       }
515       else
516         return Player.Illegal;
517     }
518     
519     
520     // place a tile without taking opponent tiles
521     
522     public void occupy(Player player, int row, int col) {
523       long m = 1L << (row + col * RANKS);
524       long nm = ~m;
525       if (player.code_ == Player.BLUE)  { 
526         blue_ |= m;
527         green_ &= nm;
528       }
529       else if (player.code_ == Player.GREEN) { 
530         blue_ &=  nm;
531         green_ |= m;
532       }
533       else { 
534         blue_ &= nm;
535         green_ &= nm;
536       }
537     }
538     
539     public void unoccupy(int row, int col) {
540       long nm = ~(1L << (row + col * RANKS));
541       blue_ &=  nm;
542       green_ &= nm;
543     }
544     
545     
546     
547     // place a tile, taking all adjacent tiles of opponent
548     
549     public void take(Player player, int row, int col) {
550       int k =  (row + col * RANKS);
551       long dest = 1L << k;
552       long nbrMask = adjacentMasks[k];
553       long sourceBlue = blue_;
554       long sourceGreen = green_;
555       if (player.code_ == Player.BLUE) {
556         blue_ = sourceBlue | dest | (sourceGreen & nbrMask);
557         green_ = sourceGreen & ~(sourceGreen & nbrMask);
558       }
559       else {
560         blue_ = sourceBlue & ~(sourceBlue & nbrMask);
561         green_ =  sourceGreen | dest | (sourceBlue & nbrMask);
562       }
563     }
564     
565     public boolean gameOver() {
566       return 
567         (((blue_ | green_) & FULL) == FULL) ||
568         ((blue_ & ~BLUEBIT) == 0) ||
569         ((green_ & ~BLUEBIT) == 0);
570     }
571     
572     
573     public int score(Player player) {
574       if (player.isBlue()) {
575         return score(blue_, green_);
576       }
577       else {
578         return score(green_, blue_);
579       }
580     }
581     
582     static int score(long b, long g) {
583       
584       // much faster by splitting into ints
585       // and using clever shift-based bit counter
586       
587       int lb = (int)(b & ((1L << 32) - 1));
588       int hb = ((int)(b >>> 32)) & ((1 << (CELLS - 32)) - 1);
589 
590       lb -= (0xaaaaaaaa & lb) >>> 1;
591       lb = (lb & 0x33333333) + ((lb >>> 2) & 0x33333333);
592       lb = lb + (lb >>> 4) & 0x0f0f0f0f;
593       lb += lb >>> 8;
594       lb += lb >>> 16;
595 
596       hb -= (0xaaaaaaaa & hb) >>> 1;
597       hb = (hb & 0x33333333) + ((hb >>> 2) & 0x33333333);
598       hb = hb + (hb >>> 4) & 0x0f0f0f0f;
599       hb += hb >>> 8;
600       hb += hb >>> 16;
601 
602       hb = ((lb + hb) & 0xff);
603 
604       int lg = (int)(g & ((1L << 32) - 1));
605       int hg = ((int)(g >>> 32)) & ((1 << (CELLS - 32)) - 1);
606 
607       lg -= (0xaaaaaaaa & lg) >>> 1;
608       lg = (lg & 0x33333333) + ((lg >>> 2) & 0x33333333);
609       lg = lg + (lg >>> 4) & 0x0f0f0f0f;
610       lg += lg >>> 8;
611       lg += lg >>> 16;
612 
613       hg -= (0xaaaaaaaa & hg) >>> 1;
614       hg = (hg & 0x33333333) + ((hg >>> 2) & 0x33333333);
615       hg = hg + (hg >>> 4) & 0x0f0f0f0f;
616       hg += hg >>> 8;
617       hg += hg >>> 16;
618 
619       return hb - ((lg + hg) & 0xff);
620     }
621     
622     
623     
624     static int slowscore(long b, long g) {
625       int score = 0;
626       for (int l = 0; l < CELLS; ++l) {
627         score += (int)(b & 1);
628         b >>>= 1;
629         score -= (int)(g & 1);
630         g >>>= 1;
631       }
632       return score;
633     }
634    
635     
636   }
637   
638   /**
639    * Moves represent transitions across Board states
640    **/
641 
642 
643   static final class Move  {
644 
645     static final int NO_VALUE = -1;     // row/col value if not yet set
646     static final int PASS_VALUE = -2;   // special value for pass moves
647     
648     // utilities for classifying moves
649     
650     public static boolean twoFrom(int a, int b) { 
651       return (a - b == 2) || (b - a == 2); 
652     }
653     
654     public static boolean withinTwo(int a, int b) { 
655       int diff = a - b; return -2 <= diff && diff <= 2;
656     }
657     
658     // representations
659     
660     int fromRow;
661     int fromCol;
662     
663     int toRow;
664     int toCol;
665     
666     Player player_;
667     Board board_;
668     
669     boolean committed = false; // true if board reflects move
670     
671     // constructors and intializers
672     
673     public Move(Player turn, Board board) { 
674       fromRow = NO_VALUE; fromCol = NO_VALUE;
675       toRow = NO_VALUE;   toCol = NO_VALUE;
676       player_ = turn;
677       board_ = board;
678     }
679     
680     public Move(Player turn, Board board, boolean isCommitted) { 
681       fromRow = NO_VALUE; fromCol = NO_VALUE;
682       toRow = NO_VALUE;   toCol = NO_VALUE;
683       player_ = turn;
684       board_ = board;
685       committed = isCommitted;
686     }
687     
688     synchronized void reset() {
689       fromRow = NO_VALUE;
690       fromCol = NO_VALUE;
691       toRow = NO_VALUE;
692       toCol = NO_VALUE;
693     }
694     
695     // setters:
696     
697     synchronized void player(Player p)       { player_ = p;  }
698     synchronized void board(Board b)         { board_ = b;  }
699     synchronized void from(int sr, int sc)   { fromRow = sr; fromCol = sc;  }
700     synchronized void to(int dr, int dc)     { toRow = dr;   toCol = dc; }
701    
702     //  accessors:
703     
704     synchronized boolean isFrom(int r, int c) { 
705       return fromRow== r && fromCol == c; 
706     }
707     synchronized boolean isTo(int r, int c)   { 
708       return toRow == r && toCol == c; 
709     }
710     synchronized Board board() { 
711       return board_; 
712     }
713     synchronized Player player() { 
714       return player_; 
715     }
716     
717 
718     // status checks:
719     
720     synchronized boolean isPass() { // is this a `pass' move?
721       return (toRow == PASS_VALUE || fromRow == PASS_VALUE);
722     }
723     
724     synchronized boolean isJump() {
725       return 
726         (fromRow - toRow == 2) || (toRow - fromRow == 2) ||
727         (fromCol - toCol == 2) || (toCol - fromCol == 2);
728     }
729     
730     synchronized boolean hasFrom() { // is from set?
731       return fromRow != NO_VALUE && fromCol != NO_VALUE;
732     }
733     
734     synchronized boolean hasTo() { // is to set?
735       return toRow != NO_VALUE && toCol != NO_VALUE;
736     }
737     
738     
739     synchronized boolean possibleTo(int r, int c) { // is (r, c) a legal `to'?
740       return hasFrom() &&
741         withinTwo(fromRow, r) &&
742         withinTwo(fromCol, c) &&
743         board_.occupant(r, c).isEmpty();
744     }
745     
746     synchronized boolean isLegal() {
747       if (isPass()) 
748         return true;
749       else if (!board_.occupant(toRow, toCol).isEmpty()) 
750         return false;
751       else if (!board_.occupant(fromRow, fromCol).same(player_)) 
752         return false;
753       else if (!(withinTwo(fromRow, toRow) && withinTwo(fromCol, toCol))) 
754         return false;
755       else
756         return true;
757     }
758     
759     synchronized void commit() { // update board to reflect move
760       if (!committed) {
761         committed = true;
762         if (isLegal() && !isPass())  {
763           if (isJump()) board_.occupy(Player.Empty, fromRow, fromCol);
764           board_.take(player_, toRow, toCol);
765         }
766       }
767     }
768     
769   }
770   
771   /**
772    *  Mover is an abstract class to simplify code dealing with
773    *  either user moves or auto moves.
774    **/
775   
776 
777   static abstract class Mover {
778     
779     // caller for move callbacks
780     protected Microscope game;
781     
782     protected Mover(Microscope ap) { game = ap; }
783     
784     // start a turn as player on given board
785     public abstract void startTurn(Board b, Player p);
786     
787     // cancel current partial move
788     public abstract void cancel();
789     
790     // return true if move not yet ready
791     public abstract boolean placing();
792     
793   }
794   
795   /**
796    *  User builds moves via instructions/clicks by users
797    **/
798 
799   static class User extends Mover {
800 
801     private Move current;
802     
803     public User(Microscope ap) { super(ap); current = null; }
804     
805     public synchronized void startTurn(Board b, Player p) {
806       current = new Move(p, b);
807     }
808     
809     public boolean placing() { 
810       return current != null && current.hasFrom() && !current.hasTo(); 
811     }
812     
813     public synchronized void cancel() { 
814       if (current != null) {
815         current.reset(); 
816         current = null; 
817       }
818     }
819     
820     public synchronized void choose(int row, int col) {
821       if (current != null) {
822         if (row == Move.PASS_VALUE) {
823           current.from(row, col);
824           game.move(current, this);
825           current = null;
826         }
827         else if (!current.hasFrom()) {
828           if (current.board().occupant(row, col).same(current.player())) {
829             current.from(row, col);
830           }
831         }
832         else {
833           current.to(row, col);
834           game.move(current, this);
835           current = null;
836         }
837       }
838     }
839     
840     public synchronized boolean canMoveTo(int row, int col) {
841       return placing() && current.possibleTo(row, col);
842     }
843     
844     public synchronized boolean hasMovedFrom(int row, int col) {
845       return current != null && current.isFrom(row, col);
846     }
847     
848   }
849 
850 
851   /**
852    *     AutoMover constructs Finders that compute actual moves
853    **/
854 
855   static class AutoMover extends Mover {
856 
857     FJTaskRunnerGroup group = null;
858     boolean cancelled = false;
859     RootFinder currentFinder = null;
860 
861     public AutoMover(Microscope ap) {
862       super(ap);
863     }
864   
865     
866     public synchronized boolean placing() { 
867       return currentFinder != null; 
868     }
869 
870     synchronized void stopPlacing() { 
871       currentFinder = null;
872     }
873     
874     
875     public synchronized void cancel() {
876       if (placing())  { 
877         currentFinder.cancel();
878         stopPlacing();
879       }
880     }
881     
882 
883     public synchronized void startTurn(Board board, Player player) {
884       try {
885         if (group == null) {
886           group = new FJTaskRunnerGroup(Microscope.nprocs);
887         }
888         if (!placing()) {
889           currentFinder = new RootFinder(board, player, 
890                                          Microscope.lookAheads, this);
891           group.execute(currentFinder);
892         }
893       }
894       catch (InterruptedException   ex) {
895         stopPlacing();
896       }
897     }
898     
899     public void stats() {
900       if (group != null) group.stats();
901     }
902    
903 
904     synchronized void relay(Move move) { // relay callback from finder
905       if (placing()) {
906         stopPlacing();
907         game.move(move, this);
908       }
909     }
910     
911   }
912   
913 
914   /**
915    * Implements a classic all-possible-move search algorith using FJTasks.
916    * The move finder is not all that smart. Among other possible
917    * improvements, it could keep a cache of explored moves and
918    * avoid repeating them. This would likely speed it up since
919    * most expansions are duplicates of others. It could also be changed to
920    * prune moves, although this is unlikely to work well without
921    * better partial evaluation functions.
922    **/
923   
924   static class Finder extends FJTask {
925 
926     static final int NOMOVE = Integer.MIN_VALUE;
927     static final int LOSE   = NOMOVE+1;
928     static final int WIN    = -LOSE;
929     
930     final long ours;     // bits for our tiles
931     final long theirs;   // bits for opponent tiles
932     final int level;     // current number of lookAheads
933     final Finder next;   // Each Finder is placed in a linked list by parent
934 
935     // Assigned once; must be volatile since accessed by parents
936     volatile int bestScore;
937 
938     Finder(long ours, long theirs, int level, Finder next) {
939       this.ours = ours;
940       this.theirs = theirs;
941       this.level = level;
942       this.next = next;
943     }
944     
945     public final void run() {
946 
947       // Handle sure wins and losses here
948       if ((ours & ~Board.BLUEBIT) == 0)  
949         bestScore = LOSE;
950 
951       else if ((theirs & ~Board.BLUEBIT) == 0) 
952         bestScore = WIN;
953 
954       else if (((ours | theirs) & Board.FULL) == Board.FULL) {
955         int score = Board.score(ours, theirs);
956         if (score > 0) bestScore = WIN;
957         else if (score < 0) bestScore = LOSE;
958         else bestScore = 0;
959       }
960 
961       else 
962         search();
963     }
964     
965 
966     final void search() {
967       int best = NOMOVE;    // For direct evaluation when level == 1
968       Finder forked = null; // list of forked subtasks when level > 1
969       
970       long open = ~(ours | theirs);  // currently empty cells
971       long here = 1;                 // travserse through bits
972       
973       for (int k = 0; k < Board.CELLS; ++k, here <<= 1) {
974         
975         if ((here & ours) != 0) {
976           /*
977            * Step through possible destinations to find jumps for this tile
978            */
979           
980           byte[] dests = Board.jumpDestinations[k];
981           for (int j = 0; j < dests.length; ++j) {
982             byte d = dests[j];
983             long dest = 1L << d;
984 
985             if ( (dest & open) != 0) {
986               long adjacent = Board.adjacentMasks[d];
987 
988               long nTheirs = theirs & ~adjacent;
989               long nOurs = (ours & ~here) | dest | (theirs & adjacent);
990 
991               if (level > 1) 
992                 (forked = new Finder(nTheirs, nOurs, level-1, forked)).fork();
993 
994               else {
995                 int sc = Board.score(nOurs, nTheirs);
996                 if (sc > best) best = sc;
997               }
998             }
999           }
1000        }
1001
1002        else if ((here & open) != 0) {
1003          
1004          /*
1005           * If this cell is open, and is within 1 of one of our tiles,
1006           * it can be taken in some copy move.  It doesn't matter which
1007           * of the adjacent cells is considered to be source of copy
1008           * move 
1009           */
1010          
1011          long adjacent = Board.adjacentMasks[k];
1012          
1013          if ((ours & adjacent) != 0) {
1014
1015            long nTheirs = theirs & ~adjacent;
1016            long nOurs = ours | here | (theirs & adjacent);
1017
1018            if (level > 1) 
1019              (forked = new Finder(nTheirs, nOurs, level-1, forked)).fork();
1020
1021            else {
1022              int sc = Board.score(nOurs, nTheirs);
1023              if (sc > best) best = sc;
1024            }
1025          }
1026        }
1027      }
1028
1029      if (level > 1)
1030        collect(forked);
1031      else
1032        bestScore = best;
1033    }
1034
1035    /**
1036     * Join all subtasks and evaluate moves. Default is sub-finder version.
1037     * Overridden in RootFinder
1038     **/
1039
1040    void collect(Finder forked) {
1041
1042      int best = NOMOVE;
1043
1044      while (forked != null) {
1045
1046        while (!forked.isDone()) { // interleave joins with cancel checks
1047          if (isDone()) {
1048            cancelAll(forked);
1049            return;
1050          }
1051          else 
1052            yield();
1053        }
1054
1055        int score = -forked.bestScore; // negate opponent score
1056        
1057        if (score > best) {
1058          best = score;
1059          if (score >= WIN) {
1060            cancelAll(forked.next);
1061            break;
1062          }
1063        }
1064        forked = forked.next;
1065      }
1066
1067      bestScore = best;
1068    }
1069
1070    /**
1071     * Cancel all forked subtasks in list
1072     **/
1073
1074    void cancelAll(Finder forked) {
1075      while (forked != null) {
1076        forked.cancel();
1077        forked = forked.next;
1078      }
1079    }
1080
1081  }
1082
1083  /**
1084   * Root Finder class -- wait out other finders and issue callback to game.
1085   **/
1086
1087  static class RootFinder extends Finder {
1088    final AutoMover automover; 
1089    final Player player;
1090
1091    RootFinder(Board board, Player p, int level, AutoMover automover) {
1092      super( (p.isBlue()? (board.getBlue()| Board.BLUEBIT) : board.getGreen()),
1093             (p.isBlue()? board.getGreen() : (board.getBlue()| Board.BLUEBIT)),
1094             level,
1095             null);
1096
1097      this.player = p;
1098      this.automover = automover;
1099    }
1100
1101
1102    /**
1103     * This differs from default version by recording
1104     * and calling back with best move
1105     **/
1106
1107    void collect(Finder forked) {
1108
1109      int best = NOMOVE;
1110      Finder bestFinder = null;
1111
1112      while (forked != null) {
1113
1114        while (!forked.isDone()) {
1115          if (isDone()) {
1116            cancelAll(forked);
1117            return;
1118          }
1119          else 
1120            yield();
1121        }
1122
1123          
1124        int score = -forked.bestScore; // negate opponent score
1125        
1126        if (bestFinder == null || score > best) {
1127          best = score;
1128          bestFinder = forked;
1129          if (score >= WIN) {
1130            cancelAll(forked.next);
1131            break;
1132          }
1133        }
1134        
1135        // Just for fun, introduce a little randomness via hashcodes
1136        
1137        else if (score == best &&
1138                 !Microscope.DETERMINISTIC &&
1139                 (System.identityHashCode(forked) > 
1140                  System.identityHashCode(bestFinder))) {
1141          bestFinder = forked;
1142        }
1143        
1144        forked = forked.next;
1145        
1146      }
1147
1148      
1149      Move move = null;
1150
1151      if (bestFinder != null) {
1152        /* 
1153           Even though accessed here,
1154           the ours and theirs vars of Finders do not
1155           need to be volatile because they are immutably
1156           established in constructors.
1157        */
1158        
1159        long nextOurs = bestFinder.theirs;
1160        long nextTheirs = bestFinder.ours;
1161        long blue = (player.isBlue())? nextOurs : nextTheirs;
1162        long green = (player.isBlue())? nextTheirs: nextOurs;
1163        move = new Move(player, new Board(blue, green), true);
1164      }
1165      
1166      automover.relay(move);
1167    }
1168  }
1169
1170  
1171}
1172
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags