Try this website for an explanation of the rules and to play the game (against a rather dumb opponent).
For this extra credit program you'll write a program that calculates the number of different tic-tac-toe boards there are, taking many factors (e.g., symmetry) into account.
Traditionally 'X' goes first, and there are 9 locations in which 'X' can go. There are nine "different" boards with one 'X' as shown below. (See the discussion on symmetry for why there are really only 3 different boards.)
X | | | X | | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | | | | | | | | | | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | X | | | X | | | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | X | | | X | | | XAfter this spot is taken there are 8 locations for 'O' to go so there are 72 (9*8) different boards with one 'X' and one 'O'. Continuing with this reasoning leads to 9*8*7*6*5*4*3*2*1 = 9! different board configurations in which all squares are taken with 5 X's and 4 O's since X goes first. Note that in the real game one player may win before all squares are taken, but 9! is an upper bound on the number of boards with all squares taken.
The total number of boards, i.e., with one X; one X and one O; two X's and one O, and so on is then
9 + 9*8 + 9*8*7 + 9*8*7*6 + 9*8*7*6*5 + ... + 9! = 986,409
The program TicTac.java generates
each of these boards and stores
each of the 986,409 boards in an ArrayList.
Note that there are lots of duplicate boards, for example consider the two
sequences of moves below which lead to the same board. The
third board in each row below is generated twice by
the program since it places an X in every location, then an O
in the remaining locations, and so on.
X | | X | O | X | O | X ---+---+--- ---+---+--- ---+---+--- | | | | | | ---+---+--- ---+---+--- ---+---+--- | | | | | | | | X | O | X X | O | X ---+---+--- ---+---+--- ---+---+--- | | | | | | ---+---+--- ---+---+--- ---+---+--- | | | | | |If all the duplicates are removed from the vector of 986,409 there are 6,045 different boards generated. In a real sequence of games, not all of these could be generated since once a player wins, no more X's or O's are placed, but the program TicTac.java doesn't take this into account.
Symmetry
Many of the boards generated by the
program are the same board because
of symmetry. For example, there are are really only three
different first moves as shown below.
X | | | X | | | ---+---+--- ---+---+--- ---+---+--- | | | | | X | ---+---+--- ---+---+--- ---+---+--- | | | | | |The other moves are all symmetric to, or the same as, one of these. For example, any corner move is the same for the first move for the purposes of strategy in playing the game. Similarly, there are 12 really different boards containing one X and one O if symmetry is taken into account, as shown below.
X | O | X | | X | | O X | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | O | | | | | | | O ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | | | O | | | O | | | O ---+---+--- ---+---+--- | X | | X | ---+---+--- ---+---+--- | | | | O | X | | X | | X | | X | | X | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | O | | | | O | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | O | | | O |
This means that once a game has been won, no more moves are made. All symmetry is taken into account. There are three rotational symmetries: rotate 90, 180, and 270 degrees shown below, respectively, for the board on the left.
X | O | | X | X | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- X | | | | O | | X O | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | O | X X | X |There are four reflective symmetries: horizontal, vertical, left/right-diagonal, and right/left-diagonal as shown below, respectively, for the board on the left.
X | O | | | | O | X X | X | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- X | | X | | | | X O | | | | O ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | X | O | | | | | | X | X
The output from your program should be every really-different board printed, one board per line, with each line consisting of 9 characters, either 'X' or 'O' or space ' '. Use the numbering/indexing scheme below
0 | 1 | 2 ---+---+--- 3 | 4 | 5 ---+---+--- 6 | 7 | 8So that the string "X O OX X " represents the board below.
X | | O ---+---+--- | O | X ---+---+--- | X |This means the number of lines your program prints is the number of really-different tic tac toe boards.
Your program's output should be in lexicographical/sorted order. This means that if you've stored strings representing the boards in an ArrayList, you'll need to sort it before printing.
For each possible board, if there's more than one representation of the board when taking symmetry into account you must use the lexicographically smallest of these symmetric boards. For example for the symmetric boards above, their string representations are (from top-to-bottom, left-to-right in each of the two rows using '.' instead of space ' ' and not repeating the same board twice):
"XO.X....." "...X..XO." ".OX..X..." "XX.O....." ".....O.XX"
Of these, the last board is the lexicographically first since a space comes before either 'O' or 'X'.
This means, for example, that when creating a board you can generate all possible symmetries, sort the representations (as strings) and the smallest/first one will be the board to keep. Think about how to structure data to help. In Java, you can create a String from an array of char values and you can generate such an array from a string. This is helpful since you can't change a string once it's been created, strings are immutable.
As always, the README should include your name/NetID, thoughts of the assignment, a list of people with whom you discussed the assignment, a list of resources used, and how much time you spent on it.