[ Jocelyn Ireson-Paine's Home Page | Try Traveller | Traveller for the student | Traveller source | Traveller PHP script ]

The design of Traveller

Traveller arises from a belief that students (and indeed teachers) will find it fun to play with autonomous robots or animals, and to pit them against one another so that the best programmed robot wins. Given suitable graphics, this combines the fun of video-games, computer hacking, and competition in general - and of building working models from kits, a pastime whose fascination is demonstrated by the continuing popularity of Meccano.

Precursors to Traveller

During one course, I experimented with a game which concerned a simple ``mind'', with organs of vision and hearing. This was embedded inside a two-dimensional world divided into small squares, each containing one or more objects. An important part of this game was the world-manager, which translated the current state of the (perceivable) objects into clauses allowed to be called by the mind, and representing its perceptions of sight and sound:
    hear( sentence, [what,can,you,see,now,?] ).
    hear( noise, [loud,bang] ).
    behold( [ [large,tall,green],
              [large,round,red],
              [small,round,brown]
            ],
            /* in square number */ 67
          ).

The ``mind'' itself was written as a predicate reflect which could call the perceptual clauses, decide what to do next (actions included moving, picking things up, and speaking), and finally transmit these actions to its motor effectors. Here the world-manager received them and updated the world state, generating new perceptual clauses for the next perceive-think-act cycle. Such separation of perception, action and thought is no longer fashionable in A.I., but it is a convenient framework on which to base interesting exercises. One of these was built around perceptual classification; given the perceptual clauses, students had to write code for reflect which would infer from the visual features of shape, colour and size, the most likely contents of each square. This was a good introduction to inference methods and expert systems amongst other things.

Another exercise involved comprehension and memory models. The mind had to ``listen'' to a sentence, extract its meaning (either by searching for key words, or by using a DCG grammar to translate into Prolog goals which it could then call), and correlate the meaning with the contents of its memory. Questions could be answered by searching the memory; facts could be tested for consistency with what was known, their truthfulness reported on, and the fact asserted if deemed to be true.

This approach can be taken far, provided that there is enough C.P.U. time to simulate the world, and that the graphics can display the world and mind in an appealing and comprehensible form. The ultimate is to build a complete artificial agent, complete with physiology, memory and perceptions, plus the intelligence to handle and resolve goals, drives, and plans. To some extent, this has been tried already - see [Mauldin et al. 1983,Coderre 1989,Travers 1989] - but such attempts stop far short of what can be done.

Traveller has been influenced by such ideas, but also owes much to a game developed at Xerox Palo Alto Research Centre to teach programming in LOOPS.

Truckin'

LOOPS is a ``multi-paradigm'' toolkit implemented in Lisp, providing rules and object-oriented programming as well as procedural programming. What concerns us here is its use in teaching an expert systems course at Xerox Parc [Stefik et al. 1983]. This was intended for professionals who wanted to learn about building expert systems. To motivate them, making the course fun as well as useful, the authors borrowed from a study on what makes games fun to play [Malone 1981].

The authors considered various designs, all centered around ``intelligent'' agents which could be programmed in LOOPS, and then left to compete with other agents in some kind of simulated world. One possible design was a video-game, perhaps rocket ships with LOOPS programs controlling thrust and phasers. This was rejected because it would require too much C.P.U. power, and also because it does not connect with the real world. This is an important pedagogical principle: students will find their agents easier to program if they can induce rules from their own experience, so the game should involve familiar situations. After considering Monopoly, the authors settled on a game of buying and selling. The players would simultaneously drive lorries around a board marked with shops, fuel stations, weighbridges, pot-holes, speed-traps, bandits and other hazards and resources. Their job would be to plan routes and make a profit, while employing enough intelligence to buy fuel when necessary, not drive too fast past speed traps, avoid bandits, and so on.

Goal conflicts were designed into the game. A lorry going too fast over a bumpy road might damage the fragile items it was carrying. Perishable goods, such as fruit, must be delivered quickly; but going too fast past a speed-trap would result in a fine, as would trying to carry too heavy a load over a weigh-station.

Inevitably, some players' lorries were not programmed as well as one might hope, and a number of amusing errors resulted:

Traveller

Truckin' was a great success, with the players often identifying closely with their artificial partners, so it was natural to use it as a starting point for Traveller. One feature I wanted to keep was that the game should be laid out in space, and should involve some kind of network, such that you could only get from A to B if they were connected. There should also be a notion of distance between points, because it can be tied to properties like speed and fuel consumption.

The spatial aspect makes it easier to visualise how the board-description facts work, and makes them less abstract. Having routes and connections means that one can introduce A.I. concepts such as path-planning and search methods, as well as the notion of a list for holding routes. It also provides material round which to build constraints, for example the closed loop without fuel stations mentioned above, and the dead-end which though superficially attractive because it houses many cheap shops, draws you away from the board's main profit centres.

One thing lacking from Traveller's world is discrete objects that can be picked up and put down. It would be nice to include these, because one could then move into blocks-world planning, and also introduce an object-classification hierarchy, thus giving students experience of a powerful A.I. technique. Such a hierarchy is little use in Traveller as it stands because there are no generic values common, say, to all coal shops or all shops. Each shop, for example, sets its own price. However, I have not managed to find a convincing way to integrate objects, even those as simple as in the blocks world, with Traveller. Doing so would need a more detailed model of space: for example, some area around the shops where crates could be stacked. One would also have to model space inside the lorries. Rather than distort Traveller in this way, I have retained the caves world, and have also experimented with a treasure-hunt game.

An immediate limitation was the moronic graphics provided on our VAX; it is impossible to paint a picture of the board using the 80 by 25 screen on a VT100 or compatible terminal. Truckin's appealing screen layout, wherein little icons race round a game board on which insets show the prices of commodities, and on which gauges display the level of fuel, had to be dropped in favour of plain teletype-style output.

I also had to consider the Tutor's limitations. It must be feasible to write sensible rules using only the number editor, so no clause should contain more than about 5 goals. The state of a player, represented as facts, should occupy no more than about 10 lines, so that it could be understood quickly while reading the textbase version of these facts, and could be easily summarised in English. Moreover, it should be possible to write some kind of agent using only a subset of these facts, as I do in the current supplement; and to do so without needing a route-planner. This is the reason for clockwise, the closed loops, and Colliery Row. Even within these constraints, the environment should be rich enough so that stupid traders will not survive.

A more general design point was that the problems and rewards imposed on players should arise naturally from the structure of the environment. An analogy can be made here with fiction. There are many fantasy series, loosely patterned after Tolkien, in which the hero finds himself persued for no particular reason by a succession of dwarves, dragons and dinosaurs until, tiring of the writing, the author allows him to achieve his goal: usually some magical device which will save world, hero, and the author's bank balance. Neither the goal nor the threats grow naturally from the universe: instead, they are ``plot coupons'' [Sterling 1990] dropped in from outside. This contrasts with the careful physical and sociological world-building performed by good authors, in which threats, goals and goal conflicts are a logical consequence of the universe's laws of nature and the characters' mentalities. For example, in Traveller and Truckin', we want something in the environment which, if not placated every so often with money, will remove a player from the game. This enables us to introduce a goal conflict which players must resolve: do you spend money to make a profit, or to ensure your continued existence? Introducing fuel stations allows us to implement such a financial imposition without being arbitrary. This design principle is not stated in the Truckin' paper (though Truckin' does not violate it), and is worth mentioning here for the benefit of other designers.

