4 —
Due Thursday, 10 October 2024, 11:59:59pm
Purpose T to develop the one non-trivial algorithm that every system comes with
Every software system contains some components that implement a non-trivial algorithm. Some years, this course comes with game components whose implementation is challenging; this year, the strategies are non-trivial tree-search algorithms.
In the olden days, computer science departments confused programming with algorithm development. Many still do, especially faculty members who avoided building software systems for their research. By now you understand that algorithm development is only one aspect of software system development. And in many cases, companies hire specialists for the truly complex algorithms in the system. This milestone gives you an opportunity to figure out whether “algorithm design” is the place in the software industry where you want to end up or whether other aspects are more to your liking.
Delivery Place the product of this week’s milestone into your git repo as follows:
for the Programming Task, place the player’s strategy functionality into Bazaar/Player/strategy.PP;
for the Design Task, place player-protocol.md into Planning/
for the Testing task, place xturn and Tests/ into a top-level repo directory named 4
Programming Task Fundamentals I and II teach to abstract after you have seen several similar pieces of code. Here you can see ahead of time that the playing mechanics remains the same while the decision-making process changes. It is therefore appropriate to abstract immediately. An AI player needs a strategy for playing turns. Indeed, an ambitious participant in a Bazaar game may wish to experiment with more than one strategy. So a player component should handle the mechanics of playing and should abstract over a strategy component.
should it request a pebble or request exchanges or forgo both?
To simplify the task a bit, we whimsically decide that players request a pebble from the bank only if they cannot perform any exchanges.
once the player has the pebbles it wants, which cards should it buy and in what order?
Pick a sequence of exchanges followed by a sequence of cards that maximize the number of points that the purchase of cards can achieve during a single turn.
Pick a sequence of exchanges followed by a sequence of cards that maximize the number of cards that a player can purchase during a single turn.
Implementing these maximization goals requires searches of trees of potential candidates. While the search for a maximizing sequence of card purchases is naturally limited by the number of available cards, the search for a maximum-enabling exchange strategy comes without such natural limit. For now we impose an artificial limit of 4.
Tie breaking Conceptually, these maximizing search strategies collect “best so far” candidates in sets. Collecting candidates is necessary because these processes may encounter several different maximizing exchange-and-purchase arrangements. When the search is done and the set contains more than one element, it is necessary to break ties.
The search process eliminates any candidates that do not yield the highest number of points. (This rule vacuously applies to the points-maximizing strategy.)
The search process eliminates any candidates that do not yield the largest number of remaining pebbles in the player’s wallet.
The search process picks the candidate with the smallest wallet, unless all candidates have equal wallets.
This code hides auxiliaries so that nobody can include it directly into a code base.
Here is the definition for the comparison of wallets from the oracle implementation:
#; {Wallet Wallet -> Boolean} ;; ‘1wallet‘ is below ‘2wallet‘ if the strings formed from the two are string<? ;; assuming they are of the same size; other just compare sizes (define (wallet<? 1wallet 2wallet) (if (= (wallet-size 1wallet) (wallet-size 2wallet)) (string<? (wallet->string 1wallet) (wallet->string 2wallet)) (< (wallet-size 1wallet) (wallet-size 2wallet)))) #; {Wallet -> String} ;; turn the wallet into a sorted color string and check string<? (define (wallet->string a-wallet) (let* ([s (wallet->list a-wallet)] [s (map p:pebble-color-first-letter s)] [s (sort s char<=?)]) (list-of-chars->string s))) The search process picks the candidate with the smallest sequence of cards, unless all candidates have equal sequences of cards.
Card c is less than card d ifd is happy and c is not; or
c's happiness is the same as d's, and c's bag of pebbles considered as a wallet is less than d's bag of pebbles considered as a wallet.
c and d don't both come with a face and c doesn't display one; or
if c's pebbles considered as a wallet is less than d's pebbles considered as a wallet.
A sequence of cards c* is less than a sequence of cards d* if the first is shorter than the second or for some i in the range of the length of the two equally-long sequences, the 0-through (i-1)ith cards of c* are the same as in d*, and the ith card of c* is less than the ith card of d*.
each card in c* at position i is less than the corresponding card in d* at i for i in range for the shorter of the two equally-long sequences.
from equivalent candidates, pick the ones that need the smallest number of trades;
from the remaining equivalent candidates, use the tie breaker for card purchases; and if this still leaves a non-singleton set of equal candidates,
pick the one that uses the smallest pebble-exchanges.
A pebble exchange P is less than a pebble exchange Q the pebbles on the left-hand side of P (as a wallet) are less than the pebbles on the left-hand side of Q (as a wallet) or, assuming those are equal, if the pebbles on the right-hand side of P (as a wallet) are less than the pebbles on the right-hand side of Q (as a wallet).
A sequence of pebble exchanges P* is less than a sequence of pebble exchanges Q* if the first is shorter than the second or or for some i in the range of the length of the two equally-long sequences, the 0-through (i-1)ith trade of P* are the same as in Q*, and the ith trade of P* is less than the ith trade of Q*.
each exchange in P* at position i is less than the corresponding exchange in Q* at i for i in range for the shorter of the two equally-long sequences.
Design Task The player components must communicate with the referee.
This communication involves both function/method calls and orderings of those,
i.e., a protocol. Since outsiders will program to this interface, it must be
spelled out precisely and in detail. Hint To start your
brainstorming—
A protocol supplements an API to explain the calling sequence. Protocols are rarely checked, violations hard to detect, and the resulting errors tend to be obscure.
Design the interaction protocol between the referee and the player(s). The document, named player-protocol.md, should be a well-organized English write-up. If you are familiar with UML sequence diagrams (or you have time to read up on them), illustrate the prose with one of those.
One page should suffice. Less is more.
Keep in mind our Bazaar.Com, a Plan while you work on a design task.
Testing Task Create a test harness named xturn. The harness consumes its JSON input from STDIN and produces its results to STDOUT. Create five three tests ([0-2]-{in,out}.json) and place them in the specified Tests/ folder.
A test case always consists of given inputs and expected outputs. For this
course, a test consists of a pair of files: n-in.json, the input file, and
n-out.json, the expected output file, where n is an integer between 0
and the requested number of tests (exclusive).—
The input of xturn is a Game in JSON format; its output is the corresponding Turn in JSON format.
Here are the relevant JSON specifications:
INTERPRETATION A Game instance describes the referee's knowledge about
the pebbles available for exchange, the visible cards, the cards to
be unveiled, and the pebbles that the players own as well as their
current scores. The array lists the player in the order in which they
will take turns.
INTERPRETATION A Turn instance describes knowledge that the referee
will share with the player whose turn it is next:
the pebbles available for exchange, the visible cards, the active
player's pebbles and its score, plus the scores of the remaining
players in the order in which they will take turns.
INTERPRETATION A Player instance specifies the pebbles that
the player owns and its score.
INTERPRETATION A Card instance specifies the pebbles that |
are displayed on the card and whether it displays a smiley. |
|
CONSTRAINT The array contains no more than 6 Players. |
CONSTRAINT The array contains at least one Player for this milestone. |
|
|
|
Well-formed and Valid You may assume that all inputs to your test harnesses from STDIN are well-formed and valid. A well-formed piece of JSON satisfies the grammar; such a piece is valid if it also satisfies all the side constraints of a schema specification.