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
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)
No comments:
Post a Comment