CSCE-315: Programming Studio (Spring 2010)

Project 2: Reversi Online

Updates

  1. displayon display-on (10/28)
  2. client does not send any acknowledgment (OK) to the server (10/28)
  3. Reversi protocol slightly updated (addition of "Black/White" response from server)
  4. You may use Java or C# (these are recommended over C++, for this project).
  5. Reversi mock server (by Tim Mann): rmatch.jar (note: some commands are different and will be fixed [e.g., human-ai instead of local-AI]).

Team configuration

This project is a team project, ideal team size is three. If the number of students is not divisible by three, we can have a few teams with size close to three. The team will be assigned by the TA based on the individual expertise demonstrated in project 1.

In a nutshell

This project is about the game of Reversi (also known as Othello). It is a two-player board game played on a 8 x 8 grid where the objective is to occupy as many cells. See this wikipedia entry on Reversi for detailed rules. There are two main parts of the project:

  1. Design and implement the basic game playing mechanism (board setup, piece placement, end game determination, etc.) and an AI algorithm to play against humans.
  2. Design and implement a client-server protocol so that any combination of human and AI can play through the internet.
The outcome will be two excutable programs:
  1. Reversi server program.
  2. Reversi client program.
You may use a text-based or a graphical user interface for the display. The specifics regarding the client-server protocol will be described below.

Reversi Online Client-Server Protocol

Each row will be named 1, 2, 3, ..., 8. Each column will be named a, b, c, ... , h. Initial configuration of the board is:
  • d4 white
  • e4 black
  • d5 black
  • e5 white
  a b c d e f g h 
 +-+-+-+-+-+-+-+-+
1| | | | | | | | |
 +-+-+-+-+-+-+-+-+
2| | | | | | | | |
 +-+-+-+-+-+-+-+-+
3| | | | | | | | |
 +-+-+-+-+-+-+-+-+
4| | | |W|B| | | |
 +-+-+-+-+-+-+-+-+
5| | | |B|W| | | |
 +-+-+-+-+-+-+-+-+
6| | | | | | | | |
 +-+-+-+-+-+-+-+-+
7| | | | | | | | |
 +-+-+-+-+-+-+-+-+
8| | | | | | | | |
 +-+-+-+-+-+-+-+-+
The communication will be through simple ASCII text. The commands are pretty simple.

expr ::= command | move | ack | comment
command ::= wait-human | local-AI | local-vs-remote-AI host port | abort | display-on | display-off | easy | medium | hard
move ::= column row
ack ::= WELCOME | OK | ILLEGAL | BLACK | WHITE
comment ::= ; *
host ::= identifier.identifier.identifier.identifier
port ::= nonzerodigit { digit }
identifier ::= alpha { ( alpha | digit ) }
alpha ::= a | ... | z | A | ... | Z | _
nonzerodigit ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
row ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
column ::= a | b | c | d | e | f | g | h

An unused port should be used for the server. The entire interface should be accessable using telnet, using plain ASCII text. You have to be extra cautious with your code since your server can easily become a security hole. Before you print anything that came from the client or the server, you have to first check if these are printable characters, and make sure the length of the input is within your input buffer size.

An example is shown below. Bold is server, italic is client). Text following ";" are comments and they are simply displayed as they are received and no further action is taken (comments on the far right column are mine, just to explain it a bit). "_" is the cursor waiting for the user input.


WELCOME
local-AI		; set up game type
WHITE		; tells user which color he/she will be playing
easy			; set up AI difficulty
OK
display-on
OK
;  a b c d e f g h		; the board display is sent by the server
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;4| | | |W|B| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |B|W| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
e3     
OK
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |W| | | |
; +-+-+-+-+-+-+-+-+
;4| | | |W|W| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |B|W| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
f3				; after receiving this, client sends OK to server does not send anything to server.
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |W|B| | |
; +-+-+-+-+-+-+-+-+
;4| | | |W|B| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |B|W| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
g1     
ILLEGAL
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |W|B| | |
; +-+-+-+-+-+-+-+-+
;4| | | |W|W| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |B|W| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
_

Reversi Client (new 10/14/2010)

The client should be a stand-alone application that allows the player to specify:
  • Server hostname
  • port
  • game type selection: wait-human, local-AI, local-vs-remote-AI
  • game difficulty selection: easy, medium, hard
and support all other interactions (such as "abort").

You can either use a character-based user interface or a GUI.

Games

There are three gaming modes:
  • wait-human: Server will wait for another human user. If another human user connects and types in wait-human the game begins between the two humans.
  • local-AI: The server will take input moves through the socket connection and run its own AI engine to generate the next moves and return to the client.
  • local-vs-remote-AI: Human user logs into server 1 and initiates this command, specifying the server 2 hostname and port. Server 1 will now act like a client, connect to server 2, and play the game. To server 2, server 1 will look like any other client (e.g., a human). This way, server 1's AI can be pitted against that of server 2's AI.

Project Organization

