\\ \\ \\ Corning Community College \\ Data Structures \\ Project #2: Backgammon Implementation \\ \\ \\ \\ \\ ~~NOTOC~~ =====Objective===== To gain an understanding of tree-based data structures and their use in algorithms, while working together collaboratively. =====Overview===== 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 [[http://en.wikipedia.org/wiki/Backgammon|Backgammon]]. =====Requirements===== 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: - player vs. player - player vs. computer * on player vs. computer, there should be //at least// 3 difficulty levels: - easy - medium - 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 [[http://lab46.corning-cc.edu/notes/data|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. =====Subversion===== 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. ====setting up SSH public/private key==== 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. ====checking out the code base==== 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$ AGAIN: You only need to check the code base out ONCE. From this point on, you only need to make **commit**s and **update**s. ====updating to the latest version==== 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. ====commit changes to the repository==== 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. ====add new files 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" ====renaming files in the repository==== 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" ====other capabilities==== **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 ... =====Code Formatting===== 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. =====Links===== * [[http://en.wikipedia.org/wiki/Backgammon|Backgammon Wikipedia Article]] * [[http://en.wikipedia.org/wiki/Tables_(board_game)|Table-class Board Games Wikipedia Article]] * [[http://en.wikipedia.org/wiki/Game_trees|Game Tree Wikipedia Article]] * [[http://en.wikipedia.org/wiki/Binary_tree|Binary Tree Wikipedia Article]]