I had set the program to run overnight, but something happened because the program was not running in the morning, and the data appeared to have stopped somewhere. I think I have an idea of what happened, and it's related to shifting the first move from position 0 to position 1. I made some edits and I think I solved the problem. I won't know until it finishes, which will probably be in another couple hours.
Here's the code, with comments at the top:
Addendum: I ran the simulator again, but this time through a PuTTy connection, and it went significantly faster. I think it was done in less than an hour. I didn't time it, but it might have been as little as 30 minutes. I also needed to make a couple other minor adjustments to the code to handle the program exit properly. The final output has 255168 lines, which corresponds to the number of TTT games according to this website. This gives me a great deal of confidence that everything functioned correctly.
## Tic-Tac-Toe Game enumerator
##
## This program systematically cycles through all possible games of TTT
## and exports those games to a file that can be used to generate a set
## of games for the machine learning project.
##
## Each game consists of a 10 numbers. The first number is 0, 1, or 2 and
## indicates the winner:
## * -1 = Draw
## * 1 = X wins
## * 2 = O wins
## The remaining 9 numbers indicate the moves that are made and the order
## in which they were made. Unused moves (if someone wins before the 9th move)
## will be indicated by a -1.
##
## The game positions are as follows:
##
## 0 | 1 | 2
## -------+---
## 3 | 4 | 5
## ---+---+---
## 6 | 7 | 8
##
## In addition to the games, there is also a game state array which keeps track
## of how the board actually looks. This is a 9 element list consisting of 0s, 1s,
## or 2s, depending on what positions have been used.
##
## On each available move, the current player will play in the lowest available
## position as long as that move has not already been played. After each move, the
## game will be checked for a winner. If there is no winner and there are still
## available moves, the play will continue. Otherwise, the game will be output to
## a file.
##
## After a game is output, the last play will be removed and the search for new
## moves will continue with the next position higher than the one that was removed.
## If there are no plays that meet this constraint, then the next move is removed
## and the process is repeated.
##### Check for win
def checkWin(game, debug):
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
if debug == 1:
print "X wins!"
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
if debug == 1:
print "O wins!"
elif game[0]*game[1]*game[2]*game[3]*game[4]*game[5]*game[6]*game[7]*game[8] > 0:
winner = -1
if debug == 1:
print "Draw!"
else:
if debug == 1:
print "No winner yet."
return winner
##### Display Game State
def dispGame(game):
gameChar = []
for i in range(0,9):
if game[i] == 0:
gameChar.append(" ")
elif game[i] == 1:
gameChar.append("X")
elif game[i] == 2:
gameChar.append("O")
else:
gameChar.append("Something bad happened!")
print
print " {} | {} | {}".format(gameChar[0], gameChar[1], gameChar[2])
print "---+---+---"
print " {} | {} | {}".format(gameChar[3], gameChar[4], gameChar[5])
print "---+---+---"
print " {} | {} | {}".format(gameChar[6], gameChar[7], gameChar[8])
print
##### Main Program
game = [0]*9
move = [-1]*9
numMoves = 0
winner = 0
testMove = 0
turn = 1
removed = -1
debug = 0
while numMoves > -1 or removed > -1:
## Determine whether the last loop was additive or subtractive
## * removed == 0 means additive (or starting)
## * removed > 0 means subtractive
## Establish starting point for the search for the next move
if debug == 1:
print "Starting main loop\n"
print "numMoves = {}".format(numMoves)
print "removed = {}".format(removed)
print "move = {}".format(move)
dispGame(game)
if removed == -1:
## Start checking for valid moves from 0
lowStart = 0
else:
## Start checking for valid moves from 1 more than the move
## that was removed
lowStart = removed + 1
testMove = lowStart
## Whose turn is it?
if numMoves % 2 == 1:
turn = 2
else:
turn = 1
## Start searching for a valid move
while testMove <= 8:
## Is position testMove available?
## If so, move there. If not, increase testMove
if game[testMove] == 0:
game[testMove] = turn
move[numMoves] = testMove
numMoves += 1
removed = -1
testMove = 10
else:
testMove += 1
## If no valid play was found, remove the last move
if testMove == 9:
numMoves -= 1
game[move[numMoves]] = 0
removed = move[numMoves]
move[numMoves] = -1
## Test whether someone has won
## If so, create a new line of output and then remove the last move
winner = checkWin(game, debug)
if winner != 0:
if debug == 1:
dispGame(game)
print "move = {}".format(move)
f = open("TTTGames.txt", "a")
f.write(str(winner))
f.write(" ")
for item in move:
f.write(str(item))
f.write(" ")
f.write("\n")
f.close()
winner = 0
numMoves -= 1
game[move[numMoves]] = 0
removed = move[numMoves]
move[numMoves] = -1
No comments:
Post a Comment