Archive‎ > ‎Fall 2009‎ > ‎Course Project‎ > ‎Buddy Suite‎ > ‎

Milestone 3: Chess Game Logic

Please keep in mind the Collaboration Policy. If you have any questions regarding the assignment, do ask the course staff. For this milestone, we will meet with each team to discuss the details of your design and implementation.  Each team member must be able to present the design, the reasons behind the design decisions, and an overview of each major class (e.g., what is its responsibility and how does it fulfill it). These meetings will last for maximum one hour. We will coordinate with you on the time slots for meeting with the TAs.

The total number of points for this milestone is 100.
The points are awarded as follows:

  • 5 points - functional ant build file (if the build fails, we will not grade your code further)
  • 70 points - functionality
  • 10 points - audit methods
  • 13 points - coding principles
  • 2 points - workload information
  • 20 points - optional extra functionality

1. Implementation

In the previous milestone, you implemented a UI for the Chess game. In this milestone, you will implement the Chess game engine. Your engine must validate every chess move made by the user: when (s)he selects a chess piece using the UI, your application must allow the user to make only legal chess moves. 

To keep things easy in this milestone, the user will not yet be expected to play chess with other users, so the same user will play both as the white and the black player.

Correctly and completely implementing the requirements specified in this section will earn you 70 points.

Chess Game Rules

There are many variants and different sets of rules in chess. This guide is meant to be a common reference of the rules used in this project (i.e., the rules that your chess validation engine has to implement). Please note that our chess server will also validate the submitted moves according to the rules below, so any deviation in your implementation may result in incompatibilities for the next milestone and loss of points for the current milestone.

Starting a Game

The chess game uses pieces of two colors: black and white. The game is played between two players (in this milestone, both players are the same user). Each player is assigned a piece color. Players take turns at making moves. Each player can move only pieces of his/her assigned color. A player can make a single move when it is his/her turn.

Setting up the board. At the beginning of the game, the chess board is laid out so that each player has the white (or light) color square on the bottom right-hand side. The chess pieces are then arranged the same way each time. The second row (or rank) is filled with Pawns. The Rooks go in the corners, then the Knights next to them, followed by the Bishops, and finally the Queen, who always goes on her own matching color (white Queen on white, black Queen on black), and the King on the remaining square. The diagram on the right shows the initial setup of the chess board.

The player with the white pieces always moves first. Checking this in your implementation of the chess game will earn you 2 points.

How Chess Pieces Move

There are 6 types of chess pieces: Pawn, Rook, Knight, Bishop, Queen, and King. Pieces cannot move through other pieces (though the Knight can jump over other pieces) and can never move onto a square already occupied by a piece of their own color. However, they can move to take the place of an opponent's piece, which is then captured, removed from the chess board, and can no longer be used in a subsequent move.

Pieces can move as described by the following rules, as long as the end position of the piece is still on the chess board. Moving off the chess board is not permitted.

The King

This King is the most important piece, but also one of the weakest. The King can only move one square in any direction - one row up, one row down, one column to the left, one column to the right, or diagonally.

A check is a chess game situation in which the King can be captured by the opponent in the opponent's next move. This is described in more detail below.

The diagram on the right shows how the King can move. You can click on the and buttons to see the pieces move through the various possibilities.

Correctly implementing the King's moves will earn you 5 points.

The Queen

The Queen is the most powerful piece. She can move in any one straight direction - maintain the same column, or the same row of the chessboard, or move diagonally - as far as possible as long as she does not move through any of her own pieces.

The Queen can capture the first piece of the opposite color it encounters while performing its move. After the Queen captures a piece, her move stops on the square where the captured piece was located.

Use the diagram on the right to see how the Queen moves. Notice how the white Queen captures the black Queen and then the black King is forced to move.

Correctly implementing the Queen's moves will earn you 5 points.

The Rook

The Rook may move as far as it wants, but only along the same column, or the same row of the chess board. Just like the Queen, the Rook cannot move through pieces of its own color, and it can capture the first piece it encounters, at which point the move stops. The Rooks are particularly powerful pieces when they are protecting each other and working together.

Click on the diagram on the right to see how the Rook can move.

Correctly implementing how the Rook moves will earn you 5 points.

The Bishop

The Bishop may move as far as it wants, but only diagonally. Each Bishop starts on one color (white or black) and will always stay on that color for the entire game. Capturing pieces occurs just like in the case of the Queen's diagonal move. Bishops work well together, because they cover up each other's weaknesses.

Click on the diagram on the right to see how the Bishop can move.

Correctly implementing the Bishop's moves will earn you 5 points.

The Knight

