import java.util.Scanner;
import java.util.Collection;
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;

class Player {

  public static final boolean LOCAL = false;

  public Scanner in = new Scanner(System.in);

  public static int turnCount;

  public static PlayerColor MY_COLOR;
  public static PlayerColor OPPONENT_COLOR;
  public static Move OPPONENTS_LAST_MOVE = new Move(-1, -1, PlayerColor.WHITE);
  public static int MY_SCORE;
  public static int OPPONENT_SCORE;
  public static int BOARD_SIZE;
  public static int FIELDS_ON_BOARD;
  public static PlayerColor[][] BOARD;

  public MoveCalculator calculator;
  public Move chosenMove;

  static {
    MoveCalculatorFactory.usedCalculatorImplementation =
        MoveCalculatorImplementation.MOVE_CALCULATOR_LEVEL_1;
    // MoveCalculatorFactory.usedCalculatorImplementation =
    // MoveCalculatorImplementation.MOVE_CALCULATOR_LEVEL_2;
    // MoveCalculatorFactory.usedCalculatorImplementation =
    // MoveCalculatorImplementation.MOVE_CALCULATOR_LEVEL_3;
  }

  /** Entry point at Codingame, which calls then the play() method. */
  public static void main(String[] args) {
    Player p = new Player();
    p.play();
  }

  /**
   * This method is called, by the main Method, which is added by the Converter. This way, the game
   * should be played at Codingame.
   */
  public void play() {
    readInitialInput(in);
    while (true) {
      turnCount++;
      readFromScanner(in);
      calculateMove();
      sendMove();
    }
  }

  private void readInitialInput(Scanner in) {
    String myColor = in.nextLine();
    BOARD_SIZE = in.nextInt(); // the size of the board (width and height)
    MY_COLOR = PlayerColor.fromCharCode(myColor);
    OPPONENT_COLOR = PlayerColor.getOpposizeColor(MY_COLOR);
  }

  /**
   * Default read in logic comes here.
   *
   * @param in Scanner, which provides the defined input lines.
   */
  public void readFromScanner(Scanner in) {
    int opponentX =
        in
            .nextInt(); // The x coordinate of your opponent's last move (or -1 if the opponent
                        // passed)
    int opponentY =
        in
            .nextInt(); // The y coordinate of your opponent's last move (or -1 if the opponent
                        // passed)
    OPPONENTS_LAST_MOVE = new Move(opponentY, opponentX, PlayerColor.getOpposizeColor(MY_COLOR));
    MY_SCORE = in.nextInt(); // Your current score (the number of captured stones)
    OPPONENT_SCORE = in.nextInt(); // the opponents current score (the number of captured stones)

    FIELDS_ON_BOARD = BOARD_SIZE * BOARD_SIZE;
    if (in.hasNextLine()) {
      in.nextLine();
    }
    String[] lines = new String[BOARD_SIZE];
    for (int i = 0; i < BOARD_SIZE; i++) {
      String line =
          in
              .nextLine(); // A row of the current board where 'B' marks a black stone, 'W' marks a
                           // white stone and '.' marks an empty field
      lines[i] = line;
    }

    BOARD = Referee.getBoard(lines);

    chosenMove = null;
  }

  public void sendMove() {
    if (chosenMove == null) {
      System.err.println("ERROR: NO MOVE CHOSEN - USING DEFAULT: PASS");
      System.out.println("PASS");
    } else if (chosenMove.isPass()) {
      System.out.println("PASS");
    } else {
      System.out.println(chosenMove.getCol() + " " + chosenMove.getRow());
    }
  }

  public void calculateMove() {
    if (calculator == null) {
      calculator = MoveCalculatorFactory.createCalculator();
    }
    calculator.calculateMove(this);
  }

  public void setChosenMove(Move chosenMove) {
    this.chosenMove = chosenMove;
  }

  public abstract static class AbstractMoveCalculator implements MoveCalculator {

    public Referee referee;

    public AbstractMoveCalculator() {
      referee = new Referee();
    }

    public abstract void calculateMove(Player player);

    public List<Group> findGroups(Referee ref, PlayerColor color) {
      List<Group> groups = new ArrayList<Group>(Player.FIELDS_ON_BOARD / 2);
      Set<FieldPosition> known = new HashSet<>();
      for (int row = 0; row < Player.BOARD_SIZE; row++) {
        for (int col = 0; col < Player.BOARD_SIZE; col++) {
          FieldPosition pos = new FieldPosition(row, col);
          if (!known.contains(pos) && ref.getStoneColor(pos) == color) {
            Group group = Group.findGroup(ref, pos);
            groups.add(group);
            known.addAll(group.getStones());
          }
        }
      }

      return groups;
    }

    protected void update() {
      // update current scores
      referee.getGame().setStonesCaptured(Player.MY_COLOR, Player.MY_SCORE);
      referee
          .getGame()
          .setStonesCaptured(PlayerColor.getOpposizeColor(Player.MY_COLOR), Player.OPPONENT_SCORE);
      // update the board
      referee.addMove(Player.OPPONENTS_LAST_MOVE);
      referee.setBoard(Player.BOARD);
      referee.setBoard(referee.getBoardCopy());
    }

