Week 7 - Recursion and Assignment 2

This week is probably the most exhausting week for CSC148, not because of lecture nor test, but it's because of the coming due date of assignment 2. When I first started university, I had handed in many late assignments, not because of  I didn't complete the work in time, but it was because of that I completed just in time, and went on a break forgetting about handing the assignment in. Due to these bad incidents I have made a habit of starting assignment earlier than before, so same with this assignment I started right on the night of Friday of this week.

There were so many challenges with the assignment, first I had to read and understand completely the given game view and game state structure, and on top of that I had to follow the formula and make a harder game state with a more intelligent move chooser. The hardest part for me was writing the winner function for Tippy (a function that checks if either player had won the game) and suggest_move function for MiniMax strategy. The winner function for Tippy was hard in the sense that I had to write so many lines to check all the possibilities for each position on the game board and restrict places that were been checked on the board. The suggest_move function for MiniMax strategy was without a doubt the hardest part in this assignment for me, and as the title of this week's blog suggest it is related to recursion, and in fact I had to write two very hard helper function using recursion to make suggest_move work, and as you can imagine all the different bugs I had when writing suggest_move, where I spend most of the time tracing values in the recursion functions.

So... what is recursion? Basically to put into the simplest words recursion is preformed when a function calls it self in the program. Recursion can be useful when writing harder functions (like ones I mentioned in assignment 2). For example, there is a list that contains many list and integer, and those list inside also could potentially contain more lists and integer (nested list with integer), and we want to write a function that adds all the integer in the list up. By writing a function with a for loop looping each variables (whether a list or integer) and calls the itself (the function) with the variables we can simply accomplish this task, no matter how many list is nested inside the first list. 

(sample function by me)

Recursion is super important nowadays, everything function I write this week involves some sort of recursion, like assignment 2 and even what we learned in class and tutorial. This week's lecture we learned to write functions for a new class, BTnode, of course involving recursion. Basically BTnode is a class that similar to list and Tree, where it creates a variable, that can contain up to 2 variables, which can be either a number (int) or BTnode. Since this is similar to list and Tree, there are so many new functions that we learned to write using recursion.

(example of BTnode from week 7 lecture slide)

Thus to conclude my adventure for this week, I found understanding recursion and knows how to write it is very important for writing Python functions (or maybe as well for other programming language). Although it was very tiring this week trying to fix all the bugs in assignment 2 tracing recursions, but I found it very exciting to program those functions, and very rewarding when I found that my programmed AI can beat me most of the times. Especially when AI goes first on Tic Tac Toe (very similar to Tippy I made on spare time), the win rate for AI is really high!

(game of Tic Tac Toe and found it to be more fun than Tippy on 3x3, since 4x4 is impossible to run)

Week 6 - Tree and Writing Recursion

This week's lecture was pretty challenging, we learned class Tree and how to write recursion for Tree. I have some knowledge on how Tree works as I have studied class Tree last week in preparation of the midterm, but it was still challenging to write recursion for Tree. Basically the class Tree works pretty much as a list with list value inside, except the current list or so called 'node' has a value to it. Also it is possible for a node to have no 'children' or no sub-list.

Visual representation of a Tree object. (Writing Recursion Exercise)

The tutorial for this week is very hard, probably the hardest tutorial I have had so far, and this is the first time where I have not able to finish all method example on lab handout. Similar to lecture this week's lab is about writing recursion for class Tree, and it is very tricky. Methods that we were asked to write like return all the value in Tree object where it has at least one children are extremely complicated and requires a lot of thinking. The quiz in the end was also very tricky, where we were asked to write a  function that returns the maximum depth in the Tree object, and I had little confidence on the correctness of my answer.

  

Week 5 - Midterm Review

We have a midterm exam in this week's lecture... although I am writing this blog a week late but I can still recall what happened during that week. I started reviewing past exams few days before the exam, and studied many questions even ones with tree and exceptions. The exam was pretty easy however, with just questions about writing hidden methods, tracing recursion calls and inherit sub-class methods. Surprisingly there is no question about stack in the exam, which I thought its a must have question form observation though past exams.

The tutorial was very interesting, we learned a new class similar to stack which is called queue. The main difference with queue and stack is that when use the method .pop() on stack it delete and returns the object the top of the list while use the method .pop() on queue it delete and returns the first object in the list.