Dots and Boxes Game Project

This project involves developing a C++ program to play the Dots and Boxes game against a human opponent. The program is divided into three phases: pre-game (determining grid size), game (turns involving grid display, score updates, move input/generation, and move application), and post-game (final score and game outcome). The computer player utilizes a multi-level strategy to select moves, prioritizing completing boxes and maximizing degrees of freedom. The human player inputs moves via the console, and input validation is implemented. The program handles various scenarios, including invalid input, game completion, and win/loss/tie conditions. The project provides a detailed specification, including examples of game output and expected behavior.

Dots and Boxes is a common pencil and paper game. In this project you will
develop a program to play a game against a human opponent.
1. The Game
The game is played on rectangular grids of varying sizes. Originally, only
thedots are marked at each grid intersection.
On their turns, players fill in an edge between 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 Player
You 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 Rule
 If 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}

For each edge E in the list, compute the degrees of freedom of that edge by counting
the 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 Rule
Select 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 Rule
Select 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
the double-cross strategy of 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 a
player 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 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.
In this program, the human player will always move first.
3.1 Pre-Game
In 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 read
from 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 Game
The game phase consists of multiple turns. The human player will go first.
Each turn consists of
 Printing the grid
 Printing the score
 Obtaining the next move
 Applying that move
These 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 Grid
The grid consists of N boxes, where N is 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,

a + +-+ + | |H| b + +-+-+ |C| c +-+-+-+ |C|C| d + +-+-+ 1
2 3 4
A blank space separates the index characters on the left from the grid itself.
However the bottom index line is printed immediately below the bottom line of
the grid.
Printing the Score
Immediately after the grid, the current score is printed on a single line as
follows:
You: NN Me: MM
where NN and MM are replaced by the appropriate human and computer player
scores and there are 4 blank spaces between NN and the following word Me:. The
two scores are printed as integers in the conventional format - they do not need
to occupy exactly two digits.
This is then followed by a second, empty line.
Obtaining the Next Move
If it is currently the computer’s turn, then computer player selects a move
according to the strategy outlined above. It then announces that move by
printing a line:
I choose to connect dots DN and DM.
where DN and DM are dot names, each consisting of a lower-case letter followed
by a single-digit number. The order of the two names should be to present the
lower-valued letter (row) first in a vertical edge and the lower-valued number
(column) first in a horizontal edge.
If it is currently the human player’s turn, the program will prompt for a move as
follows:
What two dots would you like to connect? (Q to quit)
with a single space (but not a line terminator) following the )
The program then reads a line of input from standard in. If an end-of-input
signal is reached, the program immediately goes into the Post-Game phase.
Otherwise, all non-alphanumeric characters are discarded from the input. If

what remains is the single letter ‘Q’, then the program immediately moves to
the post-game phase. If what remains consists of 4 characters, with one letter
and one digit among the first two characters and one letter and one digit among
the last two characters, and if each letter-digit pair is in the legal range for our
grid, and if the two dots are only one edge apart and the edge between them is
open, then the move is accepted. If the input is not acceptable, then the program
will print a line:
Sorry, try again.
and then will repeat the prompt and input sequence.
3.3 Apply the Move
When an acceptable move has been obtained for the current player, the grid and
score is updated with that move and the identity of the player who will take the
next turn is determined. That ends the current turn. A single empty line is
printed. If all edges have been filled in, then the program moves to the post-
game phase. Otherwise, the program then moves on to the next turn, as just
described in this section.
3.4 Post-Game
In the post-game phase, the program prints the grid as described above, then
prints one empty line, then prints:
Final Score: You:NN Me :MM
replacing the NN and MM by the appropriate human and computer player scores.
As before, these are printed as integers, using the conventional format. The
second and third lines above are indented by exactly 2 spaces.
The program will then print a farewell line, one of the following:
Congratulations! Better luck next time. I think we need a rematch.
in the event of a human win, a computer win, or a tied score, respectively. The
program then exits.
4. Example
Here is a transcript of a possible game.

What size grid would you like? (2..8) 2
a + + +
b + + +
c + + +
1 2 3
You: 0 Me: 0
What two dots would you like to connect? (Q to quit) a1 a2
a +-+ +
b + + +
c + + +
1 2 3
You: 0 Me: 0
I choose to connect dots b1 and b2.
a +-+ +
b +-+ +
c + + +
1 2 3
You: 0 Me: 0
What two dots would you like to connect? (Q to quit) 2a,b2
a +-+ +
|
b +-+ +
c + + +
1 2 3
You: 0 Me: 0
I choose to connect dots a1 and b1.
a +-+ +
|C|
b +-+ +
c + + +
1 2 3
You: 0 Me: 1
I choose to connect dots c1 and c2.
a +-+ +
|C|
b +-+ +
c +-+ +
1 2 3
You: 0 Me: 1
What two dots would you like to connect? (Q to quit) Q
a +-+ +
|C|
b +-+ +
c +-+ +
1 2 3
Final Score: You:0 Me :1
Better luck next time.