Overview / Usage

**MINIMAX **is a backtracking algorithm which is used to choose an optimal move for a player assuming that the other player is also playing optimally. It is used in games such as tic-tac-toe, go, chess and many other two-player games.This algorithm let you know the most optimal move from all possible moves available at that any in the game.

Terminologies:

Game Tree: It is a structure in the form of a tree consisting of all the possible moves which allow you to move from a state of the game to the next state.

A game can be defined as a search problem with the following components:

• Initial state: It comprises the position of the board and showing whose move it is.
• Successor function: It defines what the legal moves a player can make are.
• Terminal state: It is the position of the board when the game gets over.
• Utility function: It is a function which assigns a numeric value for the outcome of a game. The outcome is either a win, a loss, or a draw, and these can be represented by the values +1, -1, or 0, respectively.. A utility function can also be called a payoff function

​

Methodology / Approach

THE WORKING OF ALGORITHM:

In Minimax the two players are called maximizer and minimizer. The maximiser tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.

Every board state has a value associated with it. In a given state if the maximizer has upper hand then, the score of the board will tend to be some positive value. If the minimizer has the upper hand in that board state then it will tend to be some negative value.

The general process of the Minimax algorithm is as follows:

Step 1 : First, generate the entire game tree starting with the current position of the game all the way upto the terminal states.

Step 2: Apply the utility function to get the utility values for all the terminal states.

Step 3: Determine the utilities of the higher nodes with the help of the utilities of the terminal nodes.

Step 4: Calculate the utility values with the help of leaves considering one layer at a time until the root of the tree.

Step 5: Eventually, all the backed-up values reach to the root of the tree, i.e., the topmost point. At that point, MAX has to choose the highest value.

​

Here are some useful links:

https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/

​

Technologies Used

HTML, CSS, JAVASCRIPT.

Repository

https://github.com/asis45/AI-tic-tac-toe-game