Programming Antiobjects 18-2

6m ago
6 Views
0 Downloads
2.68 MB
12 Pages
Last View : 14d ago
Last Download : n/a
Upload by : Bennett Almond
Transcription

Collaborative Diffusion: Programming AntiobjectsAlexander RepenningAgentSheets Inc & University of ColoradoBoulder, Colorado, [email protected] INTRODUCTIONObject-oriented programming has worked quite well – so far.What are the objects, how do they relate to each other? Once weclarified these questions we typically feel confident to design andimplement even the most complex systems. However, objects candeceive us. They can lure us into a false sense of understanding.The metaphor of objects can go too far by making us try to createobjects that are too much inspired by the real world. This is aserious problem, as a resulting system may be significantly morecomplex than it would have to be, or worse, will not work at all.We postulate the notion of an antiobject as a kind of object thatappears to essentially do the opposite of what we generally thinkthe object should be doing. As a Gedankenexperiment antiobjectsallow us to literally think outside the proverbial box or, in thiscase outside the object. This article discusses two examples, aPacman game and a soccer simulation where antiobjects areemployed as part of a game AI called Collaborative Diffusion. InCollaborative-Diffusion based soccer the player and grass tileagents are antiobjects. Counter to the intuition of mostprogrammers the grass tile agents, on top of which all the playersare moving, are doing the vast majority of the computation, whilethe soccer player agents are doing almost no computation. Thisarticle illustrates that this role reversal is not only a different wayto look at objects but, for instance, in the case with CollaborativeDiffusion, is simple to implement, incremental in nature and morerobust than traditional approaches.Overall, object oriented programming has worked very well. Afterearly concerns about performance the intuitive appeal of objectoriented programming concepts has literally changed the way wethink about programming. Over time object orientation hasmigrated from an art mastered only by early hacker typeprogrammers using object extensions to Lisp or using Smalltalk toa more mature engineering discipline. Intangible design intuitionhas been gradually replaced with more principled approachesculminating in the unified modeling language (UML). All this hasled to a strong sense of what objects are and what they should bedoing. Once we know what the objects are and how they related toeach other we typically feel confident to design and implementeven the most complex systems. However, objects can deceive us.They can lure us into a false sense of understanding. Themetaphor of objects can go too far by making us try to createobjects that are too much inspired by the real world. This is aserious problem as a resulting system may be significantly morecomplex that it would have to be, or worse, will not work at all.Categories and Subject DescriptorsD.1.3 [Programming Techniques]: Object-oriented ProgrammingGeneral TermsAlgorithms, Performance, Design, Reliability, Human Factors,Languages, Theory.KeywordsObject-Oriented Programming, Psychology of Programming,Collaborative Agents, End-User Programming, Diffusion, GameAI, Incremental AI, multi-agent architecture, Distributed ArtificialIntelligence.In teaching we can observe the kind of thinking going on innovice programmers learning about object-oriented programming.I have been creating objected-oriented programming languages[22], using and teaching object-oriented design long enough to geta sense on how people conceptualize object-orientedprogramming. In my game design and development coursesstudents are learning about game design and development bybuilding weekly games using AgentSheets [23]. We start withclassic applications including Frogger, Sokoban and SpaceInvaders. Students have access to reference material includingdetailed game descriptions found in the Wikipedia.Sokoban is a simple game in which a person needs to push boxesonto targets. What makes Sokoban interesting is that the personcannot pull boxes. If a box is pushed into a corner the game islost. At advanced levels Sokoban can be surprisingly intricaterequiring players to carefully plan their moves. Figure 1 shows agraduate student level 1 implementation of the game.Figure 1. Sokoban Student Implementation. The Smileyperson can only push boxes. Boxes need to be moved ontotargets.

