Dots and Boxes is a common pencil and paper game.
Added on - Sep 2019
Showing pages 1 to 3 of 6 pages
Dots and Boxesis a common pencil and paper game. In this project you willdevelop a program to play a game against a human opponent.1. The GameThe game is played on rectangular grids of varying sizes. Originally, onlythedotsare marked at each grid intersection.On their turns, players fill in anedgebetween two currently unconnected dots.If the player adds an edge that completes a box surrounded by 4, single length,filled-in edges, then the player marks the box with their initial, claims a pointfor that box, and immediately takes another turn. Otherwise, play passes to theother player.When all edges have been filled in, the player who has scored the most pointswins the game.2. The Computer PlayerYou will be implementing the software to manage a game in progress and totake the part of the one player.A perfect game player is beyond the scope of this course, you will insteadimplement an aggressive strategy in which the computer player selects an open(i.e., not yet filled in) edge to fill in as follows:2.1 First-level RuleIf there are any boxes that have 3 out of their 4 edges filled in, chooseone and fill in its fourth edge.Otherwise, select an open edge that does not add a third edge to any box.Otherwise, select an open edge.It is possible, even likely, that the above rules will not uniquely identify asingle edge, but will instead produce a list of equally acceptable edges. Withinsuch a list, select the preferred edge as follows:2.2 Second-Level Rule}
For each edge E in the list, compute thedegrees of freedomof that edge by countingthe total number of open edges that touch upon either dot at an end of E. Selectthe edge(s) with the maximum degrees of freedom.If the above two rules still yield multiple edges as possible moves, then applythe next rule:2.3 Third-Level RuleSelect the edge E between dots D1 and D2 from the list that minimizes the sumof the x-coordinates of D1 and D2.Finally, if you still have multiple edges to consider, break the final tie with thisrule:2.4 Fourth-Level RuleSelect the edge E between dots D1 and D2 from the list that minimizes the sumof the y-coordinates of D1 and D2.This is by no means a perfect player. It does not, for example, implementthedouble-cross strategyof giving away short chains to one’s opponent to setup a longer chain that can be claimed later.In a real implementation of the game, we would probably replace the last tworules by a random selection from among the tied edges, as this would result in aplayer that was less predictable and therefore probably more fun to playagainst. But, for now, we will sacrifice randomness in favor of easier testing.It’s hard to test code that is allowed to make random choices.3. Managing the GameThe program must take all input from the standard input stream,cin, andproduce all output on the standard output stream,cout. The entire programmust implement 3 distinct phases: pre-game, game, and post-game.In this program, the human player will always move first.3.1 Pre-GameIn the pre-game phase, the program should prompt the human player:
What size grid would you like? (2..8)with one blank space (but no new-line) after the ‘)’. The program will then readfrom the standard input, attempting to obtain an integer input in the range 2..8.An integer outside that range, or any non-integer input, should result in a line:Sorry, try again.followed by a repeat of the prompt and another attempt to obtain a suitableinteger. This may be repeated as often as necessary. If, however, an end-of-input condition is reached, the program exits immediately.3.2 GameThe game phase consists of multiple turns. The human player will go first.Each turn consists ofPrinting the gridPrinting the scoreObtaining the next moveApplying that moveThese are described in more detail below. At the end of any turn, if all edgesare filled in, the program moves to the post-game phase.Printing the GridThe grid consists ofNboxes, whereNis the grid size obtained in the pre- phase.Each box is represented as a 3x3 sequence of characters with a ‘+’ at eachcorner, a ‘-’, ‘|’ or ’ ’ to denote a filled-in horizontal or vertical edge or an openedge, and the central character containing a ‘H’, ‘C’, or ’ ’ to indicate the boxhas been claimed by the human player, the computer player, or by neither.Boxes that share an edge will be drawn with only the single shared edgebetween them. For example, a 3x3 grid might be drawn as:+ +-+ + | |H| + +-+-+ |C| +-+-+-+ |C|C| + +-+-+As an aid to navigation, however, the grid will actually be printed with indexcharacters on the left and bottom. These name the columns using the numbers1..N+1 and the rows using the letters ‘a’..‘a’+N. The index characters arealigned with the edges/dots, not the boxes. For example,