CSCE-315: Programming Studio (Fall 2015)

Project 2: Breakthrough Online

Updates

Updates will be posted here.
The teams will be the same as project 1 unless notified differently.

Team configuration

The team will be the same as project 1, except for a small number of reshuffles.

In a nutshell

The game you will implement is "Breakthrough". See Wikipedia entry on Breakthrough for game rules. You can also look at this page for some initial strategies.

There are three main parts of the project:

Design and implement the basic game playing mechanism and an AI algorithm to play against humans and other AI.
Design and implement a client-server protocol so that humans (or other AI) can connect to the game server and play the game online. Implement the server and use telent as the client for initial test.
Design and implement a GUI-based client to connect to your game server and play the game.
- Note: the GUI client is supposed to be a really dump client -- almost no game mechanics (legal move check, etc.) other than displaying the board and displaying the moves.

Here are some additional requirements:

For this project, using the unix environment for programming will be more convenient, in terms of socket programming, etc.
For game server and AI, use C++.
For the GUI, use Java.
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.

Breakthrough Game Play

Here are some ground rules:

The game is played on an 8 x 8 grid.
Each row is indexed 1 2 3 4 5 6 7 8 (from bottom to top).
Each column is indexed a b c d e f g h (from left to right).

The initial state is as shown below.

   A B C D E F G H
8 |X|X|X|X|X|X|X|X|
7 |X|X|X|X|X|X|X|X|
6 |_|_|_|_|_|_|_|_|
5 |_|_|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|_|
3 |_|_|_|_|_|_|_|_|
2 |O|O|O|O|O|O|O|O|
1 |O|O|O|O|O|O|O|O|

The client always plays first, with 'O'.
You can move your piece forward one step, straight or diagonally if the space is empty.
You can take your opponent's piece and move into its space only if the direction is diagonal.
Whoever reaches the opponent's home row wins (O's home row = 1, X's home row = 8).
All pieces act like the pawn in Chess (except that it cannot jump 2 steps).

'O' indicates white and 'X' indicates black. The first few moves are shown.

   A B C D E F G H
8 |X|X|X|X|X|X|X|X|
7 |X|X|X|X|X|X|X|X|
6 |_|_|_|_|_|_|_|_|
5 |_|_|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|_|
3 |_|_|_|_|_|_|_|_|
2 |O|O|O|O|O|O|O|O|
1 |O|O|O|O|O|O|O|O|

E2 to E3

   A B C D E F G H
8 |X|X|X|X|X|X|X|X|
7 |X|X|X|X|X|X|X|X|
6 |_|_|_|_|_|_|_|_|
5 |_|_|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|_|
3 |_|_|_|_|O|_|_|_|
2 |O|O|O|O|_|O|O|O|
1 |O|O|O|O|O|O|O|O|

D7 to D6

   A B C D E F G H
8 |X|X|X|X|X|X|X|X|
7 |X|X|X|_|X|X|X|X|
6 |_|_|_|X|_|_|_|_|
5 |_|_|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|_|
3 |_|_|_|_|O|_|_|_|
2 |O|O|O|O|_|O|O|O|
1 |O|O|O|O|O|O|O|O|

D2 to C3

   A B C D E F G H
8 |X|X|X|X|X|X|X|X|
7 |X|X|X|_|X|X|X|X|
6 |_|_|_|X|_|_|_|_|
5 |_|_|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|_|
3 |_|_|O|_|O|_|_|_|
2 |O|O|O|_|_|O|O|O|
1 |O|O|O|O|O|O|O|O|

Breakthrough Client-Server Protocol

The communication will be through simple ASCII text. All commands should be case insensitive. The commands are pretty simple.

statement	::= password \| command \| move \| comment
password	::= arbitrary string
command	::= EXIT \| DISPLAY \| UNDO \| HUMAN-AI difficulty \|AI-AI server port password my-difficulty opponent-difficulty
move	::= column row move-dir
move-dir	::= FWD \| LEFT \| RIGHT
difficulty	::= EASY \| MEDIUM \| HARD
my-difficulty	::= difficulty
opponent-difficulty	::= difficulty
comment	::= ; *
column	::= a \| b \| c \| d \| e \| f \| g
row	::= 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8
server	::= IP address or hostname
port	::= positive integer

The commands should function as follows:

EXIT: exit and disconnect from the server
DISPLAY: toggles board display
UNDO: undo AI's move and your last move. Up to 10 UNDO's should be supported.
HUMAN-AI difficulty: human client against server AI with the selected difficulty.
AI-AI server port password my-difficulty opponent-difficulty: this server's AI against another server's AI running on server port. password is the other server's password. my-difficulty and opponent-difficulty sets the AI's difficulty level on the client side and the server side, respectively.

The server will show these messages to the user:

ack	::= PASSWORD \| WELCOME \| OK \| move \| ILLEGAL \| comment
	Definitions for move and comment are the same as above.

The server will always acknowledge the client's command with OK It will behave differently to password and move. See below.

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.


