1. Trees
Tree is a recursive structure.
1.1 math nodes
https://class.coursera.org/principlescomputing-001/wiki/view?
page=trees
1.2 CODE无parent域的树
http://www.codeskulptor.org/#poc_tree.py
class Tree: """ Recursive definition for trees plus various tree methods """ def __init__(self, value, children): """ Create a tree whose root has specific value (a string) Children is a list of references to the roots of the subtrees. """ self._value = value self._children = children def __str__(self): """ Generate a string representation of the tree Use an pre-order traversal of the tree """ ans = "[" ans += str(self._value) for child in self._children: ans += ", " ans += str(child) return ans + "]" def get_value(self): """ Getter for node's value """ return self._value def children(self): """ Generator to return children """ for child in self._children: yield child def num_nodes(self): """ Compute number of nodes in the tree """ ans = 1 for child in self._children: ans += child.num_nodes() return ans def num_leaves(self): """ Count number of leaves in tree """ if len(self._children) == 0: return 1 ans = 0 for child in self._children: ans += child.num_leaves() return ans def height(self): """ Compute height of a tree rooted by self """ height = 0 for child in self._children: height = max(height, child.height() + 1) return height def run_examples(): """ Create some trees and apply various methods to these trees """ tree_a = Tree("a", []) tree_b = Tree("b", []) print "Tree consisting of single leaf node labelled 'a'", tree_a print "Tree consisting of single leaf node labelled 'b'", tree_b tree_cab = Tree("c", [tree_a, tree_b]) print "Tree consisting of three node", tree_cab tree_dcabe = Tree("d", [tree_cab, Tree("e", [])]) print "Tree consisting of five nodes", tree_dcabe print my_tree = Tree("a", [Tree("b", [Tree("c", []), Tree("d", [])]), Tree("e", [Tree("f", [Tree("g", [])]), Tree("h", []), Tree("i", [])])]) print "Tree with nine nodes", my_tree print "The tree has", my_tree.num_nodes(), "nodes,", print my_tree.num_leaves(), "leaves and height", print my_tree.height() #import poc_draw_tree #poc_draw_tree.TreeDisplay(my_tree) #run_examples()
1.3 CODE有parent域的树
http://www.codeskulptor.org/#user36_3SjNfYqJMV_4.py
import poc_treeclass NavTree(poc_tree.Tree): """ Recursive definition for navigable trees plus extra tree methods """ def __init__(self, value, children, parent = None): """ Create a tree whose root has specific value (a string) children is a list of references to the roots of the children. parent (if specified) is a reference to the tree's parent node """ poc_tree.Tree.__init__(self, value, children) self._parent = parent for child in self._children: child._parent = self def set_parent(self, parent): """ Update parent field """ self._parent = parent def get_root(self): """ Return the root of the tree """ if self._parent == None: return self; else: return self._parent.get_root(); def depth(self): """ Return the depth of the self with respect to the root of the tree """ pass def run_examples(): """ Create some trees and apply various methods to these trees """ tree_a = NavTree("a", []) tree_b = NavTree("b", []) tree_cab = NavTree("c", [tree_a, tree_b]) tree_e = NavTree("e", []) tree_dcabe = NavTree("d", [tree_cab, tree_e]) print "This is the main tree -", tree_dcabe print "This is tree that contains b -", tree_b.get_root() import poc_draw_tree poc_draw_tree.TreeDisplay(tree_dcabe) print "The node b has depth", tree_b.depth() print "The node e has depth", tree_e.depth() run_examples()# Expect output#This is the main tree - [d, [c, [a], [b]], [e]]]#This is tree that contains b - [d, [c, [a], [b]], [e]]#The node b has depth 2#The node e has depth 1 1.4 CODE arithmetic expreesion由树来表达
Interior nodes in the tree are always arithmetic operators. The leaves of the tree are always numbers.
http://www.codeskulptor.org/#poc_arith_expression.py
# import Tree class definitionimport poc_tree# Use dictionary of lambdas to abstract function definitionsOPERATORS = {"+" : (lambda x, y : x + y), "-" : (lambda x, y : x - y), "*" : (lambda x, y : x * y), "/" : (lambda x, y : x / y), "//" : (lambda x, y : x // y), "%" : (lambda x, y : x % y)}class ArithmeticExpression(poc_tree.Tree): """ Basic operations on arithmetic expressions """ def __init__(self, value, children, parent = None): """ Create an arithmetic expression as a tree """ poc_tree.Tree.__init__(self, value, children) def __str__(self): """ Generate a string representation for an arithmetic expression """ if len(self._children) == 0: return str(self._value) ans = "(" ans += str(self._children[0]) ans += str(self._value) ans += str(self._children[1]) ans += ")" return ans def evaluate(self): """ Evaluate the arithmetic expression """ if len(self._children) == 0: if "." in self._value: return float(self._value) else: return int(self._value) else: function = OPERATORS[self._value] left_value = self._children[0].evaluate() right_value = self._children[1].evaluate() return function(left_value, right_value) def run_example(): """ Create and evaluate some examples of arithmetic expressions """ one = ArithmeticExpression("1", []) two = ArithmeticExpression("2", []) three = ArithmeticExpression("3", []) print one print one.evaluate() one_plus_two = ArithmeticExpression("+", [one, two]) print one_plus_two print one_plus_two.evaluate() one_plus_two_times_three = ArithmeticExpression("*", [one_plus_two, three]) print one_plus_two_times_three import poc_draw_tree poc_draw_tree.TreeDisplay(one_plus_two_times_three) print one_plus_two_times_three.evaluate() run_example() 2 List In Python, lists are primarily iterative data structures that are processed using loops. However, in other languages such as Lisp and Scheme, lists are treated primarily as recursive data structures and processed recursively. 2.1 a list example
class NodeList: """ Basic class definition for non-empty lists using recursion """ def __init__(self, val): """ Create a list with one node """ self._value = val self._next = None def append(self, val): """ Append a node to an existing list of nodes """# print "---------called---append()--------\n" if self._next == None:# print "A:"+str(isinstance(val,int))+"\n";# print "B:"+str(isinstance(val,type(self)))+"\n"; new_node = NodeList(val) self._next = new_node else: self._next.append(val) def __str__(self): """ Build standard string representation for list """ if self._next == None: return "[" + str(self._value) + "]" else: rest_str = str(self._next) rest_str = rest_str[1 :] return "[" + str(self._value) + ", " + rest_str def run_example(): """ Create some examples """ node_list = NodeList(2) print node_list sub_list = NodeList(5)# print "--------" sub_list.append(6)# print "--------" sub_list2 = sub_list node_list.append(sub_list) node_list.append(sub_list2) print node_list run_example()3 Minimax
https://class.coursera.org/principlescomputing-001/wiki/minimaxX and O alternate back and forth between min and max.In X’s term, try to maximize the score.the O’s term, try to minimize the score.
4 Mini Project Tic Tac Toe with Minimax
"""Mini-max Tic-Tac-Toe Player"""import poc_ttt_guiimport poc_ttt_provided as provided# Set timeout, as mini-max can take a long timeimport codeskulptorcodeskulptor.set_timeout(60)# SCORING VALUES - DO NOT MODIFYSCORES = {provided.PLAYERX: 1, provided.DRAW: 0, provided.PLAYERO: -1}def minimax(board, player): """ Make a move through minimax method. """ check_res = board.check_win() if check_res != None: return SCORES[check_res] , (-1,-1) else: empty_list = board.get_empty_squares() com_score = -2 max_score = -2 max_each = (-1,-1) changed_player = provided.switch_player(player) for each in empty_list: cur_board = board.clone() cur_board.move(each[0], each[1], player) cur_score_tuple = minimax(cur_board, changed_player) cur_score = cur_score_tuple[0] if cur_score * SCORES[player] > com_score: com_score = cur_score * SCORES[player] # used for compare max_score = cur_score # used for return a value max_each = each if com_score == 1: return max_score, max_each return max_score, max_each def mm_move(board, player): """ Make a move on the board. Returns a tuple with two elements. The first element is the score of the given board and the second element is the desired move as a tuple, (row, col). """# print "-----------------new_move--------------"# print "B1:"+" player="+str(player)+"\n" # print board# print "----------------" score_and_board = minimax(board, player)# print "C1"# print score_and_board# print "-----------------new_move--------------" return score_and_boarddef move_wrapper(board, player, trials): """ Wrapper to allow the use of the same infrastructure that was used for Monte Carlo Tic-Tac-Toe. """ move = mm_move(board, player) assert move[1] != (-1, -1), "returned illegal move (-1, -1)" return move[1]# Test game with the console or the GUI.# Uncomment whichever you prefer.# Both should be commented out when you submit for# testing to save time.#test1#mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.EMPTY, provided.EMPTY], [provided.PLAYERO, provided.PLAYERO, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERX, provided.EMPTY]]), provided.PLAYERX) #mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.PLAYERO, provided.EMPTY], [provided.PLAYERO, provided.PLAYERO, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERX, provided.PLAYERX]]), provided.PLAYERX) #mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.EMPTY, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERO, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERX, provided.EMPTY]]), provided.PLAYERO) #mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.EMPTY, provided.EMPTY], [provided.PLAYERO, provided.PLAYERO, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERX, provided.PLAYERX]]), provided.PLAYERO) #mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.EMPTY, provided.EMPTY], [provided.PLAYERO, provided.PLAYERO, provided.PLAYERX], [provided.PLAYERO, provided.PLAYERX, provided.EMPTY]]), provided.PLAYERX) #mm_move(provided.TTTBoard(3, False, [[provided.PLAYERX, provided.EMPTY, provided.EMPTY], [provided.PLAYERO, provided.PLAYERO, provided.EMPTY], [provided.EMPTY, provided.PLAYERX, provided.EMPTY]]), provided.PLAYERX) #mm_move(provided.TTTBoard(2, False, [[provided.EMPTY, provided.EMPTY], [provided.EMPTY, provided.EMPTY]]), provided.PLAYERX)#test1#provided.play_game(move_wrapper, 1, False) #poc_ttt_gui.run_gui(3, provided.PLAYERO, move_wrapper, 1, False) 注意上面的minimax()方法进行了一些简化处理: In Minimax, you need to alternate between maximizing and minimizing. Given the SCORES that we have provided you with, player X is always the maximizing player and play O is always the minimizing player. You can use an if-else statement to decide when to maximize and when to minimize. But, you can also be more clever by noticing that if you multiply the score by SCORES[player] then you can always maximize
假设要用if else的写法。是这种:
check_res = board.check_win() if check_res != None: return SCORES[check_res] , (-1,-1) else: empty_list = board.get_empty_squares() if player == provided.PLAYERX: max_score = -2; max_each = (-1,-1) changed_player = provided.switch_player(player) for each in empty_list: cur_board= board.clone() cur_board.move(each[0], each[1], player) cur_score_tuple = minimax(cur_board, changed_player) cur_score = cur_score_tuple[0] if cur_score > max_score: max_score = cur_score max_each = each if max_score == SCORES[provided.PLAYERX]: return max_score, max_each return max_score, max_each elif player == provided.PLAYERO: min_score = 2; min_each = (-1,-1) changed_player = provided.switch_player(player) for each in empty_list: cur_board= board.clone() cur_board.move(each[0], each[1], player) cur_score_tuple = minimax(cur_board, changed_player) cur_score = cur_score_tuple[0] if cur_score < min_score: min_score = cur_score min_each = each if min_score == SCORES[provided.PLAYERO]: return min_score, min_each return min_score, min_each