Try this website for an explanation of the rules and to play the game (against a rather dumb opponent).
In the Wikipedia article there is lots of information about the number of winning boards for 'X', for 'O', as well as information about symmetry as described in this assignment below.
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.
It's possible you'll need to increase Java's heap-space with -Xmx1024M to run the program in Eclipse.
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 11 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 | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | O | | | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | O | | | O |
In determining unique boards you must take the following into account.
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 | XThis means there are eight symmetric representations of the left-most board on each line above. Instead of storing and printing all eight, your program will store and print just one -- details as to which one are provided below.
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/not-symmetric, valid 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 eight symmetric boards above, their string representations are shown below.
'XO.X.....' '.XX..O...' '.....X.OX' '...O..XX.' '...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.
total # boards = XXXX, # wins for 'O' = YYYY, # wins for 'X' = ZZZZ
Where the README includes your thoughts of the assignment, a list of people with whom you discussed the assignment, and how much time you spent on it.