Game playing was one of the first tasks undertaken in Artificial Intelligence. Game theory has its history from 1950, almost from the days when computers became programmable. The very first game that is been tackled in AI is chess. Initiators in the field of game theory in AI were Konard Zuse (the inventor of the first programmable computer and the first programming language), Claude Shannon (the inventor of information theory), Norbert Wiener (the creator of modern control theory), and Alan Turing. Since then, there has been a steady progress in the standard of play, to the point that machines have defeated human champions (although not every time) in chess and backgammon, and are competitive in many other games.

•  Types of Game

•  Perfect Information Game: In which player knows all the possible moves of himself and opponent and their results. E.g. Chess.

•  Imperfect Information Game: In which player does not know all the possible moves of the opponent. E.g. Bridge since all the cards are not visible to player.

Definition

Game playing is a search problem d efined by following components:

1.Initial state: This defines initial configuration of the game and identifies first payer to move.

2. Successor function: This identifies which are the possible states that can be achieved from the current state. This function returns a list of (move, state) pairs, each indicating a legal move and the resulting state.

3. Goal test: Which checks whether a given state is a goal state or not. States where the game ends are called as terminal states.

4. Path cost / utility / payoff function: Which gives a numeric value for the terminal states. In chess, the outcome is win, loss or draw, with values +1, -1, or 0. Some games have wider range of possible outcomes.

Characteristics of game playing

1. Unpredictable Opponent: Generally we cannot predict the behavior of the opponent. Thus we need to find a solution which is a strategy specifying a move for every possible opponent move or every possible state.

2. Time Constraints: Every game has a time constraints. Thus it may be infeasible to find the best move in this time.

How to Play A Game in AI?

Typical structure of the game in the AI is:

E.g. Tic- Tac- Toe, Checkers, Chess, Go, Nim, Othello

For dealing with such types of games, c onsider all the legal moves you can make from the current position. Compute the new position resulting from each move. Evaluate each resulting position and determine which is best for you. Make that move. Wait for your opponent to move and repeat the procedure. But for this procedure the main problem is how to evaluate the position? Evaluation function or static evaluator is used to evaluate the 'goodness' of a game position. The zero- sum assumption allows us to use a single evaluation function to describe the goodness of a position with respect to both players. Lets consider, f(n) is the evaluation function of the position 'n'. Then,

- f(n) >> 0: position n is good for me and bad for you

- f(n) << 0: position n is bad for me and good for you

- f(n) near 0: position n is a neutral position

e.g. evaluation function for Tic- Tac- Toe:

f( n) = [# of 3- lengths open for me] - [# of 3- lengths open for you]

where a 3- length is a complete row, column, or diagonal

Minimax

Game Trees

Games are represented in the form of trees wherein nodes represent all the possible states of a game and edges represent moves between them. Initial state of the game is represented by root and terminal states by leaves of the tree. In a normal search problem, the optimal solution would be a sequence of moves leading to a goal state that is a win. Even a simple game like tic-tac-toe is too complex for us to draw the entire game tree. Fig 1 shows part of the game tree for tic-tac-toe.

Applications

Game theory has vast applications in different fields. Some of the important are mentioned below.

a. Entertainment: Game theory is used to define different strategies of different games.

b. Economics: Each factor in the market, such as seasonal preferences, buyer choice, changes in supply and material costs, and other such market factors can be used to describe strategies to maximize the outcome and thus the profit.

c. Military: Game theory can be useful in Military also. Military strategists have turned to game theory to play "war games". Usually, such games are not zero-sum games, for loses to one side are not won by the other.

d. Political science: The properties of n-person non-zero-sum games can be used to study different aspects of political science and social science. Matters such as distribution of power, interactions between nations, the distribution of classes and their effects of government, and many other matters can be easily investigated by breaking the problem down into smaller games, each of whose outcomes affect the final result of a larger game.

Conclusion