I've been working on Python and wanted to challenge myself. I had wanted to make a Tic Tac Toe game for a while, so I decided to give it a try.
The first thing I had to figure out were the rules of Tic Tac Toe as a computer would need to understand them. Here's what I came up with, in no particular order:
1) X's go first, then O's, then X's again, and so on until someone wins or the game ties.
2) If you go first, take the middle spot.
3) Try to get 3 of your symbol in a row.
4) Prevent your opponent from getting 3 of their symbols in a row.
5) You cannot place a symbol on an already occupied space.
6) The maximum amount of moves in a game is 9: 5 X's, 4 O's.
7) If you get 3 of your symbol in a row, the game is over and you've won.
8) If your opponent gets 3 symbols in a row, the game is over and your opponent has won.
9) If neither you nor your opponent get 3 symbols in a row, the game over and tied.
Then next thing I had to figure out was a way for the computer to keep track of what symbols were where, and which spaces were free. To do this, I assigned a letter to each spot on the grid:
A | B | C
----------
D | E | F
----------
G | H | I
To keep track of the game-play, I used arrays: one for the overall game-play, one for the computers moves, and one for the humans moves. So one game might look like this: [E,A,B,C,D,F,H] with X taking [E,B,D,H] and O taking [A,C,F] for a win for X.
To check for a win, I determined which combinations of taken places resulted in a win (there's 8 combinations). Then I had the computer check each players arrays against those arrays after every turn. If a player had any combination of spaces used by a winning combination, the game would end.
Now, it was easy enough to have the computer just play random spots (if they weren't taken), but a human player doesn't do that, they strategize. Unfortunately, I had no idea how to make the computer observe the field and determine (using algorithms) the best move to make. What I did know, was that it could carry out preprogrammed moves. So my first thought was to program every possible game of Tic Tac Toe and have the computer determine which moves have already been made, compare that to the database, then make a move. It turns out there are 255168 (not including symmetries) games of Tic Tac Toe that can be played. So that idea was out. Then I thought, "why not make it learn from it's victories?" So I did. When the computer won or tied, it would save the gameplay, and refer to it at each stage of subsequent games. In summary, the computer's thought process would be:
1) Is there a winning move I can make right now? if so, make it. If not:
2) Is there a move I can make right now that will prevent the human from winning afterward? If so, make it. If not:
3) Do the current pieces in this game match a game I've won before? If so, what was the next move I made at that time? Make it. If not:
4) Do the current pieces in this game match a game I've tied before? If so, what was the next move i made at that time? Make it. If not:
5) Make a random move.
Then I programmed in the niceties: placing X's and O's, updating the playing field, saving the game-plays, and so on. The last thing I did was give the user the option of playing X's or O's. Now I'm a bit embarrassed, but my solution to this broke a fundamental rule of programming: Don't Repeat Yourself. Although I repeated myself all over the place, the quickest and easiest solution was to duplicate the entire game with the symbols swapped, then give the player the choice of which game to start. It's not a perfect program, but I accomplished what I set out to do which is the first step of any bit of code.