Part of the homework is to draw UML diagrams illustrating thebasic game action. The sequence diagram below shows onesituation in which the player is trying to push a box to the rightonto an empty tile. When asked about the homework – aftergrading – some students indicate that drawing the UML diagramshelped them thinking about the game but the large majority of thestudents confesses that they made the UML diagrams afterfinishing the game. A large percentage of the students in thesecourses (computer science graduate and undergraduate students)has taken Object-Oriented Design course. Interestingly, if theyhave taken an OOD course played no significant role in theirdecision to use UML diagrams either as thinking tools – beforeprogramming – or as means of documentation, afterprogramming.Figure 2. UML sequence diagram of person pushing box rightonto empty tile. The person makes the box check if it canmove. The box can move. It will move itself and the person.Up to this point in the progression of increasingly complex gamesobject-oriented design techniques have worked well. Students hada good intuition helping them to identify what the objects shouldbe and how these objects should interact with each other.Next students need to implement a game in which agents arepursuing each other through a complex world such as a maze. Asophisticated version of a tracking-based game would be a gamelike the Sims [32] where people agents are tracking other agentssuch as food or other people agents. A much simpler version ofsuch a game would be Pacman where ghosts are trying to catchthe user-controlled Pacman. To test students design intuitions wewould show them a specific scenario in a Pacman game in whicha ghost agent would try to tackle the Pacman.Figure 3. Ghost tries to pursue Pacman. Which way should itgo and how should we program this?The ghost finds itself on the other side of the wall (Figure 3). In aEuclidian sense the ghost is very close to the Pacman. In atopological sense the ghost is far away. The question at this pointto the students is: how would you program this game? How canthe ghost track the Pacman. Here are the categorized answerssuggested by students:1)Brownian Motion: the ghosts should move around randomly.At each step in the game the ghost re-evaluates all the placesit could go that are one step away. It will then pick one placerandomly. Sooner or later they will find the Pacman. This isa very simple strategy to implement. Many games actuallyuse this strategy. Problems: players will interpret the randomwalk as such. The ghosts do not appear to be intelligent at all.2)Point and Shoot: the ghost selects a random direction andkeeps moving in that direction until it hits an obstacle. At thispoint it determines a new random direction. Problems: Whilethe ghost appears to be less random than in approach #1 itstill does not come across as intelligent because there is agood chance it will move in obvious ways away from thePacman.3)Incremental Approach: the ghost should try to move closer.This also is done incrementally. At each step in the game theghost will explore all the places it could go and select the onethat is closest (in the Euclidian sense). Problems: This ideadoes not take obstacles into account and as such can beineffective. In the situation in Figure 3 the ghost would bestuck at its current location because moving left of rightwould increase its distance to the Pacman.A brief discussion of trade offs of each approach typically leads toa discussion how these ideas could be combined:2a) Smart Point and Shoot: The ghost selects a direction aimingat the Pacman. If the ghost hits an obstacle it will re-evaluatethe direction to the Pacman again. Problems: If the directionis the same as the current direction the ghost gets stuck.3a) Incremental Approach with Trap Detector: If the ghost getsstuck by minimizing Euclidian distance it should change itsstrategy and pick a random direction. Problems: Withoutremembering where the ghost has been it will be difficult tomake the decision when to switch back and forth betweenincremental approach and random move.Object-oriented design just trapped us. The kind of discussionmentioned above can last for quite some time. As the discussionprogresses it becomes clear to the students that while someapproaches work better than others none of these ideas work well.After all, if there is a way from the ghost to the Pacman then theghost should be able to find it. Instead, ghosts will wander aroundand get occasionally stuck. However, the direction of explorationappears to be clear. Better solutions require more sophisticatedprogramming of the ghost. The ghost just needs to do a bettersearch by having a more complex state, more methods, and moresophisticated ways to parse the scene. Perhaps all we need to do itto add a few transitions to our current UML diagram – or perhapsnot.The psychology of programming attempts to explainprogrammer’s intuition. Syntonicity [31] is an introspectivebehavior that makes us want to be the ghost in order to thinkabout what the ghost should do and how it should do it. Moregenerally, body syntonicity makes programmers explore ideas thatare compatible with their own feeling of being in a body. Whatwould I do if I were this ghost?

