Project 2: Lines of Action

Please check Piazza for updates, useful resources, and a changelog.


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 one’s 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 combined, 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.


We'll denote columns with letters a–h from the left and rows with numerals 1–8 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 $c_1n_1$ to $c_2n_2$ is denoted $c_1n_1$-$c_2n_2$

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.

As long as the commands described so far work properly, you may add any additional commands you want.


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.


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


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.

Running Your Program

Your job is to write a program to play Lines of Action. Appropriately enough, we'll call the program "loa." To run your program, you'll type

    java -ea loa.Main [--display] [--log=LOGFILE] [INPUT-FILE [OUTPUT-FILE]]

Here, square braces enclose optional arguments. The --display option applies only if you do the extra-credit GUI. The --log argument specifies a file into which the program writes all the commands and moves entered into it (good for capturing the details of a session). The INPUT-FILE specifies a source of commands; by default it is simply the standard input (generally your terminal). Finally, the OUTPUT_FILE specifies a file to receive output printed by the program; by default it is simply the standard output.

Your Task

The shared repository will contain skeleton files for this project, which you can merge into your repository as usual with

    git fetch shared
    git merge shared/proj2

Be sure to include tests of your program (that is part of the grade). The makefile we provide has a convenient target for running such tests. Our skeleton directory contains a couple of trivial tests, but these do not constitute an adequate set of tests! Make up your tests ahead of time and update your makefile to run them. To help with testing and debugging, we will provide our own version of the program, so that you can test your program against ours (we'll be on the lookout for illegal moves).

Your AI should at least be able to find forced wins within a small number of moves. Otherwise, we won't be too particular. In fact, we suggest that you first aim to produce an AI that is simply capable of making legal moves. A forced win in $N$ moves is a situation in which one side can always win after making $N$ moves with proper play, no matter what the opponent does. We'll eventually run a tournament among programs that pass our tests. If you want to understand how to implement your AI, please watch Lecture 22 (Game Trees).

As usual, we'll run a style checker on your code. The skeleton contains deliberate style errors that are there to draw your attention to certain things, including skeletons for extra-credit code. Just because you didn't write the lines that cause them, don't think you can ignore them. You are responsible for all the code you hand in, regardless of who originally wrote it.

Testing Harness and Staff Solution

There is a staff solution available to play against or to better understand the spec. Type staff-loa on the instructional machines to run it. It takes the same arguments as your solution is supposed to take.

Our testing of your projects will be automated. The testing program will be finicky, so be sure that

    make check

runs your tests on the instructional machines.

The integration test program, test-loa, feeds commands to one or two running programs and passes appropriate moves from one to the other, allowing you to test your program and to test it against another program (such as the staff version). To run test-loa, you'll use

python3 testing/test-loa

to run through your program and

python3 testing/test-loa

to run two programs simultaneously so that each one sends all of its AI's moves (such as "* b4d6" as described previously) to the other program. (Replace "TESTFILE" with the actual name of your test file.)

Each .in file should start with a Unix-style command for running a program preceded by "#*", such as

 #* java -ea loa.Main

(You will probably use just the command command above; the autograder will sometimes replace it with an invocation of staff-loa.) The rest of the .in file is fed to this program as the standard input, except for lines that start with "#*" in the first column, which are special instructions to the testing script.

A few other commands apply only to the two-argument form of test-loa. They are intended to allow two programs to play each other.

The idea with these two commands is that one of the two scripts will, at a certain point, contain the commands

#*remote move/win

and the other will contain

#*remote move/win

so that the first sends a move from its AI to the other program, which then waits for a response from its AI to send back, and so forth.

For the remote commands, both programs should generate "wins" messages, and test‑loa will check that they are the same.

The test-loa script throws out any other output from either program except for properly formatted board dumps, as are supposed to be produced by the dump command described previously. You can see all the output by running it with

 python3 testing/test-loa --verbose


 python3 testing/test-loa --verbose

which will show all the commands sent to each program and all their output.

The test-loa program will report an error if a program hangs or times out, or if it exits abnormally (with an exception or an exit code other than 0). Finally, if there is a file TESTFILE-1.std or TESTFILE-2.std, make check will check it against the output from the program for (likewise for TESTFILE-2.std against the output for; make check uses on the script testing/ to do this comparison.


Information about the checkpoint is on Piazza here. The checkpoint is due Friday April 3 11:59 PM.

Extra Credit

Instructions to submit the EC are on Piazza.

For extra credit, you can implement the --display option, and play the game using a graphical user interface (GUI). Don't even think about this until you get your project working! However, you might consider how to structure your solution to make the addition of a GUI simple. The package ucb.gui2 contains classes that make it pretty easy to construct a simple GUI. You will also have to examine the classes java.awt.Graphics and java.awt.Graphics2D to see how to draw things.

We will be manually grading the GUI and awarding points based on this rubric:

Advice & Resources

We've implemented some fussy bits or possibly useful classes in the skeleton. Always remember, however, that you don't have to use them. Your job is to provide tests and make java -ea loa.Main conform to the specification, period. If you need random numbers, take a look at java.util.Random and Chapter 11 of Data Structures (Into Java).

I suggest working first on the representation of the board (the skeleton has a class Board, which is supposed to represent the game board and state of play.) We have also included a skeleton Game class that uses Board to keep track of a series of games and interpret commands. Get this to work with a manual ("human") player first. Then you can tackle writing an automated player MachinePlayer. Start with something really simple (perhaps choosing a legal move at random) and introduce strategy only when you get the basic game-running machinery working properly.

The TAs have created helpful walthrough videos for the numContig method in the Board class, findMove for the MachinePlayer class, and heuristics for the MachinePlayer class. They can be found on Piazza here.