Tic Tac Toe with recursion (Python) -

i can't figure out how tie these functions hard ai, in can never lose. i'm supposed using recursion in form or fasion , these function names , contracts pre-written, filled in actual definition. googling later, can't find relates. ideas fellas?

"""   state s2 *successor* of state s1 if s2 can the next state after s1 in legal game of tic tac toe.  safe: state -> bool successor: state x state -> bool  1. if s over, s safe if 'x' not have 3 in row in s. 2. if o's move in s, s safe iff @ least 1 successor of s safe. 3. if x's move in s, s safe iff successors of s safe.  *statelist* list of states.  """   # safe: state-> bool # # state s *safe* if player 'o' can force win or tie s.  def safe(s):     if over(s): return not threeinrow('x',s)     if turn(s)=='o': return somesafesuccessor(s)     if turn(s)=='x': return allsafesuccessors(s)  def threeinrow(p,s):     if p == 'x':         if all(t in s[0] t in (1,2,3)):             return true         elif all(t in s[0] t in (4,5,6)):             return true         elif all(t in s[0] t in (7,8,9)):             return true         elif all(t in s[0] t in (1,4,7)):             return true         elif all(t in s[0] t in (2,5,8)):             return true         elif all(t in s[0] t in (3,6,9)):             return true         elif all(t in s[0] t in (1,5,9)):             return true         elif all(t in s[0] t in (3,5,7)):             return true     else:         if all(t in s[1] t in (1,2,3)):             return true         elif all(t in s[1] t in (4,5,6)):             return true         elif all(t in s[1] t in (7,8,9)):             return true         elif all(t in s[1] t in (1,4,7)):             return true         elif all(t in s[1] t in (2,5,8)):             return true         elif all(t in s[1] t in (3,6,9)):             return true         elif all(t in s[1] t in (1,5,9)):             return true         elif all(t in s[1] t in (3,5,7)):             return true  # somesafesuccessor: state -> bool # # if s state, somesafesuccessor(s) means s has # @ least 1 safe successor.  def somesafesuccessor(s):     flag = false     # flag means have found safe successor     x in successors(s):         if safe(x): flag = true     return flag  # allsafesuccessors: state -> bool # # if s state, allsafesuccessors(s) means every # successor of s safe. def allsafesuccessors(s):   flag = true   x in successors(s):     if not safe(x): flag = false   return flag       # successors: state -> statelist # # successors(s) list members of successors of s. def successors(s):   statelist=[]   in range(1,10):     if empty(i,s):       statelist.extend(s[0],s[1]+[i])   return statelist 

followup on comment.

the trees visualized when describing minimax (/alpha-beta pruning) algorithm not 'real tree' in sense construct entire tree in memory. conceptual tree, result of testing every move depth first, taking note of scores @ each leaf (alpha, beta, etc) , propagating them up.

note words, depth-first. means recursive minimax-implementing function starts calling first move can make. starts calling first move can make. , on until reach maximum depth or terminal move, return. can see logic never have more boards in memory or external storage other single chain of moves being considered right (and, @ each level, you'll iterating through list of possible moves make - there's memory of how far through are, etc).

tl;dr doing depth-first minimax recursion, won't make new functions except single recursive function.