From the viewpoint of a problem solving design space we havebeen lead to a local maximum. We found a solution that kind ofworks just not very well. The Pacman example of course onlyserves as illustration of the effect. After all, our goal is probablynot to make the world best Pacman game. However, even in gamedesign this more general pathway search problem is real andimportant. Of course there are well known solutions to solve theproblem. A* algorithms [6] for instance do a good job at least tofind non-moving targets.This breakdown prompts us to think about reconceptualizing theproblem. Perhaps it is not really the ghost agent that should bedoing the heavy lifting at all. Perhaps the background tiles, whichup to this point, we only considered to be passive backgroundobjects, i.e., decoration, with no behavior whatsoever should helpsomehow with the search. This is a case for antiobjects. As weshall see later, by removing computation from the agents thatappear to do the search (the ghost) and redistributing it in aparallel fashion to the agents that define the space to be searched(the background tiles) we get a solution that is remarkablyeffective yet simple to implement. The challenge to find thissolution is a psychological, not a technical one. An approachcalled Collaborative Diffusion will be described in detail in thefollowing sections.The ghost and floor tiles are examples of antiobjects. If there issuch as notion of background and foreground we tend to think ofthe agents such as the floor tiles as background while the ghostagents are part of the foreground. Yet, as antiobjects their rolesare reversed. The background does most of the work, theforeground just needs to react in simple ways to the computationof the background. This runs counter to our body syntonicexperience. When we think of the Pacman game and think aboutobjects such as floor tiles we do not envision any computation.We know, floor tiles do not compute in the real world, why shouldthey in our game world? This is a hard question and perhaps thesimplest answer is because they can. If we would build a physicalembodiment of a Pacman game we would have a robotrepresenting the ghost. Even if we wanted to, in the physicalworld we could not easily add computation to objects such asfloor tiles. All we can do is to make our ghost robot really smartand equip it with good sensors.In addition to reversing roles antiobject also distributecomputation differently. The apparent computational intelligenceof a single agent, for instance the ghost’s ability to track down amoving target, is distributed to a potentially large set of agents.Instead of having one ghost doing the work, all floor tiles need toengage in highly parallel computation. As we shall see in theCollaborative Diffusion based Pacman implementation the floortiles effectively diffuse the smell of the Pacman. All the floor tilesparticipate in a highly parallel diffusion computation. Meanwhile,the ghost agents can engage in simple hill climbing.Computationally speaking the floor tile antiobjects are doingpractically all the work while the ghost antiobject is doing almostnone.We will claim in this paper that antiobjects work very well forCollaborative Diffusion, which is a general framework that can beapplied to many game applications. Beyond the many simulationsthat we have built using Collaborative Diffusion ranging from AIpathfinding, bridge construction design and soccer simulations tothe simulation of electric systems we have also successfullytaught the use of antiobject to students. We started with teachinggame design and development to graduate and undergraduatecomputer science students. Each time we faced that difficultmoment to make the transition from what students intuition was tohow we need to reconceptuallize the problem completely in orderto solve it. Using UML diagrams did not help with this transition.However, once student made this step they have createdwonderfully complex games with amazingly little effort. As wekeep teaching we gradually introduced new visualizationtechniques to better illustrate the nature of antiobjects. Instead ofusing traditional debugging techniques such as method tracing wehad to built tools that would be able to visualize in real time 3Dplots superimposed over the game world. Using these techniqueswe tried to push the idea of antiobjects even further by trying tohave kids in middle school to build AI-based games involvingantiobjects. To our amazement that worked out well. Not onlywere we able to teach 11 year old middle school kids to createCollaborative Diffusion based games but the few kids that wereintroduced to the technique showed their friends how to do thesame.The following sections describe Collaborative Diffusion as anexample of programming antiobjects. Antiobjects are a means toreconceptualizing computation. However, in addition to beingdifferent we will show that in the context of Game AI antiobjectsexhibit a number of positive characteristics includingeffectiveness, incrementalism and robustness. To be able to makethese points we will move from the more philosophical treatmentof objects in this introduction to a more technical discussioncomparing Collaborative Diffusion to related work in ArtificialIntelligence.2. ANTIOBJECTS & GAME AIFor some time now games have served as an ideal test bed toexplore computational intelligence [24] and as motivationalcontext for object-oriented design classes. As many have pointedout, the game industry is approaching the size of a multi-billiondollar movie industry. Games such as Halo 2 and Doom III havereached levels of colossal complexity. Hardware is advancingquickly as well. One of the next generation game consoles, theSony PlayStation 3, is expected to deliver close to two Terra Flopsof computational power. However, most of the computationalpower seems to be spent in either rendering complex scenes withextremely large polygon counts or computing physics. Beforelong, the rendering quality of games will produce photorealisticimages that will be hard to differentiate from reality. But, whatabout Artificial Intelligence in games? The AI exhibited by manymodern games is considered weak AI [25] in the sense that it ismostly concerned with practical engineering approaches to makemachines appear to be intelligent without necessarily employingsophisticated computational schemes. Particularly weak arecurrent implementation schemes involving multiple agentscollaborating and competing with each other. This paper exploreswhy it is hard to build collaborative agents and introduces theCollaborative Diffusion framework addressing these issues.A quick survey of game developer resources indicates a richpresence of AI related topics. Numerous books, e.g., AI for GameDevelopers [3], and websites, e.g., gameai.com, are dedicated towhat is colloquially called Game AI. Discussions found there aretypically covering a spectrum ranging from simple state machinebased AI, over path finding to learning. There is surprisingly littlecoverage on general techniques that could be used to implementcollaborative and competitive multi agent games. One possibleexplanation is that the apparent complexity of collaboration AIschemes found in academic research is simply exceeding the

