I haven't touched minimax since my Univeristy days so I thought I'd have a little brush up since it might be useful for some work I'm embarking on, so my first point of call like it is with any of these things was Wikipedia and I came accross this diagram
Now what's got me in a bit of a muddle is the idea that the maximizing player (who likes positive numbers) by the rules of the algorithm, would take the right branch when it contains a possible losing state for that player (indicated by the -infinity), where as the left branch contains a possible winning state (+infinity)
I'm very rusty on this stuff, just seems that the right branch isn't a particularly safe choice. Would appreciate any help clearing it up in my mind.
Might be helpful if I post the description of the diagram!
--------------------------------------------------------------------------- Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree on the right, where the squares represent the moves of the player running the algorithm (maximizing player), and circles represent the moves of the opponent (minimizing player). Because of the limitation of computation resources, as explained above, the tree is limited to a look-ahead of 4 moves.
The algorithm evaluates each leaf node using a heuristic evaluation function, obtaining the values shown. The moves where the maximizing player wins are assigned with positive infinity, while the moves that lead to a win of the minimizing player are assigned with negative infinity. At level 3, the algorithm will choose, for each node, the smallest of the child node values, and assign it to that same node (e.g. the node on the left will choose the minimum between "10" and "+∞", therefore assigning the value "10" to himself). The next step, in level 2, consists of choosing for each node the largest of the child node values. Once again, the values are assigned to each parent node. The algorithm continues evaluating the maximum and minimum values of the child nodes alternatively until it reaches the root node, where it chooses the move with the largest value (represented in the figure with a blue arrow). This is the move that the player should make in order to minimize the maximum possible loss. ---------------------------------------------------------------------------
The circle (AI) always picks the highest choice available, while the box (opponent) always picks the lowest choice available.
The AI doesn't pick a branch based on what 'could' happen. It picks based on what _will_ happen if both players play perfectly.
The reason it takes the branch that has a possible -infinity is because it KNOWS that -infinity will never actually happen. If the enemy player made a mistake and allowed the AI to enter that branch of the game, the AI KNOWS that it would have the option of a score of +5, and so would take it.
Here is a walkthrough of the left-most side of the tree:
At depth 3, the enemy has a choice between 10 and +infinity. 10 is a better choice for the enemy. In otherwords, assume the enemy will make the move which would deprive the AI of a score of +infinity.. The other sibling node at 3 only has one choice (5).
At depth 2, the AI can pick between 10 and 5. 10 is better than 5, so it takes it. (edit) In other words, the AI has the option to deprive the enemy of a score of 5.
At depth 1 the enemy can pick between -10 and 10. -10 is worse for the AI, so it takes -10. Therefore, the best possible outcome for the AI on the left branch is -10. This assume the enemy plays perfectly of course.
[Edited by - willh on November 25, 2010 11:43:32 AM]
