6 ms·

Antiobjects

133 points by raganwald 17y ago

RiderOfGiraffes 17y ago
Looking at the pacman solution, there's a problem when two ghosts end up on the same square, then they might tend to follow the same path, whereas programming them as objects (and not anti-objects) you can include avoidance strategies. To get that from the scent-following, hill-climbing algorithm requires some work.
- anigbrowl 17y ago
  They did mention that ghosts block the pac-scent, so the differential equation for the square would yield different values in the case of an adjacent ghost. The specific case you mention is discussed in the paper on page 6 - http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobj... It's well-written and makes for an interesting read. As someone interested in AI but without much skill I found this approach much more intuitive, though I wonder about the CPU efficiency of simulating a dynamic environment. Will Larson also discusses these ideas in a very nuts-and-bolts manner, albeit briefly: http://lethain.com/entry/2007/jun/07/anti-objects-and-reflexive-decisions-repost/ http://lethain.com/entry/2007/jun/07/anti-objects-and-reflex...
- ludwig 17y ago
  Yeah, because ghosts are physical corporeal entities that couldn't possibly be in the same place at once :-)
  - Confusion 17y ago
    The point is that the challenge gets less if two ghosts merge, because they start following the exact same path. You could probably even abuse that to create effectively 1 ghost. (However, as others note, this problem does not actually arise, because ghosts block the pac-scent)
  - joshu 17y ago
    I wonder if there's an upper limit to the number of cospatial ghosts...
    - glhaynes 17y ago
      Modern scholasticism! :)
- jordyhoyt 17y ago
  I think a distinction needs to be made. The anti-object seems to provide the environment in which the object moves. I don't think the point is for there to be absolutely no logic in the object itself, the logic should merely be simplified. On the contrary, the ghost object in this example still has to implement the hill climbing algorithm. It could go down the hill (as it would do if pac man got one of the super pellets), or it could ignore the hill altogether. I think this also implies that it could avoid collisions with other ghosts, or even avoid grouping with other ghosts by paying attention to their scent as well. Seems like it would be trivial for a tile to further provide the scent value for all interesting objects in the maze.
- DannoHung 17y ago
  More importantly, in Pac-Man, each ghost has a separate algorithm that each follows in their pursuit.
  - eru 17y ago
    http://www.webpacman.com/ghosts.html http://www.webpacman.com/ghosts.html
- allenp 17y ago
  One of the biggest advantages of implementing the ghosts as objects is that they can actively work together to corner pac-man.
  - lmkg 17y ago
    Never underestimate the power of emergent behavior of a small number of interacting rules. The ghosts do not have to explicitly interact in order for them to coordinate. The fact that a ghost blocks scent means that they influence each other in a way that leads to them covering multiple paths. I'm not an expert, but I would bet hard cash that such a strategy works better than any explicit coordination strategy that takes up to an order of magnitude more effort to implement, and I wouldn't be surprised if it's mathematically optimal.
RiderOfGiraffes 17y ago
Now I remember why this seems so familiar ... I used a similar method to the pacman solution to make a simulation of traffic. By modelling the road as well as the cars, I could measure the distance between cars by having the road remember when a car last passed over, and give that information to the next car that passes over. The simulation was enormously simpler by modelling the road and storing information in that, rather than just in the obvious objects - the cars. In effect, cars left traces behind for the next cars to collect and process. Distances between cars could be calculated simply by knowing the times of transits and speeds of cars. Uncertainties needed to be taken into account, but the road could also contain pointers/references to the cars that had passed over. In my case I distributed the simulation over 1024 processors and the messages were explicit. I find object-oriented programming largely to miss the point. As Alan Kay once said, the point was never the objects - it was always intended to be about the messages. Of course, that's a religious argument, and probably better discussed elsewhere. ADDED IN EDIT: I really ought to write up some of my experiences ...
- BigZaphod 17y ago
  Rambling thoughts your comment triggered: When we model position of things in code, we often put the position within the thing being modeled - car, game character, window, etc. So you can do things like: aCar.position - but I think that might be conceptually wrong and have been thinking that for a long time but haven't had much chance to explore the idea. The idea of putting the responsibility for (eg.) location of each object within the world into the world itself seems to fit better with reality, too. After all, in our physical reality there's rules that "the world" imposes on things within it. One big one is that only one physical object (atom or what-have-you) can exist in a given location in space at a given time. Having the location of an atom in space be stored in the atom itself would seemingly make it a lot more difficult to make sure that rule goes unbroken and, arguably, can't be how the universe works as we seemingly cannot "see" location encoded within physical objects in our universe (that I know of). Therefore the location of a thing is probably "stored" within the fabric of the universe itself... Anyway... If you write up your experiences, please post them to HN - I'm betting they'd be interesting!
  - 17y ago
