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.