Knights move in a very different way from the other pieces: going two squares in one direction, and then one square at a 90 degree angle, just like the shape of an "L". Knights are also the only pieces that can jump over other pieces. If a Knight lands on top of an opponent's piece, then that piece is captured.

The diagram on the right shows how Knights move.

Correctly implementing the Knight's moves will earn you 5 points

The Pawn

Pawns are unusual, because they move and capture in different ways: they move forward, but capture diagonally. Pawns can only move forward one square at a time, except for their very first move, when they can move forward either one or two squares. Pawns can move diagonally one square if they capture an opponent's piece. They can never move or capture backwards. If there is another piece directly in front of a Pawn, the Pawn cannot move past or capture that piece, regardless of who it belongs to.

Click on the diagram to the right to see how the Pawn can move.

Correctly implementing the Pawn's moves will earn you 5 points

Special Moves

Promotion

Pawns have a special ability: if a Pawn reaches the opposite side of the board, i.e., the Pawn has moved six squares, it can be promoted to any other chess piece. A common misconception is that Pawns may only be exchanged for a piece that has been captured; this is not true.

A Pawn is usually promoted to a Queen, but not necessarily. Only Pawns may be promoted. A Pawn cannot be promoted into a Pawn!

Correctly implementing promotion will earn you 4 points. 

To receive the points, you have to display a list that enables the user to select which piece to promote the Pawn to. However, during replay of a PGN-described chess game, this dialog should not be displayed. The PGN encoding already specifies the piece to which the Pawn was promoted.

Castling

This move allows you to do two important things in one move: get your King to safety, and get your Rook out of the corner and into the game. On a player's turn, (s)he may move his/her King two squares over to one side and then move the Rook over the King, immediately to his side (on the opposite side relative to where the rook was before). See the example on the right.

In order to castle, the following conditions are required:

  • it must be the King's very first move
  • it must be the Rook's very first move
  • there cannot be any pieces between the King and Rook to move
  • the King may not be in check, pass through check while castling, or end up in check after castling. Passing through check means that, if the King moves from e1 to g1, the King cannot be in a check situation at position f1 (this is the algebraic notation introduced in the previous milestone).
  • castling can only occur along the same rank, never along a column. This prevents situations in which a promoted Pawn becomes a "fresh" Rook on the same column with the King; in such a case, castling is not permitted, even though both the King and the Rook have not moved yet.

Correctly implementing castling will earn you 4 points

En passant

Another rule about Pawns is called "en passant." If a Pawn moves out two squares on its first move, and by doing so lands to the side of an opponent's Pawn (effectively jumping past the other Pawn's ability to capture it), that other Pawn has the option of capturing the first Pawn as it passes by. This special move must be done immediately after the first Pawn has moved past, otherwise the option to capture it is no longer available.

Correctly implementing "en passant" will earn you 4 points

Check and Checkmate

The purpose of the game is to checkmate the opponent's King. This happens when the King is put into check and cannot get out of check.

There are only three ways to get a King out of check:

  • move the King out of the way (though the King cannot castle),
  • block the check with another piece, or
  • capture the piece threatening the King.
If the King is in check, then only such moves are allowed! In addition, no move that results in the King ending up in check is allowed!

If a King cannot escape check, then the game is over. This situation is called checkmate. Customarily, the King is not captured per se or removed from the board, rather the game is simply declared over. The diagram on the right shows an example of checkmate.

The ability to detect check situations will be rewarded with 4 points. The user must be notified about every check situation via a Toast message.

Checkmate detection will be rewarded with 5 points. The user must be informed by using a dialog that requires the user's confirmation to close.

Draws

