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 19 20 public class Microscope extends JPanel { 21 22 27 28 static boolean DETERMINISTIC = false; 29 30 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 64 Board board = new Board(); 66 synchronized Board getBoard() { return board; } 67 synchronized void setBoard(Board b) { board = b; boardPanel.repaint(); } 68 69 Player player = Player.Blue; 71 synchronized Player getPlayer() { return player; } 72 synchronized void setPlayer(Player p) { player = p; } 73 74 75 final AutoMover auto; final User user; Mover mover = null; 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(); 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(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 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 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 void stopMover() { 241 Mover mvr = getMover(); 242 if (mvr != null) { 243 setMover(null); 244 mvr.cancel(); 245 } 246 } 247 248 249 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 void userMove(int row, int col) { 267 startMover(user); 268 user.choose(row, col); 269 } 270 271 void updateStatus() { 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; 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 for (int row = 0; row < Board.RANKS; row++) { 327 for (int col = 0; col < Board.RANKS; col++) { 328 329 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 g.fillRect(row * CELL_SIZE, col * CELL_SIZE, CELL_SIZE, CELL_SIZE); 344 } 345 } 346 347 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)) { 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 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 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 422 423 static final class Board { 424 425 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 static final long BLUEBIT = (1L << CELLS); 436 437 static final long[] adjacentMasks = new long[CELLS]; 439 440 static final long[] cellBits = new long[CELLS]; 442 443 static final byte[][] jumpDestinations = new byte[CELLS][]; 445 446 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 486 long blue_; long green_; 489 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 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 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 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 641 642 643 static final class Move { 644 645 static final int NO_VALUE = -1; static final int PASS_VALUE = -2; 648 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 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; 671 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 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 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 720 synchronized boolean isPass() { 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() { return fromRow != NO_VALUE && fromCol != NO_VALUE; 732 } 733 734 synchronized boolean hasTo() { return toRow != NO_VALUE && toCol != NO_VALUE; 736 } 737 738 739 synchronized boolean possibleTo(int r, int c) { 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() { 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 775 776 777 static abstract class Mover { 778 779 protected Microscope game; 781 782 protected Mover(Microscope ap) { game = ap; } 783 784 public abstract void startTurn(Board b, Player p); 786 787 public abstract void cancel(); 789 790 public abstract boolean placing(); 792 793 } 794 795 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 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) { if (placing()) { 906 stopPlacing(); 907 game.move(move, this); 908 } 909 } 910 911 } 912 913 914 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; final long theirs; final int level; final Finder next; 935 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 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; Finder forked = null; 970 long open = ~(ours | theirs); long here = 1; 973 for (int k = 0; k < Board.CELLS; ++k, here <<= 1) { 974 975 if ((here & ours) != 0) { 976 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 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 1039 1040 void collect(Finder forked) { 1041 1042 int best = NOMOVE; 1043 1044 while (forked != null) { 1045 1046 while (!forked.isDone()) { if (isDone()) { 1048 cancelAll(forked); 1049 return; 1050 } 1051 else 1052 yield(); 1053 } 1054 1055 int score = -forked.bestScore; 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 1073 1074 void cancelAll(Finder forked) { 1075 while (forked != null) { 1076 forked.cancel(); 1077 forked = forked.next; 1078 } 1079 } 1080 1081 } 1082 1083 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 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; 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 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 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 | Popular Tags |