davidmathers 17y ago
This reminds me of Luca Cardelli's theory of objects: http://books.google.com/books?id=4xT3LgCPP5UC&pg=PA7&lpg=PA7&source=bl&ots=9FMwvzLe9M&sig=U3K5GwytAgpPWXi4ZwgI8EhJ3ac&hl=en&ei=nE4dS-TsMI2VtgeS7O3lAw&sa=X&oi=book_result&ct=result&resnum=2&ved=0CA8Q6AEwAQ#v=onepage&q=&f=false http://books.google.com/books?id=4xT3LgCPP5UC&pg=PA7&#38... According to Luca the correct way to think about objects is not as the entities of the software model, but as the construction materials for the software model. He uses the analogy of making a physical model of the solar system. In your model the planets don't move themselves, they're moved by gears, tracks, and motors. So it could be entirely appropriate to think of the pacman board being made up of tiles and those being true, properly understood, OOP objects. I think he would say that "The metaphor of objects can go too far by making us try to create objects that are too much inspired by the real world." is exactly how not to think about OOP in the first place.
bd 17y ago
That's actually a quite common pattern in artificial life community (inspired by real world behaviors from insects): http://en.wikipedia.org/wiki/Stigmergy http://en.wikipedia.org/wiki/Stigmergy http://en.wikipedia.org/wiki/Ant_colony_optimization http://en.wikipedia.org/wiki/Ant_colony_optimization Also Sims had some "intelligence" embedded into objects instead of the agents: http://www.gamedev.net/columns/events/coverage/feature.asp?feature_id=51 http://www.gamedev.net/columns/events/coverage/feature.asp?f...
jrockway 17y ago
This is not a new concept, but rather just exercising good programming technique. If you are modeling a collection of elements, and the elements need to be aware of themselves in relation to the other elements, then you need to model the container. A simple example is an array. You don't ask an array element for the array's length or for the i-th array element; you model the container and let the container do that.
panic 17y ago
This duality shows up in fluid simulation as well: http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specification_of_the_flow_field http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specifi...
bham 17y ago
This reminds me of a funny Cracked skit about the 1979 game developer's conference wherein the birth of Frogger was reenacted. "Ok ok you are a truck driver and you try to run over frogs crossing the road". "No, no, you ARE the frog!" "Whoooa" http://www.cracked.com/video_16019_video-game-pitch-meeting-1979.html http://www.cracked.com/video_16019_video-game-pitch-meeting-...
bartl 17y ago
A major difference between the Pacman ghosts as described here, and cars in traffic, is that the ghosts will always be able to smell the pacman, no matter how far he is, and a driver in a car has a limited view on the traffic surrounding him. The latter (limited) is easier if you use objects for the cars, the former (unlimited) is easier using antiobjects.
- thomas11 17y ago
  You could have tiles forget the scent/roads forget the traffic. With each simulation step, decrease it until it's gone after however long you want it to be remembered. Then, ghosts would have to be somewhat near pacman, and cars are only influenced by what goes on around them, not what happened a while ago. Of course, simulating the actual view of a driver, i.e., excluding things behind the vehicle etc., takes a lot more work.
_ck_ 17y ago
I can't help but see the pacman problem as a relational database ;-) SELECT location FROM tiles ORDER BY scent DESC LIMIT 1 (then apply algorithm to move to that location) Replace the DB with a matrix of parallel processing elements as tiles and there you go?
tome 17y ago
I would be tempted to call these "co-objects" since they are in some sense dual to your standard objects.

