# Lines of Action

Introduction
Lines of Action is a board game invented by Claude Soucie. It is played on a checkerboard with ordinary checkers pieces. The two players take turns, each moving a piece, and possibly capturing an opposing piece. The goal of the game is to get all of ones pieces into one group of pieces that are connected. Two pieces are connected if they are adjacent horizontally, vertically, or diagonally. Initially, the pieces are arranged as shown in Figure 1. Play alternates between Black and White, with Black moving first. Each move consists of moving a piece of your color horizontally, vertically, or diagonally onto an empty square or onto a square occupied by an opposing piece, which is then removed from the board. A piece may jump over friendly pieces (without disturbing them), but may not cross enemy pieces, except one that it captures. A piece must move a number of squares that is exactly equal to the total number of pieces (black and white) on the line along which it chooses to move (the line of action). This line contains both the squares behind and in front of the piece that moves, as well as the square the piece is on. A piece may not move off the board, onto another piece of its color, or over an opposing piece.

Initial Board and Moves
Figure 1. (a) Initial position, showing standard designations for rows and columns. (b) Possible moves for the black piece at f3. In (b) the piece at f3 cannot move horizontally to the right because it would be forced to move 4 steps, which would push it off the board. The same piece cannot move vertically up because there are 4 pieces in the vertical line of action and moving 4 steps up would require it to move over enemy pieces

Figure 1b illustrates the four possible moves for a black piece in the position shown. (The examples here are taken from the BoardSpace website.) The move f3-d5 is a capture; all others are ordinary moves. The diagonal moves are all two squares, since there are two pieces along each of the diagonals shown. The horizontal move is four squares because of the four pieces in row 3.

The game ends when one side’s pieces are contiguous: that is, there is a path connecting any two pieces of that side’s color by a sequence of steps to adjacent squares (horizontally, vertically, or diagonally), each of which contains a piece of same color. Hence, when a side is reduced to a single piece, all of its pieces are contiguous. If a move causes both sides’ pieces to be contiguous, the winner is the side that made that move. One can have infinite games, where players just repeat positions indefinitely. We will prevent this with a move-limit rule: if the current move limit is L moves (the default is 60), then after the two sides both make L moves (without either side winning), the game ends in a tie. Our testing will always include time limits; somebody will eventually lose if two players repeat positions many times. Figure 2a shows a final position. Figure 2b shows a board just before a move that will give both sides contiguous pieces. Since the move is White’s, White wins this game.

Initial Board and Moves
Figure 2. End positions. Position (a) is a win for Black. In position (b), White can move as shown, capturing an isolated black piece and giving both players contiguous pieces. Since it is White’s move, however, the result is counted as a winning position for White.

Notation
We’ll denote columns with letters ah from the left and rows with numerals 18 from the bottom, as shown in Figure 1 and Figure 2. The square at column c and row n is denoted cn. A move from c1n1 to c2n2 is denoted c1n1-c2n2
Textual Input Language
Your program should respond to the following textual commands (you may add others). There is one command per line, but whitespace may precede and follow command names and operands freely. Empty lines have no effect, and a command line whose first non-blank character is # is ignored as a comment. Extra arguments to a command (beyond those specified below) are ignored. An end-of-file indication on the command input should have the same effect as the quit command.

new: Abandons the current game (if one is in progress), and clears the board to its initial configuration. Sets the current player to Black. Takes moves alternately from Black and White.
c1r1-c2r2: As indicated under Notation, denotes a move from c1r1 to c2r2 (e.g., b8-b6.) This command is not valid after a game has ended and before the board has been cleared for a new game. The first and then every other move is for the Black player, the second and then every other is for White, and the normal legality rules apply to all moves.
auto P: Causes player P to be played by an automated player (an AI) on subsequent moves. The value P must be “black” or “white” (ignore case”black” or “BLACK” also work.) Initially, White is an automated player.
manual P: Causes player P to take moves from the terminal on subsequent moves. The value of P is as for the auto command. Initially, Black is a manual player.
set CR P N: Depending on P, sets the contents of square CR. P may be black, white, or – (denoting empty). Make N (black or white) the next player to move. As for auto and manual, case is irrelevant. This command is intended for setting up particular positions quickly for testing or study, and is not intended for normal play.
dump: This command is especially for testing and debugging. It prints the board out in exactly the following format:

===
– b b b b b b –
w – – – – – – w
w – – – – – – w
w – – – – – – w
w – – – – – – w
w – – – – – – w
w – – – – – – w
– b b b b b b –
Next move: black
===
with the === markers at the left margin and the board indented four spaces. Here, – indicates an empty square, and w and b indicate white or black pieces. Don’t use the two === markers anywhere else in your output. This gives the autograder a way to determine the state of your game board at any point. It does not change any of the state of the program.

seed N: If your program’s automated players use pseudo-random numbers to choose moves, this command sets the random seed to N (a long integer). It has no effect if there is no random component to your automated players (or if you don’t use automated players in a particular game). It doesn’t matter exactly how you use N as long as your automated player behaves identically each time it is seeded with N. In the absence of a seed command, do what you want to seed your generator. The idea behind seed is to make it possible to have reproducible results when testing an AI. For example,

import java.util.Random;
Random r = new Random();
r.setSeed(100000000);
System.out.println(r.nextInt(100));
System.out.println(r.nextInt(100));
(The call nextInt(int r) returns an integer between 0 and the r.) When we run this program, we will deterministically get the same output every time. For example, if we get 80 and then 30 printed, the next time we run the program, 80 and 30 will print again, even though the nextInt method returns a “random” number (this is why we officially call these “pseudo-random numbers.”)

limit N Sets the move limit to 2N (initially, it is N=30). If both players make N moves and neither side has won, the game is a draw. The value of N may not be less than or equal to the number of moves made so far by either player.
help: Prints a brief summary of the commands.
quit: Exits the program.
As long as the commands described so far work properly, you may add any additional commands you want.

Errors
Moves must be legal, or your program must reject them without affecting the board. Humans are expected to make errors; your program should ask for another move when this happens. Similarly, your program should respond to other invalid commands by simply reporting the error and prompting for a new command. AIs must never make illegal moves.

Output
Each time the program expects a move from a human player, it should prompt. You may prompt however you please with a string that ends with > followed by any number of blanks (one does not typically print a newline after a prompt.) Write prompts to the standard output. It is probably wise to “flush” System.out explicitly after printing a prompt with

System.out.flush();
Do not print a > character except as a prompt.

Whenever an AI moves, your program should print the move on the standard output using exactly the following format:

* a2-c2
(with asterisk shown). Do not print these lines out for a manual player’s moves.

When one side wins, the program should print out one of

* White wins.
* Black wins.
* Tie game.
(also with periods) as appropriate. Do not use the * character in any other output you produce.

Your program should not exit until it receives a quit command or reaches the end of its input.

You are free to produce any other output you want, subject to the restrictions above (which are there to make autograding easier). So, for example, you might want to print the board automatically from time to time, especially when at least one player is an AI. As long as you do so without using the === markers, you are free to produce whatever output you want.