Teaching
6515 S '13
 
Projects
Presentations
SVN
 
Acquire
Acquire, Revised
Acquire Plan
Project 1
Project 2
Project 3
Project 4
Project 5
Project 6
Project 7
Project 8
Project 9
Project 10
Project 11
Project 12

Project 9

Due date: 3/25, 23:59

Objective 1: to design and implement a rule enforcer in the form of a game tree

Objective 2: to formulate contracts for interfaces


Task 1: Design and implement a game tree module for Acquire. The module should come with two interfaces:

  1. one for the game administrator, which can use the tree to control the execution of the game.
  2. one for the player(s), which can probe the tree for information to decide the next move -- assuming perfect information.

At a minimum, your game tree module must support one constructor:

  generate : InternalState -> Tree
The given InternalState may describe the state after setting up the players with their initial tiles or an intermediate state after the game administrator has removed some unruly player. From the given state, generate creates a tree that describes all possible actions that the administrator and the players can take. A complete turn contains branches for all possible tiles a player can place, all possible hotels that could be involved, all possible combinations of shares to be bought, and finally all possible tiles that the administrator can hand over to the player. The result of these steps is a subtree, whose top-tier InternalState describes the result of these actions plus the rotation of the players.

The construction of an Acquire game tree is an algorithmic problem. An initial tree is a quite "bushy" tree. If three players participate, the first layer of share distribution has up to 3 out of 175 possibilities (which is 893,376), the second one 3 out of 174 (878,150), and so on. If you consider all possible cross-products, you get some 784,518,134,400 possibilities on the first two levels alone.


Task 2: Change the game administrator so that it uses the game tree module to control the game. After setting up the players with tiles, the administrator generates a game tree. Once a player specifies the actions it wishes to perform for its turn, the administrator calls a function/method on the game tree to navigate to the appropriate subtree. In case navigation fails, the player cheated. The game ends if the internal state at the root of the tree is a final state.


Task 3: Your second task is to implement and deliver a two piece test harness Each test case that exposes a flaw in some other code base gets you a bonus point. A test case that does not pass my reference implementation means a loss of one point.

The test harness will consist of two pieces:

  1. for the administrator interface, ensure that the revised game administrator passes the same tests as the original one. That is, you will create the harness itself, dubbed game-tester, which responds to requests in the form of XML elements with responses. It should come with a subfolder, game-tests, with up to three test cases specified as a pair of files: inN.xml and outN.xml for N = 0, ..., 2. See project 7 for the specification of requests and responses.

  2. for the player interface, the test harness will request an inspection of the game tree starting from a certain state. The test harness will have to implement two kinds of queries on game trees: one to find out how many hotel foundings may happen and the other one to find out how many mergers may happen. A real player may wish to query the tree for other forms of information.

    For this second harness, you will create the harness itself, dubbed player-tester and a subfolder, player-tests, with up to three test cases specified as a pair of files: inN.xml and outN.xml for N = 0, ..., 2. See below for the specification of requests and responses.

  Query = <founding n=Nat> State Order ... </founding>
	| <merging n=Nat> State Order ... </merging>
  Order = <order />
	| <order> Xotel </order>
	| <order> Xotel Xotel </order>
	| <order> Xotel Xotel Xotel </order>
  Xotel = <hotel label=Label /> 
  State = ... as in project 7 ...
requests
  Count = <count n=Nat/>
responses
  
  Nat   = String, interpretable as a natural number (non-negative integer) 
common forms of data

A request's tag and attribute specify which kind of transition between states to look for and for how many levels of turns to inspect. Its nested elements specify the start state and the purchase policies that a player wishes to pursue. To keep queries simple, each purchase policy is specified as an order of specific hotel shares to be bought. In a realistic setting, an automated player may wish to explore purchasing policies that are functions of the current state.


Task 4: Extract any checks from your methods and functions and formulate them as contracts:

  1. if your language supports a contract system, use it to express the contracts;
  2. if it doesn't, formulate separate contract checking methods:
      // add tile t to this board 
      void addTileToBoard(Tile t) throws NotPlaced {
        checkAddTileToBoard(Tile t); 
    
        // proper implementation here 
      } 
    
    You should arrange your files so that these contract checking methods are easily reachable from your component interfaces.


last updated on Wed Apr 10 20:51:12 EDT 2013generated with Racket