The End is Where We Begin

-D04, M04, Y15-

Cheesy title? Cheesy title.
Hello there, glad you could make it. Essentially, the course for computer science related to this blog has come to an end. Will this be the final post? I doubt it. Anywho, let us get started.

Having received marks for the second term test, it is clear that my primary problem is failing to take into consideration all cases--outcome options available--in my functions. Minor problems, such as forgetting the structure of binary trees for a specific case and forgetting to reset the value of a node in a linked list when the function or method is looking at the front are quickly resolved. Dealing with multiple cases will likely be a stronger problem resolved simply through practice.

Concerning the final assignment and the three versions of minimax, I discovered a solution to memoization by ignoring my intuition. My intuition was telling me to add results to the dictionary only at the very end of each tree branch while somehow remembering the internal nodes that brought the recursive function to that outcome. Because that intuition was failing to be effective (I may have said this before, but my memoize 'optimization' was actually running slower than my original minimax strategy), I trusted in the fact that recursion can come up with a result "earlier on"--that is, I could add results to the dictionary while the function was still on an internal node. I do not know if that makes any sense, but it seems to work. As for pruning...I believe I ruined that optimization. I have no intuition as to how it should exactly work. I attempted to have my function remember the best outcome for the original player as well as the best outcome for the enemy player as well as deal with each state of the game differently depending on whether it was the original player's turn or not, but it did not work well. Trying to keep track of the best outcome for each player and compare them properly in a recursive function with many different moves is painful. I hope it becomes more transparent and easy-to-follow as I progress in this field. Then again, a senior engineering friend of mine says recursion never gets any clearer, so there's that.

And as for what we were doing in class these past two weeks: it was--for me--review of Big Oh notation and determining the operating complexity of different functions. If that type of stuff catches your attention, check out my archived posts from mid to late 2014. On top of that: recursion operates on the logarithmic order of complexity. This makes sense, since the height of a full binary tree with n nodes is approximately log(n) with a base of 2. Worst-case scenario: At each level of the tree, the recursive code would enact its function(s) and continue to the next level of the tree until the entire tree is traversed.

Overall, this course was very helpful in introducing the structures of data and the ways in which data can be manipulated. Efficient coding through inheritance of structure and operation from parent classes to be used by subclasses for specific implementations, the power of recursion to deal with convoluted data structures like binary trees, and the use of linked lists to reduce run-time complexity in searching over data are all foundational necessities that both reveals the scope of computer science and offers the opportunity to narrow one's interest down to more specialized fields...like video game design.

Thank you for reading.

Revisitation to Minimax

-D29, M03, Y15-

This week I am required to revisit a previous slog post of mine and explore it in greater detail. I am more than fine with this, for I have succeeded in implementing a working version of the minimax artificial intelligence strategy. As such, I will be revisiting my slog post from the 21st of March, with the exception of deep-copying, since I already went 'in too deep' analyzing copy issues.

After exploring a number of my fellow students' distinctly empty blogs, I stumbled upon a gif and concise interpretation of what it felt like to implement minimax and 'tippy' (an adaptation of tic-tac-toe): behold! Check out Xie's week 9 post. Also partake in the terror posted here under the Impressions of week 7 topic. What do these two 'sloggers' have in common? They both worked in groups and succeeded in creating minimax on time. As I stated on the 21st of March, I failed to do either.

BUT NOW, NOW I CAN RAISE MY FIST IN THE AIR, CHAMPION OF MINIMAX. Not only did I implement the strategy without utilising any form of summation--I instead determined each game move's chances of victory by dividing its outcome by the depth of recursion taken to reach it--but I did it without a group.
However, I must give major props to this man (I posted his slog link in my previous post as well) for opening my eyes to the fact that I could not depend upon the outcome method implemented within the games themselves. Why not depend on the outcome of a game to determine a score? Quite simply because the outcome takes a specific game-state as an argument, therefore, regardless of who the next player at this specific game-state is, the result will always be a loss. As such, upon reaching this end of the game--this leaf node in a branch of many game-states--it is necessary to compare the outcome's losing player to the player from the original--the root--game-state.