This project will be approached by trying to follow an approach similar to one that would be used in an agile development environment. Due to team size, and even more significant, due to time constraints, we will not be able to follow a "real" agile approach, but we will try to capture some of the themes. We will use an iterative approach to this assignment. Your team will be asked to implement the program over three "sprint" iterations, each just over 1 week in length. At the end of each iteration, your team should have a complete, working program. More features and functionality should be added at each iteration. In addition, you are to keep a backlog, a burndown chart, and hold SCRUM meetings. Each of these will be discussed below. The following will be the project schedule:

  • October 3: Project Assigned
  • October 7 (11:59 p.m.) - Product backlog and initial burndown chart created
  • October 10 (11:59 p.m.) - Sprint 1 backlog created
  • October 16 (11:59 p.m.) - Iteration 1 completed
  • October 17 (11:59 p.m.) - Sprint 2 backlog created
  • October 23 (11:59 p.m.) - Iteration 2 completed
  • October 24 (11:59 p.m.) - Sprint 3 backlog created
  • November 2 (11:59 p.m.) - Final Iteration completed

Details

  1. First Deadline
    Although not a lot of work needs to be done by the time of the first deadline, this work will be critical to the success of the project. By the first deadline, your team should have done the following:
    • Appointed one member to be the project manager. The project manager will be responsible for maintaining the backlogs and burndown charts. This person will also serve as the SCRUM Master during the sprints. As a result, this individual should have somewhat less of the programming responsibility when tasks are assigned
    • Created a product backlog. Specifically, your team should try to break the overall program into a number of tasks that need to be implemented.
    • Created an initial burndown chart. This should be an estimate of the overall amount of time taken for all of the tasks that will be completed. Your team should help make this estimate.

    On this first deadline, your project manager should turn in, via csnet, the product backlog and the initial burndown chart estimate.

  2. Sprint Backlogs
    Note: Although your sprint backlog has a due date, you are welcome to set your backlog earlier (though it must be after the completion of the previous sprint). Your sprint backlog should be a subset of the product backlog. Note that you may (and probably will) choose not to include all of the remaining product backlog in the final sprint if you don't believe it will fit in. You should set your sprint goals realistically.

    You should also set at least 4 SCRUM meeting times when your team will meet during the next sprint. Class lab times can be used for these meetings. SCRUM meetings must be held after the backlog is created, which is another reason to set your backlog early. For example, if your backlog is set before Thursday afternoon, you can hold your first SCRUM meeting during the day, Thursday.

    At each of the sprint backlog deadlines, the project manager should turn in the following:

    • The backlog to be used on this sprint
    • A list of which tasks were assigned to which person (at least initially - this could change during the sprint)
    • The initial burndown chart for the sprint
    • A list of when the SCRUM meetings for your team will be.
  3. During the sprint -- SCRUM meetings
    Note that the sprints are very short in length. You should have at least 4 SCRUM meetings in this period. This usually means meeting most days. SCRUM meetings should be kept to no more than 15 minutes.

    The SCRUM master (project manager) should update the sprint burndown chart after each meeting, based on any feedback from team members.

    In addition, the product manager should update the product burndown chart at least once during the sprint, and once again at the end of the sprint. Thus, by the end of the project, there should be at least 7 data points on the product burndown chart: one initial one, one from the start of each of the last two sprints (the start of the first sprint will be the same as the initial one), one from in the middle of each of the three sprints, and one from the end of the final sprint (note that you might not have emptied your backlog)

  4. Iteration end
    At the end of each iteration (sprint), the project manager should turn in the following:
    • Your source code. You should have a full implemented program, usually missing many features, but still "working."
    • The burndown chart from that sprint. It should have at least 6 data points: one initial point, one after each of the 4 SCRUM meetings, and one final one.
    • The burndown chart for the project, to this point.
  5. Other project organization
    You should use the department SVN server for your team. Ideally, each person working on the code should update the code each time a feature is added.

    The project manager should maintain the backlogs and burndown chart in a location that other team members can easily refer to them.

    The project manager/SCRUM master should be given somewhat fewer tasks during the sprint, due to responsibilities for maintaining backlogs and burndown charts.

    The "customer" in this case is represented by the instructor and TA. You should involve the customers in your work, getting feedback from the customers often to make sure you are on track.

SCRUM tips

Here's an example template of the product backlog:

        Backlog example

And, here's the burndown chart:

        Burndown chart example

Some tips:

        For the project, you should focus on the tasks in the following
        order (near the top is most important). Set up your backlog
        accordingly. Your backlog will be much more detailed than this.

        1. Game mechanics
                - board and game state representation
                - operators
                - operator legality (is a certain move allowed?)
                - move: once a move is made, update the board (flip the
                        intervening tiles)
                - termination condition detection (can any more
                  pieces be placed?)
                - game result report (win/lose/draw).

        2. Game Server
                - allows clients to connect
                - wait-human games supported (initially).
                - can use telnet (e.g., putty, with telnet option) to
                  connect

        3. Game AI
                - initially random player (randomly pick from available
                  moves).
                - min-max with limited depth
                - alpha-beta-pruning-based
                - [optional] more advanced game AI

        4. Client
        	- initially just use telnet

        As for the burndown chart, you will initially not have
        any data. Use your estimated time for each task and
        during which sprint you will get those done to come up
        with a mock burndown chart.

Grading

There will be a team grade assigned for the project, and like the first project, the team grade will be apportioned out to the individuals. The rough breakdown of team grade is:

15% Agile computing methodology - setting, using, adjusting backlogs and burndown charts

30% Completeness and quality of the game manager/interface

30% Completeness and quality of the AI

10% Additional features added on (AI, interface, etc.)

15% Code style (naming, layout, etc.)

Team Assignment

The TA will assign the team.
Original concept/design/most of the text by John Keyser. Modifications by Yoonsuck Choe.