Occasionally, chess games do not end with a winner, but with a draw. There are five reasons why a chess game may end in a draw:

  • Draw by stalemate. The game reaches a stalemate when it is one player's turn to move, but his/her King is NOT in check and yet (s)he does not have any other legal move.

    You must detect this type of draw automatically, and the game has to be stopped.

    Correctly implementing this type of draw will earn you 3 points.

  • Draw by agreement. The players may simply agree to a draw and stop playing. For this Milestone, a draw by agreement is reached if the user asks for a draw and confirms the draw. This feature has been implemented for Milestone 2.

    Correctly implementing this type of draw will earn you 2 points.

  • Draw by impossible checkmate. If a game situation arises in which neither player could possibly checkmate the other via a series of legal moves, the game is a draw. This is usually because there is insufficient material left (not enough pieces on the chess board), but may occur in other situations too. Combinations with insufficient material to checkmate are:
    • King and Bishop versus King
    • King and Knight versus King
    • King and Bishop versus King and Bishop, with the Bishops on the same color. (Any number of additional Bishops of either color on the same color of square do not affect the situation, e.g., if you promote one or more Pawns to Bishops)

    This type of draw, caused by insufficient material on the board, has to be automatically detected and the game has to be stopped.

    Correctly implementing this type of draw will earn you 4 points.

  • Draw by triple repetition. If the current game situation has just occurred at least twice in the past, with the same player to move, both players may claim a draw. In such a case, the draw is not automatic: a player must claim it, if (s)he wants the draw. A position is considered identical to another if:
    • the same player is on turn
    • the same types of pieces of the same colors occupy the same squares, and
    • the same moves are available to each player. In particular, each player still has the same castling options. Remember, a player may lose his/her right to castle during the three moves, in which case the position is no longer considered identical.

    If a draw request is not made on the move in which the repetition occurs, the player forfeits the right to make the claim.

    Correctly implementing this type of draw will earn you 4 points. Notify the player via a Toast message that (s)he has the opportunity to draw.

    You can see an example of a game that ends in a draw by triple repetition by looking at the test cases associated with this milestone.

  • Draw by fifty-move rule. If, in the previous fifty moves by each side, no Pawn has moved and no capture has been made, a draw may be claimed by either player. Here, again, the draw is not automatic, and must be claimed if the player wants the draw. As with the triple repetition, the right to claim the draw is forfeited if it is not used on that move, but the opportunity may occur again.

    Correctly implementing this type of draw will earn you 4 points. Notify the player via a Toast message that (s)he has the opportunity to draw.

    A game that ends in a draw by fifty-move rule is presented in the test cases associated with this milestone.

When a draw is made, the game has to automatically be ended. The result of the game, a draw in this case, has to be communicated to the user by using a Dialog that waits for the user's confirmation. The Dialog must also communicate the type of draw that ended the game.

Optional Functionality

Implementing extra functionality will earn you an additional 20 points, for a total maximum of 120 points.

Note: The points for the optional functionality are awarded only if all other points have been awarded, that is, if the team has 100 points for the required functionality. These potential extra points can be counted toward future milestones where you do less well.

The extra functionality that you can implement is:

  • Save played chess games as PGN files. This functionality must allow the user to specify the file name of the saved game - 4 points
  • Implement a computer-based chess player. The human user will play with the white pieces, while the computer-based player will play with the black pieces. You should then implement one of the algorithms that you can find here. If you decide to implement a different algorithm from the ones described on the linked page, ask the SwEng staff in advance whether the algorithm is acceptable or not - 16 points

2. Testing the Implementation

You will have to reuse the replay mechanism developed for Milestone 2, i.e., the Replay button. Remember, the Replay button has to start the automatic replay of a sequence of chess games expressed in the PGN format. The games to be replayed are located in a file named "res/raw/kasparov.pgn" that is accessible from your project. If this functionality is not present, you will lose 5 points.

However, in this milestone, the chess pieces have to move according to the rules described above. That is, you have to replay the legal chess games described by the PGN file.

The PGN file standard allows only correct chess moves to be encoded. To test that your chess engine does not allow illegal chess moves, you will have to provide a class that implements the ChessGameTestInterface.

3. Coding Style

Your code will be checked against the following selected coding principles. If your code respects the principles, you will receive 13 points, otherwise points will be subtracted, up to a maximum of 13.

Your code should:

  • not use uninitialized variables
  • not generate any compiler warnings (the only exception to this rule are Serializable objects)
  • not contain unused variables
  • contain descriptive variable names, e.g., playerID rather than i
  • have correctly paired methods names, e.g., if you have a method called beginCommunication, then its paired method must be called endCommunication
  • use named constants instead of literals, e.g., you should not have code that looks like new Object[10], rather should be Object[SIZE]
  • have boolean variables whose names suggest the positive value, not the negative one, e.g., loggedIn rather than notLoggedIn
  • not contain variables, classes, methods, fields that have names with similar meaning, e.g., you should not have two variables called recordNum and numRecords
  • group related statements together
  • not have loops whose code is more than 20 lines long
  • have loop indices that have descriptive names, e.g., rank instead of i
  • not explicitly modify the loop counter within the body of that loop in order to force an exit
  • not use the terminal value of a loop counter outside of the body of the loop
  • have code to prevent infinite recursive function calls, e.g., by checking for the base case upon entry into the recursive function
  • not use the == operator for any operations except on primitive types and enums, or when testing if a reference is null; use the equals method instead.

4. Audit Methods

You have to write audit methods for the three classes in your project that have the most complex rep(resentation) invariants.

One way to select the three classes may be to sort all your classes according to the number of data members and relationships between the data members, then select the top three and write audit methods for each of them.

