CSCE-315: Programming Studio (Summer 2012)

Project 2: Reversi Online

Updates

[6/12] You may use Java for this project, since a large portion of this code will be reused for project 3.
[6/12] Deadlines have been changed (see course web page).

Team configuration

The team will be the same as project 1.

In a nutshell

The game you will implement is Reversi. See Wikipedia entry on Reversi for game rules.

There are two main parts of the project:

Design and implement the basic game playing mechanism and an AI algorithm to play against humans.
Design and implement a client-server protocol so that humans can connect to the game server and play the game online. Implement the server and use telent as the client.

Here are some additional requirements:

For this project, using the unix environment for programming will be more convenient, in terms of socket programming, etc. However, developing in the unix environment is optional, and you will get 5% extra credit for developing in the unix environment (CSE unix servers).
We will use the SCRUM method and each of your submissions should be accompanied by SCRUM backlogs and the burndown chart, as well as the code and other documentation.

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

'O' indicates white and '@' indicates black.

  a b c d e f g h 
 +-+-+-+-+-+-+-+-+
1| | | | | | | | |
 +-+-+-+-+-+-+-+-+
2| | | | | | | | |
 +-+-+-+-+-+-+-+-+
3| | | | | | | | |
 +-+-+-+-+-+-+-+-+
4| | | |O|@| | | |
 +-+-+-+-+-+-+-+-+
5| | | |@|O| | | |
 +-+-+-+-+-+-+-+-+
6| | | | | | | | |
 +-+-+-+-+-+-+-+-+
7| | | | | | | | |
 +-+-+-+-+-+-+-+-+
8| | | | | | | | |
 +-+-+-+-+-+-+-+-+

The communication will be through simple ASCII text. The commands are pretty simple.

expr	::= command \| move \| comment
command	::= EXIT \| DISPLAY_ON \| DISPLAY_OFF \| EASY \| MEDIUM \| HARD \| BLACK \| WHITE \| UNDO \| REDO \| SHOW_NEXT_POS
move	::= column row
comment	::= ; *
identifier	::= alpha { ( alpha \| digit ) }
alpha	::= a \| ... \| z \| A \| ... \| Z \| _
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

The commands are self-explanatory, except that SHOW_NEXT_POS will show the human player what are the available legal positions.

The server will show these messages to the user:

ack	::= WELCOME \| OK \| ILLEGAL \| BLACK \| WHITE \| comment
comment	::= ; *

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). "_" at the end is the cursor waiting for the user input.


WELCOME
WHITE			; choose side
WHITE			; confirms user's choice
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| | | |O|@| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |@|O| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
e3     
OK
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |O| | | |
; +-+-+-+-+-+-+-+-+
;4| | | |O|O| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |@|O| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
f3				; server tells you which move it made
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |O|@| | |
; +-+-+-+-+-+-+-+-+
;4| | | |O|@| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |@|O| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
g1     
ILLEGAL
;  a b c d e f g h
; +-+-+-+-+-+-+-+-+
;1| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;2| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;3| | | | |O|@| | |
; +-+-+-+-+-+-+-+-+
;4| | | |O|O| | | |
; +-+-+-+-+-+-+-+-+
;5| | | |@|O| | | |
; +-+-+-+-+-+-+-+-+
;6| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;7| | | | | | | | |
; +-+-+-+-+-+-+-+-+
;8| | | | | | | | |
; +-+-+-+-+-+-+-+-+
_

Reversi Client

The telnet command will be used as the client, so there's no need to write the client.

telnet <hostname> <port>

Games

The server will by default play the AI-side and the client will be the human.

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 a few days in length. At the end of each iteration, your team should have a complete, working program feature set. 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 (almost everyday). Each of these will be discussed below.

The following will be the project schedule:

Project Assigned
Product backlog and initial burndown chart created
Sprint 1 backlog created (game mechanics)
Iteration 1 completed
Sprint 2 backlog created (AI engine)
Iteration 2 completed
Sprint 3 backlog created (client-server)
Final Iteration completed

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?)
		- undo/redo
		- show next possible positions
                - game result report (win/lose/draw).

        2. Game Server
                - allows clients to connect
                - 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, customize heuristics

        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:

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

20% Completeness and quality of the game mechanics

30% Completeness and quality of the AI

10% Completeness and quality of the client-server interface.

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

Deliverables

The deliverables for each submission will be as follows:

Design documents, SCRUM product log (with initial burndown chart), and game mechanics code (plus sprint 1 backlog and burndown chart).
- The design document requirements are the same as Project 1.
- See the SCRUM tips above for product log format.
- Game mechanics code should include fully playable board display undo/redo, etc. Assume that two human players each specify their move (no AI involved).
AI engine code, sprint 2 backlog and burndown chart.
- AI engine should at the minimum implement the MIN-MAX algorithm.
- You should also design and implement an evaluation function to use at the cut-off state (depth limit).
- Alpha-beta pruning is optional (5% extra credit).
Final version. Fully integrated system.
- Client-server code, sprint 3 backlog and burndown chart.
  - Server should be startable with a command line argument that takes the port number.
  - Human play should be able to use telnet to connect to the game server and play the game.
- an updated version of your design document
- post production notes (changes you had to make to your design and why, difficulties, solutions, lessons learned)
- individual work load distribution (percentage)
- self-evaluation (briefly discuss how you contributed to the project) and peer evaluation (rate all other team members on the scale of 1 to 5, 5 being best; plus brief comments). Peer evaluation should be submitted individually.
- Development log.

Original concept/design/most of the text by John Keyser. Modifications by Yoonsuck Choe.