133 points by raganwald 17y ago

Looking at the pacman solution, there's a problem when two ghosts end up on the same square, then they might tend to follow the same path, whereas programming them as objects (and not anti-objects) you can include avoidance strategies. To get that from the scent-following, hill-climbing algorithm requires some work.

anigbrowl 17y ago
They did mention that ghosts block the pac-scent, so the differential equation for the square would yield different values in the case of an adjacent ghost. The specific case you mention is discussed in the paper on page 6 - http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobj... It's well-written and makes for an interesting read. As someone interested in AI but without much skill I found this approach much more intuitive, though I wonder about the CPU efficiency of simulating a dynamic environment. Will Larson also discusses these ideas in a very nuts-and-bolts manner, albeit briefly: http://lethain.com/entry/2007/jun/07/anti-objects-and-reflexive-decisions-repost/ http://lethain.com/entry/2007/jun/07/anti-objects-and-reflex...
ludwig 17y ago
Yeah, because ghosts are physical corporeal entities that couldn't possibly be in the same place at once :-)
- Confusion 17y ago
  The point is that the challenge gets less if two ghosts merge, because they start following the exact same path. You could probably even abuse that to create effectively 1 ghost. (However, as others note, this problem does not actually arise, because ghosts block the pac-scent)
- joshu 17y ago
  I wonder if there's an upper limit to the number of cospatial ghosts...
  - glhaynes 17y ago
    Modern scholasticism! :)
jordyhoyt 17y ago
I think a distinction needs to be made. The anti-object seems to provide the environment in which the object moves. I don't think the point is for there to be absolutely no logic in the object itself, the logic should merely be simplified. On the contrary, the ghost object in this example still has to implement the hill climbing algorithm. It could go down the hill (as it would do if pac man got one of the super pellets), or it could ignore the hill altogether. I think this also implies that it could avoid collisions with other ghosts, or even avoid grouping with other ghosts by paying attention to their scent as well. Seems like it would be trivial for a tile to further provide the scent value for all interesting objects in the maze.
DannoHung 17y ago
More importantly, in Pac-Man, each ghost has a separate algorithm that each follows in their pursuit.
- eru 17y ago
  http://www.webpacman.com/ghosts.html http://www.webpacman.com/ghosts.html
allenp 17y ago
One of the biggest advantages of implementing the ghosts as objects is that they can actively work together to corner pac-man.
- lmkg 17y ago
  Never underestimate the power of emergent behavior of a small number of interacting rules. The ghosts do not have to explicitly interact in order for them to coordinate. The fact that a ghost blocks scent means that they influence each other in a way that leads to them covering multiple paths. I'm not an expert, but I would bet hard cash that such a strategy works better than any explicit coordination strategy that takes up to an order of magnitude more effort to implement, and I wouldn't be surprised if it's mathematically optimal.

RiderOfGiraffes 17y ago

Now I remember why this seems so familiar ... I used a similar method to the pacman solution to make a simulation of traffic. By modelling the road as well as the cars, I could measure the distance between cars by having the road remember when a car last passed over, and give that information to the next car that passes over. The simulation was enormously simpler by modelling the road and storing information in that, rather than just in the obvious objects - the cars. In effect, cars left traces behind for the next cars to collect and process. Distances between cars could be calculated simply by knowing the times of transits and speeds of cars. Uncertainties needed to be taken into account, but the road could also contain pointers/references to the cars that had passed over. In my case I distributed the simulation over 1024 processors and the messages were explicit. I find object-oriented programming largely to miss the point. As Alan Kay once said, the point was never the objects - it was always intended to be about the messages. Of course, that's a religious argument, and probably better discussed elsewhere. ADDED IN EDIT: I really ought to write up some of my experiences ...

