CSCE-315: Programming Studio (Fall 2012)
Project 2: Five-in-a-Row Online
Updates
- Updates will be posted here.
- The default language is C++. Ask instructor for permission to use a different language.
- [10/15] Correct syntax for move is row column, not column row.
Team configuration
The team will be the same as project 1, except for a small number of reshuffles. See team assignment.
In a nutshell
The game you will implement is "Five in a row". See Wikipedia entry on Five in a Row for game rules. Also, there are plenty of online versions that you can play: flash game (there are Chrome apps as well).
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 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.
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.
Five-in-a-Row Game Play
- The game is played on a 15x15 grid.
- Each row and column will be named in hexadecimal: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f.
- The initial state is blank.
- The client always plays first, with black.
- Whoever connects exactly five will win.
- No other local rules will apply, for simplicity: e.g., ban on 3x3, 4x4, connect 6, etc.
; 1 2 3 4 5 6 7 8 9 a b c d e f ;1 + + + + + + + + + + + + + + + ;2 + + + + + + + + + + + + + + + ;3 + + + + + + + + + + + + + + + ;4 + + + + + + + + + + + + + + + ;5 + + + + + + + + + + + + + + + ;6 + + + + + + + + + + + + + + + ;7 + + + + + + + + + + + + + + + ;8 + + + + + + + + + + + + + + + ;9 + + + + + + + + + + + + + + + ;a + + + + + + + + + + + + + + + ;b + + + + + + + + + + + + + + + ;c + + + + + + + + + + + + + + + ;d + + + + + + + + + + + + + + + ;e + + + + + + + + + + + + + + + ;f + + + + + + + + + + + + + + +
Five-in-a-Row Client-Server Protocol
expr | ::= command | move | comment |
command
|
::=
EXIT | DISPLAY | EASY | MEDIUM | HARD | UNDO | HUMAN-AI|AI-AI <server> <port> |
move | ::= row column |
comment | ::= ; * |
identifier | ::= alpha { ( alpha | digit ) } |
alpha | ::= a | ... | z | A | ... | Z | _ |
digit | ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
hex | ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
row | ::= hex |
column | ::= hex |
server | ::= IP address or hostname |
port | ::= digit { digit } |
- EXIT: exit and disconnect from the server
- DISPLAY: toggles board display
- EASY | MEDIUM | HARD: selects AI difficulty
- UNDO: undo AI's move and your last move. Up to 10 UNDO's should be supported.
- HUMAN-AI : human client against server AI
- AI-AI <server> <port>: this server's AI against another server's AI
The server will show these messages to the user:
ack | ::= WELCOME | OK | move | ILLEGAL | comment |
move | ::= column row |
hex | ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
row | ::= hex |
column | ::= hex |
comment | ::= ; * |
The server will always acknowledge the client's input with OK
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 HUMAN-AI ; choose game OK EASY ; set up AI difficulty OK DISPLAY ; toggle board display OK ; 1 2 3 4 5 6 7 8 9 a b c d e f ;the board display is sent by the server ;1 + + + + + + + + + + + + + + + ;2 + + + + + + + + + + + + + + + ;3 + + + + + + + + + + + + + + + ;4 + + + + + + + + + + + + + + + ;5 + + + + + + + + + + + + + + + ;6 + + + + + + + + + + + + + + + ;7 + + + + + + + + + + + + + + + ;8 + + + + + + + + + + + + + + + ;9 + + + + + + + + + + + + + + + ;a + + + + + + + + + + + + + + + ;b + + + + + + + + + + + + + + + ;c + + + + + + + + + + + + + + + ;d + + + + + + + + + + + + + + + ;e + + + + + + + + + + + + + + + ;f + + + + + + + + + + + + + + + 88 ; your move OK ; 1 2 3 4 5 6 7 8 9 a b c d e f ;1 + + + + + + + + + + + + + + + ;2 + + + + + + + + + + + + + + + ;3 + + + + + + + + + + + + + + + ;4 + + + + + + + + + + + + + + + ;5 + + + + + + + + + + + + + + + ;6 + + + + + + + + + + + + + + + ;7 + + + + + + + O + + + + + + + ;8 + + + + + + + @ + + + + + + + ;9 + + + + + + + + + + + + + + + ;a + + + + + + + + + + + + + + + ;b + + + + + + + + + + + + + + + ;c + + + + + + + + + + + + + + + ;d + + + + + + + + + + + + + + + ;e + + + + + + + + + + + + + + + ;f + + + + + + + + + + + + + + + 78 ; server tells you its move 89 ; your move OK ; 1 2 3 4 5 6 7 8 9 a b c d e f ;1 + + + + + + + + + + + + + + + ;2 + + + + + + + + + + + + + + + ;3 + + + + + + + + + + + + + + + ;4 + + + + + + + + + + + + + + + ;5 + + + + + + + + + + + + + + + ;6 + + + + + + + + + + + + + + + ;7 + + + + + + + O + + + + + + + ;8 + + + + + + + @ @ + + + + + + ;9 + + + + + + + + O + + + + + + ;a + + + + + + + + + + + + + + + ;b + + + + + + + + + + + + + + + ;c + + + + + + + + + + + + + + + ;d + + + + + + + + + + + + + + + ;e + + + + + + + + + + + + + + + ;f + + + + + + + + + + + + + + + 99 ; server tells you its move 8a ; your move OK ; 1 2 3 4 5 6 7 8 9 a b c d e f ;1 + + + + + + + + + + + + + + + ;2 + + + + + + + + + + + + + + + ;3 + + + + + + + + + + + + + + + ;4 + + + + + + + + + + + + + + + ;5 + + + + + + + + + + + + + + + ;6 + + + + + + + + + + + + + + + ;7 + + + + + + + O + + + + + + + ;8 + + + + + + O @ @ @ + + + + + ;9 + + + + + + + + + O + + + + + ;a + + + + + + + + + + + + + + + ;b + + + + + + + + + + + + + + + ;c + + + + + + + + + + + + + + + ;d + + + + + + + + + + + + + + + ;e + + + + + + + + + + + + + + + ;f + + + + + + + + + + + + + + + 87 ; server tells you its move DISPLAY ; toggle off display OK 8b ; your move OK 8c ; server tells you its move
Five-in-a-Row 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 serevr to you so that you know what moves were made.
Games
For the human vs. AI game, human always goes first and plays black.
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 black.
- Also, the game difficulty in this case should be HARD (for both sides).
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 for testing 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 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.
Grading
20% Agile computing 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
15% Completeness and quality of the server interface.
15% Completeness and quality of the GUI client
10% Code style (naming, layout, etc.)
Deliverables
- 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.
- 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 random AI player (AI choosed randomly among available moves).
- 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).
- 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.
- 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)
- 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.