Initial version of statistics and ELO rating. Donated by Martin Rexa
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
4 * The contents of this file are subject to the terms of either the GNU
5 * General Public License Version 2 only ("GPL") or the Common
6 * Development and Distribution License("CDDL") (collectively, the
7 * "License"). You may not use this file except in compliance with the
8 * License. You can obtain a copy of the License at
9 * http://www.netbeans.org/cddl-gplv2.html
10 * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
11 * specific language governing permissions and limitations under the
12 * License. When distributing the software, include this License Header
13 * Notice in each file and include the License file at
14 * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
15 * particular file as subject to the "Classpath" exception as provided
16 * by Sun in the GPL Version 2 section of the License file that
17 * accompanied this code. If applicable, add the following below the
18 * License Header, with the fields enclosed by brackets [] replaced by
19 * your own identifying information:
20 * "Portions Copyrighted [year] [name of copyright owner]"
24 * Portions Copyrighted 2009 Jaroslav Tulach
27 package cz.xelfi.quoridor;
29 import cz.xelfi.quoridor.Player.Direction;
30 import java.io.BufferedReader;
31 import java.io.EOFException;
32 import java.io.IOException;
33 import java.io.Reader;
34 import java.io.StringReader;
35 import java.io.StringWriter;
36 import java.io.Writer;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.BitSet;
40 import java.util.Collection;
41 import java.util.Collections;
42 import java.util.HashSet;
43 import java.util.List;
45 import java.util.TreeSet;
46 import java.util.regex.Matcher;
47 import java.util.regex.Pattern;
50 * Represents a snapshot of the game position,
51 * including all the placed and not-yet placed fences and player positions.
52 * It it can print itself to stream in
53 * <a href="http://www.gamerz.net/pbmserv/quoridor.html">ascii art format<a/>
54 * and can it read back. The class is immutable
55 * but it contains {@link #apply(cz.xelfi.quoridor.Move)}
56 * that produce new {@link Board} with position created after
57 * applying some {@link Move}. Use:
59 * Board whiteOnTurn = Board.empty();
60 * Board blackOnTurn = whiteOnTurn.apply(Move.NORTH);
61 * Board whiteAgain = blackOnTurn.apply(Move.SOUTH);
62 * Board withOneFence = whiteAgain.apply(Move.fence('D', 7));
65 * @author Jaroslav Tulach
67 public final class Board {
69 private final Player winner;
71 private final List<Player> players;
72 /** fences placed on board */
73 private final Set<Fence> fences;
74 /** occurpied bits (coordinates encoded by toIndex methods)
77 +-----------------------------------+
95 +-----------------------------------+
96 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
99 * even indexes == position of the pawns
100 * odd indexes == centers of fences
101 * even x odd == side of a fence
102 * odd x even == side of a fence
104 private final BitSet occupied;
105 /** which player's turn is next? */
106 private final int turn;
109 * Creates a new instance of Board
111 private Board (int x1, int y1, int f1, int x2, int y2, int f2) {
112 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
113 new Player (x1, y1, f1, Player.Direction.NORTH),
114 new Player (x2, y2, f2, Player.Direction.SOUTH),
116 this.fences = Collections.emptySet ();
118 this.occupied = computeOccupied (players, fences);
119 } catch (IllegalPositionException ex) {
120 throw new IllegalStateException (ex.getMessage ());
126 /** Copy constructor that provides players and fences.
128 private Board (int turn, List<Player> players, Set<Fence> fences)
129 throws IllegalPositionException {
130 this.players = Collections.unmodifiableList (players);
131 this.fences = Collections.unmodifiableSet (fences);
132 this.occupied = computeOccupied (players, fences);
134 for (Player p : players) {
135 BitSet bs = new BitSet(17 * 17);
136 if (!accessibleFinalLine (p, p.endDirection, occupied, bs)) {
137 throw new IllegalPositionException ("Player " + p + " cannot reach " + p.endDirection + " side"); // NOI18N
140 this.turn = turn % players.size();
144 /** Copy constructor for resigning the game */
145 private Board(Board previous, int winner) {
146 this.players = previous.players;
147 this.turn = winner % players.size();
148 this.fences = previous.fences;
149 this.occupied = previous.occupied;
150 this.winner = players.get(this.turn);
153 /** Returns empty board with default starting position.
154 * @return board with two pawns.
156 public static Board empty () {
157 return new Board (8, 0, 10, 8, 16, 10);
160 /** Returns players in the game.
161 * @return player object
163 public List<Player> getPlayers () {
167 /** The fences currently on board.
169 * @return immutable set of Fences
171 public Set<Fence> getFences () {
175 /** The player that is supposed to play now.
176 * @return the player to do next move, null if the game is over
178 public Player getCurrentPlayer() {
179 if (getWinner() != null) {
182 return players.get(turn);
185 /** The play who wins on current board.
187 * @return the winning player or <code>null</code>
189 public Player getWinner() {
190 if (winner != null) {
193 for (Player p : players) {
194 if (p.endDirection.reached(p)) {
201 /** Applies given move to current board.
203 * @param move move creates by one of the factory methods or fields of the {@link Move} class
204 * @return new board derived from this one
206 * @throws cz.xelfi.quoridor.IllegalPositionException throws exception if the move is illegal
208 public Board apply(Move move) throws IllegalPositionException {
209 if (getWinner() != null) {
210 throw new IllegalPositionException("Game finished!"); // NOI18N
213 if (move.direction != null) {
214 return move(getCurrentPlayer(), move.direction);
216 if (move.fence != null) {
217 return fence(getCurrentPlayer(), move.fence);
219 return new Board(this, turn + 1);
224 /** Can the move be applied to current board position?
226 * @param move the move to apply
227 * @return true if one can call {@link #apply} method without getting
230 public boolean isApplicable(Move move) {
232 // trivial implementation is enough for now
235 } catch (IllegalPositionException ex) {
240 /** Moves the player in given direction. The direction usually
241 * is one of Player.Direction constants, but in case the move
242 * is a jump over another players pawn it can be followed by
243 * another (usually, if there is no fence the same) direction.
245 * @param player the player to move
246 * @param where one or two directions saying where
247 * @return the new board
248 * @exception IllegalPositionException if the move is not possible
250 final Board move (Player player, Player.Direction... where) throws IllegalPositionException {
251 if (where.length != 1 && where.length != 2) {
252 throw new IllegalPositionException ("Move over one or two Directions"); // NOI18N
255 int index = players.indexOf (player);
256 Player[] arr = players.toArray (new Player[0]);
258 Player oneStep = newPosition (player, where[0]);
260 if (where.length == 1) {
261 arr[index] = oneStep;
262 return new Board(turn + 1, Arrays.asList (arr), fences);
265 // straight jump over
266 for (Player p : players) {
267 if (p.getXInternal () == oneStep.getXInternal () && p.getYInternal() == oneStep.getYInternal ()) {
268 // ok, we are jumping over this one
269 GO_ON: if (where[0] != where[1]) {
270 // first of all ensure that we cannot go straight
272 newPosition (oneStep, where[0]);
273 } catch (IllegalPositionException ex) {
277 throw new IllegalPositionException ("You have to jump straight if there is no wall"); // NOI18N
279 arr[index] = newPosition (oneStep, where[1]);
280 return new Board (turn + 1, Arrays.asList (arr), fences);
283 throw new IllegalPositionException ("Cannot use multi direction when there is not oponent pawn"); // NOI18N
286 final Board fence (Player player, char x, int y, Fence.Orientation orientation) throws IllegalPositionException {
287 return fence(player, new Fence ((x - 'A') * 2 + 1, y * 2 - 1, orientation));
290 private void columnLine(int width, int spaceX, Writer w) throws IOException {
292 for (int x = 0; x < width - 1; x++) {
293 if (x % (spaceX + 1) == 0 && x > 0) {
295 ch = (char) (ch + 1);
302 private Board fence(Player player, Fence fence) throws IllegalPositionException {
303 if (player.getFences () == 0) {
304 throw new IllegalPositionException ("Not enough fences: " + player); // NOI18N
307 int index = players.indexOf (player);
308 Player[] arr = players.toArray (new Player[0]);
309 arr[index] = new Player (arr[index].getXInternal(), arr[index].getYInternal(), arr[index].getFences() - 1, arr[index].endDirection);
311 HashSet<Fence> fen = new HashSet<Fence> (this.fences);
312 if (!fen.add (fence)) {
313 throw new IllegalPositionException ("Fence already prsent: " + fence); // NOI18N
316 return new Board (turn + 1, Arrays.asList (arr), fen);
323 private static final Pattern northSouthPattern = Pattern.compile("(\\+(\\|*)(\\*)?-+\\+)");
325 /** Reads the board from a reader. Opposite operation to {@link #write(java.io.Writer)}.
327 * @param r the reader
328 * @return the read board
329 * @throws IOException if I/O error occurs
330 * @throws IllegalPositionException if the reader does not contain description
333 public static Board read(Reader r) throws IOException, IllegalPositionException {
334 BufferedReader b = new BufferedReader(r);
336 String s = b.readLine();
338 throw new IOException("No board found!");
340 Matcher m = northSouthPattern.matcher(s);
342 return readFromBetween(b, m);
347 /** Translates the string into board, if possible. String created by
348 * use of {@link #toString()} is accepted, more information about the
349 * format is avaliable in the description of {@link #write(java.io.Writer)}
352 * @param board string to analyze
353 * @return board object, if the string can be read
354 * @throws IllegalPositionException if the string does not represent the board
356 public static Board valueOf(String board) {
357 return new Board(board);
360 public static Board picture2board(String board) throws IllegalPositionException {
362 return read(new StringReader(board));
363 } catch (IOException ex) {
364 // shall not happen, StringReader does not throw IOException
365 throw (IllegalPositionException)new IllegalPositionException(ex.getMessage()).initCause(ex);
369 private static int assertChar(String s, int pos, char... ch) throws IOException {
370 if (s.length() >= pos) {
371 for (int i = 0; i < ch.length; i++) {
372 if (ch[i] == s.charAt(pos)) {
377 throw new IOException("Not found " + ch[0] + " at " + pos + " in" + s);
380 private static Player findPlayer(
381 Player previous, String line, int y, int spaceX, Player.Direction dir, int fences
383 int index = line.indexOf(dir.player);
387 int x = (index - 1) / (spaceX + 1) * 2;
388 return new Player(x, y - 1, fences, dir);
391 private static Board readFromBetween(BufferedReader b, Matcher firstMatcher)
392 throws IOException, IllegalPositionException {
393 final int from = firstMatcher.start(1);
394 final int to = firstMatcher.end(1);
395 final int northFences = firstMatcher.end(2) - firstMatcher.start(2);
396 final int spaceX = (to - from - 1) / 9 - 1;
397 final int spaceY = 1;
401 Set<Fence> fences = new HashSet<Fence>();
403 StringBuffer sb = new StringBuffer();
405 for (int y = (spaceY + 1) * 9 - 1; y > 0; y--) {
406 String s = b.readLine();
408 throw new EOFException();
412 if (s.length() < to) {
413 throw new IOException("Too short line: " + s); // NOI18N
415 assertChar(s, from, '|');
416 assertChar(s, to - 1, '|');
418 if (y % (spaceY + 1) == 0) {
419 for (int x = 1; x < 9; x++) {
420 switch (assertChar(s, from + (spaceX + 1) * x, '+', '-', '|')) {
422 fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.HORIZONTAL));
425 fences.add(new Fence(x * 2 - 1, row * 2 + 1, Fence.Orientation.VERTICAL));
435 String line = s.substring(from, to);
436 p = findPlayer(p, line, y, spaceX, Player.Direction.NORTH, -1);
437 q = findPlayer(q, line, y, spaceX, Player.Direction.SOUTH, northFences);
441 String last = b.readLine();
443 throw new EOFException();
445 Matcher lastMatcher = northSouthPattern.matcher(last);
446 if (!lastMatcher.find()) {
447 throw new IOException("Unrecognized last line: " + last);
450 List<Player> arr = new ArrayList<Player>(2);
452 int southFences = lastMatcher.end(2) - lastMatcher.start(2);
453 arr.add(new Player(p.getXInternal(), p.getYInternal(), southFences, p.endDirection));
455 int turn = "*".equals(lastMatcher.group(3)) ? 0 : 1; // NOI18N
456 return new Board(turn, arr, fences);
461 /** Writes the board to the provided writer. <b>P</b> denotes position
462 * of the first player and <b>Q</b> of the second. Number of remaining
463 * fences of each player are shown in left bottom and left top corner
464 * as appropriate number of <b>|||</b> - one <b>|</b> per fence. The
465 * player that is supposed to move in this turn has <b>*</b> right after
466 * the set of its fences.
473 +|||||------------------------------+
475 8--| + + + + + + + + |--8
477 7--| + | + +-------+-------+ |--7
479 6--|-------+-------|-------+-------+ |--6
481 5--| + + + + + + + + |--5
483 4--| + + + | + + +-------|--4
485 3--| + + + +-------+ + + |--3
487 2--| + + + + + + + + |--2
489 1--| + + + + + | + + |--1
491 +|||*-------------------------------+
497 * @param w writer to write the board to
498 * @exception IOException if communiction with writer fails
500 public void write (Writer w) throws IOException {
504 private void northSouthSign(int width, char sign, Writer w) throws IOException {
505 int middle = width / 2;
506 for (int x = 0; x < width; x++) {
508 if (x == middle - 1) {
514 if (x == middle + 1) {
519 w.write(System.getProperty("line.separator")); // NOI18N
522 private void subColumnLine(int width, int spaceX, Writer w) throws IOException {
523 for (int x = 0; x < width - 1; x++) {
524 if (x % (spaceX + 1) == 0 && x > 0) {
532 /** This will print the board with provided spacing.
533 * This is example of 3:1 spacing:
539 * and this 4:2 spacing:
547 private void write (Writer w, int spaceX, int spaceY) throws IOException {
548 int width = spaceX * 9 + 10;
549 int height = spaceY * 9 + 10;
550 char[][] desk = new char[height][];
551 for (int i = 0; i < height; i++) {
552 desk[i] = new char[width];
553 for (int j = 0; j < width; j++) {
554 if (i % (spaceY + 1) == 0 && j % (spaceX + 1) == 0) {
561 desk[i][width - 1] = '|';
563 for (int i = 1; i < width - 1; i++) {
565 desk[height -1][i] = '-';
568 desk[0][width - 1] = '+';
569 desk[height - 1][0] = '+';
570 desk[height - 1][width - 1] = '+';
573 for (Player p : players) {
574 int px = p.getXInternal() / 2;
575 int py = p.getYInternal() / 2;
577 [1 + py * (spaceY + 1) + spaceY / 2]
578 [1 + px * (spaceX + 1) + spaceX / 2] = p.endDirection.player;
579 paintLeftFences(desk, p.endDirection, p.getFences(), p.equals(getCurrentPlayer()));
583 for (Fence f : fences) {
584 int fx = (f.getX() / 2 + 1) * (spaceX + 1);
585 int fy = (f.getY() / 2 + 1) * (spaceY + 1);
586 switch (f.getOrientation()) {
588 for (int i = -spaceX; i <= spaceX; i++) {
589 desk[fy][fx + i] = '-';
593 for (int i = -spaceY; i <= spaceY; i++) {
594 desk[fy + i][fx] = '|';
598 throw new IllegalStateException ("Unknown orientation: " + f.getOrientation ()); // NOI18N
602 northSouthSign(width, 'N', w);
603 w.write(System.getProperty("line.separator")); // NOI18N
605 columnLine(width, spaceX, w);
606 w.write(System.getProperty("line.separator")); // NOI18N
608 subColumnLine(width, spaceX, w);
609 w.write(System.getProperty("line.separator")); // NOI18N
611 for (int y = height - 1; y >= 0; y--) {
612 if (y == height / 2) {
617 boolean number = y % (spaceY + 1) == 0 && y > 0 && y < height - 1;
620 w.write(Integer.toString(cnt));
625 for (int x = 0; x < width; x++) {
630 w.write(Integer.toString(cnt));
634 if (y == height / 2) {
637 w.write(System.getProperty("line.separator")); // NOI18N
640 subColumnLine(width, spaceX, w);
641 w.write(System.getProperty("line.separator")); // NOI18N
643 columnLine(width, spaceX, w);
644 w.write(System.getProperty("line.separator")); // NOI18N
645 w.write(System.getProperty("line.separator")); // NOI18N
647 northSouthSign(width, 'S', w);
651 private void paintLeftFences(char[][] desk, Direction endDirection, int fences, boolean currentTurn) {
652 assert fences >= 0 && fences <= 10 : "Players: " + players;
653 switch (endDirection) {
655 for (int i = 0; i < fences; i++) {
656 desk[desk.length - 1][i + 1] = '|';
659 desk[desk.length - 1][fences + 1] = '*';
664 for (int i = 0; i < fences; i++) {
665 desk[0][i + 1] = '|';
668 desk[0][fences + 1] = '*';
684 public int hashCode () {
685 return occupied.hashCode ();
689 public boolean equals (Object o) {
690 if (o instanceof Board) {
692 return occupied.equals (b.occupied) && players.equals (b.players);
697 /** Converts the board into string representation. For more information
698 * about the format see {@link #write(java.io.Writer)}. To read the
699 * string back use {@link #valueOf(java.lang.String)}.
701 * @return string representing the board
704 public String toString() {
705 return Board.board2HashCode(this);
708 public String boardToPicture() {
709 StringWriter w = new StringWriter();
712 } catch (IOException ex) {
713 return ex.toString();
720 // Validation methods
723 /** Computes new position of a player and checks whether there is no
724 * fence between the old and new.
726 private Player newPosition (Player old, Player.Direction direction) throws IllegalPositionException {
727 return newPosition (old, direction, occupied);
731 private static Player newPosition (Player old, Player.Direction direction, BitSet occupied) throws IllegalPositionException {
754 default: throw new IllegalStateException ("Unknown direction: " + direction); // NOI18N
757 if (nx < 0 || nx > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N
758 if (ny < 0 || ny > 16) throw new IllegalPositionException ("Wrong player position: " + nx + ":" + ny); // NOI18N
760 int fenceIndex = toIndex (fx, fy);
761 if (occupied.get (fenceIndex)) {
762 throw new IllegalPositionException ("You cannot go over fences"); // NOI18N
765 return new Player (nx, ny, old.getFences (), old.endDirection);
768 /** @param position the current position of the player
769 * @param endDir the side the player wants to reach
770 * @param fences bits set to 1 when fences are placed
771 * @param reached bits on squares that were already reached (modified during run)
772 * @return true if the end line can be reached
774 private static boolean accessibleFinalLine (Player position, Player.Direction endDir, BitSet fences, BitSet reached) {
775 int index = toIndex (position);
776 if (reached.get (index)) {
777 // already visited without success
781 if (endDir.reached(position)) {
787 for (Player.Direction oneDirection : Player.Direction.values ()) {
789 if (accessibleFinalLine (newPosition (position, oneDirection, fences), endDir, fences, reached)) {
792 } catch (IllegalPositionException ex) {
800 /** Computes mask of the occupried bits.
802 private static BitSet computeOccupied (
803 Collection<Player> players, Collection<Fence> fences
804 ) throws IllegalPositionException {
805 BitSet occupied = new BitSet (17 * 17);
807 for (Player p : players) {
808 if (p.getXInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N
809 if (p.getYInternal() % 2 == 1) throw new IllegalPositionException ("Wrong player position: " + p); // NOI18N
811 int index = toIndex (p);
812 if (occupied.get (index)) {
813 throw new IllegalPositionException ("There cannot be two players at " + p); // NOI18N
815 occupied.set (index);
818 for (Fence f : fences) {
820 for (int i = -1; i <= 1; i++) {
821 int index = toIndex (f, i);
822 if (index < 0 || index > occupied.size ()) {
823 throw new IllegalPositionException ("Wrong fence position: " + f); // NOI18N
825 if (occupied.get (index)) {
826 throw new IllegalPositionException ("Fence collition: " + f); // NOI18N
829 occupied.set (index);
837 /** Converts twodimensional coordinates of player to one dimensional index.
839 private static int toIndex (Player p) {
840 return toIndex (p.getXInternal(), p.getYInternal());
843 /** Converts twodimensional coordinates of fence to one dimensional index.
845 * @param whichPart (-1, 0, 1)
847 private static int toIndex (Fence f, int whichPart) {
851 switch (f.getOrientation ()) {
852 case HORIZONTAL: x += whichPart; break;
853 case VERTICAL: y += whichPart; break;
854 default: throw new IllegalStateException ("Wrong orientation: " + f.getOrientation ()); // NOI18N
857 return toIndex (x, y);
860 /** Diagonal conversion of two positive integers to one integer.
869 private static int toIndex (int x, int y) {
870 assert x >= 0 && x < 17;
871 assert y >= 0 && y < 17;
875 public Board(String hashCode) throws IllegalStateException{
876 this.fences = new HashSet<Fence>();
877 if((hashCode != null) && (hashCode.length() > 6)){
878 char[]c = hashCode.toCharArray();
879 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
880 new Player ((c[0]-'A')*2, (c[1]-'0')*2, c[2]-'a', Player.Direction.NORTH),
881 new Player ((c[3]-'A')*2, (c[4]-'0')*2, c[5]-'a', Player.Direction.SOUTH),
891 this.winner = this.players.get(0);
894 this.winner = this.players.get(1);
899 for(int i=7; i<c.length;i+=2){
900 int f = Integer.parseInt(hashCode.substring(i, i+2),16);
901 Fence.Orientation o = Fence.Orientation.HORIZONTAL;
903 o = Fence.Orientation.VERTICAL;
906 fences.add(new Fence((f/8)*2+1, (f%8)*2+1,o));
909 this.players = Collections.unmodifiableList (Arrays.asList (new Player[] {
910 new Player (8,0,10,Player.Direction.NORTH),
911 new Player (8,16,10,Player.Direction.SOUTH),
917 this.occupied = computeOccupied (players, fences);
918 } catch (IllegalPositionException ex) {
919 throw new IllegalStateException (ex.getMessage ());
923 public static String board2HashCode(Board b){
924 StringBuilder sb = new StringBuilder();
925 for(Player p: b.getPlayers()){
926 sb.append((char)(p.getColumn() + 'A'));
927 sb.append((char)(p.getRow() + '0'));
928 sb.append((char)(p.getFences() + 'a'));
930 Player winner = b.getWinner();
932 if(b.players.indexOf(b.getCurrentPlayer())==0)
934 else if(b.players.indexOf(b.getCurrentPlayer())==1)
939 if(b.players.indexOf(winner)==0)
941 else if(b.players.indexOf(winner)==1)
947 TreeSet<Integer> fences = new TreeSet<Integer>();
948 for(Fence f: b.getFences()){
949 int a = (f.getColumn() - 'A')*8 + (f.getRow()-1);
950 if(f.getOrientation().equals(Fence.Orientation.VERTICAL))
957 sb.append(Integer.toHexString(f));
959 return sb.toString();