general scope of game AI. In other words, it may simply be toohard to transfer academic research approaches dealing withcollaborative agents to the more pragmatic world of game AIbecause of practicality issues. Additionally, it may also bepossible that game contexts may impose additional constraints andcause scaling challenges difficult for existing AI approaches todeal with. These concerns are the motivation behind our approach.Instead of conceptualizing Game AI as the pragmatic cousin of AInew frameworks directly relevant to games must be explored.Despite this focus on games many of the findings will be relevantto general AI. Games are more than just test beds for AIapproaches; they also become a conceptual development spaceyielding new notions of computational intelligence that can betransferred, for a change, from Game AI to regular AI.Compared to rendering and physics simulation, Game AI hasmuch room for improvement. Players are beginning to demandmore refined game play based on sophisticated AI. Some of themost frequently played games today are based on the idea that theplayer is manipulating a game character, through first or thirdperson view, exploring some intricate space populated with“enemy” agents. As part of a mission the player needs to reach avariety of goals also located in that space. The enemy agents willtry to prevent the player from reaching said goals by trying toblock ways, wound or even kill the player. The player, in turn, hasa repertoire of weapons that can be used to eliminate enemies.What is missing in this type of game is collaborative andcompetitive behavior. The AI found in most is by no meanstrivial. They can locate the player and put up the right level ofresistance making ultimately a game fun to play. However, theirbehavior, with few exceptions, is overly autonomous. They aretypically not collaborating with other enemy agents in noticeableways. Collaborating enemy agents would make the game playmore interesting. The player will get the opportunity to deal withmore complex levels of behaviors not only at the level ofindividual enemy agents but also at the level of group behaviors.Especially in game contexts this collaboration-based enemy agentadvantage will have to be managed carefully. After all, a gamefeaturing agents that are so smart that they immediately beat theplayer would be an aggravating game playing experience. Tobalance game play again in favor of the player additional agentscould be introduced to a game collaborating with the player andcompeting with enemy agents.Collaborate Diffusion is a framework based on antiobjects thatcan be used to build games with large numbers of agentscollaborating and competing with each other. One particularlyattractive characteristic of Collaborative Diffusion is how itssimple implementation results in sophisticated emergent behavior.Figures 11-13 show collaborative behaviors in the context of asoccer game. Players from the same team are truly collaboratingwith each other and competing with all the members of theopposite team. For instance, if there is a player in a better positionthan a player covered by an opponent player, the covered playerwill pass the ball to that other player of his team. An intriguingaspect of this behavior is that it had not to be “programmed” intothe agents but, instead, was an emerging property of the soccerCollaborative Diffusion process. The soccer game only serves asan example exhibiting collaboration and competition. Theapplicability of Collaborative Diffusion is not limited to soccerlike games or even games in general. Collaborative Diffusion hasbeen applied to various complex optimization problems includingapplications such as bridge design [23], mudslide, electricalcircuits, avalanche and traffic flow simulations. Common to all ofthese applications is the process of diffusion.Architecturally speaking, antiobjects and Collaborative Diffusiongrew out of some of our multi-agent scientific simulations runningon a Connection Machine CM-2. Powered by sixty four thousandCPUs connected through a twelve dimensional hypercube theConnection Machine achieved unprecedented performance ofabout 2 Giga Flops. Much more important, from today’s point ofview, than computational performance were the conceptualinsights gained from using the Connection Machines. The idea ofmassively parallel problem solving provides radically differenceperspectives that can lead to new conceptual frameworks.Antiobjects, an example of such a framework, clash withtraditional notions of object-oriented design in the sense thatobject-orient design does not help with the understanding or useof these new computational frameworks.Today, thanks to the rapid advance of hardware, these frameworkscan be implemented on more traditional sequential architectures.Ultimately, CPU cycles will always become cheaper thancognitive cycles. Just a couple of years ago CollaborativeDiffusion would not have been computationally feasible to buildconsumer oriented games capable of running on desktopcomputers. Now that a 400 PlayStation 3 roughly has thefloating-point power of 1000 Connection Machines we can allowourselves to reconceptualize computation.3. BASIC DIFFUSIONCollaborative Diffusion is a versatile collaboration andcompetition framework for building multi-agent games based onantiobjects. Agents such as the ones used in AgentSheets [23] livein a space (2D or 3D). Typically, the space is organized as a gridsimilar to a spreadsheet. The grid contains agents representinggame characters, e.g., soccer players, but also the environmentcontaining these characters, e.g., the soccer playfield. Agents maybe stationary or mobile. To collaborate and compete with eachother, character agents, as well as environment agents, jointlyengage in one or more diffusion processes.Game design patterns [2] help to conceptualize agent behaviorsfor typical game applications. Common to many games is thenotion of pursuit and evasion. In Pacman ghost are pursuingPacman, in the Sims, Sims characters are pursuing other sims,sources of food, entertainment, and so on. Agents participating inpursuit can be categorized into the following roles:1)Goal Agents: Goal agents are pursued by other agents. Goalagents may be static or mobile. For instance, a refrigerator isa static goal, typically located in a kitchen, pursued by anagent representing a hungry person in a “The Sims”-likegame [32]. A soccer ball, in contrast, is a mobile goalattracting soccer players.2)Pursuer Agents: One or more pursuer agents may beinterested in certain goal agents. Multiple pursuer agentssharing interest in the same goal may collaborate or competewith each other. If there are multiple types of goals, such asfood, and entertainment, then the pursuer agent includes agoal selection mechanism determining the priorities of goalsbeing pursued.3)Path Environment Agents: A path environment agentenables a pursuer agent to move towards a goal agent. In ahousehold simulation a path environment agent mayrepresent a kitchen tile, or a piece of carpet. A pathenvironment is an active agent participating computationallyin the diffusion process that is helping pursuer agents tolocate goal agents.4)Obstacle Environment Agents: Like path environmentagents, obstacle environment agents are part of anenvironment but they deter pursuer agents from reachingtheir goals. Walls, closed doors, fires, fences, and rivers canall interfere with the pursuer’s attempt to reach a goal.Interference can be at different levels. A wall may