These classes will then have to implement the following interface:

Auditable

package epfl.sweng.audit;


public interface Auditable {

   /**

   * the audit method. It returns the number of errors encountered while

   * verifying that the representation invariant holds

   * @return the number of representation invariant violations found

   */

   int auditErrors();

}


To enable the auditing of objects, you should include the following class in your program. Its purpose is to perform periodic calls to the audit methods of Auditable objects.

AuditingEntity

package epfl.sweng.audit;


import java.util.List;

import java.util.Timer;

import java.util.TimerTask;

import java.util.Vector;


import android.util.Log;


public class AuditingEntity {

   private static final List<Auditable> listOfAuditableObjects;

   private static Timer timerForAuditingThread;

   static {

      listOfAuditableObjects = new Vector<Auditable>();

      timerForAuditingThread = new Timer();

      timerForAuditingThread.scheduleAtFixedRate(new TimerTask() {

         /**

         * Periodically invokes the <i>auditErrors()</i> method on Auditable objects. It then logs the number of errors found for each object

         */

         public void run() {

            synchronized (listOfAuditableObjects) {

               Log.e("Running ", "Auditing");

               for (Auditable auditable : listOfAuditableObjects)    {

                  Log.e("AUDIT(" + auditable + ")", ""+ auditable.auditErrors());

               }

            }

         } 

      }, 1000, 1000);

   }


   /**

   *adds an Auditable object to the list of Auditables that will have their

   * auditErrors method called

   */

   public static void addAuditable(Auditable auditable) {

      synchronized (listOfAuditableObjects) {

         listOfAuditableObjects.add(auditable);

      }

   }


   /**

   *removes an Auditable object from the list of Auditables that will have their

   * auditErrors method called

   */

   public static void removeAuditable(Auditable auditable) {

      synchronized (listOfAuditableObjects) {

         listOfAuditableObjects.remove(auditable);

      }

   }


}


Here is an example of using the interface and the provided class:

An Example

package epfl.sweng;


import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Vector;


import android.graphics.drawable.Drawable;

import android.util.Log;


import com.google.android.maps.ItemizedOverlay;

import com.google.android.maps.OverlayItem;


import epfl.sweng.audit.Auditable;

import epfl.sweng.audit.AuditingEntity;

import epfl.sweng.friend.Friend;


public class FriendLocationOverlay extends ItemizedOverlay<OverlayItem> implements Auditable {


   private final Map<Friend, OverlayItem> myFriendsOverlay;

   private final List<Friend> myFriendsList;


   public FriendLocationOverlay(Drawable defaultMarker, Iterable<Friend> friends) {

      super(boundCenterBottom(defaultMarker));

      myFriendsOverlay = new HashMap<Friend, OverlayItem>();

      myFriendsList = new Vector<Friend>();

      for (Friend f : friends) {

         OverlayItem newItem = new OverlayItem(f.whereIs(), f.ID(), "Interact with: " + f.ID());

         myFriendsOverlay.put(f, newItem);

         myFriendsList.add(f);

      }

      /**

       * the data structure is consistent right now. Thus, we can add it to the

       * list of data structures to be audited

       */

      AuditingEntity.addAuditable(this);

   }


   /**

    * Auditing should not be performed while the data structure is being

    * updated. Locking the data structure during updates and also during

    * auditing prevents this. The auditErrors() method also locks the object

    */

   public synchronized void updateFriendLocation(Friend friend) {

      OverlayItem item = new OverlayItem(friend.whereIs(), "My friend", "Le friend");

      myFriendsOverlay.put(friend, item);

      friend_lookup: for (Friend f : myFriendsList) {

         if (friend.equals(f)) {

            f.setStatus(friend.isLoggedIn());

            break friend_lookup;

         }

      }


      populate();

   }


   public int size() {

      return myFriendsOverlay.size();

   }


   /**

    * The method should not audit this data structure while the data structure

    * is being updated. Locking the data structure during updates and also

    * during auditing prevents this. The updateFriendLocation(Friend) method

    * also locks the object

    */