    protected Move getRandomMove() {
      Move random;
      do {
        random =
            new Move(
                (int) (Math.random() * Player.BOARD_SIZE - 6 + 3),
                (int) (Math.random() * Player.BOARD_SIZE - 6 + 3),
                Player.MY_COLOR);
      } while (!referee.isValidMove(random));
      return random;
    }

    protected List<FieldPosition> getStonesOnBoard() {
      List<FieldPosition> stones = new ArrayList<FieldPosition>(Player.FIELDS_ON_BOARD);
      PlayerColor[][] board = referee.getBoard();
      for (int i = 0; i < Player.BOARD_SIZE; i++) {
        for (int j = 0; j < Player.BOARD_SIZE; j++) {
          if (board[i][j] != null) {
            stones.add(new FieldPosition(i, j));
          }
        }
      }
      return stones;
    }

    protected List<FieldPosition> getFreeFieldsNear(List<FieldPosition> placedStones) {
      List<FieldPosition> freeFieldsNear = new ArrayList<>(Player.FIELDS_ON_BOARD);
      for (FieldPosition stone : placedStones) {
        for (FieldPosition pos : stone.getFieldsNear()) {
          if (referee.isFieldEmpty(pos)) {
            freeFieldsNear.add(pos);
          }
        }
      }
      return freeFieldsNear;
    }
  }

  public static class Vector2D implements Cloneable {

    public double x;
    public double y;

    public static final Vector2D NAN_VEC = new Vector2D(Double.NaN, Double.NaN);
    public static final Vector2D NULL_VEC = new Vector2D(0, 0);

    /*public enum Axis {
    	X,
    	Y;
    }*/

    public Vector2D() {}

    /** Crate a new Vector2D with x and y components. */
    public Vector2D(double x, double y) {
      this.x = x;
      this.y = y;
    }

    public Vector2D(double... val) {
      if (val.length != 2) {
        // throw new LinearAlgebraException("A 2D Vector has 2 entries.");
      }
      x = val[0];
      y = val[1];
    }
    /**
     * Create a Vector2D by an angle (in degree). An angle of 0° results in (x, y) = (1, 0); 90° in
     * (x, y) = (0, 1); ... The resulting vector has a length of 1.
     *
     * @param angleDegree The angle of the new vector in degree.
     */
    public Vector2D(double angleDegree) {
      this(Math.cos(angleDegree * Math.PI / 180), Math.sin(angleDegree * Math.PI / 180));
    }

    private Vector2D(Vector2D clone) {
      this.x = clone.x;
      this.y = clone.y;
    }

    /** Clone this Vector2D object. */
    public Vector2D clone() {
      return new Vector2D(this);
    }

    public String toString() {
      return "Vector2D[x: " + x + " y: " + y + "]";
    }

    public String toString(String format) {
      return String.format(format, x, y);
    }

    public boolean equals(Object obj) {
      if (obj instanceof Vector2D) {
        Vector2D v = (Vector2D) obj;
        return Math.abs(x - v.x) < 1e-8 && Math.abs(y - v.y) < 1e-8;
      }
      return false;
    }

    /** Get this vector as 2D-Array. */
    public double[] asArray() {
      return new double[] {x, y};
    }

    /** The (euclidean) length of the Vector. */
    public double length() {
      return Math.hypot(x, y);
    }
    /**
     * The length of this vector in a given norm.
     *
     * @param norm The norm of the vector length.
     * @return The length of this vector in the given norm.
     */
    public double length(int norm) {
      if (norm == Integer.MAX_VALUE) {
        return Math.max(x, y);
      }
      return Math.pow(Math.pow(x, norm) + Math.pow(y, norm), 1.0 / norm);
    }

    /**
     * Rotate the Vector an angle (in degrees) resulting in a new Vector that is returned.
     *
     * @param degrees The angle to return the vector.
     * @return The new created vector.
     */
    public Vector2D rotate(double degrees) {
      return new Vector2D(getAngle() + degrees).setLength(length());
    }

    /**
     * Project the vector given as parameter on this vector.
     *
     * @param vec The vector that is to be projected on this vector.
     * @return The projected vector.
     */
    public Vector2D project(Vector2D vec) {
      return mult(scalar(vec) / Math.pow(length(), 2));
    }

    /**
     * Add another Vector2D to this vector resulting in a new Vector that is returned.
     *
     * @param vec The vector added to this vector.
     * @return The new created vector.
     */
    public Vector2D add(Vector2D vec) {
      return new Vector2D(x + vec.x, y + vec.y);
    }
    /**
     * Subtract another Vector3D from this vector resulting in a new Vector that is returned.
     *
     * @param vec The vector subtracted from this vector.
     * @return The new created vector.
     */
    public Vector2D sub(Vector2D vec) {
      return new Vector2D(x - vec.x, y - vec.y);
    }
    /**
     * Multiply this vector with a scalar resulting in a new Vector that is returned.
     *
     * @param scalar The scalar to multiply this vector with.
     * @return The new created vector.
     */
    public Vector2D mult(double scalar) {
      return new Vector2D(x * scalar, y * scalar);
    }

