• Game Tree: It is a structure in the form of a tree consisting of all the possible moves that 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 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 that assigns a numeric value for the outcome of a game. For instance, in chess or tic-tac-toe, the outcome is either a win, a loss, or a draw, and these can be represented by the values +1, -1, or 0, respectively. There are games that have a much larger range of possible outcomes; for instance, the utilities in backgammon varies from +192 to -192. A utility function can also be called a payoff function