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

Introduction

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.

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).

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.

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:

• set-up state, meaning that no game is in progress. Pieces can still be moved according to the usual rules (in order to set up a position, for example). This is the initial state.
• playing state, where players are entering moves and the game is not yet over.

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

• clear Abandons the current game (if one is in progress), clears the board to its initial configuration, and places the program in the set-up state. Abandoning a game implies that you resign. This command is valid in any state.
• start Enters playing state (has no effect if already in playing state). White and Black alternate moves. If there have been moves made during the set-up state, then play picks up at the point where these moves leave off (so, for example, if there was one set-up move made before start, then Black will move first). In the (unusual) case where the set-up moves have already won the game, start causes the program to report the winner and go into set-up state.
• quit Abandons any current game (as for clear) and exits the program. The end of input has the same effect.

Parameter-setting commands

• auto C Puts the game in set-up state and sets up the program so that player C (White or Black) is an AI. Initially, and after a clear command, White is a manual player and Black is an AI. Thus, the command auto White causes both White and Black to be AIs, so that the start command causes the machine to play a game against itself.
• manual C Puts the game in set-up state and Sets up the program so that player C (White or Black) is a manual player. Thus, the command manual Black causes both White and Black to be manual players (who presumably alternate entering moves on a terminal).
• seed N If your program's AIs use pseudo-random numbers to choose moves, this command sets the random seed to N (a long integer). This command has no effect if there is no random component to your automated players (or if you don't use them in a particular game). It doesn't matter exactly how you use N as long as your automated player(s) behave(s) identically in response to any given sequence of moves. In the absence of a seed command, do what you want to seed your generator.

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.

• help Print a brief summary of the commands.

• dump This command is especially for testing and debugging. It prints the board out in exactly the following format:

  ===
    b w - b b
    - w - - -
    b - w w w
    - - - - -
    b - w - b
  ===

  Here, - indicates an empty square, w indicates a White piece, and b indicates a Black piece. Don't use === 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.

• load file Reads the given file and in effect substitutes its contents for the load command itself.
• set C SPEC Puts the current game in set-up state, and sets the board so that it is player C's turn (C is white or black), and the board is as given by SPEC. SPEC is a sequence of 25 'b', 'w', and '-' characters, optionally interspersed with blanks and tabs. These give the board contents row by row starting from row '1'. Initially, all horizontal piece moves are allowed.

Output

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:

• Any input prompts you print must end in a colon (":").
• Do not use the "===" marker except in the specified output from the dump command.
• Do not output any lines containing the words "wins", or "moves", except in the specified cases described above.

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).

Milestone

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.