Week 8 – Why I hate my professor’s minimax.

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
StrategyMinimax.suggest_move.

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.

and here:

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 problem

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.

Advertisements
Standard

One thought on “Week 8 – Why I hate my professor’s minimax.

  1. Somebody had to say it, the implementation we worked with was terrible. It inhibited us from learning how minimax truly works, and thus made completely irrelevant any explanation outside of class about pruning. You see, we weren’t really pruning on a minimax algorithm, we were pruning on a maxmax algorithm that made no sense. Great article, and good suggestions. Also, I learned a lot from this explanation.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s