Using Bugs and Viruses to Teach Artificial Intelligence
By Peter Cowling, Richard Fennell, Robert Hogg, Gavin King, Paul Rhodes, Nick Sephton
University of Bradford, Dept. of Computing, Bradford BD7 1DP.
Black Marble Ltd., Business & Innovation Centre, Angel Way, Listerhills,
Bradford BD7 1BX.
Microsoft Ltd., Microsoft Campus, Thames Valley Park, Reading RG6
Games, Teaching, AI, Virus, Terrarium Academic.
In this paper we wish to add further to the growing body of evidence that games provide a good platform for teaching advanced computing concepts. We describe our experiences of teaching a group of 45 final year undergraduate students at the University of Bradford in the module “Artificial Intelligence for Games”. The students were required to create artificial intelligence for a turn-based board game called Virus, and for a real time artificial life environment, Terrarium Academic. Easy-to-use APIs and sophisticated graphical clients were developed for each game and a server application allowed student AI to compete in a round-the- clock tournament. We describe our experiences in developing and using the Virus game and Terrarium Academic, focussing particularly on what lessons we have learned that could usefully be applied in other teaching that employs games as a medium of instruction. Student feedback, and the quality of student work, suggests that the module was highly successful in its aims, especially in teaching advanced artificial intelligence and programming ideas to students, some of whom were rather nervous about their ability in both of these areas before starting the module.
A significant number of students pursue a course of study in computing motivated in part by their interest in computer games. In spite of a financial structure that keeps rewards for game developers lower than for other computer industries, and a distinct lack of job security, many students desire to join the computer games industry on graduation. Even where students do not wish to become games developers, they are often keen computer (and non-computer) game players. Teachers can tap into this enthusiasm for games in order to motivate students to learn related topics. Since computer games are often at the “bleeding edge” of computer software, using a wide variety of techniques, a very broad range of advanced software topics can be motivated by considering computer games. Moreover, games are starting to be perceived by the research community as a useful test bed for investigating novel AI approaches (Schaeffer 2001) (Laird and van Lent 2001).
Here we will discuss our observations and experience of using games to motivate students in the design and implementation of artificial intelligence techniques. A cohort of 45 students studied for the final year undergraduate “Artificial Intelligence for Games” module at the University of Bradford. This is a fairly large cohort for an entirely optional module, which lends some evidence to the idea that students were interested in the games content of the module. Within the first couple of weeks of the module there was a small increase in the number of students, with students drifting from other options. Content was delivered using only a small number of traditional slides and a lot of discussion of real AI, using the Virus and Terrarium academic platforms to write examples, often in real time within a lecture. The modest size of the cohort allowed for significant and useful question and answer sessions in lectures and this was used extensively. A large number of links and documents were placed in a module web page which was very regularly updated. The module was assessed entirely by two pieces of coursework, described in detail in the following sections. It is arguable that students are also motivated to study courses which do not involve written examinations. However, it was made clear to all students prior to signing up for the option, that the coursework would involve writing two significant pieces of software, and learning a new language, C# (pronounced C-sharp), and development platform, Visual Studio.NET (VS.NET) in order to do this. It was also made clear that all coursework would be marked by a single person, and that all cases of plagiarism would be detected and severely punished. While it is clearly impossible to catch all cases of plagiarism, we have not detected any instances. Student feedback suggests that this up-front attitude to describing the skills required and the ground rules was appreciated by students. Some students were concerned that they did not have the requisite programming and AI skills. These students were simply given further information on the course content and coursework deliverables. Several of the students whose previous marks showed weakness in programming and AI opted to take the module, with most of them doing reasonably well and some achieving excellent results.
The paper is structured as follows. In the next two sections we will discuss the Virus and Terrarium Academic games and the APIs that were developed together with the server which allowed each student’s AI to compete against the other student’s AI and AI written by the instructors. These sections consider students’ feedback and lessons learned which may be of use to other instructors using games as a teaching medium. Finally we give conclusions which highlight the effectiveness and drawbacks of using games to teach AI and programming topics.
The Virus Game
The Virus game is a two player game of perfect information, played on an 8x8 board (as in chess, draughts or Othello). There are two players, black and white, who play alternately, starting with black. Initially the board is set up as in Fig. 1.
Two types of moves are available at each turn. The first type of play involves growing a new piece adjacent to an existing piece of the same colour (Fig. 2). The second type of play involves moving a piece to another square a distance exactly 2 squares away (via an empty square) (Fig. 3). Note that squares are considered adjacent if they adjoin or if they share a corner. In either case all opposing pieces next to the moved piece change colour.
Play continues until neither player can move, or until one player has no pieces left, when the player with the most pieces wins the game.
Teaching Using the Virus Game
The Virus game was chosen as a game with very simple rules, but having complex game play. Whilst it is hard to quantify that complexity, at least in terms of branching factor the Virus game appears to have similar (although arguable higher) complexity than draughts (Schaeffer et al. 1992) and Othello (Buro 2002). The advantage of using the Virus game over better known games is that the opportunity for plagiarism by finding software on the web is eliminated. Indeed checking that the web resources available for the Virus game were limited was an important preparatory step. It also meant that module web pages were able to actively link to selected sources of information on Othello, draughts, chess and other games.
Students were required to write a board evaluation function for use in a search of the move tree. Software for searching the move tree (minimax with alphabeta pruning (Knuth and Moore 1975)) was written, and students had to write a function which returns a value for each position which represents the probability of the black player winning in the given position. Since one requirement was that games between student AI had to run very quickly, the tree was searched to three moves ahead, requiring evaluation of around thirty thousand positions per move in the middle game. Initial concerns from the academics in the team over the speed of C# proved unfounded, and very fast tree searches of a speed approaching that of native C++ code were observed. It proved effective to present this situation to students as “the software looks forward three moves, your evaluation function looks forward the rest of the game”. However, it became apparent after a couple of weeks that there was confusion amongst the weaker students as to whether the evaluation function itself makes a move. A clearer explanation that the evaluation function is but a part of the AI player was needed sooner and more repeatedly. However, all students overcame this misunderstanding within a couple of weeks. To allow a reasonable amount of time per board evaluation and at the same time ensure that games ran quickly on the server, a total of 10 seconds was allowed for each AI player to complete all its moves in a game. Any AI player that used more time than this automatically lost. The aim was to teach students techniques of minimax tree search, positional analysis, pattern matching and evolutionary board tuning by using binary board representations and binary operators such as AND, OR and NOT.
Students implemented their board evaluation function by writing a class MyPlayer which inherited from our VirusPlayer class, and overriding the GetEstimatedScore() function of that class. Although students had little or no familiarity with Visual Studio .NET or C#, since they had previously used the Java programing language, they were all able to handle this and understand the very basic debugging features of VS.NET following a couple of hours of instruction in labs with Black Marble and Prof Cowling. Although several students reported some concern that they would have to learn a new computer language and environment as well as the AI techniques on this module, at the end of the module the students expressed that they had found it useful to familiarise themselves with C# and VS.NET during their degree course, and that it had not slowed them too considerably.
Sponsorship from Microsoft and development by Black Marble made it possible to write a sophisticated client for the Virus game (Fig. 4), which allowed students to learn strategies by playing against each other and against simple AI players. It also allowed students’ AI players to play against each other. There were some issues of trust here, which were presented early on to students, due to the possibility of decompilation for C#. However, once students were made aware of this possibility, they only traded AI players with other trusted colleagues and this does not appear to have caused instances of plagiarism.
Black Marble also wrote a server application for the Virus game, which allowed a competition to run continuously between student AI players, maintaining a league table that permitted students to continuously monitor the relative performance of their AI player against those of the other students. This proved to be a huge motivator for the majority of students, especially since the algorithm for determining which two AI players should play next was designed so that any AI uploaded to the server would get a game almost immediately. This resulted in many students working very hard into the early hours to improve their AI players. Student feedback was very positive on this aspect of the module. AI players were uploaded by FTP. The students could complete a “nickname” field for each AI player, which proved very useful in further raising the interest level of students. The competition for the silliest nickname was almost as fierce as that for the best AI! In addition to student players, the two instructors on the module wrote AI players of varying strengths (some designed to be at the bottom, middle and top of the league). After the first couple of weeks of familiarisation with the module and the environment a benchmark player was added, which simply counted (number of black pieces) – (number of white pieces) and reported the piece advantage of the black player as the position evaluation. Students were given plenty of notice that beating this player would be a requirement for a “pass” in terms of AI performance.
Assessment was 30% for performance on the server and 70% for a short written design document and a printout of source code. A one page document was prepared which described precisely what was required, without giving a restrictive marking scheme. The emphasis of that document was on originality first, league performance second and good software engineering and documentation third.
Over 600,000 games of the Virus game were played on the server over a period of four weeks. It was very satisfying to see the benchmark player start high in the league, descend to mid table after a couple of weeks, and finish rock bottom at the time of coursework submission.
Since software development took place in parallel with teaching, students had to tolerate some uncertainty as development encountered snags. Giving students a complete picture of what was going in when snags occurred arguably increased the enthusiasm and involvement of the student body, as they felt involved in a real development process to create a complex piece of software.
Student coursework demonstrated a lot of originality and coding ideas. One of the pleasant surprises was the emergence of a student “add-on” community, with students creating a test server for local testing of AI players, optimising code for low level bit counting functions, developing a GUI for generating board shapes using the binary representation of the client software, and recreating functions which were in parts of the code not made available to students. Student approaches demonstrated a good deal of originality and insight and included: using very fast bit operators and low level code optimisation for speed, notions of safety, mobility, limited look-ahead, patternmatching, flood-fill, degrees of ownership, positional scores, parameter weighting of features, opening book analysis, biological ideas such as surface are over volume, enclosure, game stage analysis, randomness and terminal node checking. This list cannot do full justice to the effectiveness and originality of student approaches, but should give a flavour. All students submitted a coursework on time and weaker as well as strong students were motivated to do well.
Artificial Life has been an interesting area for the investigation of Artificial Intelligence for some time now, inspired by the work of Conway (Berlekamp et al. 1982), Reynolds (Reynolds 1987) and others. Terrarium is an artificial life environment created by Microsoft developers (http://www.gotdotnet.com/Terrarium), where the aim is to give software agents (which represent bugs and plants) intelligence and effective real time behaviour to survive and multiply in the environment created by other bugs and plants. The software has an interface that renders the Terrarium world observable using rather beautiful animated graphics. Initially it was a spare time project for the developers, but more recently it has been embraced by Microsoft as a .NET sample application, and indeed Microsoft ran a highly successful international Terrarium competition. Terrarium is itself an interesting tool to use directly as a tool for teaching AI in real time environments, but since the Terrarium environment is extremely rich and complex, and significant levels of software engineering skill are needed to understand the API and create effective and original Terrarium bugs, it was considered too difficult for one half of a module given to final year undergraduates in Computing. Moreover, the source code for significant numbers of Terrarium bugs is available on the Internet.
Simplification was needed to the API, and also the measure of success for a bug needed to be simpler, so that observing a bug would more readily give information as to how that bug could be enhanced. To that end, Terrarium Academic was created, by extending the existing Terrarium beta source code (Fig. 5). Terrarium Academic replaced reproduction and the notion of survival of the fittest with a points system that rewarded collection of points from fixed goals (which the creatures had to find) and used rocks to
define a variety of maze-like environments for the bugs so that path finding would be an essential activity for a successful bug (Mika and Charla 2002). Terrain building and loading were added as functions. The dual energy and injury system of Terrarium was replaced by a single system for injury. Finally, plants were regarded as a way to cure injury and were made into indestructible, fixed objects (again to encourage mapping and pathfinding). Each bug in Terrarium Academic is called once per “tick” so that each student bug was required simply to override the DoAction() function of a basic bug object. Students did not have to handle other events. The aim was to teach multi-level planning, rule-based and state-based system ideas, pathfinding, opponent modelling and real-time software agent ideas.
Again, a server application was developed by Black Marble, which functioned in much the same way as for the Virus game, as a Terrarium environment without a graphical representation, that recorded the results of each Terrarium run in an SQL database. An important difference is that each Terrarium game can take several minutes to run, so that students were unable to immediately see the effectiveness of a submitted bug. While students were certainly happy with this setup, many wished for the immediacy of the Virus game server, and this is an issue which it would be desirable to address by allowing bugs to be directly added to the Terrarium environment as they are uploaded to the server.
The course instructors wrote a variety of bugs for students to test against, since observation of their own bugs interacting with other bugs using the graphical Terrarium Academic client proved to be the most effective way of refining bugs.
Students found the Terrarium API much harder to get to grips with than the corresponding API for the Virus game, in spite of our simplifications and instruction. Several approaches were used to aid their understanding, by far the most effective of which was providing students with full source code for four bugs (including one very highly functional bug with mapping and pathfinding capabilities). It was made clear to students that no credit would be given for reproducing the functionality in these bugs, and that they would have to write the action planning code in order to use the tools provided in the bugs given. All of the students used state based and rule based approaches to do this, with most agents having a sensible fixed plan, such as attack any adjacent bug, otherwise go to or search for a goal. Some of the more advanced bugs had more sophisticated strategies based upon a correct supposition that most of the other bugs would have a relatively simple fixed behaviour, using methods designed to beat common behaviour, such as hiding until most bug combat had finished, or searching the map for a secluded spot with a goal in it. All students again submitted coursework, which varied from reasonable to excellent. Student feedback suggested that although all students found this coursework harder than the Virus coursework, they also found it more rewarding due to the obvious link with AI in use in the video game industry.
Student feedback for the Virus game and Terrarium, and the quality of coursework submitted, strongly support the idea of games as a tool to teach advanced AI and programming concepts. Of course, some things could have been done better. Since the application was being written as teaching progressed, refinement of the API was limited, however students obtained excellent knowledge of the process of working with beta code, which changed over time, written by other developers. The time and effort required for this detracted to an extent from the time available for implementing AI. This balance will shift back with recent refinement to the APIs of both the Virus game and Terrarium Academic. Developing support software alongside lectures was time consuming and difficult, but it meant that instructors and developers were very well aware of student problems and issues. Two of the lectures were given over to unscripted question and answer sessions which were a great success given the common issues being faced by students and teachers.
Overall, students appreciated being asked to think creatively “outside the box” and rewarded for creativity, originality and effort in a well-structured coursework. All of the students’ feedback, with one notable exception, was very positive with many comments to the effect that some students found this the most interesting and rewarding experience of their University career. The one exceptional student who vocally protested about the non-traditional methods of the module in a question and answer session found that all of the other students argued very vigorously against this.
We would like to see games used as a medium for teaching AI and software engineering (and other topics) more widely. To this end we aim to make available, free of charge, the clients and servers for the Virus game and Terrarium for teaching use in other Universities and teaching institutions. Please contact Professor Cowling (P.I.Cowling@bradford.ac.uk) for more information. There is the potential for inter-University competition or competition at national and international levels using refinements of the tools described in this paper. We are currently investigating effective ways to set up such competitions.
E.R. Berlekamp, J.H. Conway, R.K. Guy. 1982. Winning Ways for Your Mathematical Plays, Vol. II. Academic Press. Knuth, D.E., Moore, R.W. 1975. “An analysis of alpha-beta pruning.” Artificial Intelligence 6: 293-326.
M. Buro. 2002. “Improving Heuristic Mini-Max Search by Supervised Learning.” Artificial Intelligence 134, nos. 1-2: 85-99.
D.E. Knuth, R.W. Moore. 1975. “An analysis of alpha-beta pruning.” Artificial Intelligence 6: 293-326. J. E. Laird, M. van Lent. 2001. “Human-Level AI's Killer Application Interactive Computer Games.” AI Magazine, Summer 2001.
M. Mika, C. Charla. 2002. “Simple, Cheap Pathfinding.” In AI Game Programming Wisdom, S. Rabin, ed. Charles River Media, Hingham, MA, USA.
C.W. Reynolds. 1987. “Flocks, Herds, and Schools: A Distributed Behavioral Model.” Computer Graphics 21, no. 4: 25-34.
J. Schaeffer, J. Culberson, N. Treloar, B. Knight, P. Lu and D. Szafron. 1992. “A World Championship Caliber Checkers Program.” Artificial Intelligence 53, nos. 2-3: 273-290.
J. Schaeffer. 2001. “A Gamut of Games.” AI Magazine, Fall 2001.
Peter Cowling (http://www.inf.brad.ac.uk/~picowlin) is a Professor of Computing at the University of Bradford. He leads the Modelling Optimisation Scheduling And Intelligent Control (MOSAIC) research centre (http://mosaic.ac), whose main research interests lie in the investigation and development of new modelling, optimisation, control and decision support technologies, which bridge the gap between the theory and practice of optimisation, using artificial intelligence and operational research techniques. These approaches have been used in a variety of real world problems involving the planning and scheduling of personnel and production, in collaboration with commercial and industrial partners. He has sat on the programme committees of over 20 international scientific conferences in the past 5 years, and has published over 40 refereed journal and conference papers.
Peter Cowling has been fascinated by games and game AI since his father bought a Commodore Pet computer in the late 1970s. In addition to the work described in this paper, he is currently investigating generic approaches to game tree search in perfect information board games, artificial intelligence for deck construction and game play in collectible card games and learning approaches for real time video game agents.
He lives in the Yorkshire countryside with his wife and three sons.
Article content copyright © Peter Cowling, Richard Fennell, Robert Hogg, Gavin King, Paul Rhodes, Nick Sephton, 2004.
All content copyright © 1998-2007, Generation5 unless otherwise noted.