How does minimax recursion work?

Question

So, I was looking for Mini-max for the Tic-Tac-Toe game, but couldn't figure out how recursion works? Okay, so basically these are my questions:

• How does minimax know what it is? What is the best way to tell the player whose move he is generating?
• How do you create possible moves?
• How do you know when you are at a terminal node, and how do you create terminal nodes?

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 α 

Is the node right board? And is there a depth of the number of layers that the code should omit in recursion? Also what is the function max and where are the nodes from?

Now I have this code to create 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 do I know whose turn it is? And how do I create child nodes for a board?

Answer 1

First we will use your tic-tac-toe.

• The minimax algorithm is best suited for games where players alternate, but can be adapted to games in which players can make several moves per turn. For simplicity, we will consider the first. In this case, you do not need to store “X to move” or “O to move” with each node, because it can only be determined by the parity of the depth of the node (whether it is an even number of steps, or an odd number of steps, above).
• Generating possible moves from each position requires that you know whose move (which can be defined as before) and the rules for legal movements from a specific position. For a simple game, such as tic-tac-toe, taking into account the position, it is enough to list all the states that consist of a copy of the current position plus a new part belonging to the current player, placed in turn on each empty square. For games like Othello, you also need to check each place to make sure it matches the rules, and update the end position according to the consequences of the rule (for Othello, turning a bunch of pieces upside down). In general, from each valid position that you are tracking, you list all the possible locations of the new part and check which of them are allowed by a set of rules.
• In general, you NEVER generate the entire tree, as the size of the game tree can easily exceed the capacity of the Earth’s storage. You always set the maximum iteration depth. The node terminal, then, is simply a node at maximum depth or node, of which there are no legal movements (for tic-tac-toe, a board with each square filled). Do not create terminal nodes before; they are generated naturally when building the game tree. Tic-tac-toe is simple enough that you can generate the entire game tree, but then do not try to use the tic-tac-toe code, for example. Othello

Looking at your pseudo code:

• max(a, b) is any function that returns more than a or b . This is usually provided by a math library or similar.
• depth - the maximum depth to which you will search.
• The heuristic value that you calculate is some numerical value that describes the value of the board. For a game like tic-tac-toe, which is simple enough for you to list the entire game tree, you can designate 1 for the position of the board that wins for the player performing the analysis, -1 for the position of the board that wins the other player and 0 for any unconvincing position. In general, you will have to prepare a heuristic yourself or use the well-accepted option.
• You generate nodes on the fly during analysis based on their parent nodes. The root of the node is always the position from which you are doing the analysis.

If you have not worked with graphs or trees, I suggest you do this first; A primitive tree element, in particular, is important for this problem.

---

As a response to a comment in this thread asking for an example of determining whose move for a given node, I suggest 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 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 able to track its absolute depth from the "root" node. When we try to determine how we should create positions on the board for the next step, we check whose move it is based on the ratio of our depth (result self.depth % 2 ) and our record of who moved first.

Answer 2

1) How does minimax know whose it is? What is the best way to tell the player whose move he is generating?

You have an argument of depth . If the depth is even, then one player turns if it is odd, then he turns by another player.

2) How do you create possible moves?

Using the rules of the game. In tic tac toe, a possible move means placing one mark in a free cell.

3) How do you know when you are at a terminal node, and how do you create terminal nodes?

A node terminal is a node where someone won. You generate them by recursion. Each recursive call must be assigned the current state of the board. I think the node and child parameters are in your pseudocode. So if in this situation someone won, then this is the terminal, otherwise you will try all legal steps and recurs.

Answer 3

I can give a little idea about what you are looking for since I wrote a minimax algorithm for tic-tac-toe.

To answer your questions directly:

• My minimax algorithm did not define this. He accepted an argument defining which player used the algorithm.

• Knowing the player to move, draw all the empty squares on the board and for each of them create a node with the current player token on this square. Recursively proceed from there.

• I used a function that returned a value indicating whether the game ended and whether it was a draw or a win.

My main algorithm did this:

• Entrance: player to move and board status.
• Find all the spaces left on the board.
  • Create a new panel in which the player moves in this space.
  • If the game is over, generate a node with the result of the game.
  • Otherwise, run the algorithm by transferring to another player and a new board and create a node with the result of an ideal opponent move.
• Determine which of the node (move) will lead to the best worst case.
• Result: the best result, and information about the game is obtained from it.