Project 2: Qirkat (Alquerque)

Due: Thursday, 9 November 2017. Milestone Due: Monday, 6 November 2017.


The ancient game of Qirkat (more commonly known by its Spanish name, Alquerque) is a forebear of checkers (draughts) and numerous other games throughout the world. It appears to be of middle-eastern origin, and to have been introduced into Europe by Moorish invaders. You can find more information in this article.

In this project, you will be writing a program to play this game. The program will incorporate an AI so that a single human player can play, although it will also provide options for completely manual play and for completely automated play. Your AI need not be terribly sophisticated, but must be able to find forced wins within some number of moves. In addition to the basic text-based interface, you may provide a GUI for playing the game for extra credit.

As usual, first make sure that everything in your repository is properly updated and checked in. Before you start, the command

$ cd  ~/repo
$ git status

should report that the directory is clean and that there are no untracked files that should be added and committed. Never start a new project without doing this.

To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence

git fetch shared
git merge shared/proj2 -m "Get proj2 skeleton"
git push

from your Git working directory. Should we update the skeleton, you can use the same sequence (with an appropriate change in the -m parameter) to update your project with the same changes.

The Game

Qirkat is played by two players (whom we'll call black and white) on a 5x5 grid in which the 25 cells are connected to each other according to the pattern shown in the figure on the left below. Initially, each player has 12 pieces, positioned as shown in the figure on the right. The lettering below and numbering to the left show the notations we will use to identify the positions of pieces. Thus a1 is the lower-left position and e5 the upper right.

Qirkat starting board

There is a frustrating variety variations of the rules of play. Here, we pick and choose a bit, so don't expect other versions of this game to be exactly the same as ours.

The white player moves first, after which play alternates. There are two types of move: non-capturing moves (which we'll simply call moves) and capturing moves (which we'll call jumps). Pieces may move one space along any of the 1 to 5 lines that radiate from its position and do not go backwards towards the base row (which is the bottom of the board for white, or the top of the board for black), except that pieces on the opponent's base row may not move (only jump).

If a piece is adjacent to an enemy piece along a line, and the position immediately on the other side of the enemy piece along the same line is empty, it must capture that enemy piece by jumping over it to the empty position, removing the enemy piece from the board. Jumps may happen in any direction. If after jumping, another jump is possible, it must also be taken, with the process continuing as long as there is an available jump. At any point, when several different jumps are possible, the player may pick any one (there is no requirement to find the longest sequence of jumps). Pieces are removed as soon as they are jumped, so no sequence of jumps can jump over the same position twice.

For example, on the board below, the transparent pieces show the five possible moves moves available to the black piece and the three possible moves available to the white piece (when those positions are empty, as in the figure).

Qirkat moves

The three boards below show three possible capturing sequences (of 4, 1, and 3 white pieces, respectively) for the central black piece. The captured white pieces are numbered with the sequence in which they are captured.

Qirkat jumps

Each player must move or jump on every turn. A player who cannot do so loses. In order to prevent ties, we add one additional rule: a piece may not move back to a position it has previously occupied unless it has jumped since occupying that position. Since pieces can only move forward or horizontally, this is equivalent to saying that when a piece moves horizontally, it must not make a horizontal move in the opposite direction when it is next played (it may still jump in that direction, however).

Textual Input Language

The players (we'll simply call them White and Black) can each be either a manual player, entering moves as input, or an automated player (we'll call it an AI for short). Manual players can talk to the program using either a textual interface, described in this section, or (for extra credit) a GUI.

At any given time, your program can be in one of two states:

Your program should respond to the following textual commands (you may add others). There is one command per line, but otherwise, whitespace may precede and follow command names and operands freely. Empty lines have no effect, and everything from a # character to the end of a line is ignored as a comment.

Commands to begin and end a game

Parameter-setting commands

Entering moves.

One can enter moves either in set-up state or in playing state. In set-up state, moves serve to manually set up a position on the playing board. The first and then every other move is for the White player, the second and then every other is for Black, and the normal legality rules apply to all moves.

We'll denote columns with letters a--e from the left and rows with numerals 1--5 from the bottom, as shown in our initial description of the game board.

A move or jump consists of two or more positions separated by hyphens in the format $c_0r_0-c_1r_1-...$ (e.g., a1-b2 or c3-a5-a3 ). The first position gives a piece owned by the current player, and the second -- and for jumps, subsequent -- positions give empty positions to which the piece moves or jumps.

Your program must reject illegal moves from any player (they have no effect on the board; the program should tell the user that there is an error and request another move). An AI must not make illegal moves.

Miscellaneous commands.


When either player enters a winning move, the program should print a line saying either White wins. or Black wins. (both with a period) as appropriate. Use exactly those phrases, alone on their line. At that point, the program goes back into set-up state (maintaining the final state of the board so that the user may examine it). Don't use these phrases in any other situation.

Whenever a player is an AI, it should print out each move that it makes, using one of the formats

 White moves C0R0-C1R1-....
 Black moves C0R0-C1R1-....

(replacing C0R0-C1R1-... with an actual move, of course.) Again, use exactly those phrases, alone on their line and ending with periods.

Other than this, you may produce any additional user-friendly output you choose, subject to a few restrictions:

Running Your Program

Your job is to write a program to play Qirkat. As usual, you'll run the program with the command

java -ea qirkat.Main

Your AIs must make only legal moves. They are required to be somewhat smart: they should be able to find a forced win that is within five moves of the current position. There will be a tournament at the end.

For extra credit, you can provide a GUI (after all, what computer board game is complete without a GUI?). By default, the command shown above should not use a GUI. Instead, you indicate explicitly that you want it:

java -ea qirkat.Main --display

If you choose not to implement a GUI, make sure that your program terminates with an error exit code of 2 when given the --display parameter. Otherwise, your program should exit with exit code 0, as usual, even if someone entered invalid commands during a session (and simply print error messages in response to the errors).


There is a milestone due the Monday before the final due date. It will be worth some fraction of your total grade for the project. There is no grace period for the milestone. At the milestone, your program must pass the integration tests we gave you in the testing directory, and it must pass the style checks made by the command make pre-style (which does not perform the full set of style checks; it is missing checks on internal comments.)
Submit it with a tag of the form proj2a-N, where N is some decimal numeral.

Your final submission must pass the full make style checks, as well as the autograder's more extensive set of tests.

Submission and Version Control

It is important that you commit work to your repository at frequent intervals. Version control is a powerful tool for saving yourself when you mess something up or your dog eats your project, but you must use it regularly if it is to be of any use. Feel free to commit every 15 minutes; Git only saves what has changed, even though it acts as if it takes a snapshot of your entire project.

The command git status will tell you what you have modified, removed, or possibly added since the last commit. It will also tell you how much you have not yet sent to your central repository. You needn't just assume that things are as you expect; git status will tell you whether you've committed and pushed everything.

If you are switching between using a clone of your central repository on the instructional computers and another at home (or on your laptop), be careful to synchronize your work. When you are done working on one system, be sure push your work to the central repository:

$ git status       # To see what needs to be added or committed.
$ git commit -a    # If needed to get everything committed.
$ git push

When you start working on the other system, you then do

$ git status          # To make sure you didn't accidentally leave
                      # stuff uncommitted or untracked.
$ git pull --rebase   # Get changes from your central repo.

Submit your project by committing and tagging it:

$ git tag proj2-0     # Or proj2-1, etc.
$ git push
$ git push --tags

Be sure to respond to all prompts and to make sure the messages you get indicate that the submission was successful. Don't just "say the magic words" and assume that everything's OK.