Lab46 Wiki

To gain an understanding of tree-based data structures and their use in algorithms, while working together collaboratively.

The intent of this project is to explore the use of tree-based data structures through the implementation of a Backgammon board game.

If you are not familiar, please reference the Wikipedia article on Backgammon.

Your task, working together as a class, is to implement this game.

You must:

• Implement an accurate version of this game on Lab46
  • code should compile and link without error (preferably no warnings)
  • code should execute without logical errors
  • code should execute without runtime errors
  • game rules need to be enforced for all modes of game
  • implementations should include:
    1. player vs. player
    2. player vs. computer
  • on player vs. computer, there should be at least 3 difficulty levels:
    1. easy
    2. medium
    3. challenging
• The entire class is working together on this project
  • everyone needs to make regular contributions to the code base (commits to the repository)
  • everyone needs to make regular contributions to the wiki page (updates to the wiki page)
• ALL solutions must utilize “pointer”-based trees (nodes)
• The project must have a wiki page providing:
  • general user documentation
  • explanation of rules
  • Programming APIs (classes, functions)
• Source code must be:
  • well documented (no function should be without comments)
  • organized and uniform in style (use indent)
  • easy to read (wrap comments at 80 characters, try to break up long lines of code)
• You are to make use of a version control system, such as subversion, to develop the project.
• Implementations should consist of at least 4 sources files, plus utilize a Makefile for automated building
• In the base of your implementation directory, have an all-caps file called “README” which has:
  • the essential information for building
  • executing
  • and using your implementation (summary of what should be on the wiki)

The reason I have chosen this particular game is that it enables the application of a tree-based Data Structure, often in the form of a game tree, which plays a role in the artificial intelligence routines responsible for the computer's actions.

The project is to be done using C++, and can incorporate some Object-Oriented structures.

I had asked you to read some chapters out of an online book on subversion; if you have yet to do so, please read them.

To facilitate access to the repository, we need to set up a public/private SSH key so that we aren't constantly bombarded with a password.

To do this, run the genkey script on Lab46:

lab46:~$ genkey

You'll be prompted to enter a passphrase. Unless you know what you're doing, JUST HIT ENTER. Keep hitting enter until you get the prompt back. This will set up the SSH keys and put them in the appropriate keychain.

I have established a repository for the backgammon project, which each person in the class has to checkout in order to begin contributing.

Instructions for doing that (you only need to do this once) can be found in the following command lines:

lab46:~$ cd src
lab46:~/src$ svn checkout svn+ssh://repos/svn/fall2010/backgammon
A    backgammon/main.cc
A    backgammon/README
Checked out revision 2.
lab46:~/src$ cd backgammon
lab46:~/src/backgammon$ 

As people work on the code and commit changes to the repository, your copy will become outdated. To bring your copy up to date, simply do the following (from within the backgammon/ directory):

lab46:~/src/backgammon$ svn update

Any new changes since your last update will be pulled down.

You will want to do an update on a regular basis, as people could be making changes at any time.

As you work on the code, and make an alteration, you need to push your code back to the repository. To do this, we commit it, as follows:

lab46:~/src/backgammon$ svn commit -m "brief description of the change you just made"

You'll notice the file(s) you've changed will be listed, and the revision number of the repository will increment.

You will want to commit as you make changes to the code. Nobody else can utilize your changes until you commit it back to the repository.

subversion tracks and versions the files it has been made aware of. As we work on the project, there will likely be additional files added (a Makefile, additional .cc and .h files, etc.), which we will also want to include in version control.

So if one of your changes involves the inclusion of a new file (or directory), we'll need to add it before performing a commit. In the following example, I'll add the file node.h:

lab46:~/src/backgammon$ svn add nodeinit.h
A         nodeinit.h
lab46:~/src/backgammon$ svn commit -m "Added new file nodeinit.h; contains node struct definition and node function prototypes"

If it is realized that a file could be renamed or moved to better accommodate the project, we need to have subversion take care of it, so the file can remain tracked (and the history prior to the name change preserved and associated with the same file).

In my example, I will rename nodeinit.h to node.h:

lab46:~/src/backgammon$ svn rename nodeinit.h node.h
A         node.h
D         nodeinit.h
lab46:~/src/backgammon$ svn commit -m "Renamed nodeinit.h to node.h"

subversion has a number of other capabilities available to us through the svn command. We can issue a help command to it to see a list and find out more:

lab46:~/src/backgammon$ svn help
...

To facilitate the readability of your code, when preparing your code for submission, I'd like for you to make sure certain qualifications are met:

• you use consistent indentation
  • multiple levels of code see proper indentation
  • there are no “mostly there” inconsistent indentations
  • no stray statements with 0 indentation
  • all selection, iteration, and function statements receive uniform formatting

If you'd like, I have configured a facility on Lab46 to enable you to conveniently beautify your code to the ANSI/Allman style of coding. This is my preferred coding style, and would help me to better read your code.

So, if you aren't already consistent at code formatting (some have well-established coding habits and their code, although styled slightly different than mine, is still far more readable because it is consistent), please go through the following exercise for all your source files.

In this example, I will assume your files are called: main.c, display.c, and backgammon.h

lab46:~$ cd src
lab46:~/src$ indent main.c
lab46:~/src$ indent display.c
lab46:~/src$ indent backgammon.h
lab46:~/src$ 

You will find that a backup of your original formatted source code is saved in files called main.c~, display.c~, and backgammon.h~. But the plain .c files are now nicely formatted.

If you find yourself tracking down elusive bugs and have experienced an unbalanced curly brace… you may want to consider passing your code through indent so as to save yourself some work and time. You'd be amazed what a little code beautification will do for you.

• Backgammon Wikipedia Article
• Table-class Board Games Wikipedia Article
• Game Tree Wikipedia Article
• Binary Tree Wikipedia Article