The same principle can be applied at a higher level, to the structure or ``plot'' of the Prolog course as a whole. Exercises set for the student should not be arbitrary, but should again appear to arise as a natural sequence of problems to be solved. This principle conflicts with the need to show Prolog in a variety of different settings; I have tried to follow it in these lessons by using Traveller and the caves world as environments in which successively more complex objects and actions can be constructed.

I end this section with some references. We could view Traveller as a ``microworld'', a ``province of Prolog-land'' in which students have to learn Prolog in order to survive (or to teach their players to survive). According to Seymour Papert in his book ``Mindstorms'' [Papert 1984], to put students into such worlds is a very effective way of helping them learn: Papert has experimented with turtle graphics and Logo in order to construct a ``maths microworld'', and some of his insights are relevent to the design of games like Traveller. To make such games interesting and challenging, we do not want to make them too easy. Whereas most software is designed to be easy to use, games should present some difficulty, so we must violate some of our usual design principles! This is an interesting twist on the usual process of design, and is discussed further in [Norman 1988]. A reference mentioned earlier, [Malone 1981], discusses what makes games fun to play.

The Traveller board

The present board layout was adopted for the reasons listed below. It has benefited from some useful discussions with Johann Butting.

Colliery Row

It is easy to get students started here, since there is only one type of shop, so fewer decisions need be made. COLLIER2.LOGIC is a simple coal-trader. Running this for a long time, or working out average accounts from the prices, will show that coal-trading is not quite profitable enough to cover the cost of fuel, thus motivating students to try trading in other goods.