   public synchronized int auditErrors() {


      int auditErrors = 0;


      /*

       * Rep invariant for this class:

       * 

       * Each element in myFriendsList is a valid friend and has a corresponding

       * valid element in myFriendsOverlay. Both myFriendsList and

       * myFriendsOverlay must be initialized and have the same number of

       * elements.

       * 

       * The goal of auditing is not solely to determine whether the invariant

       * holds or not, but to identify all the ways in which it is violated. We

       * put the checks on the then-branches of if statements.

       */

      if (myFriendsList == null || myFriendsOverlay == null) {

         if (myFriendsList == null) {

            auditErrors++;

            Log.e("AUDIT", "FriendLocationOverlay - List of friends is null");

         }

         if (myFriendsOverlay == null) {

            auditErrors++;

            Log.e("AUDIT", "FriendLocationOverlay - Map of friends overlays is null");

         }

         return auditErrors; // we cannot check anything more beyond this

      }


      if (myFriendsList.size() != myFriendsOverlay.size()) {

         auditErrors++;

         Log.e("AUDIT","FriendLocationOverlay - Lists of friends and overlays differ in size");

         // we can still check the friend correspondence, even if sizes

         // differ, so don't return yet

      }


      int friendIdx = 0;

      for (Friend friend : myFriendsList) {

         if (friend == null) {

            auditErrors++;

            Log.e("AUDIT", "FriendLocationOverlay - Found null friend at position" + friendIdx);

            continue;

         }


         OverlayItem overlayForFriend = myFriendsOverlay.get(friend);

         if (overlayForFriend == null) {

            auditErrors++;

            Log.e("AUDIT","FriendLocationOverlay - Null overlay for friend "  + friend.ID() + " at position " + friendIdx);

         }


         friendIdx++;

      }


      return auditErrors;

   }


   protected OverlayItem createItem(int index) {

      return myFriendsOverlay.get(myFriendsList.get(index));

   }

}



As you can see, the call to AuditingEntity.addAuditable(this) is performed in the constructor/initialization method of the class to be monitored. This "registers" the auditable class.

The int auditErrors() method checks the representation invariant: the list of friends and the map from friends to Overlays should not be null, there should be as many Overlays as there are friends, and there must be an Overlay for each friend. When one of these conditions does not hold, the number of encountered errors is incremented.

Implementing the required interfaces and classes correctly and completely will earn you 10 points.

5. Deliverables

Please send an email to the SwEng Staff with the link to the SVN repository where your project is located. Remember, the structure of the folder defined by the address you provide must pass the check_structure.bat test. The link to your SVN repository should be sent by November 23, the latest.

By November 24, you have to hand in:
  • The code for FriendFinder + ChessGameUI + ChessGame Logic
  • ant build file that:
    • compiles the code
    • creates the apk file
    • installs FriendFinder+ChessGameUI+ChessGame Logic on the two running emulators, corresponding to two friends
    • runs the provided test suite plus the test you developed

    A functionally complete build file will be rewarded with 5 points. If your build file does not do all of the required actions, you will get 0 points. Furthermore, your project will not be evaluated.

  • Note: The code you deliver must run on the client's machine. A client is not going to be happy if the developers tell him/her that the program worked on the developers' machines. The computers in the BC07-08 laboratory are the client's machines. Your code must run on the BC machines.
  • You must use the script check_structure.bat on the BC machines to check that your build system complies with the requirements. Download the attached check_structure.ba_ and rename it to check_structure.bat. Run it by invoking c:\path_to_check_structure\check_structure.bat path_to_project, for example using check_structure.bat "c:\Documents and Settings\myname\sweng".
    You must send the path to the SVN repository of your project reported by the script to sweng-staff-fall09@googlegroups.com

    Note: this script will download Subversion since it is not installed on the BC machines yet. We are working with the IT department to fix this problem.

 

6. Managing Large Teams

In this milestone, you will work in teams of six to seven people. Working in a big team requires careful partitioning of the work, to ensure that each team member contributes optimally. You should keep track of progress for the entire project and follow the guidelines describes in lecture.

Your teams can operate in several possible configurations. Two of these options are as two teams of 3-person subteams, or three teams of 2-person pairs.

If you go for the 2x3 option, you could have a Red subteam and a Blue subteam. In this case, you might partition the work by assigning the Red Team 35 points' worth of implementation (Pawn moves including promotion and en passant, Queen moves, Bishop moves, Knight moves, Rook moves, and making sure the white player starts), and to the Blue Team the other 35 points' worth (King moves including castling, check and checkmate detection, and all draw situations). The remaining 25 points would be covered by collective work.

If you opt for the 3x2 alternative, you could have a Red pair, a Blue pair, and a Yellow pair.  The Reds could get 25 points' worth of work (e.g., King moves including castling, check and checkmate detection, Rook moves, and making sure the white player starts), the Blues could get another 25 points' worth (Pawn moves including promotion and en passant, Queen moves, Bishop moves, and draw by agreement), while the Yellows could get another 25 points' worth (Knight moves, all remaining draw situations, and the ant build file).

Of course, these are just examples; you are free to partition the work as you see fit. We strongly advise that you design the overall interfaces and achieve collective agreement on them before going off and coding things up.