So why is it taking so long? For one thing, I forgot to take into account the time of reading through the list of attained game states. But right now, I'm only up to around 3000 game states. What I think has happened is that I have underestimated the time of reading the file. I am willing to bet that reading off the of SD card isn't particularly efficient, so that all of the opening and closing of the file and reading the data over and over again is just chewing up all sorts of time.
Nonetheless, I've included the code for completeness. I don't really have time to write a new program tonight or the next several nights, so I'm just going to let it continue to run for the next few days and see if it reaches the end. If I were to create a new program, I would do the enumeration differently. I think I would go back to the original enumeration program. Every time a move is added, it would have to be a new position. But if I remove a move, I would be returning to a previously created position. I think I've even got that type of language written into the program. It's simple enough that I could probably do it tonight if I really wanted to. But I don't.
Addendum - After thinking about it for a moment longer, I realized that the above won't quite work. There will be lots of repetitions. I'll have to do a more careful enumeration perhaps ordered by the number of moves. But then I have to worry about positions that are impossible to reach. Or do I? I'm not sure, but I think that impossible to reach positions really just mean positions where both X and O have a 3 in a row. It's possible for X or O to get a double-win with a single move. But there will never be a situation where both win. (Also, I'll always alternate turns between X and O, so there will be at most 5 Xs, which cannot make two distinct TTTs.)
## Tic-Tac-Toe Game State Generator
##
## This program takes all possible games of Tic-Tac-Toe and generates a list
## of all possible game states. This will be the foundation of the game tree
## that will be used to analyze the game for machine learning.
##
## The program will take in the ordered games created by the TTT_Enumerator
## program and use this to generate mid-game states. This will be a
## non-redundant system, so that as new states are generated they are checked
## against the existing states. This means that each game state will be listed
## exactly once.
##### Generate game board given moves list
def playGame(moves):
game = [0]*9
for turn in range(1,10):
if moves[turn] > -1:
if turn % 2 == 0:
player = 2
else:
player = 1
game[moves[turn]] = player
return game
##### Check if the game already exists
def alreadyExists(thisGame, debug):
checkFile = open("TTTGameStates.txt", "r")
for line in checkFile:
gameAsStr = line.split()
game = [0]*9
for i in range(0,9):
game[i] = int(gameAsStr[i])
if debug == 1:
print "Checking game match"
print "game = {}".format(game)
print "thisGame = {}".format(thisGame)
if game[0] == thisGame[0] \
and game[1] == thisGame[1] \
and game[2] == thisGame[2] \
and game[3] == thisGame[3] \
and game[4] == thisGame[4] \
and game[5] == thisGame[5] \
and game[6] == thisGame[6] \
and game[7] == thisGame[7] \
and game[8] == thisGame[8]:
if debug == 1:
print "Match!\n\n"
checkFile.close()
return 1
if debug == 1:
print "Not a match"
checkFile.close()
if debug == 1:
print "No matches at all"
return 0
##### Check for win
def checkWin(game):
winner = 0
# X win?
if game[0]*game[1]*game[2] == 1 \
or game[3]*game[4]*game[5] == 1 \
or game[6]*game[7]*game[8] == 1 \
or game[0]*game[3]*game[6] == 1 \
or game[1]*game[4]*game[7] == 1 \
or game[2]*game[5]*game[8] == 1 \
or game[0]*game[4]*game[8] == 1 \
or game[2]*game[4]*game[6] == 1:
winner = 1
elif game[0]*game[1]*game[2] == 8 \
or game[3]*game[4]*game[5] == 8 \
or game[6]*game[7]*game[8] == 8 \
or game[0]*game[3]*game[6] == 8 \
or game[1]*game[4]*game[7] == 8 \
or game[2]*game[5]*game[8] == 8 \
or game[0]*game[4]*game[8] == 8 \
or game[2]*game[4]*game[6] == 8:
winner = 2
elif game[0]*game[1]*game[2]*game[3]*game[4]*game[5]*game[6]*game[7]*game[8] > 0:
winner = -1
return winner
##### Main Program
debug = 0
inputFile = open("TTTGames.txt", "r")
checkFile = open("TTTGameStates.txt", "w")
checkFile.write("0 0 0 0 0 0 0 0 0 0\n")
checkFile.close()
for line in inputFile:
## Get move data
movesAsStr = line.split()
moves = [0, -1, -1, -1, -1, -1, -1, -1, -1, -1]
for i in range(1,10):
moves[i] = int(movesAsStr[i])
## Check each step of the game to see if it already exists in the list
stepMoves = [0, -1, -1, -1, -1, -1, -1, -1 ,-1 ,-1]
for depth in range(1,10):
if moves[depth] > -1:
stepMoves[depth] = moves[depth]
thisGame = playGame(stepMoves)
if debug == 1:
print "stepMoves = {}".format(stepMoves)
print "thisGame = {}\n\n".format(thisGame)
## If the game does not exist, add it to the list
if alreadyExists(thisGame, debug) == 0:
thisGame.append(checkWin(thisGame))
if debug == 1:
print "Adding thisGame"
print "thisGame = {}".format(thisGame)
if debug == 1:
print "\n"
addToFile = open("TTTGameStates.txt", "a")
for item in thisGame:
addToFile.write(str(item))
addToFile.write(" ")
addToFile.write("\n")
addToFile.close()