Now, even with this success in mind, yet another challenge has arisen: optimization of the dreaded minimax strategy. For the final assignment for this class, we were given the option to explore and optimise minimax (which I naturally chose in my stubborn refusal to be bested by a program that other people managed to implement), or some other clearly less exciting option which I skimmed over. But how can one optimise a program that always chooses the best choice in any two-player game?
1) Memoization: Basically, if you have seen the game-state before, then don't bother recalculating the outcome; just grab the number obtained in the previous calculation. Us human beings can easily recognize when we are wasting time: do you, at this point in time, really need to calculate 5/2 via long division each and every time you see it? Surely not! Your brain has created something like a dictionary for such menial tasks, e.g., {'5/2': 2.5}.
2) Pruning: The more one looks at the game-states as a tree, the better. To prune a tree, one cuts off unnecessary branches and leaves. Similarly, if you have 50 moves to choose from, each leading to who knows how many more choices, it would be great to cut short all computations that lead to something worse than the choices already discovered before it.
3) Myopia: Or maybe, we are just lazy, so rather than spend time computing all these things, we should just stop after going n levels deep into the game-state tree. If we find an outcome by that nth level, we'll take note of it; but if we don't, we'll have some other method determine a rough outcome for that state of the game without looking any deeper.

Noticeably, the last optimisation is the least accurate of the two, which also makes it the easiest to implement (I speak from experience). Moreover, Memoization is more difficult to implement, and my current version is not adding enough branches and outcomes to the dictionary as it should be. Finally, Pruning stands squarely as my greatest adversary of the three. All detailed explanations of pruning I have heard from professors and the World Wide Web have not been of great help. I can see how it would work if the optimisation finds a really strong move early on, allowing it to just toss the remaining x number of options in the trash for this gem of a move; however, I can't escape the intuition that one must at least glance at the other outcomes to make sure that one has indeed caught hold of the best choice. Hopefully, the majority of this intuition is correct, and that the correct implementation(s) of pruning in minimax do not require significant alterations to the structure of my minimax algorithm.

In sum, minimax is still a dreadful monster of a program; nevertheless, it is not impossible, and it has been a powerful teacher of the utility of recursion. Even if my grade does not reflect what I have come to understand, I at least will know that I have learned quite a bit.

Thank you for reading.

BREAKING: Fearful Strategy and Mutation Threat

-D22, M03, Y15-

Good evening, morning, or afternoon. So. Two or so weeks ago, I had an assignment to do that involved created a game similar to tic-tac-toe and an insane strategy dubbed 'minimax.' To those who have experience in the field of recursion, you may have heard of it by the similar name, 'minmax.' Unfortunately, I have still not been able to successfully create a working version of the recursive strategy--my version is only capable of returning the correct move a small percentage of the time.
Now I do think that I have written on this topic beforehand, but as a refresher: minimax recursively plays a game, determines each option's outcome, and then chooses to play the real game with the strongest move it came across during the function/method's "thinking" period. It is truly a terrifying construct and many of us humans often forget that this type of strategy is something we do on a daily basis: you know it as thinking ahead/planning. Now, typical human beings think ahead and, at the same time, cut out 'branches' of ideas/plans whose outcomes are not of interest.

Fearfully, minimax. Does. Not.

Minimax looks at every. Single. Move. All of them. Make no mistake, because if the computer can ensure victory...it will. No matter how slow it must be. Recently in class however, the professor revealed what seemed to be a working minimax function. I eagerly copied it down to test out, since mine (at the time) was essentially a tidy pile of "this is hardly passable."

To my chagrin, the function did not work. I am not certain if the professor did this intentionally, or whether my implementation of suggesting the move the minimax function returned was insufficient. Regardless, I attempted to fix it, and even spoke with other students (check them out here, and here) about it. In the end, we concluded that the only way to successfully implement minimax was to recursively sum up the outcomes of each branch and then choose from the resulting list the branch which had the highest score (greatest likelihood) to produce a win.

I can faintly here criticism of this implementation, so feel free to criticize it, especially since I am interested on exploring this terror of a function to a greater degree. [And I cannot stand the fact that I have failed to properly produce a working version of the bloody thing].

