''' Layout positions:
0 1 2
3 4 5
6 7 8
'''
# layouts look like "_x_ox__o_"
import time
Wins = ((0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6))
# Transformations
Rot90 = (6,3,0,7,4,1,8,5,2)
Rot180 = (8,7,6,5,4,3,2,1,0)
Rot270 = (2,5,8,1,4,7,0,3,6)
VertFlip= (2,1,0,5,4,3,8,7,6)
Transformations = ((Rot90,),(Rot180,),(Rot270,),(VertFlip,),(Rot90,VertFlip),(Rot180,VertFlip),(Rot270,VertFlip))
XWins = 0
OWins = 1
Draws = 2
NumBoards = 3
NumIrrBoards = 4
Stats = [0,0,0,0,0]
Boards = set()
IrrBoards = set()
# Given a current board, look at the entire game tree (the future from this board state) counting unique
# wins and unique boards and unique irreducible board families along the way.
# Therefore CalcStats('_x_ox__o_') will look at all possibilities after this particular 4-move state,
# and CalcStats('_________') will tell us the full results for the original question.
def CalcStats(sboard):
lboard = list(sboard) # list version
tboard = tuple(lboard) # tuple version
# Add to Boards if not found there
if tboard not in Boards:
Boards.add(tboard)
# Check Irreducible version
CheckIrr(lboard)
# end of game?
result = IsWin(sboard)
if result == 'x':
Stats[XWins] += 1
return
if result == 'o':
Stats[OWins] += 1
return
if result == 'd':
Stats[Draws] += 1
return
# Not end of game: go to next possible moves
next_move = 'x'
if sboard.count('x') != sboard.count('o'): next_move = 'o'
for i in range(9):
if lboard[i] == '_':
new_board = lboard[:]
new_board[i] = next_move
CalcStats(''.join(new_board))
# Try all transformations on this board, and if none of them are in the IrrBoards set, then add it.
def CheckIrr(lboard):
for trans_family in Transformations:
lboard2 = lboard[:]
for trans in trans_family:
tr_board = [-1]*9
for i in range(9):
tr_board[i] = lboard2[trans[i]]
lboard2 = tr_board[:]
if tuple(lboard2) in IrrBoards:
return
IrrBoards.add(tuple(lboard))
def IsWin(sboard):
for awin in Wins:
if sboard[awin[0]] != '_' and sboard[awin[0]] == sboard[awin[1]] and sboard[awin[1]] == sboard[awin[2]]:
return sboard[awin[0]]
if sboard.count('_') == 0:
return 'd'
return None
def main(sboard):
global Stats, Boards, IrrBoards
Stats = [0]*5
Boards = set()
IrrBoards = set()
CalcStats(sboard)
print('XWins',Stats[XWins])
print('OWins',Stats[OWins])
print('Draws',Stats[Draws])
print('Num games',Stats[XWins]+Stats[OWins]+Stats[Draws])
print('Num boards',len(Boards))
print('Num irreducible boards',len(IrrBoards))