How does minimax algorithm work on tictactoe?

Question

I've read a lot of documents regarding minimax algorithm and it's implementation on the game of tic-tac-toe but I'm really having a hard time applying it. Here are links that I've read 1, 2, 3, 4, 5 and an example using java 6

Considering the pseudocode: 7

function minimax(node, depth, maximizingPlayer) 
if depth = 0 or node is a terminal node
    return the heuristic value of node

if (maximizingPlayer is TRUE) {
    bestValue = +∞
    for each child of the node {
        val = minimax(child, depth-1, FALSE)
        bestValue = max(bestValue, val)
    }

    return bestValue
} else if maximizingPlayer is FALSE {
    bestValue = -∞
    for each child of the node {
        val = minimax(child, depth-1, TRUE)
        bestValue = min(bestValue, val)
    }

    return bestValue
}

Here are my questions:
1. What will I pass to the signature node, is it the valid moves for the current player?
2. What is + and - infinity, What are their possible values?
3. What is the relationship between minimax and the occupied cells on the board.
4. What are child nodes how are values extracted from it?
5. How will I determine the maximum allowed depth?

Answer 1

1. Node is the grid with the information of which cells were already played

2. ±∞ is just a placeholder, you can take int.maxValue or any other "big"/"small" value in your programming language. It is used later as a comparison to the calculated value of a node and 0 might already be a valid value. (Your pseudocode is wrong there, if we assign +∞ to bestValue, we want min(bestValue, val) and max(bestValue, val) for -∞.

3. Not sure what you mean.

4. Child nodes are possible moves that can be made. Once no move can be made the board is evaluated and score is returned.

5. The search space in TicTacToe is very small, in other games a heuristic score is returned, depending if the situation is is favorable to the player or not. In your scenario there should be no hard depth.

Answer 2

First of all, stop asking 100 questions in one question. Ask one, try to understand and figure out whether you actually need to ask another.

Now to your questions:

What will I pass to the signature node, is it the valid moves for the current player?

No, you will pass only node, depth, maximizingPlayer (who plays - min or max). Here for each child of the node you find the possible moves from that node. In real scenario most probably you will have a generator like getChildren using which you will get your children

What is + and - infinity, What are their possible values?

minimax algorithm just tries to find the maximum value over all minimum values recursively. What is the worst possible result a maximum player can get - -infinity. The worse for minimum is when maximum will get +infinity. So these are just starting values.

What is the relationship between minimax and the occupied cells on the board.

Not sure what do you mean here. Minimax is the algorithm, occupied cell is an occupied cell. This question is similar to what is the relation between dynamic programming and csv file.

What are child nodes how are values extracted from it?

they are all possible positions that can be reached from your current position. For example

How will I determine the maximum allowed depth?

In standard minimax it is till you will reach the end of the tree. At the end of the tree your evaluation function will give you a reward. Because the tree is most of the time too huge to fit anywhere people use a cutoff and use approximation to evaluation function (heuristics). The easiest cut of is look n moves ahead and hope that your evaluation function is good enough and your opponent think n-1 moves ahead.