So I was looking up Mini-max for a Tic-Tac-Toe Game, but couldn't understand how the recursion worked? Okay, so basically here are my questions:
For example in this Pseudo-code
function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
α = max(α, -minimax(child, depth-1))
return α
A node
is a board correct? And is the depth how many plies the code has to go down in recursion? Also what is the max
function and where are the nodes being generated from?
Now, so far I have this code for creating a board:
class Board{
public:
Board();
~Board(){};
public: // The board
// In the board, 1 is x, 2 is o, 0 is empty square.
int board[3][3];
};
But how would I know whose turn is it? And how do I generate the child nodes for the board?
We'll use your tic-tac-toe as an example first.
Looking at your pseudocode:
max(a, b)
is any function that returns the larger of a
or b
. This is usually provided by a math library or similar.depth
is the maximum depth to which you will search.1
for a board position that wins for the player doing the analysis, -1
for a board position that wins for the other player, and 0
for any inconclusive position. In general, you'll have to cook up a heuristic yourself, or use a well-accepted one.If you haven't worked with graphs or trees yet, I suggest you do so first; the tree primitive, in particular, is essential to this problem.
As an answer to a comment in this thread asking for an example of determining whose turn it is for a given node, I offer this pseudo-Python:
who_started_first = None
class TreeNode:
def __init__(self, board_position = EMPTY_BOARD, depth = 0):
self.board_position = board_position
self.children = []
self.depth = depth
def construct_children(self, max_depth):
# call this only ONCE per node!
# even better, modify this so it can only ever be called once per node
if max_depth > 0:
### Here's the code you're actually interested in.
if who_started_first == COMPUTER:
to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
elif who_started_first == HUMAN:
to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
else:
raise ValueError('who_started_first invalid!')
for position in self.board_position.generate_all(to_move):
# That just meant that we generated all the valid moves from the
# currently stored position. Now we go through them, and...
new_node = TreeNode(position, self.depth + 1)
self.children.append(new_node)
new_node.construct_children(max_depth - 1)
Each node is capable of keeping track of its absolute depth from the 'root' node. When we try to determine how we should generate board positions for the next move, we check to see whose move it is based on the parity of our depth (the result of self.depth % 2
) and our record of who moved first.
1) How does minimax know whose turn is it? Whats the best way to indicate the player whose turn it is generating?
You have that depth
argument. If the depth is even, then it's one player's turn, if it's odd, then it's the other player's turn.
2) How do you generate possible moves?
Using the rules of the game. In tic tac toe, a possible move means placing one's mark into a free cell.
3) How do you know when you are at a terminal node, and how do you generate the terminal nodes?
A terminal node is a node where someone has won. You generate them by recursion. Each recursive call should be given the current state of the board. I guess that's the node
and child
parameters in your pseudocode. So if in that situation someone has won, then it's terminal, otherwise you try all legal moves and recurse.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With