Programming Question

note @1405 →
201 views
Actions ▾
P5 chooseMove, minValue, maxValue Explained
Here’s an explanation for how choose Move, minValue, and maxValue work together in the recursive process and eventually choose a move for the Al. This is a long post, so get comfy.
Here are some general notes about the Al, minValue, and maxValue:
• The base cases are always looking at the board from this player’s perspective.
• The Al tries to maximize it’s chances of winning, so through recursion (starting from chooseMove) it will look at all the possible scenarios that can take place based on what the opponent’s move was and what its future moves can be.
This is what possible Moves is used for.
• The maxValue method represents the part when it’s the opponent’s turn. It’s trying to map out all the possible moves the opponent can make, and choose the highest value.
。 This will always be among the following 3 numbers: 1.0, 0.0, -1.0.
。 If the value is 1.0, it means the best case scenario is the AlPlayer winning.
•
If the value is 0.0, it means the best case scenario is a draw.
。 If the value is -1.0, it means the best case scenario is the AIPlayer losing.
• But, because maxValue calls minValue to map these out, you actually need to get the possible Moves for the opponent in minValue.
。 The start of the recursive process will be in chooseMove.
• The minValue method represents the part when it’s the Al’s turn. It’s trying to calculate the minimum number of points it’s opponent can get from the board.
。 This means the Al assumes the worst case scenario for itself. This is why the maxValue method is trying to choose the maximum minValue, and what is meant by “the AIPlayer assumes that its opponent is going to try and
choose the move option on the next board which minimizes its return.”
I.e. the Al assumes the player will try to minimize it’s chances of winning.
■ I.e. try to reduce it’s max minValue.
• And, because minValue calls maxValue to map these out, you will actually need to get possible Moves for the Al in maxValue.
。 The idea is this: the base cases outline what could happen for that boad (winning, losing, draw), and if none of those are true, the recursive case calls for the other side.
• Important: Keep the above underlined portions in mind while you read the rest of this post and the image.
The image below shows a snippet of the traced recursion. Before the current board, similar recursive steps were taken by the Al to produce such a board. However, this is only for explanation purposes to show all the possible cases
(-1.0, 0.0, 1.0). There is no guarantee that your Al will/will not be able to create the same board, but you can feed it manually into your chooseMove function to check your output(s).Key:
ΑΙ
Opponent
XOX
0101X
Most optimal move is
max minValue = 1.0
In chooseMove
Current board
min maxValue: -1.0
min maxValue: 0.0
min maxValue: 1.0
XOX
OX
XOX
OX
XOX
0x
О
In minValue
Al’s turn
max minValue: -1.0° max minValue: 0.0 max minValue: 1.0
XOX
XOX
Х
Х
0101x
О
OX
OX
-1.0 X
max minValue: 0.0
XOX
0101x
☑O
+1.0
In maxValue
Opponent’s turn
min maxValue: 0.0 min maxValue: 1.0 min maxValue: 0.0
XOX XOX
0|0|x| 0101x
XOX
0101X
XX
OOXX
XX O
+0.0
+1.0
+0.0
In minValue
Al’s turnSome notes on the image:
. ‘X’ represents the Al’s character, and ‘O’ represents the opponent’s character. Note that this is reversed in your project in the given VSComputer.
• Assuming we get the first board passed into choose Move. We first want to get all the possible moves of this player. Then, we want to go through the the possible moves to find the max minValue–this will be the move the Al player will
choose (i.e. the board returned by chooseMove) and is highlighted in yellow above.
• The green boxes represent the minValue method, were the Al looks at the possible moves it can choose from, and the red box represents the maxValue method where the Al looks at all the possible moves its opponent can choose
from.
• The arrows represent the array returned by possible Moves. So, for the current board, possible moves returned 3 TicTacToe objects in an array, and for the boards in the first green box, the two leftmost boards have 2 TicTacToe objects
each, returned in an array, and the rightmost one hit a base case, and so on.
Some notes on the algorithm itself:
• For every possibleMove it has (first green box), the Al then calculates the possible Moves it’s opponent has (red box). Then for each possible Move its opponent has (red box), the Al calculates the possible Moves it has (second green
box). This goes on and on until a base case is hit, and the recursion goes all the way back up after.
• Going back to “keep the underlined portions in mind”–the coding portion will always be one step behind where the image is. So, the possibleMoves in the first green box are actually being calculated in chooseMove. The
possible Moves in the red box are actually being calculated in first recursive part of minValue, and so on.
• Keep in mind that the Al assumes the worst possible case scenario for itself.
• Starting from the first green box and mapping all the possible moves that can take place after all of its possible moves, the Al finds that there is a chance it can lose in the leftmost branch from the minimum maxValue, however we
don’t have a maximim minValue yet, so our optimal choice is this one for now.
。 The best case scenario is losing for the Al 🙁
• In the middle box, the Al finds the best case scenario for itself is a draw. This is a better option than the previous one (the maximum minValue is greater), so our optimal choice changes to this.
。 The best case scenario is a draw for the Al :/
• In the last scenario, the Al finds it has a chance to win. This is a better maximum minValue, so this is the best option.
。 The best case scenario is a win for the Al. It will return this board from chooseMove 🙂
• For each recursive step, the thinking is essentially this: If I choose this possible move from the ones I have, what are the possible moves of my opponent, and most importantly, from all these possible moves, which possible move
branch has a chance for me to win?
One last thing the project description mentions that I want to emphasize: because of how these methods works here, the Al will never lose. It will either win or it will be a draw. This might help you in testing your code. Try to see if you can
beat your Al.
I know this was a long post, but I hope it helps clarify some things about the recursive process. Feel free to ask questions or make a follow-up to this post if you still need clarification. I’ve tried to give out implementation hints here and there
as well.
Good luck!