Artificial
Intelligence Approaches to Game Playing
CIS 203 Research Paper
November 21, 2001
By Thomas Thomas
An Artificial Intelligence approach to game playing is very successful for many reasons. Compute games are popular these days; a lot of people use these game at home or outside, and it’s really important to know how these games are working. Artificial Intelligence has been applied to the playing of games for more than fifty years. Artificial Intelligence provides various techniques for solving the problem in the course of playing the game.
A lot of people use their computer to play games, and most games required an opponent of some type to make the game more interesting. Computer opponents were usually found mainly in board games, such as chess, backgammon, othello, and many others. Most of these games are different but use almost same techniques to simulate an intelligent opponent to play against. Various AI researchers around the world have developed these techniques.
Early AI Game Playing:
The most common board game that AI is applied is chess and now days computerized chess games can be found in most of the toy stores. The first work on machines playing chess occurred in the early 1950’s. Alan Turing and Claude Shannon both produced papers on the subject in the early 50’s, working independently of each other the idea of Turing paper used to develop the actual chess game. However, slightly before this research in the field of computerized game players came the work of Arthur Samuel in 1947. He wasn’t working on chess but he was working to implement an intelligent computer for simpler games of checkers. In fact, his checker’s playing program wasn’t up to beat champions until 1962. Ever since, the development of computer program for playing board game has continued. Its easy to see that people been trying to use AI in game playing since a long time ago.
Adversarial Search:
Most of the board games are two player contests, where each player tries to gain territory or possession of pieces at the expense of the other player. These require what are often described as ‘ adversarial search’ techniques. These require adversarial search techniques, and intelligent computerized player for this type of game is called a “minimax” search. This type of approach basically entails deciding on a value for the state of play after each of the possible moves open to the computer player. For each moves in the game, the computer player is said to be trying to “maximise” the static evaluation score, while the human will be trying to “ minimise” it hence the term “minimax” the field of game playing in AI is will understood in many respects. Its possible to apply minimax and related searches to game with more than one opponent, but in these circumstances their effectiveness tends to be weakened.
There are two main reasons to this problem. The first problem is the type of the search depends on the opponent always taking the worst possible move for the computer player, and in multi-player game, and this is not the highest priority for the other player because they may be competing against each other. The second problem with using minimax search in multi-player game is that the number of branches representing possible game state at each decision point is very high.
Genetic Algorithms:
Almost all kinds of games now claim some kind of sophisticated AI is guiding the computer opponent within the game. One of the goals for intelligence is that it should be capable of learning from previous experiences. An AI field builds on this area is that of Genetic Algorithms. In Genetic Algorithms start with larger number of players then it keep the best ones. Sometimes its necessary that the individuals can be mutated in a way that will not stop them from working to implement a genetic algorithm for playing games. One of the disadvantages of this approach to generating good game playing algorithms is that it is slow for requiring much iteration for truly competent players to start emerging. Another disadvantage is that the game playing routine that are evolved from this process will not be optimum game players.
An advantage of this is that it is requires little or no human intervention, so that whole process can take place at the highest speed that the machine is capable of. Overall, the area of GA must be the promising in AI, with the potential to continually improve upon the current routine mean that the theory can be end up at best game playing algorithms.
Conclusions:
The field of game playing in AI is well understood in many respects, but still offers a good proving ground for new techniques developed for other areas of AI that can work in the fields of game play. Also, research into game play is still leading to new techniques being invented which might then be applied to other areas in the broader field of Artificial Intelligence research. Although, well known problem such as chess and checkers more towards a brute force solution, they are still valid testing ground for work in the area of search techniques.
There are also many game which do not succumb to this type if brute force approach and it is possible that AI research will move towards using these as environments better suited to its purposes. However, chess will always retain its status, as a respected game using the brute force approach will surely be accorded plenty of attention from other researchers in the AI fields. Finally, GA has the potential to be the most exciting field of AI for the future works on game playing, with the independent evolution of a population or many populations of game playing routines leading to new advance in how computers play games. One of the things, I find about computer game is that it’s easy to follow the rules. Computer’s can follow rules and regulations easily than humans. By looking at these facts I think Artificial Intelligence applied to game playing been really successful for many games like chess, board game, checkers, and many other games.
Winston, 1993, Artificial Intelligence, 3rd Edition. Addison-Wesley, Wokingham, England.
Bench-Capon, 1990.Knowledge Representation: An Approach to Artificial Intelligence. Academic press, London, England.