Beverly Hills

A high-profit loop: diamonds and glassware. But since there are no fuel stations, a simple-minded agent may get stuck in a tight loop, not realising it has to leave to refuel.

In fact, the current fuel tank size is 20, which renders this area a trap anyway: agents that scan the board for the highest profit area will enter Beverly Hills and run out of fuel before having both bought and sold their diamonds. However, if we increase capacity to 26 or more, a skilled trader can make a quick run from RideRite (or even Pirana's), grab some easy gains, and scoot back. A not-so-smart trader will still run out.

The Hub

A medium profit loop, easier than Beverly Hills, since there are fuel stations (though Pirana's should be avoided, since it will cost more than the average profit).

The link between The Hub and Beverly Hills

Running down into Beverly Hills may be useful for a quick profit. However, a trader that grabs everything it sees on the way will fill its lorry with coal, thus leaving no capacity for trading in Beverly Hills.

The Plain

No shops here. But the cheap fuel and goods on the radiating cul-de-sacs may entrap the unwary into unnecessary purchases, and may even lure them to a stop if their route-planning is bad.

In one version of the game, the start is one from the end of the southern road off the Plain, forcing beginning traders to pass these lures.

The long Eastern tail road from Collier's Row

This contains several traps. There is a tempting sequence of TV sellers, but no-one to buy: the naïve may waste capacity with unsaleable televisions.

The long run between the high-profit diamond seller and buyer may cause incompetant traders to run out of fuel.

If the game is modified to make fruit perishable, this may go off in the long distance between Pippin's and First Fruits.

Scargill's may tempt coal-traders out of Colliery Row and leave them unable to get back.

I also designed the layout so it would look reasonably attractive, if drawn with the diagonal lines replaced by quarter circles, and with the board oriented so the Hub is top left, with Beverly Hills below it and Colliery Row on its right.

Prices and unit volumes have been chosen so that unintelligent traders will not succeed. Assuming, as currently in TRAVELLER.PL, that the starting cash is £ 5000 and the maximum load is 1000 cubic feet, then the average cost of fuel per station is somewhere round £ 40; £ 80 as in Pirana's, is definitely high. With this, one spends about £ 320 going round one of the loops. Apart from the Plain, they are all the same size.

The average profit on coal is such that it is less than the average cost of fuel. Coal is superficially tempting, because it is cheap and has a large profit margin, but it is no good for long-term gains.

One can, as things stand, make a profit on televisions and glassware. However, the average profit is not far above the cost of fuel for a loop, and chance events such as truck repairs (compare street repairs in Monopoly) can easily wipe out these profits. Thus diamonds are the only sure thing. They are expensive though, and one must maintain a high level of funds to start trading.

Variations on the theme

The game design means there are no problems concerning object sizes or shapes. In a more realistic game, where objects were not simply dimensionless points, we would have to worry about simulating impacts, transmitted forces, motion past obstacles, and so on. This can be done - the Oxford Robotics Group has developed programs for simulating the movement of two-dimensional robots within a crowded environment - but it doesn't add much to this kind of game, since the activities - buy, sell, move one square - are so ``symbolic''. The discrete nature of the board simplifies matters even more. One could envisage a scenario in which though still dimensionless points, objects were allowed to move into any position on the board, or at least any position on a road. This would make path planning much less symbolic; such a game might offer a convenient environment for simple autonomous guided vehicles, controlled perhaps by neural networks, but would lack a convenient framework on which to hang the tasks I'm concerned with, such as route-planning by depth-first search.

Even within Traveller's universe, there are many possible variations. move can be allowed to move more than one unit; goods can be made to perish if kept too long or to break if moved too fast. Shops and fuel stations can be allocated finite reserves, so that after a time, the high-profit loops become deserts. Lorry drivers could suffer from fatigue and hunger, having to take rest- or café- stops to keep going. Road closures could be introduced, so that traders suffer unless they update their route plans periodically.

Knowledge of the board could be limited; instead of having access to all the clauses defining the map, traders would have to gain knowledge by exploration, building up memory models piecewise. Perception could be introduced; instead of getting a complete symbolic description of the contents of a square, traders might only ``see'' particular features, from which they would have to infer the contents. Prices could vary, and the range of goods be increased. One possibility would be to control traders using a production system - see, for example, Chapter 6 of [Scott and Nicolson 1991]. This would make a nice demonstration in cognitive science.

Boards could be generated dynamically, so that traders must work out for themselves where the good parts of a board are, instead of having the knowledge programmed in advance. We are now well into Artificial Intelligence, when considering a trader so general that it can cope with any board layout, with defective or ambiguous perceptions, and with dynamically varying road layouts.

Finally, we can introduce competition, with several players running ``concurrently'' on one board (this is one reason for the T argument to the predicates). There are various ways of picking the winner: the trader who survives longest; the trader who has the greatest assets after a given number of cycles; or the trader who wins a race to the winning post.

References

Coderre 1989
Bill Coderre, Modeling Behaviour in Petworld, from Artificial Life, Christopher G. Langton, Addison-Wesley, Reading, Massachusetts, 1989, ISBN 0-201-09356-1.

Sterling 1990
Bruce Sterling, A Workshop Lexicon, from Interzone, September 1990, ISSN 0264-3596.

Mauldin et al. 1983
Michael Mauldin, Guy Jacobson, Andrew Appel and Leonard Hamay, ROG-O-MATIC: A Belligerent Expert System, Technical Report CMU-CS-83-144, Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, 1983.

Malone 1981
T. W. Malone, Towards a Theory of Intrinsically Motivating Instruction, from Cognitive Science, volume 3, number 4, 1981.

Norman 1988
Donald A. Norman, The Psychology of Everyday Things, Basic Books, New York, 1988, ISBN 0-465-06709-3.

Papert 1984
Seymour Papert, Mindstorms, Harvester Press, Brighton, 1980, ISBN 0-71080-472-5.

Scott and Nicolson 1991
Peter J. Scott and R.I.Nicolson, Cognitive Science Projects in PROLOG, Lawrence Erlbaum Associates, London, 1991, ISBN 0-86377-182-3.

Stefik et al. 1983
Mark Stefik, Daniel G. Bobrow, Sanjay Mittal and Lynn Conway, Knowledge Programming in Loops: Report on an Experimental Course, from The AI Magazine, Fall 1983.

Travers 1989
Michael Travers, Animal Construction Kits, from Artificial Life, Christopher G. Langton, Addison-Wesley, Reading, Massachusetts, 1989, ISBN 0-201-09356-1.

1st November 2008.