CODEWITHSUNDEEP
algorithmartificial-intelligenceminimaxminmax
Andre Liberty
Andre Liberty

Reputation: 757

Minimax without a tree

Minimax is often illustrated with a tree,but I know that it can be implemented without the tree !However,I can not figure out how to do it without the tree!Can you clarify it for me?

Upvotes: 0

Views: 529

Answers (2)

redwrasse
redwrasse

Reputation: 31

As pointed out in the first comment, minimax is formally defined on a tree structure but for many practical applications it's not necessary to formally compute over the entire tree, and even the game tree structure does not need to be known beforehand- if the possible next moves and termination (game over) states are known, the tree can be built as the algorithm runs. For non-reversible games (like tic tac toe) duplicate states at different points of the tree have the same partial subtrees; hence the only structure that needs to be learned is the value of each state, calculated by minimax; these values can be cached as well for reuse during the algorithm.

By the way, one interesting and popular application of this 'non-explicit tree structure' use of minimax is Generative Adversarial Networks:

From the abstract

..a generative model G that captures the data distribution, and a discriminative model D that estimates the probability that a sample came from the training data rather than G. The training procedure for G is to maximize the probability of D making a mistake. This framework corresponds to a minimax two-player game.

Upvotes: 1

xXliolauXx
xXliolauXx

Reputation: 1313

Minimax by definition always works like a tree, no matter how you implement it. How you visualise it is another story.

Usually, Minimax is implemented recursively (which can be best visualised using a tree) or iteratively, which still goes through the nodes of a minimax tree, just with another approach.

Upvotes: 1

Related Questions