    /**
     * Check whether this vector is linearly dependent to the parameter vector.
     *
     * @param vec The checked vector.
     * @return True if the vectors are linearly dependent. False otherwise.
     */
    public boolean isLinearlyDependent(Vector2D vec) {
      double t1 = (x == 0 ? 0 : vec.x / x);
      double t2 = (y == 0 ? 0 : vec.y / y);
      return Math.abs(t1 - t2) < 1e-5 && t1 != 0; // all parameters t are equal and != 0
    }

    /**
     * Check whether the parameter vectors are linearly dependent.
     *
     * @param vectors The vectors that are checked.
     * @return True if the vectors are linearly dependent. False otherwise.
     */
    public boolean isLinearlyDependentVectors(Vector2D... vectors) {
      if (vectors.length < 2) {
        return false;
      } else if (vectors.length > 2) {
        // 3 or more vectors in the R^2 are always linearly dependent
        return true;
      } else {
        return vectors[0].isLinearlyDependent(vectors[1]);
      }
    }

    /**
     * Calculate the scalar product of this vector and the parameter vector.
     *
     * @param vec The vector to calculate the scalar with this vector.
     * @return The scalar of the vectors.
     */
    public double scalar(Vector2D vec) {
      return this.x * vec.x + this.y * vec.y;
    }

    /**
     * Create a new vector with the same direction but a different length as this vector.
     *
     * @param length The length of the new vector.
     * @return The new vector with a new length.
     */
    public Vector2D setLength(double length) {
      double len = length();
      return new Vector2D(x * length / len, y * length / len);
    }

    /**
     * Get the distance of this point's position vector to another point's position vector.
     *
     * @param p The second point's position vector.
     * @return The distance between the points.
     */
    public double distance(Vector2D p) {
      return Math.sqrt((this.x - p.x) * (this.x - p.x) + (this.y - p.y) * (this.y - p.y));
    }

    /** Change this vector to the new coordinates. */
    public void move(double x, double y) {
      this.x = x;
      this.y = y;
    }

    /**
     * Move a point's position vector in a direction (by a vector) and a distance.
     *
     * @param p The direction vector.
     * @param distance The distance to move the new vector
     * @return The new created vector.
     */
    public Vector2D moveTo(Vector2D p, double distance) {
      double d = distance(p);
      double dx = p.x - x;
      double dy = p.y - y;
      double coef = distance / d;
      return new Vector2D(x + dx * coef, y + dy * coef);
    }

    /** Get the angle of this vector. Angle: 0° is right ((x, y) = (1, 0)); on clockwise (degree) */
    public double getAngle() {
      return ((Math.atan2(y, x) * 180 / Math.PI) + 720) % 360;
    }

    /** Get the angle of this vector as radiant. */
    public double getAngleRad() {
      return (Math.atan2(y, x) + 4 * Math.PI) % (2 * Math.PI);
    }

    /**
     * Get the angle difference of this vector to another vector.
     *
     * @param vec The other vector.
     * @return The angle difference of the two vectors (from 0° to 180°).
     */
    public double getAngleDeltaTo(Vector2D vec) {
      double delta = Math.abs(getAngle() - vec.getAngle());
      if (delta > 180) {
        delta = 360 - delta;
      }
      return delta;
    }

    /**
     * Get the vector from this point to another.
     *
     * @param vec The point to which the vector is calculated.
     * @return The vector from this points position vector to the other point.
     */
    public Vector2D vectorTo(Vector2D vec) {
      return new Vector2D(vec.x - x, vec.y - y);
    }

    /**
     * Checks whether a point (by its position vector) is in a given range of this point.
     *
     * @param p The point that is checked.
     * @param range The range used for the check.
     * @return True if the point is in the range of this point (distance <= range).
     */
    public boolean isInRange(Vector2D p, double range) {
      return p != this && distance(p) <= range;
    }

    public double getX() {
      return x;
    }

    public double getY() {
      return y;
    }
  }

