Page 1 of 1

Game Playing in Artificial Intelligence

PostPosted: Mon May 07, 2012 3:23 pm
by Prasanth
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.

1.1 Types of Game

1. Perfect Information Game: In which player knows all the possible moves of himself and opponent and their results. E.g. Chess.
2. 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.

1.2 Definition

Game playing is a search problem defined 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