The most well-known algorithm for programming artificial players is called min-max. The algorithm should explore the whole tree and label each leaf as winning or losing and then backpropagate this information to the root.
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.