  /** The stronges AI for the third and last league */
  public static class MoveCalculatorLevel3 extends AbstractMoveCalculator
      implements MoveCalculator {

    /** The total number of moves that can be simulated in time */
    public final int CALCULATED_MOVES = 100;

    private int numScoreCalculations;
    private long start;

    public void calculateMove(Player player) {
      update();
      numScoreCalculations = 0;
      start = System.currentTimeMillis();
      DebugUtils.pause();

      // first move is random
      if (Player.turnCount == 1) {
        player.setChosenMove(getRandomMove());
        return;
      }

      Map<Move, Referee> possibleMoves = new HashMap<Move, Referee>();

      // add passing as possible move
      possibleMoves.put(new Move(-1, -1, Player.MY_COLOR), referee.clone());

      // stones beneath other placed stones
      List<FieldPosition> placedStones = getStonesOnBoard();
      List<FieldPosition> nearPlacedStones = getFreeFieldsNear(placedStones);

      DebugUtils.print("TIMING after nearPlacedStones: " + (System.currentTimeMillis() - start));

      if (nearPlacedStones.size() > CALCULATED_MOVES) {
        Collections.shuffle(nearPlacedStones);
        nearPlacedStones = nearPlacedStones.subList(0, CALCULATED_MOVES);
      }

      DebugUtils.print("TIMING: after shuffle " + (System.currentTimeMillis() - start));

      for (FieldPosition pos : nearPlacedStones) {
        Move move = new Move(pos.getRow(), pos.getCol(), Player.MY_COLOR);
        if (referee.isValidMove(move)) {
          Referee ref = referee.clone();
          ref.addMove(move);
          possibleMoves.put(move, ref);
        }
      }

      DebugUtils.print(
          "TIMING after adding near placed stones: " + (System.currentTimeMillis() - start));

      // all other positions (if spaces left)
      int calculationsLeft = CALCULATED_MOVES - possibleMoves.size();
      for (int i = 0; i < calculationsLeft; i++) {
        Move random =
            new Move(
                (int) (Math.random() * Player.BOARD_SIZE),
                (int) (Math.random() * Player.BOARD_SIZE),
                Player.MY_COLOR);
        if (referee.isValidMove(random)) {
          Referee ref = referee.clone();
          ref.addMove(random);
          possibleMoves.put(random, ref);
        }
      }

      DebugUtils.print(
          "TIMING after adding left calculations: " + (System.currentTimeMillis() - start));

      TreeMap<Double, Move> scores = new TreeMap<>();
      for (Map.Entry<Move, Referee> move : possibleMoves.entrySet()) {
        double score = calculateRefereeScore(move.getValue());
        scores.put(score, move.getKey());
      }

      Move bestMove;
      if (scores.isEmpty()) {
        bestMove = new Move(-1, -1, Player.MY_COLOR);
      } else {
        bestMove = scores.lastEntry().getValue();
      }
      player.setChosenMove(bestMove);

      referee.addMove(bestMove);
    }

    public double calculateRefereeScore(Referee ref) {
      DebugUtils.pause();
      DebugUtils.print(numScoreCalculations + ": " + (System.currentTimeMillis() - start));
      numScoreCalculations++;
      DebugUtils.start();

      double score = 0;

      int myScore = ref.getGame().getStonesCaptured(Player.OPPONENT_COLOR);
      int opponentScore = ref.getGame().getStonesCaptured(Player.MY_COLOR);

      score += myScore * 1000;
      score -= opponentScore * 1000;

      List<Group> myGroups = findGroups(ref, Player.MY_COLOR);
      List<Group> opponentGroups = findGroups(ref, Player.OPPONENT_COLOR);

      int libertiesMe = 0;
      int minLibertiesOpponent = Integer.MAX_VALUE;
      int minLibertiesMe = Integer.MAX_VALUE;

      for (Group group : myGroups) {
        int liberties = group.getLiberties(ref).size();
        libertiesMe += liberties;
        minLibertiesMe = Math.min(liberties, minLibertiesMe);
      }
      for (Group group : opponentGroups) {
        int liberties = group.getLiberties(ref).size();
        minLibertiesOpponent = Math.min(liberties, minLibertiesOpponent);
      }

      score += libertiesMe;
      score += minLibertiesMe * 10;
      score -= minLibertiesOpponent * 100;

      if (minLibertiesMe == 1) {
        score -= 1000;
      }

      return score;
    }
  }

  /** A slightly better AI for the second league: */
  public static class MoveCalculatorLevel2 extends AbstractMoveCalculator
      implements MoveCalculator {

    public void calculateMove(Player player) {
      update();

      // first move is random
      if (Player.turnCount == 1) {
        player.setChosenMove(getRandomMove());
        return;
      }

      Map<Move, Referee> possibleMoves = new HashMap<Move, Referee>();
      for (int row = 0; row < Player.BOARD_SIZE; row++) {
        for (int col = 0; col < Player.BOARD_SIZE; col++) {
          Move move = new Move(row, col, Player.MY_COLOR);
          Referee ref = referee.clone();
          if (ref.isValidMove(move)) {
            ref.addMove(move);
            possibleMoves.put(move, ref);
          }
        }
      }
      // add passing as possible move
      possibleMoves.put(new Move(-1, -1, Player.MY_COLOR), referee.clone());

      TreeMap<Double, Move> scores = new TreeMap<>();
      for (Map.Entry<Move, Referee> move : possibleMoves.entrySet()) {
        double score = calculateRefereeScore(move.getValue());
        scores.put(score, move.getKey());
      }

      Move bestMove;
      if (scores.isEmpty()) {
        bestMove = new Move(-1, -1, Player.MY_COLOR);
      } else {
        bestMove = scores.lastEntry().getValue();
      }
      player.setChosenMove(bestMove);

      referee.addMove(bestMove);
    }

    public double calculateRefereeScore(Referee ref) {
      double score = 0;

      int myScore = ref.getGame().getStonesCaptured(Player.OPPONENT_COLOR);
      int opponentScore = ref.getGame().getStonesCaptured(Player.MY_COLOR);

      score += myScore * 1000;
      score -= opponentScore * 1000;

      List<Group> myGroups = findGroups(ref, Player.MY_COLOR);
      List<Group> opponentGroups = findGroups(ref, Player.OPPONENT_COLOR);

      int libertiesMe = 0;
      int minLibertiesOpponent = Integer.MAX_VALUE;
      int minLibertiesMe = Integer.MAX_VALUE;

      for (Group group : myGroups) {
        int liberties = group.getLiberties(ref).size();
        libertiesMe += liberties;
        minLibertiesMe = Math.min(liberties, minLibertiesMe);
      }
      for (Group group : opponentGroups) {
        int liberties = group.getLiberties(ref).size();
        minLibertiesOpponent = Math.min(liberties, minLibertiesOpponent);
      }

      score += libertiesMe;
      score += minLibertiesMe * 10;
      score -= minLibertiesOpponent * 100;

      return score;
    }
  }

