Week 9: Binary Trees, Binary Search Trees and Minimax

Whew, a delayed post from a whirlwind of a week. Unfortunately, I couldn't attend any of the CSC148 lecture offerings last week due to test and assignment conflicts, which meant that I had to spend this weekend and most of yesterday teaching and reviewing the material that I missed. With that, a little on last week's material: Binary Trees, a variant Binary Search Trees and the dreaded minimax algorithm.

So first off, binary trees, or BT for short, are a method of data/object manipulation that mimic a branching tree diagram in real life, except with the binary restriction, or a maximum of two branches per node. Using the diagram below (sourced from http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/tree1.bmp), the parent node is at the top 8, and each branch has a maximum of two children (or sub-branches, if you will).

The method can be used to store information according to user-provided restrictions per branch, and is essentially an extension of recursive programming. Examining the sample code snippet below:

class Tree:
’’’ Represent a Bare-bones Tree ADT’’’

def __init__(self, value=None, children=None):
    ’’’ (Tree, object, list) -> NoneType
    Create Tree(self) with root node value
    and 0 or more children.
    ’’’
    self.value = value
    self.children = children.copy() if children else [] 

The bare-bones tree abstract data type is instantiated recursively with children, in which the children become the "parent" and thus allows for new children, which then becomes the new parent for more children and etc etc. (Except with a binary tree, the init variables are limited to self.left and self.right for its corresponding left and right children). Using this class, it's possible to implement many manipulative methods, such as getting the height (the number of nodes from the parent to the last leaf, or children-less node), getting the arity (maximum number of branches), or counting the number of leaf nodes.

Now, binary search trees, or BSTs for short, are a subset of binary trees (which in themselves are a subset of trees), except with an imposed limitation of increasing node value from left to right. All values that are less than that of the parent node are added to the left branch, and similarly, all values that are greater than that of the parent are appended to the right branch. Using the following image (sourced from programminggeeks.com), let's traverse the tree.

Suppose the values were appended in this order: 8, 10, 3, 1, 14, 6, 7, 4, 13.

The value 8 is situated as the parent node, that much is apparent. Next, the value 10 is compared to 8. It is larger, and thus placed on the right branch. Next, 3 is smaller than 8 and is placed on the left branch; the branches for the binary tree node 8 are now complete, which means that further values to be placed onto the tree are compared with its children 3 and 10. 1 is smaller than 3, and now becomes the left child of 3. 14 is larger than 10, so it becomes the right child. Similarly, 6, 7, and 4 are sorted into their own tree, and the tree ends at value 13 becoming the final left leaf of the node 14. The BST is now complete in that all values can be scanned from left to right in accordance to its literal value from smallest to largest. To me, its implementation is very similar to that of the standard binary tree, barring a condition that would examine each value before being appended to the tree.

Finally, onto the topic of minimax and assignment 2. Assignment 2's main objective was to utilize a system to "plug in" our own methods to a pre-written set of methods provided by the professors. The game that we had to implement was Tippy, or tic-tac-toe with Tetris' Z/S tetrominos. This game was created purposely such that the first player to move was guaranteed a win no matter the actions of the other player: an ideal situation to implement minimax, an unbeatable computer.

After creating my Tippy state and functions, I looked to minimax. It was an algorithm that rated each move on a basis of -1.0 for detrimental, 0.0 for neutral or non-game-ending, and 1.0 for a winning move. By playing out every single possible combination of the board and looking for the best score for itself, the computer would then play accordingly. What stumped me for the longest time was integrating the scores into choosing a move. I had solidly implemented a fashion of rating the moves with their appropriate score, but struggled with deciding which move to play based on the said score - my AI stubbornly randomly chose a move despite there being an obvious winning move.

I consulted Prof. Heap for help, and the solution seemed much more simple than I had thought: I simply wasn't telling the computer that the highest score was the best move (that, and my recursion was a bit wonky). Ironing these little kinks out, my AI worked: it could now crush me every single time, just like all my math exams.