expert systems artificial intelligence index Automatic theorem proving

Games

Another field of application where this symbolic and engineering approach has found success is that of games. Artificial intelligence generally considers games for two players moving one after the other. It considers the development of the game as a "treeDizionario" where the roots are the starting position and the leaves the final position (winning or losing).


Play Tic-Tac-Toe against the computer:





Fig. 1:
Part of the tree corresponding to a game of Tic-Tac-Toe.
(Credits: David Eppstein, Dept. Information & Computer Science, UC Irvine)



The most well-known algorithmDizionario for programming artificial players is called min-maxDizionario. The algorithm should explore the whole tree and label each leaf as winning or losing and then backpropagate this information to the root.

Fig. 2: Min-max pictorial example.
(Credits: http://www.dis.uniroma1.it/~demetres/Leonardo/Manual/Chapters/AppendixA3.html)


Obviously, because of the complexity of the games, it would be unthinkable even for a very powerful computer to develop the whole tree completely in order to chose the best move. For this reason it was necessary to apply some heuristics to cut down some of the branches and make the problem feasible. Just think of the game of chess, where the size of the problems faced is huge. At the beginning of the game there are 400 possible moves, which become 144,000 at the second move. Developing the tree of the game we would have 35100 knots. By applying techniques of symbolic manipulation and using powerful means to reduce the bulk of the research, systems capable of playing chess better than a human being were produced, although obviously using very different techniques from the ones applied by human beings. In May 1997, in New York, a machine (Deep Blue) defeated the world champion Kasparov in a six game match. It is interesting to note how such a machine, designed at a hardware level to develop and examine research spaces in parallel very quickly (Deep Blue can examine 1011 positions in about three minutes), uses brute strength more than refined heuristic techniques to reach the best solution quickly.


Fig. 3:
Deep Blue in action.

The Webweavers: Last modified Wed, 09 Mar 2005 11:05:09 GMT