  /**
   * Simple AI for first league:
   *
   * <p>if (can kill enemy stones) kill them else choose a random legal move
   */
  public static class MoveCalculatorLevel1 extends AbstractMoveCalculator
      implements MoveCalculator {

    public void calculateMove(Player player) {
      DebugUtils.print("start");
      update();
      DebugUtils.print("after update");

      // first move is random
      if (Player.turnCount == 1) {
        player.setChosenMove(getRandomMove());
        return;
      }
      DebugUtils.print("after random first turn");

      Map<Move, Referee> possibleMoves = new HashMap<Move, Referee>();
      for (int row = 0; row < Player.BOARD_SIZE; row++) {
        for (int col = 0; col < Player.BOARD_SIZE; col++) {
          Move move = new Move(row, col, Player.MY_COLOR);
          Referee ref = referee.clone();
          if (ref.isValidMove(move)) {
            ref.addMove(move);
            possibleMoves.put(move, ref);
          }
        }
      }
      DebugUtils.print("after possible moves");
      // add passing as possible move
      possibleMoves.put(new Move(-1, -1, Player.MY_COLOR), referee.clone());
      DebugUtils.print("after pass as possible move");

      TreeMap<Double, Move> scores = new TreeMap<>();
      for (Map.Entry<Move, Referee> move : possibleMoves.entrySet()) {
        double score = calculateRefereeScore(move.getValue());
        scores.put(score, move.getKey());
      }
      DebugUtils.print("after scores");

      Move bestMove;
      if (scores.isEmpty()) {
        bestMove = new Move(-1, -1, Player.MY_COLOR);
      } else {
        bestMove = scores.lastEntry().getValue();
      }
      player.setChosenMove(bestMove);

      DebugUtils.print("after setChosenMove");

      referee.addMove(bestMove);

      DebugUtils.print("end");
    }

    public double calculateRefereeScore(Referee ref) {
      double score = 0;

      int myScore = ref.getGame().getStonesCaptured(Player.OPPONENT_COLOR);
      int opponentScore = ref.getGame().getStonesCaptured(Player.MY_COLOR);

      score += myScore * 1000;
      score -= opponentScore * 1000;

      score += Math.random();

      return score;
    }
  }

  public static class Group {

    private Set<FieldPosition> stones;
    private PlayerColor color;

    public Group(Set<FieldPosition> stones, PlayerColor color) {
      this.stones = stones;
      this.color = color;
    }

    public Group(PlayerColor color) {
      this.color = color;
      this.stones = new HashSet<FieldPosition>();
    }

    public static Group findGroup(Referee ref, FieldPosition startingPosition) {
      PlayerColor groupColor = ref.getStoneColor(startingPosition);
      final int boardSize = Player.BOARD_SIZE;
      if (groupColor == null) {
        throw new IllegalArgumentException(
            "The field of the starting position is empty (position was: " + startingPosition + ")");
      }

      // complete the group by adding stones using a flood fill
      Set<FieldPosition> allStones = new HashSet<FieldPosition>();

      // initialize the current queue and the next step queue
      Set<FieldPosition> currentStones = new HashSet<FieldPosition>();
      Set<FieldPosition> nextStones = new HashSet<FieldPosition>();

      // add the starting position
      currentStones.add(startingPosition);

      // add the fields with the iterative flood fill till the queues are empty
      while (!currentStones.isEmpty()) {
        for (FieldPosition currentField : currentStones) {
          for (FieldPosition near : currentField.getFieldsNear(boardSize)) {
            if (near.exists(boardSize)
                && // the field exists on the board
                ref.getStoneColor(near) != null
                && // prevent NPE
                ref.getStoneColor(near).equals(groupColor)
                && // the field contains a stone of the group color
                !allStones.contains(near)
                && !currentStones.contains(near)) { // the field is not already added
              nextStones.add(near);
            }
          }
        }
        // add the current stones to the group, copy the next steps to the queue and clear next
        // steps
        allStones.addAll(currentStones);
        currentStones = nextStones;
        nextStones = new HashSet<FieldPosition>();
      }

      return new Group(allStones, groupColor);
    }

    public boolean isBeaten(Referee ref) {
      Set<FieldPosition> nearFreeFields = getLiberties(ref);

      return nearFreeFields.isEmpty();
    }

