64
A Survey of Methods for Implementing
Behavioural Functions
Submitted in partial requirement of the degree of
Bachelor of Science (Honours)
by
Jonathan Hitchcock
Supervised by
Dr George Wells
November 2001
Abstract
This project is an investigation into the different methods for implementing functions to control behaviour in various situations. Games are used as to provide situations to test the functions, and correct behaviour is considered to be behaviour that leads to the winning of the game. Particular attention is paid to functions that learn over time, and adapt their behaviour.
1 Introduction 1
1.1 What is Artificial Intelligence? 1
1.2 The Turing Test 1
1.3 A variation on the Turing Test 2
1.4 Games as a model for intelligence 2
1.4.1 Strict formalization 2
1.4.2 Common 3
1.4.3 Well Implemented 3
1.4.4 Well Researched 3
1.5 The Aim of the Project 3
2 Methods of Implementing Intelligences 5
2.1 Rule-based intelligence 5
2.2 Space-Search 6
2.3 Bean Learning 13
2.4 Genetic Algorithms 15
2.5 Neural Nets 17
3 Classification of Games 22
3.1 Characteristics Chosen 22
3.1.1 Options available 22
3.1.2 Space Size 23
3.1.3 Context 23
3.2 Characteristics Not Chosen 24
3.2.1 Number of Players 24
3.2.2 Perfect Information 25
3.2.3 Zero Sum 26
3.3 Characterization Map 26
3.4 Structure of this Project 27
3.5 Choice of Games 27
4 Examination of the Categories 29
4.1 Classification 1: Finite, limited, non-contextual 29
4.1.1 The Game: Tic-Tac-Toe 29
4.1.2 M.E.N.A.C.E 30
4.1.3 A Tic-Tac-Toe program 30
4.1.4 The Tic-Tac-Toe BeanPlayer 32
4.1.5 Comparison of the methods 33
4.1.5.1 Random vs. Random 33
4.1.5.2 Random vs. BeanPlayer 33
4.1.5.3 BeanPlayer vs. BeanPlayer 34
4.1.5.4 BeanPlayer vs. Human Player 35
4.1.6 Conclusion 35
4.2 Classification 2: Finite, limited, contextual 35
4.2.1 The Game: RoShamBo 35
4.2.2 Not So Simple 36
4.2.3 The Contest Rankings 37
4.2.4 The Methods Used 38
4.2.4.1 Method 1: Iocaine Powder 38
4.2.4.2 Method 2: Simple Modeller 39
4.2.4.3 Method 3: Random 40
4.2.4.4 Other Methods 41
4.2.5 Conclusions 41
4.3 Classification 3: Infinite, limited, non-contextual 42
4.3.1 The Game: Backgammon 42
4.3.2 Common Methods for Solutions 43
4.3.3 Backgammon Neural Nets 44
4.3.3.1 NeuroGammon 44
4.3.3.2 TD-Gammon 45
4.3.4 Comparisons of the programs 46
4.3.5 Conclusions 46
4.4 Classification 4: Infinite, limited, contextual 46
4.4.1 The Game: Rubik’s Cube 46
4.4.2 Problems with Solving the Cube 48
4.4.3 Solving the Cube 49
4.4.3.1 The Rule-driven Solution 49
4.4.3.2 Searching the Cube’s Space 50
4.4.3.3 A Possible Genetic Method 50
4.4.4 My Cube Implementation 51
4.4.5 Conclusions 51
4.5 Classification 5: Infinite, unlimited, non-contextual 51
4.5.1 The Game: Chess 51
4.5.2 A Very Common Problem 52
4.5.3 The Possible Methods 52
4.5.3.1 Space Searching 52
4.5.3.1.1 Optimizations 53
4.5.3.1.2 Deep Blue 53
4.5.3.2 Neural Networks 54
4.5.3.2.1 NeuroChess 54
4.5.3.2.2 Success 54
4.5.4 Conclusions 55
4.6 Classification 6: Infinite, unlimited, contextual 55
4.6.1 The Game: Bot-Wars 55
4.6.2 Implementations 55
4.6.3 Possibilities 56
4.6.3.1 Rule Based 56
4.6.3.2 Genetic 56
4.6.3.3 Neural Net 56
4.6.4 Conclusions 57
5 Summary of findings about the Methods 58
5.1 Rule-based intelligence 58
5.2 Space-Search 58
5.3 Bean Learning 59
5.4 Genetic Algorithms 59
5.5 Neural Nets 59
6 Conclusions 61
6.1 Categories Revisited 61
6.1.1 Finite, Limited, Non-Contextual 61
6.1.2 Finite, Limited, Contextual 61
6.1.3 Infinite, Limited, Non-Contextual 61
6.1.4 Infinite, Limited, Contextual 62
6.1.5 Infinite, Unlimited, Non-Contextual 62
6.1.6 Infinite, Unlimited, Contextual 62
6.2 Final Comments 63
7 References 64
64
1 Introduction
The field of Artificial Intelligence is about fifty years old, and, while much work has been done on various aspects of the subject, nothing conclusive about the possibility of real intelligence has ever been shown. There is still much debate over whether true intelligence will ever actually be achieved. However, there is much hope, and many new methods are being developed, in the hope that one of them will hold the key to intelligence.
Even if no “real” intelligence has been achieved to date, there have been some remarkable technologies developed in the process. In addition, while the general problem of intelligence has not been conclusively addressed, several specific sub-problems have been solved very satisfactorily. This project is an investigation of some of these technologies, methods and solutions.
1.1 What is Artificial Intelligence?
One of the most common definitions of the field is “the imitation of intelligent behaviour in computers” [Merriam-Webster, 1998]. There are more strict and less strict definitions, which often attempt to bypass the metaphysical questions involved in the problem of whether the human mind is a machine itself, or whether there is “something more”. There are many who are of the opinion that anything that can behave sufficiently like a human will in fact be intelligent, and that, thus, any “artificial” intelligence will be “true” intelligence.
1.2 The Turing Test
Alan Turing, often called “the Father of Artificial Intelligence”, proposed a test for intelligence, which he called “the imitation game” [Turing, 1950]. He proposed it in a general form, and applied it to machines. The way the Turing Test, as it has come to be called, works involves a judge communicating via some sort of neutral medium (teletype, or a terminal, or something) with two contestants in the game. One of these contestants is a human, and the other is a machine, but the judge does not know which is which. The judge asks them questions, and receives their replies. When he is satisfied, he then has to decide which one is the human, and which is the machine. If he cannot decide, or decides wrongly, then the machine is said to have passed the Turing Test. More accurately, if the machine is identifiable, then it has failed the Turing Test, and is not intelligent.
This test is often made a little less formal, and simply stated as: “If a machine can answer questions and communicate in such a way as to be indistinguishable from a human communicant, then it is intelligent.”
1.3 A variation on the Turing Test
The Turing Test has come under a lot of attack, for various logical, philosophical, and practical reasons, but it still stands as the archetypal test for intelligence. However, I wish to further generalize the test, and say that, if a machine can give correct responses in a certain situation, on a level with the responses that a human would give, then it may be said to be intelligent in that situation. Since conversation is possibly the most complex of situations, requiring the most from responses, the Turing Test seems to be a very good test – it has to deal with self-referential questions, motives, and context, in addition to grammar and syntax. I am going to use a substantially less complicated situation to test the intelligence of technologies currently available: games.
1.4 Games as a model for intelligence
Games have a number of advantages as a model for intelligence tests:
1.4.1 Strict formalization
Games are, almost by definition, strictly formalized. They have specified goals, rules, and boundaries. Everything about them is explicitly listed, and thus the model is exact. Modelling something less explicit means that certain factors have to be ignored, and everything becomes less exact. For example, modelling the physical world would mean that things like air-resistance and gravity have to be approximated. In games, everything is already laid out, and no accuracy needs to be lost, generally.
1.4.2 Common
There are a lot of games around, and a lot of types of games around. Any type of reaction required (a choice of paths, or a calculation, or sequence of moves, for example) will be catered for in a game somewhere. Thus, the investigation is not limited by the model – games are many and varied, and will supply situations for all the investigations needs.
1.4.3 Well Implemented
Games are a very common application of computers, and there are many implementations of a wide variety of games available. This means that I do not need to implement every game that I investigate, which saves time, and also allows me to utilize the programming skills of other, better computer scientists.
1.4.4 Well Researched
Games, for the above reasons, are a very common subject for Computer Science research. As a result, many methods have been developed for solving some common problems with games. For example, there are some very efficient search methods available – much effort has been put into making them as fast as possible. In addition, there are some game-specific algorithms that are very useful: Chess has any number of board-evaluation algorithms freely available.
For these reasons, I have chosen to use games as the model for studying intelligence in my project.
1.5 The Aim of the Project
This project aims to investigate the different methods of implementing intelligence in games. In surveying the methods that have been used in various applications, and comparing them, it hopes to find those methods that provide most promise for the field of Artificial Intelligence.
2 Methods of Implementing Intelligences
There are several commonly used methods for implementing some form of intelligence in games currently. This section will give a survey of each method, describing how it works, as well as a few of the problems that I have discovered with each method:
2.1 Rule-based intelligence
The simplest type of intelligence for a game is one based completely on rules, which detail specifically and explicitly how exactly to act.
These rules are generally of the form “condition: action”, where the condition will be a specific situation, and the action describes the response that is to be made. An example of such a rule for the game of volleyball would be “if the ball is hit slowly directly towards you, and you are at the net, then hit it very hard towards the ground on the other side of the net (i.e. spike it)”.
While this intelligence will be very exact in the situations which it has rules for, and will give responses which have been specifically designed for those situations, and will thus, presumably, be correct, it is very inflexible: if a situation arises for which there is no rule, the intelligence cannot perform any actions. In any sufficiently complex game, there will be a very large number of situations that can arise, and it is impractical, if not impossible, to have rules for them all.
Patterned rules can be made, which match a type of situation with a type of action, which could possibly be parameterized in order to tailor the response with the situation (such as, for clay-pigeon shooting, “if the pigeon is at level x and moving with velocity y, raise the gun at angle ang_func(x) and point it in direction dir_func(y), and shoot”). This may extend the possibilities for rule-based intelligences, but the situation-limit is still encountered – this time, there may be types of situations that have not been catered for.
2.2 Space-Search
This is a very common method for finding the correct solution to any problem: it involves looking through all the options available, and finding the ones which are solutions, or possibly finding the best solution. The “space” referred to in the name is the complete set of solutions to be searched. There are various ways to reduce the size of the space, and thus the time it takes to search it, without losing any solutions.
The most basic space-search is a recursive tree search: each option available is tested as a solution. If they are not solutions, then each option is tested as a path to a solution: it is assumed that the option has been chosen, and each newly available option is tested, and so on. To illustrate this, a very simple maze solution will be shown. We start at A0, and need to get to E4:
A B C D E
0
1
2
3
4
The first choice we come across is at B1: east to C1, or south to B2? Testing each choice gives a clear answer: going east leads us to a dead-end, so south is clearly the answer. Once we get to B2, however, the decision is not so clear: there are three options now, only one of which is a direct dead-end. Going west to A2 is clearly wrong, but east to D2 and south to B3 both give us further options, and so are not obvious dead-ends. However, neither of them is the solution we are looking for (E4) either. This is where the recursive search comes in. First, we test going east to D2: this gives us two options, one of which (east to E3) is a dead end, while the other one (north to D1) gives us two more options. Testing these two options, it is discovered that both of them (east to E0 and north to B0) are both dead ends. Thus, it seems that all the options that become available if we move from B2 to D2 result in dead ends, and this is clearly not the correct answer.
Had we tested the other option (south to C3), we would have been faced with two more options: east to E4 or south to A3. A3 is a dead end, but E4 is the solution we are looking for, and so this is clearly the route to take. Remembering the decisions that we hypothetically made in order to get to E4 (south to B2, south to C3, and then east again to E4) gives us the correct sequence of actions to perform in order to solve this problem.
This very simple maze was solved very laboriously and explicitly, to illustrate how a space-search works, but the problem could conceivably be a lot more complicated (just imagine a bigger maze, for example). However, this method will still work, no matter how complicated the problem is. The general algorithm is: