8 — Implementing the Player’s and its Strategy

Due Monday, October 15, midnight

Delivery For this assignment, you will still place the design documents into the Design/ folder and Santorini-specific code into the appropriate Santorini/ sub-directory.

The xstrategy harness goes into your 8/ directory, while the tests go into 8/strategy-tests.

Design Task Although we are the implementors of the player components at the moment, we have to expect that others will supply AI players and we have a mechanism to oversee games between them. Specifically, our mechanism will ensure that the outside player components follow the rules of the game. (See the Company’s Plan.) Our company dubs this component a Referee.

It is time to design the referee component. Ask yourself what this referee needs to know about the players and the Santorini game and how it can get this knowledge from the components or designs you have.

Implementation Task Implement a strategy component that supports two pieces of functionality for a fixed player: (1) placing a worker for the player during the start-up phase of Santorini and (2) picking the next action to take when it is the player’s turn.

For the placement-of-workers functionality, implement two ideas:
  • place the worker on the first point of the diagonal that is still free, starting from (0,0).

  • place the worker on a field that is as far away from the other player’s worker(s) using the notion of geometric distance on a Cartesian plane.

Note Neither of these ideas is any good for real games.

For the choice-of-action functionality, the strategy component will Lecture 10 will briefly introduce game trees. rely on the generation and exploration of a complete game tree. While the game tree for our variant of Santorini is guaranteed to be finite, it is also guaranteed to be extremely large. Hence you will want to generate only those pieces that are absolutely necessary and suspend the generation of others until needed.

The choice-of-action functionality uses the game tree to explore the question whether a player’s action ensures that the opponent cannot make a winning move after n rounds of play. A round of play denotes any player taking any turn action.

Mock-up Context To test such a small system of a number of components, it is common to implement a mock-up environment.

Create a system-level test harness, called xstrategy, which can read and interpret sequences of JSON values (from STDIN and to STDOUT, respectively). The harness will test only the choice-of-action functionality. Each test will consist of a sequence as follows:
  • a JSON string, the name of a player,

  • a Board specification that is not final,

  • a JSON (natural) number, denoting the number of For the sake of testing, this number is restricted to less or equal to 4. look-ahead rounds,

  • an optional Move, and

  • a MoveBuild if (1) Move is specified and (2) the Move is not a winning one.

The specified player will take this action on the specified board. The expected result is either "yes"meaning the action does not lead to a loss within the specified number of rounds—and "no"meaning the action may lead to a loss within the specified number of rounds.

Here is a first sample input: No, neither of these initial board configuration is realizable, but a natural implementation of the strategy component will cope.


    [["0one1", "1one2", 3, "2two1"],

     [0,       "2two2", 3]]




and of course the output must be "no". The second example illustrates how deep planning ahead can work:


    [["0one1", "0one2"],

     [3,       0],

     ["0two1", "0two2"]]




The answer here is "yes", because it takes at least 3 steps to create a three-story building.

As always, you may assume well-formed and valid JSON values. Additionally, you may assume that the requested action is legitimate with respect to the given board.

Make sure to create a testme script that we can use to run your unit tests during code walks.

Testing Task Develop five system-level tests to be used with your test harness. A test consists of a pair of files: n-in.json for an input sequence and n-out.json where n is in 1, 2, 3, 4 or 5.