In addition, emphasis was placed upon the idea of "deep-copying." All of you should be familiar with the ability to copy something--from text to youtube links to legitimately free music. However, when it comes to mutable (capable of being mutated when copied) objects such as lists--which is how I implemented my version of tic-tac-toe--it is absolutely necessary to 'deep-copy' the list in order to avoid mutating all versions of the list. Still confused as to why this is dangerous? Well, consider the above strategy minimax, which secretly plays out all the games possible given the current state of the game you are in. If it were to choose a certain move, it is very well possible that it will choose according to the branch of the game it planned out by itself...a branch with its own hidden game 'played' in the background. As such, when the computer chooses its move, it can mutate your current game to match it's own hidden game.

Truly terrifying. I am speaking from experience. I chose ONE. MOVE. And when the computer planned ahead and chose its own move, the ENTIRE game was corrupted into what it had had in mind [Yes, that is grammatically correct].

Thus, it becomes of the utmost importance to copy lists without allowing it to alias (have the same computer identity) as the previous list before it. So given a list L1 = [[1,2,3], [4,5], [6,7]], it is best to implement code such as this: L2 = [[item for item in r] for r in L1].
Why item for item in r? Because if you were to simply code [r for r in L1], you would effectively alias the inner lists within L1. This can be terrifying, especially if you are coding a regular game of tic-tac-toe, and by choosing the middle point of a 3-by-3 board, you can magically win the game:

e.g.,

[0, 0, 0]

[0, 0, 0]

[0, 0, 0]

--You chose row 1, column 1--

NEW GAME STATE

[0, X, 0]

[0, X, 0]

[0, X, 0]

--Wow! You Win!--

Truly terrifying x2. Thank you for reading! And remember: Say NO to aliasing! (unless otherwise advised)

Revisiting Binary Trees

-D16, M03, Y15-

Howdy Hello and welcome back to the most fascinating blog out there! ehe...

So anyways, last week was less education-oriented due to a midterm test combined with the ongoing strike. Essentially, we revisited Binary Trees--particularly methods of insertion and deletion. These two methods require noticeably more work simply due to the need to recognize and deal with each possible case (e.g., if the node exists, if the data at that particular node is greater than or less than the data in question, if the node is a leaf, leads to only one other node, or is an internal node, and the like). Now some may ask, why bother with a multitude of cases when you can just go through all the nodes in a Binary Tree and grab the ones you want?
The answer is simple: going through all nodes in a Binary Tree is only feasible for a small amount of nodes. When confronted with a data structure consisting of millions of pieces of data, and that data is already nicely sorted (or can be sorted with ease), it is noticeably quicker and less work-intensive to search through only a few nodes to find the data-piece you want.

Now, concerning the idea of deletion. I may have touched on this before when I spoke about Linked Lists last week, so bear with me. When something is 'deleted' from a Binary Tree, this is equivalent to having cut the ties to that particular node of data and refastening the rest of the Binary Tree together. The 'deleted' node still exists--floating out there in the sea of binary--but it is simply no longer welcome in the BT club reachable via the Binary Tree. These outcasts floating nodes of data could potentially be a problem, taking up precious computer memory without contributing to the Cause to anything. However, Python--like any proper program--is capable of taking out the trash disposing of excess pieces of information without the user having to implement a function to delete the floating node from memory directly.

I have a feeling this indirect technique of deletion will become a key feature of other data structures in the future of my education. Thanks for reading!