BigZaphod 17y ago
Rambling thoughts your comment triggered: When we model position of things in code, we often put the position within the thing being modeled - car, game character, window, etc. So you can do things like: aCar.position - but I think that might be conceptually wrong and have been thinking that for a long time but haven't had much chance to explore the idea. The idea of putting the responsibility for (eg.) location of each object within the world into the world itself seems to fit better with reality, too. After all, in our physical reality there's rules that "the world" imposes on things within it. One big one is that only one physical object (atom or what-have-you) can exist in a given location in space at a given time. Having the location of an atom in space be stored in the atom itself would seemingly make it a lot more difficult to make sure that rule goes unbroken and, arguably, can't be how the universe works as we seemingly cannot "see" location encoded within physical objects in our universe (that I know of). Therefore the location of a thing is probably "stored" within the fabric of the universe itself... Anyway... If you write up your experiences, please post them to HN - I'm betting they'd be interesting!
- 17y ago

davidmathers 17y ago

This reminds me of Luca Cardelli's theory of objects: http://books.google.com/books?id=4xT3LgCPP5UC&pg=PA7&lpg=PA7&source=bl&ots=9FMwvzLe9M&sig=U3K5GwytAgpPWXi4ZwgI8EhJ3ac&hl=en&ei=nE4dS-TsMI2VtgeS7O3lAw&sa=X&oi=book_result&ct=result&resnum=2&ved=0CA8Q6AEwAQ#v=onepage&q=&f=false http://books.google.com/books?id=4xT3LgCPP5UC&pg=PA7&#38... According to Luca the correct way to think about objects is not as the entities of the software model, but as the construction materials for the software model. He uses the analogy of making a physical model of the solar system. In your model the planets don't move themselves, they're moved by gears, tracks, and motors. So it could be entirely appropriate to think of the pacman board being made up of tiles and those being true, properly understood, OOP objects. I think he would say that "The metaphor of objects can go too far by making us try to create objects that are too much inspired by the real world." is exactly how not to think about OOP in the first place.

bd 17y ago

That's actually a quite common pattern in artificial life community (inspired by real world behaviors from insects): http://en.wikipedia.org/wiki/Stigmergy http://en.wikipedia.org/wiki/Stigmergy http://en.wikipedia.org/wiki/Ant_colony_optimization http://en.wikipedia.org/wiki/Ant_colony_optimization Also Sims had some "intelligence" embedded into objects instead of the agents: http://www.gamedev.net/columns/events/coverage/feature.asp?feature_id=51 http://www.gamedev.net/columns/events/coverage/feature.asp?f...

jrockway 17y ago

This is not a new concept, but rather just exercising good programming technique. If you are modeling a collection of elements, and the elements need to be aware of themselves in relation to the other elements, then you need to model the container. A simple example is an array. You don't ask an array element for the array's length or for the i-th array element; you model the container and let the container do that.

panic 17y ago

This duality shows up in fluid simulation as well: http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specification_of_the_flow_field http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specifi...

bham 17y ago

This reminds me of a funny Cracked skit about the 1979 game developer's conference wherein the birth of Frogger was reenacted. "Ok ok you are a truck driver and you try to run over frogs crossing the road". "No, no, you ARE the frog!" "Whoooa" http://www.cracked.com/video_16019_video-game-pitch-meeting-1979.html http://www.cracked.com/video_16019_video-game-pitch-meeting-...

bartl 17y ago

A major difference between the Pacman ghosts as described here, and cars in traffic, is that the ghosts will always be able to smell the pacman, no matter how far he is, and a driver in a car has a limited view on the traffic surrounding him. The latter (limited) is easier if you use objects for the cars, the former (unlimited) is easier using antiobjects.

thomas11 17y ago
You could have tiles forget the scent/roads forget the traffic. With each simulation step, decrease it until it's gone after however long you want it to be remembered. Then, ghosts would have to be somewhat near pacman, and cars are only influenced by what goes on around them, not what happened a while ago. Of course, simulating the actual view of a driver, i.e., excluding things behind the vehicle etc., takes a lot more work.

_ck_ 17y ago

I can't help but see the pacman problem as a relational database ;-) SELECT location FROM tiles ORDER BY scent DESC LIMIT 1 (then apply algorithm to move to that location) Replace the DB with a matrix of parallel processing elements as tiles and there you go?

tome 17y ago

I would be tempted to call these "co-objects" since they are in some sense dual to your standard objects.