Ask a question to Desklib · AI bot


Dots and Boxes Game

6 Pages1919 Words427 Views

Added on  2019-09-30

About This Document

Develop a program to play Dots and Boxes game against a human opponent. Learn the rules and strategies to win the game. The program must take all input from the standard input stream, cin, and produce all output on the standard output stream, cout. The entire program must implement 3 distinct phases: pre-game, game, and post-game.
BookmarkShareRelated Documents
Dots and Boxesis a common pencil and paper game. In this project you will develop a program to play a game against a human opponent.1. The GameThe game is played on rectangular grids of varying sizes. Originally, only thedotsare 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 point for that box, and immediately takes another turn. Otherwise, play passes to the other player.When all edges have been filled in, the player who has scored the most points wins the game.2. The Computer PlayerYou will be implementing the software to manage a game in progress and to take the part of the one player.A perfect game player is beyond the scope of this course, you will instead implement 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, choose one 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 a single edge, but will instead produce a list of equally acceptable edges. Within such a list, select the preferred edge as follows:2.2 Second-Level Rule}
Dots and Boxes Game_1
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. Select the edge(s) with the maximum degrees of freedom.If the above two rules still yield multiple edges as possible moves, then apply the next rule:2.3 Third-Level RuleSelect the edge E between dots D1 and D2 from the list that minimizes the sum of the x-coordinates of D1 and D2.Finally, if you still have multiple edges to consider, break the final tie with this rule:2.4 Fourth-Level RuleSelect the edge E between dots D1 and D2 from the list that minimizes the sum of the y-coordinates of D1 and D2.This is by no means a perfect player. It does not, for example, implement thedouble-cross strategyof giving away short chains to one’s opponent to set up a longer chain that can be claimed later.In a real implementation of the game, we would probably replace the last two rules 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 play against. 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, and produce all output on the standard output stream,cout. The entire program must 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:
Dots and Boxes Game_2
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 suitable integer. 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 edges are 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 each corner, a ‘-’, ‘|’ or ’ ’ to denote a filled-in horizontal or vertical edge or an open edge, and the central character containing a ‘H’, ‘C’, or ’ ’ to indicate the box has 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 edge between 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 index characters on the left and bottom. These name the columns using the numbers 1..N+1 and the rows using the letters ‘a’..‘a’+N. The index characters are aligned with the edges/dots, not the boxes. For example,
Dots and Boxes Game_3

Found this document preview useful?