CODEWITHSUNDEEP
artificial-intelligenceminmax
DetroitRedCoder
DetroitRedCoder

Reputation: 53

Min-Max Search tree representation

I was wondering if anyone could help me go through this question. I looked up the Min Max theory, but I still don't know how to apply this concept to this question below.

The following tree represents possible moves in a competitive game, showing that player X currently has a choice between move A and move B. Following the move of player X, player Y is allowed to select a move, and then player X is allowed to select the last move of the game. The leaf nodes of the tree are labeled W, L, or T, depending on whether that ending represents a win, loss, or tie for player X.

Use the min-max search to determine if player X should move A or B to obtain the best result X can expect.

enter image description here

To review min-max search, see http://www.nada.kth.se/kurser/kth/2D1350/progp02/lecture2.pdf

Player X should move A.

Player X should move B.

Upvotes: 1

Views: 446

Answers (1)

Millie Smith
Millie Smith

Reputation: 4604

I added numbers for the nodes, and highlighted the "max" rows. The non-highlighted rows are "min" rows (i.e., the player wants to minimize the result). Obviously an L is the lowest value, and a W is the highest value. We usually assign a 1 to a win, a -1 to a loss, and a 0 to a tie. Player Y wants to make the number as low as possible (they win if the player X gets an L). Player X wants to make the number as high as possible (he wants a W).

enter image description here

If the game plays out to node 4, you know that player X will win no matter what. Therefore, 4 is marked W (or 1). If the game plays out to node 5, you know that he loses, so it's marked L. Same happens for 6 (which gets a W).

To assign to node 2, we note that 2 is on a "min" row (it's player Y's turn). 4, 5, 6, have W, L, W, respectively. Player Y can minimize this by choosing node 5, therefore winning. Therefore, Player X knows that if Player Y is intelligent, Player X will lose if he chooses A.

We can do the same thing on the other side to show that if Player X chooses B, he will tie. Therefore, Player X should choose B.

When code is written for minimax, the code does a post-order tree traversal and assigns values to the nodes as it goes by looking at the descendants.

Upvotes: 2

Related Questions