permanently prevent a pursuer from reaching its goal while apiece of furniture in the middle of a room may just pose asimple delay caused by the need to navigate around thefurniture.This categorization scheme can be applied to nearly all arcadestyle games ranging from early classics such as Space Invaders,and Pacman to modern titles such as Halo 2 and Doom III.Although the agent categorization scheme is mostly relevant togames the Collaborative Diffusion framework can be applied to amuch wider domain of applications.constant value. This value represents the desirability of a goal.High desirability is captured with a large value (e.g., 1000).Desirability may also assume negative values. Pursuer agents willactively avoid goals with negative desirability. This attribute willbe diffused through the floor tile agents using a discrete version ofthe well-known general diffusion equation [8]:Equation 1: Diffusion Equationnu0,t 1 u0,t D# (ui,t " u0,t )i 13.1 Single DiffusionA game is built by defining the four kinds of agents describedabove and arranging instances of them in a grid-structuredworksheet. The worksheet shown in Figure 4 contains a matrixconsisting of 9 rows x 9 columns of floor tiles serving asenvironment path agents. All examples, including the diffusionvisualizations shown here are built in AgentSheets [23].A single Pacman will be the single goal agent located in the centerof the worksheet. The Pacman is a user-controlled agent pursuedby all the autonomous ghost agents.!where:n number of neighboring agents used as input forthe diffusion equationu0,t diffusion value of center agentui,t diffusion value of neighbor agent (i 0)D diffusion coefficient [0.0.5]The diffusion coefficient controls the speed of diffusion. A largervalue will result in quick diffusion. In material science eachmaterial has a specific heat diffusion coefficient. Silver, forinstance, has a much larger heat diffusion coefficient than athermal insulator such as wood. Consequently Silver will spreadheat much more rapidly than wood.In a two-dimensional application the input is limited to the fourimmediate neighbors defined by the von Neumann neighborhood[28]. The Environment Path agents consisting of all the floor tileswill now each compute the diffused values of Pacman scent p.Figure 1 shows a logarithmic 3D plot of the p values over the areaof the entire worksheet. The peek in the middle correlates with theposition of the Pacman and has a value of 1000.In the two-dimensional case, and with von Neumannneighborhood, a diffusion coefficient value of 0.25 represents aspecial case that further simplifies the diffusion equation. ForD 0.25 a new diffusion value u will simply become the averagevalue of its neighbors without even the need to refer to its ownprevious value. This is useful for quick spreadsheet-basedexperimentation.Figure 4. Worksheet with 9 x 9 floor tile agents and onePacman agent in the center. The Pacman “scent” is diffusedby the tile agents. The diffused value is shown as logarithmicplot over the worksheet area.Diffusion is a gradual process in which physical and conceptualmatter, such as molecules, heat, light, gas, sound, and ideas arespread over an N-dimensional physical or conceptual space overtime. Alan Turing was one of the first researchers to note thebroad impact of diffusion processes onto chemical and biologicalphenomena and became the first serious user of an electroniccomputer in order to model these diffusion processes [30]. He wasinterested in mathematically capturing reaction-diffusion systemsand defined diffusion to occur when “each [chemical agent]moves from regions of greater to regions of less concentration.”Agent-based diffusion has been used in a number of applicationsincluding image feature extraction [14] and more recentlydistributed optimization [29]. Collaborative Diffusion does notdiffuse discrete objects, i.e., agents, but uses agents to diffuse,track and modulate continuous diffusion values.Diffusion values are used to spread the “scent” of the Pacmangoal agent in the worksheet. The Pacman agent is given anattribute called p short for Pacman scent with an arbitrary butUsing a simple hill-climbing [7] approach, the pursuer agentstrack down the Pacman. Each pursuer agent compares thediffusion values of its four von Neumann neighbors and moves tothe neighbor cell with the largest value.So far this approach would not provide a significant advantage tomore traditional tracking approaches. For instance, a pursueragent could have determined the location of the most promisingneighbor by computing the Euclidian distance from each of theneighbors to the goal and then selecting the neighbor with thesmallest distance. However, in the presence of walls and otherkinds of environment obstacle agents these simplistic Game AIapproaches fail quickly. Figure 5, shows a complete playableversion of a Pacman game.Through the diffusion of the Pacman scent the ghost will find thecorrect solution. The important part is to understand howenvironment obstacles agents interact with the diffusion values.The walls, which are also represented by agents, will not diffusethe Pacman scent. Consequently, they will clamp down diffusionvalues. This clamping results in complex diffusion landscapesthat, again, can be plotted in 3D (Figure 5). Conceptually theselandscapes overlap with Axelrod’s Landscape theory [1] but arebetter suited for dynamic schemes that include mobile agents. Asthe Pacman and the ghosts are moving arou

2a) Smart Point and Shoot: The ghost selects a direction aiming at the Pacman. If the ghost hits an obstacle it will re-evaluate the direction to the Pacman again. Problems: If the direction is the same as the current direction the ghost gets stuck. 3a) Incremental Approach with Trap Detector: If the ghost gets stu ckby m inz gE ld a eo