PASSWORD
jfdkslfa			; enter password (single password for entire server). Sever connection when password is incorrect.
WELCOME
HUMAN-AI EASY			; choose game
OK
EASY				; set up AI difficulty
OK
DISPLAY				; toggle board display
OK
;    A B C D E F G H		; server displays the board 
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|X|X|X|X|X|
; 6 |_|_|_|_|_|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|_|_|_|_|
; 3 |_|_|_|_|_|_|_|_|
; 2 |O|O|O|O|O|O|O|O|
; 1 |O|O|O|O|O|O|O|O|
D2 FWD				; your move 
OK
;    A B C D E F G H		; server displays the board
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|X|X|X|X|X|
; 6 |_|_|_|_|_|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|_|_|_|_|
; 3 |_|_|_|O|_|_|_|_|
; 2 |O|O|O|_|O|O|O|O|
; 1 |O|O|O|O|O|O|O|O|
E7 FWD				; server tells you its move
;    A B C D E F G H 		; server displays the board 
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|X|_|X|X|X|
; 6 |_|_|_|_|X|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|_|_|_|_|
; 3 |_|_|_|O|_|_|_|_|
; 2 |O|O|O|_|O|O|O|O|
; 1 |O|O|O|O|O|O|O|O|
D3 RIGHT			; your move 
OK
;    A B C D E F G H 		; server displays the board 
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|X|_|X|X|X|
; 6 |_|_|_|_|X|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|O|_|_|_|
; 3 |_|_|_|_|_|_|_|_|
; 2 |O|O|O|_|O|O|O|O|
; 1 |O|O|O|O|O|O|O|O|
D7 FWD				; server tells you its move
;    A B C D E F G H 		; server displays the board 
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|_|_|X|X|X|
; 6 |_|_|_|X|X|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|O|_|_|_|
; 3 |_|_|_|_|_|_|_|_|
; 2 |O|O|O|_|O|O|O|O|
; 1 |O|O|O|O|O|O|O|O|
E2 LEFT				; your move 
OK
;    A B C D E F G H 		; server displays the board 
; 8 |X|X|X|X|X|X|X|X|
; 7 |X|X|X|_|_|X|X|X|
; 6 |_|_|_|X|X|_|_|_|
; 5 |_|_|_|_|_|_|_|_|
; 4 |_|_|_|_|O|_|_|_|
; 3 |_|_|_|O|_|_|_|_|
; 2 |O|O|O|_|_|O|O|O|
; 1 |O|O|O|O|O|O|O|O|

.
.
.
.
.

and so on

Breakthrough Client

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

telnet <hostname> <port>

or use putty with the "telnet" protocol.

Later on, you will write a stand-alone application that connects to the server using a GUI interface. The GUI interface should support all the functionality described in the client-server protocol.

The GUI has to be able to display the AI-AI games as well as HUMAN-AI games. For the AI-AI games, the first server you connect to will tell you its move and then redirect the move from the second server to you so that you know what moves were made.

Games

The server can either play with a human player or when the human requests, it can also connect to another server and play AI vs. AI.

For the human vs. AI game, human always goes first and plays white (O).

In case of the AI vs. AI game, specific rules must be followed:

The server that is initing contact will play the role of the client (it will send "HUMAN-AI" to the server as the game type), thus it will go first and play white (O).

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 another 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.
                - termination condition detection 
		- undo
		- 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 for testing

        3. Game AI
                - initially semi-random player (randomly pick from available
                  moves).
                - min-max with limited depth
                - alpha-beta-pruning-based
		- advanced evaluation functions
	
	4. GUI client
		- allows users to connect to the server using a
		  GUI interface

        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.

Final 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:

10% Agile development methodology - setting, using, adjusting backlogs and burndown charts, and development log

20% Completeness and quality of the game mechanics

20% Completeness and quality of the AI

10% Completeness and quality of the server interface.

10% Completeness and quality of the GUI client

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

25% Weighted grade from earlier submissions.

Deliverables

The deliverables for each submission will be as follows:

All submissions must include a README file (compilation and running instructions), and an output file with detailed test of functionality. For GUI, screenshots are required.

Design documents, SCRUM product log (with initial burndown chart),
- The design document requirements are the same as Project 1.
- See the SCRUM tips above for product log format.
- Grading:
  - 20%: All four sections
  - 60%: Game mechanics, AI, client-server, GUI client.
  - 20%: SCRUM product log and burndown chart.
Game mechanics code and server code
- Sprint 1 backlog and burndown chart.
- Game mechanics code should include fully playable: board display undo, etc. Assume a semi-random AI player (AI choosed randomly among available moves near current pieces in play while blocking only obvious cases, e.g., 3-in-a-row).
- Server code should be fully functional: user can connect to the open port and play a random game. It should implement the full protocol (you may leave out actual AI-related function: game difficulty, ai-ai).
- Grading:
  - 10%: layout, style, comments
  - 30%: all functions implemented
  - 40%: all functions working properly
  - 10%: sprint backlog and burndown chart.
  - 10%: development log
AI engine code
- sprint 2 backlog and burndown chart.
- AI engine should implement the MIN-MAX algorithm and Alpha-beta pruning.
- You should also design and implement an evaluation function to use at the cut-off state (depth limit).
- Grading:
  - 10%: layout, style, comments
  - 30%: all functions implemented
  - 40%: all functions working properly
  - 10%: sprint backlog and burndown chart.
  - 10%: development log
Final version.
- Code for AI engine and client-server system.
- GUI client code, sprint 3 backlog and burndown chart.
- 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), plus brief description of each member's contribution (less than 1 paragraph each). This must be based on consensus. In case there is a dispute, individual reports will be requested. Individual score calculation will be the same as project 1.
- Development log.
- For rubrics, see above "Final Grading".

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