    public Set<FieldPosition> getLiberties(Referee ref) {
      Set<FieldPosition> liberties = new HashSet<>();
      for (FieldPosition stone : stones) {
        for (FieldPosition pos : stone.getFieldsNear()) {
          if (pos.exists() && ref.isFieldEmpty(pos)) {
            liberties.add(pos);
          }
        }
      }
      return liberties;

      //		return stones.stream().flatMap(s -> s.getFieldsNear(Player.BOARD_SIZE).stream()) //all
      // fields near
      //				.filter(field -> field.exists(Player.BOARD_SIZE) && ref.isFieldEmpty(field)) //existing
      // and empty
      //				.collect(Collectors.toSet());
    }

    public void addStone(FieldPosition pos) {
      stones.add(pos);
    }

    public void addStones(List<FieldPosition> positions) {
      stones.addAll(positions);
    }

    public void remove(FieldPosition pos) {
      stones.remove(pos);
    }

    public void clear() {
      stones.clear();
    }

    public Set<FieldPosition> getStones() {
      return stones;
    }

    public void setStones(Set<FieldPosition> stones) {
      this.stones = stones;
    }

    public PlayerColor getColor() {
      return color;
    }

    public void setColor(PlayerColor color) {
      this.color = color;
    }
  }

  public static class DebugUtils {

    public static final boolean DEBUG = true;
    public static boolean PAUSE_DEBUG = false;

    public static final String DEFAULT_VECTOR_FORMAT = "(%4.0f|%4.0f)";

    public static void pause() {
      PAUSE_DEBUG = true;
    }

    public static void start() {
      PAUSE_DEBUG = false;
    }

    public static void printVector2D(Vector2D vec, String prefix) {
      print(prefix + vec.toString("(%4.0f|%4.0f)"));
    }

    public static void printVector2D(Vector2D vec, String prefix, String format) {
      print(prefix + vec.toString(format));
    }

    public static void printBoard(PlayerColor[][] board) {
      StringBuilder sb = new StringBuilder();
      for (PlayerColor[] line : board) {
        for (PlayerColor field : line) {
          sb.append(PlayerColor.toCharCode(field));
        }
        sb.append('\n');
      }
      print(sb.toString());
    }

    public static void print(Object obj) {
      print(obj.toString());
    }

    public static void print(String s) {
      if (DEBUG) {
        if (!PAUSE_DEBUG) {
          System.err.println(s);
        }
      }
    }
  }

  public static class Game {

    private int blackStonesCaptured;
    private int whiteStonesCaptured;

    public Game clone() {
      Game clone = new Game();
      clone.setBlackStonesCaptured(blackStonesCaptured);
      clone.setWhiteStonesCaptured(whiteStonesCaptured);
      return clone;
    }

    public int getStonesCaptured(PlayerColor color) {
      if (color == PlayerColor.BLACK) {
        return getBlackStonesCaptured();
      } else if (color == PlayerColor.WHITE) {
        return whiteStonesCaptured;
      }
      throw new IllegalStateException("Unknown PlayerColor: " + color);
    }

    public void setStonesCaptured(PlayerColor color, int captured) {
      if (color == PlayerColor.BLACK) {
        blackStonesCaptured = captured;
      } else if (color == PlayerColor.WHITE) {
        whiteStonesCaptured = captured;
      } else {
        throw new IllegalStateException("Unknown PlayerColor: " + color);
      }
    }

    public int getBlackStonesCaptured() {
      return blackStonesCaptured;
    }

    public void setBlackStonesCaptured(int blackStonesCaptured) {
      this.blackStonesCaptured = blackStonesCaptured;
    }

    public int getWhiteStonesCaptured() {
      return whiteStonesCaptured;
    }

    public void setWhiteStonesCaptured(int whiteStonesCaptured) {
      this.whiteStonesCaptured = whiteStonesCaptured;
    }
  }

  public static class FieldPosition {

    private int row;
    private int col;

    public FieldPosition(int row, int col) {
      super();
      this.row = row;
      this.col = col;
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + col;
      result = prime * result + row;
      return result;
    }

    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      FieldPosition other = (FieldPosition) obj;
      if (col != other.col) return false;
      if (row != other.row) return false;
      return true;
    }

    public List<FieldPosition> getFieldsNear() {
      return getFieldsNear(Player.BOARD_SIZE);
    }

    public List<FieldPosition> getFieldsNear(int boardSize) {
      int[][] near = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
      List<FieldPosition> nearFields = new ArrayList<FieldPosition>();
      for (int[] nearDiff : near) {
        FieldPosition position = new FieldPosition(row + nearDiff[0], col + nearDiff[1]);
        if (position.exists(boardSize)) {
          nearFields.add(position);
        }
      }
      return nearFields;
    }

    public boolean exists() {
      return exists(Player.BOARD_SIZE);
    }

    public boolean exists(int boardSize) {
      return row >= 0 && col >= 0 && row < boardSize && col < boardSize;
    }

    public int getRow() {
      return row;
    }

    public void setRow(int row) {
      this.row = row;
    }

    public int getCol() {
      return col;
    }

