Now that the Assignment 2 deadline has just passed, I have the liberty to speak my mind on it.
I HATED IT.
I believe the assignment overall was subpar – the documentation and code handouts were overly convoluted and badly worded. This is obvious from Danny’s latest announcement and reaction from fellow SLOGGERS:
I’ve seen a number of good students stuck on implementing
My fellow SLOGGER’s account on developing Minimax here:
Coming back from reading week!
This week was Assignment 2.It was a NIGHTMARE!
I still didn’t know what [sic] they’re talking about. I had no idea what to write until I read lots of articles about recursion and class.
I struggled with minimax where I eventually failed to fix the syntax error that occurred every time I ran the function. I’m sure some of my peers also struggled with the same problem, and I hope they found a solution to correctly implement it.
The bad documentation not only decreased the overall performance on assignment 2 but also provided a poor understanding of Minimax, diminishing the beauty of the algorithm. In this post, I aim supplement and provide a better understanding of how minimax works.
The minimax algorithm for assignment 2 is a sub-optimal implementation.
The word Minimax is a portmanteau of the words minimum and maximum. This is a reference to the internal working of minimax – when correctly implemented, minimax obtains the best move for the current player by looking ahead and considering the opposition’s moves in advance, similar to a chess player.
If one move your repertoire would lead to a foreseeable checkmate from the opposition’s queen, then you will disregard this move. If a different move would lead to a greater chance of victory, you would choose that move.
Similar from your opponent’s perspective:
If one move from you (the opponent) would lead to my queen checkmating and winning the game, I want the opponent to take that move. If a different move would lead to a larger chance of me losing, I want to avoid that move.
A clear concept is drawn from the situation above – you are trying to maximise your winning potential whilst the opponent is trying to minimise your winning potential. Hence Minimax.
An implementation of this minimax is demonstrated by MIT instructor Patrick Winston below:
The issue with assignment 2 is that it does not follow this paradigm.
- Determine your opponent’s score in the new position (after all, your opponent is the next player in the new position). Multiply that score by -1 to determine your score in that position.
By requiring all students to keep the score for a game_state in term of the next player’s perspective (this is done by multiplying all values by -1 at every level of recursion). Danny is effectively swaying away from the proper implementation and well-known implementation of minimax. This implementation of minimax is inefficient as it requires a programmer to keep track of the next player for every game state in mind, making the algorithm hard to debug and hard to intuitively understand. Furthermore, all hell will be raised when we shall try to optimise this implementation for alpha-beta pruning.
I hope Danny hears me out.