Reaching Depth Level
Mehes Andrew F J
When our recursive calls reach the given depth level do we evaluate the
board passed at that level and return its value, or do we first obtain a
list of valid move then place them on duplicate boards, evaluate the
boards, then return the hightest/lowest value?
Also, I was just wondering as to how this lab will be marked. As it is
possilbe to have more than one move of equal value, a different choice of
move may produce a different output.
Thank you.
Alexander Smith
The answer to your question is in the handout at the top of page three.
The first two bullets say:
- Get a list of all valid moves.
- If the depth limit has been reached, then evaluate the board position
after making each move.
The return value from minimax() is a move with its value filled in. That
means you can't just evaluate the board and return a value - you have to
return a move along with the value. So, whenever minimax() is called,
needs to determine all the possible "next" moves and evaluate all of them.
If you have reached the depth limit, then the value or each move is simply
determined by getBoardValue(). If you have *not* reached the depth limit,
then you can usually determine the value by calling minimax()
recursively. I say usually because of the one special case that is
mentioned at the top of page three.
We haven't decided exactly how this lab is going to be marked yet.
Obviously there will often be several possible moves with the same value.
That will be taken into account when marking.
Alexander
Vinson Hum
There's some confusion about this bullet: "If depth limit has been reached,
then evaluate the board position after making each move." and the
explanation and Fig. 3 of the handout. I am only concerned with the value of
".value" of the move returned here.
According to Fig. 3, at a depth of 2, White makes a move and Black makes a
move for a total of 2 moves, which means that at the depth limit, the value
of board should only be the value of these two moves (most online resources
of the minimax algorithm seems to do this, and I did this was as well).
However, the bullet mentioned above seems to imply that, for the above
example, White should make one more move before evaluating the board value,
which would mean that it is evaluating 3 moves.
So which is it?
Thank you,
Vinson Hum
Alexander Smith
You are correct - there are two different interpretations of what to do
when the depth limit is reached. The interpretation we were expecting was
what is stated in the text of the handout. If you are counting tree nodes,
this has the effect of going one level past the depth limit. (If you are
counting the number of times a minimax calls itself recursively, you get
the right number.) We didn't realize that the description in the handout
might be misleading, and no one complained about this until yesterday. So,
since it's too late to post changes to the lab now, we will accept either
interpretation. This means that what some people consider a depth limit
of 5 will be a depth limit of 6 for other people.
Alexander