    public void setCol(int col) {
      this.col = col;
    }
  }

  public interface MoveCalculator {

    public void calculateMove(Player player);
  }

  public static class MoveCalculatorFactory {

    public static MoveCalculatorImplementation usedCalculatorImplementation;

    public static MoveCalculator createCalculator() {
      switch (usedCalculatorImplementation) {
        case MOVE_CALCULATOR_LEVEL_1:
          return new MoveCalculatorLevel1();
        case MOVE_CALCULATOR_LEVEL_2:
          return new MoveCalculatorLevel2();
        case MOVE_CALCULATOR_LEVEL_3:
          return new MoveCalculatorLevel3();
        default:
          throw new IllegalStateException(
              "Unknown implementation type: "
                  + usedCalculatorImplementation
                  + "; choose a type in MoveCalculatorFactory or declare the unknown type");
      }
    }
  }

  public enum MoveCalculatorImplementation {
    MOVE_CALCULATOR_LEVEL_1, //
    MOVE_CALCULATOR_LEVEL_2, //
    MOVE_CALCULATOR_LEVEL_3, //
  }

  public enum PlayerColor {
    BLACK,
    WHITE;

    public static PlayerColor getOpposizeColor(PlayerColor lastMove) {
      switch (lastMove) {
        case BLACK:
          return WHITE;
        case WHITE:
          return BLACK;
        default:
          return null;
      }
    }

    public static String toCharCode(PlayerColor color) {
      if (color == BLACK) {
        return "B";
      }
      if (color == WHITE) {
        return "W";
      }
      return ".";
    }

    public String toCharCode() {
      return toCharCode(this);
    }

    public static PlayerColor fromCharCode(String charCode) {
      if (charCode.equals("B")) {
        return BLACK;
      } else if (charCode.equals("W")) {
        return WHITE;
      }
      throw new IllegalStateException("unknown charCode: " + charCode);
    }
  }

  public static class Referee {

    public static final int FRAME_DURATION = 800;
    public static final int FRAME_WIDTH = 1920;
    public static final int FRAME_HEIGHT = 1080;
    public static final int BOARD_WIDTH = 950;

    private Game game;

    private PlayerColor[][] board;
    private PlayerColor[][] previousBoard;

    public Referee() {
      this(new Game());
    }

    public Referee(Game game) {
      this.game = game;
      board = new PlayerColor[Player.BOARD_SIZE][Player.BOARD_SIZE];
    }

    // ***************************************************************************************************************
    // *** CG stuff
    // ***************************************************************************************************************

    // ***************************************************************************************************************
    // *** simulation
    // ***************************************************************************************************************

    public Referee clone() {
      Referee clone = new Referee(game.clone());
      clone.board = new PlayerColor[Player.BOARD_SIZE][Player.BOARD_SIZE];
      clone.previousBoard = new PlayerColor[Player.BOARD_SIZE][Player.BOARD_SIZE];

      for (int i = 0; i < Player.BOARD_SIZE; i++) {
        clone.board = getBoardCopy(board);
        clone.previousBoard = getBoardCopy(previousBoard);
      }

      return clone;
    }

    // ***************************************************************************************************************
    // *** game methods
    // ***************************************************************************************************************

    public static PlayerColor[][] getBoard(String[] lines) {
      int size = lines.length;
      PlayerColor[][] board = new PlayerColor[size][size];
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
          if (lines[i].charAt(j) == 'B') {
            board[i][j] = PlayerColor.BLACK;
          } else if (lines[i].charAt(j) == 'W') {
            board[i][j] = PlayerColor.WHITE;
          }
        }
      }
      return board;
    }

    /** Execute all moves in the list to create the current board */

    /*private*/ void fillBoard(List<Move> moves) throws IllegalArgumentException {
      if (moves != null) {
        for (Move move : moves) {
          if (isValidMove(move)) {
            addMove(move);
          } else {
            throw new IllegalArgumentException(
                "Invalid move. The given list of moves contains a move that is not valid: " + move);
          }
        }
      }
    }

    public PlayerColor[][] getBoard() {
      return board;
    }

    /** A deep copy of the current board */
    public PlayerColor[][] getBoardCopy() {
      return getBoardCopy(board);
    }

    public PlayerColor[][] getBoardCopy(PlayerColor[][] board) {
      PlayerColor[][] newBoard = new PlayerColor[Player.BOARD_SIZE][Player.BOARD_SIZE];
      if (board != null) {
        for (int i = 0; i < Player.BOARD_SIZE; i++) {
          for (int j = 0; j < Player.BOARD_SIZE; j++) {
            newBoard[i][j] = board[i][j];
          }
        }
      }
      return newBoard;
    }
    /**
     * Check whether the move is valid
     *
     * <p>Checked are:
     *
     * <ul>
     *   <li>color (players turn)
     *   <li>position (on field and empty)
     *   <li>no suicidal move (placed stone is not directly beaten)
     *   <li>ko rule (move doesn't create the same board that was there in the last move)
     * </ul>
     */
    public boolean isValidMove(Move move) {
      if (move.isPass()) {
        // passing is always a valid move
        return true;
      }
      if (!move.getPos().exists(Player.BOARD_SIZE)) {
        // position doesn't exist
        return false;
      }
      if (getStoneColor(move.getPos()) != null) {
        // field not empty
        return false;
      }

      // execute the move and check whether the state is valid
      PlayerColor[][] tmpBoard = getBoardCopy(); // keep a copy of the board for a rollback
      // make the move
      board[move.getRow()][move.getCol()] = move.getColor();
      removeBeaten(move);

      // check the group of the new stone
      Group group = Group.findGroup(this, move.getPos());
      if (group.isBeaten(this)) {
        // added stone is directly beaten
        board = tmpBoard;
        return false;
      }

      if (!Player.OPPONENTS_LAST_MOVE.isPass() && boardsEqual(board, previousBoard)) {
        // restores the board from the last move (ko rule violated)
        board = tmpBoard;
        return false;
      }

      board = tmpBoard;
      return true;
    }

    /*private*/ static boolean boardsEqual(PlayerColor[][] board, PlayerColor[][] previousBoard) {
      if (previousBoard == null) {
        // previousBoard can be null if there was no previous move
        // in this case the ko-rule can't be violated and the boards are treated as not equal (so
        // false is returned)
        return false;
      }
      boolean equal = true;
      for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
          equal &= board[i][j] == previousBoard[i][j];
        }
      }
      return equal;
    }

    /**
     * Execute a move without checking whether it's valid. The new stone is added and beaten ones
     * are removed
     */
    public void addMove(Move move) {
      if (!move.isPass()) {
        // copy the board to the previous board field
        previousBoard = getBoardCopy();

        // set the new stone
        board[move.getRow()][move.getCol()] = move.getColor();
        // remove beaten stones (if any)
        removeBeaten(move, true);
      }
    }

    /** Remove all stones that were beaten by the move */

    /*private*/ void removeBeaten(Move move) {
      removeBeaten(move, false);
    }

    private void removeBeaten(Move move, boolean countBeaten) {
      // find the fields near to the move field
      List<FieldPosition> near = move.getPos().getFieldsNear(Player.BOARD_SIZE);
      for (FieldPosition pos : near) {
        // check whether the field has a stone of the different color on it
        if (getStoneColor(pos) == PlayerColor.getOpposizeColor(move.getColor())) {
          Group group = Group.findGroup(this, pos);
          if (group.isBeaten(this)) {
            removeStones(group.getStones(), countBeaten);
          }
        }
      }
    }

    /** Remove all stones in the collection from the field */

    /*private*/ void removeStones(Collection<FieldPosition> stones) {
      removeStones(stones, false);
    }

    private void removeStones(Collection<FieldPosition> stones, boolean countBeaten) {
      int stonesBeaten = stones.size();
      PlayerColor beatenStonesColor = null;
      for (FieldPosition pos : stones) {
        beatenStonesColor = board[pos.getRow()][pos.getCol()];
        board[pos.getRow()][pos.getCol()] = null;
      }

      if (countBeaten) {
        if (beatenStonesColor == PlayerColor.BLACK) {
          game.setBlackStonesCaptured(game.getBlackStonesCaptured() + stonesBeaten);
        } else if (beatenStonesColor == PlayerColor.WHITE) {
          game.setWhiteStonesCaptured(game.getWhiteStonesCaptured() + stonesBeaten);
        }
      }
    }

    public boolean isFieldEmpty(FieldPosition pos) {
      return board[pos.getRow()][pos.getCol()] == null;
    }

    public PlayerColor getStoneColor(FieldPosition pos) {
      return board[pos.getRow()][pos.getCol()];
    }

    public Game getGame() {
      return game;
    }

    public void setBoard(PlayerColor[][] board) {
      this.board = board;
    }

    public void setPreviousBoard(PlayerColor[][] board) {
      this.previousBoard = board;
    }

    public PlayerColor[][] getPreviousBoard() {
      return previousBoard;
    }

    public void printBoards() {
      DebugUtils.print("Board");
      DebugUtils.printBoard(board);
      DebugUtils.print("Previous Board");
      DebugUtils.printBoard(previousBoard);
    }
  }

  /** @author Tobias */
  public static class Move {

    private int row;
    private int col;
    private Type type;
    private PlayerColor color;

    public enum Type {
      STONE,
      PASS;
    }

    public Move(int row, int col, PlayerColor color) {
      this.row = row;
      this.col = col;
      this.color = color;
      this.type = Type.STONE;
      if (row == -1 && col == -1) {
        this.type = Type.PASS;
      }
    }

    public static Move getPassMove(PlayerColor color) {
      Move pass = new Move(-1, -1, color);
      pass.setType(Type.PASS);
      return pass;
    }

    public FieldPosition getPos() {
      return new FieldPosition(row, col);
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + col;
      result = prime * result + ((color == null) ? 0 : color.hashCode());
      result = prime * result + row;
      return result;
    }

    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      Move other = (Move) obj;
      if (col != other.col) return false;
      if (color != other.color) return false;
      if (row != other.row) return false;
      return true;
    }

    public int getRow() {
      return row;
    }

    public void setRow(int row) {
      this.row = row;
    }

    public int getCol() {
      return col;
    }

    public void setCol(int col) {
      this.col = col;
    }

    public PlayerColor getColor() {
      return color;
    }

    public void setColor(PlayerColor color) {
      this.color = color;
    }

    public Type getType() {
      return type;
    }

    public void setType(Type type) {
      this.type = type;
    }

    public boolean isPass() {
      return type == Type.PASS;
    }
  }
}