[List]---[List] (It's a Linked list ok)

-D08, M03, Y15-

Hello and welcome back to another slog post brought to you by our sponsors:
Just kidding, I have no sponsors. In fact, at the moment, a substantial portion of all higher learning staff members--primarily teaching assistants--are on strike, so everything is 'up-in-the-air' (uncertain). Hopefully, the universities involved will be able meet the union's grievances without causing further suffering for us victims students.

Anywho! An assignment we had last week was quite challenging--particularly in the case of creating an artificial intelligence that employs recursion to determine the best outcome. I had hoped to work together with a friend on the assignment; but alas, all my friends had already paired off, and I wasn't going to throw my chips in with someone I didn't know or someone who did not aim to work just as hard as I would. *shrugs*

Aside from that, we went over a new data structure: Linked Lists. Values that 'point' to other similar values in such a way that each value only points to one other value--think of a regular Python list (or not, here's an example: [1, 2, 3]) except with arrows replacing the commas and an additional arrow at the end pointing towards 'the end itself' (e.g., [1] => [2] => [3] => [X]). Because this type of chain-listing does not exist by itself, a 'Linked List Wrapper' is used to keep track of this data structure (the first value is referred to as the 'front,' the last value as the 'back,' and the like). Overall, I do not see this as too terrifying an idea. As with all things, there are likely to be difficult pieces to this puzzle; nevertheless, lists are not particularly as intimidating as recursion.

Thank you for reading.

A Special Announcement... and Trees

-D01, M03, Y15-

Hello and welcome back! Due to the absence of classes the week before last, there was nothing to report. And now, for a specialized announcement:

----------------------------------------------------------------------------------------------------

Dear TA,
    I choose my summary of object-oriented programming for assessment. It may not be technical;        however, I was of the opinion that the concepts were of greater importance.

----------------------------------------------------------------------------------------------------

And now, back to our regular program:

So this previous week we came upon recursion in what have been termed 'binary trees.' Rather than create trees of code where the root and its internal nodes have any number of child nodes, these binary trees always have no more than two children per internal node or root. For those who are having trouble visualising such a thing, consider factor trees from your childhood:

The difference between binary trees and factor trees include:
+Binary Trees ["BT's"] contain unique data (no repeats of data)
+BT's do not require factoring--only the structure is the same.

In addition, we learned how to utilize binary search methods (recursively of course) on these binary trees. These search methods, which are dependent upon the organization of the BT data structures (for example, a BT could be organized such that all numbers to the left of each internal node--and the root node--are less than the node in question, and the numbers to the right are larger than that node) allow for data to be searched for supremely faster than if the computer was forced to check every piece of data within the BT. Binary search methods are equivalent to the logarithm function, and I must say, I definitely prefer searching through the log(10-kajillion) than searching through 10-kajillion pieces of data.
Just my personal preference. No pressure.
Just kidding, this shouldn't even be up for debate. 10-kajillion searches when data is already organized in a clearly helpful manner is madness.
Thanks for reading!

Class-Action Python-suit

-D15, M02, Y15-

"You are not the Father."
If you have heard that line before, you have either been on the internet far too long, or you have watched that particular show. For those of you who are familiar with object-oriented programming, the negation of that statement should ring a few bells. Or alarms. Or whatever it is your class does.

For those who aren't familiar with object-oriented programming:
Think of a thing that has a function. Think of a washing machine, a cash register, an ATM, a racehorse. Now, strip away its physical manifestation, leaving only what it does in its stead. A cash register can take in money, money can be taken out of it, money can be exchanged, it's possible to check how much money is in a register.
Now, transform those things into binary, all contained within one grouping of code.

That, is a class. 

Amazing, is it not? 

Rather than toss a load of functions into some file, you can group them together in a class. Although they work like functions, they are referred to as methods when this occurs. If a function requires the use of a class/a classes various arguments of inputs/outputs, then consider transplanting it into the class. This form of structuring code is useful in keeping similar code together and working, allowing for a process dubbed 'inheritance.'
Inheritance allows a class to bestow its methods for use in other, more specialized classes. This way, if you must alter your code in some fundamental aspect, you will not need to go through each class of code that requires the power of the 'father/mother-class.' Unless what you changed was specifically utilized by the child-classes of course. Moreover, because the child-classes have all the attributes of the parent-class, and then some, it is no longer necessary to directly access the parent-class's methods.
Thus, you turn objects--fiction or non-fiction--into lines of code.
For a less concept-focused perspective, the Python Foundation has an extensive explanation on the nuts and bolts of __init__, class(), __repr__, instance variables, and the like.
Thank you for reading.

Post Scriptum:
Zvikaramba, if you're reading this, THANKS FOR THE FEEDBACK. And the name's Jameson.
John.
Jonah.
Jameson.