7 ms·
Similar story of unexpected AI outcomes... As part of my PhD research, I created a simplified Pac-Man style game where the agent would simply try to stay alive
by TomAnthony 5y ago
Similar story of unexpected AI outcomes...
As part of my PhD research, I created a simplified Pac-Man style game where the agent would simply try to stay alive as long as possible whilst being chased by the 3 ghosts. The agent was un-motivated and understood nothing about the goal, but was optimising for maximising its observable control over the world (avoiding death is a natural outcome of this).
I spent sometime trying to debug a behaviour where the agent would simply move left and right at the start of each run, waiting for the ghosts to close in. At the last minute it would run away, but always with a ghost in the cell right behind it.
Eventually, I realised this was an outcome of what it was optimising for. When ghosts reached cross-roads in the world they would got left or right randomly (if both were same distance to catching the agent). This randomness reduced the agent's control over the world, so was undesirable. Bringing a ghost in close made that ghost's behaviour completely predictable.
- McMiniBurger 5y agohm... "keep your friends close but your enemies closer" ...?
- TchoBeer 5y agoHow did you measure control over the world?
- greenpresident 5y agoIn an active inference approach you would have the agent minimise surprisal. Choose the action that is most likely to produce the outcome you predicted.
- TomAnthony 5y agoThe approach I used was similar. The idea of maximising observed control of the world means you seek states where you can reach many other states, but _predictably_ so. This comes 'for free' when using Information Theory to model a channel.
- cmehdy 5y agoDo you have any reading you'd recommend related to this? I naively thought it would be some kind of Kalman filtering of sorts but from what I gather in your words it doesn't even have to be "that" complicated, right? edit: found your link to the paper in another post ( https://news.ycombinator.com/item?id=27749619 https://news.ycombinator.com/item?id=27749619 ), thanks!
- benlivengood 5y agoWhat's the tradeoff between "delete all state in the world with 100% certainty" and "be able to choose any next state of the world with (100-epsilon)% certainty"?
- TomAnthony 5y agoIn Information Theory, there is a concept of Channel Capacity. If a channel is defined as the probability of the output being s if you send a, across all possible values of a, then the Channel Capacity is the maximum amount of information you can communicate across this channel, measured in bits. To achieve the Channel Capacity you need to find the optimum distribution across a - i.e. what set of signals maximises the information you can transmit on this channel. There are known algorithms for finding this distribution (e.g. Blahut-Arimoto). Now if you model the world as a channel, where s represents the reachable states and a represents the actions the agent can take (and the channel, P(s|a), represents the dynamics of the world), you can calculate what actions allow you maximal control (in terms of states you can controllably reach). More info in this paper: https://uhra.herts.ac.uk/handle/2299/15376 https://uhra.herts.ac.uk/handle/2299/15376
- yodelshady 5y agoI believe that tactic is called "kiting" and used by speedrunners?
- TomAnthony 5y agoYes! Exactly - kiting. I didn't know the term but when I explained the behaviour I was seeing to a colleague they told me about this.
- joe_the_user 5y agoYeah, waiting for the ghosts to get close was a standard strategy I used back when I played lots of Pacman. Having all the ghosts behind you gives you more control since they'll follow you in a line. That the ghosts follow the player is what makes the game winnable. If they formed a grid and gradually closed-in, it would be impossible to escape. Edit: What was unexpected in this case was that the system found a strategy the programmer didn't think of.
- NaturalPhallacy 5y agoYup! It's also used in other games a lot. For example in EVE Online with a 1v1 fight two basic tactics are either Kite or Brawl. A kiter that can maintain range will beat a brawler. But a brawler that 'catches' a kiter will generally win.
- Retr0id 5y agoAnother similar story, I remember reading about an AI that simply paused the game when it was about to die. I can actually remember doing something similar as a child.
- 0110101001 5y agohttps://youtu.be/xOCurBYI_gY&t=15m10s https://youtu.be/xOCurBYI_gY&t=15m10s
- fnord77 5y agothis sounds interesting. can you link your research or paper?
- TomAnthony 5y agoSure! The PDF is available here: https://uhra.herts.ac.uk/handle/2299/15376 https://uhra.herts.ac.uk/handle/2299/15376
- Iv 5y agoA while ago, a very simple agent I made had to do tasks in the maze and evaluate strategies to reach them. I wanted it to have no assumptions about the world, so it started with minimum knowledge. Its first plan was to try to remove walls, to get to the things it needed. It is a fun feeling when your own program surprises you.
- johbjo 5y agoIt can depend on what the agent "sees" and how many time-steps away the "consequences" are. If the ghosts are so far away that any action will take t time-steps before consequences to the agent, the actions are pseudo-random because there is no reward to optimize on. The number of outcomes in branching_factor^t (very large) makes the action-values at t=0 (where the agent chooses between two/three actions) almost uniform random.
- TomAnthony 5y agoYes, you are right. I experimented with different time horizons, mostly look 3-7 steps ahead. In terms of the 'reward', that was implicit within the model - if the ghosts caught you, your ability to influence the state of the world dropped to 0.
- joek1301 5y agoYet another similar story. A side project of mine was building a rudimentary neural network whose weights were optimized via a genetic algorithm. The goal was operating top-down, 2D self-driving cars. The cars' "fitness" function rewarded cars for driving along the course and punished them for crashing into walls. But evidently this function punished a little too severely: the most successful cars would just drive in tight circles and never make progress on the course. But they were sure to avoid walls. :)
- edejong 5y agoSame story as one I shared 4 years ago. Seems to be the best tactic! https://news.ycombinator.com/item?id=14031932 https://news.ycombinator.com/item?id=14031932 Edit: don’t want to sound accusatory
- wildmanx 5y ago"Completely predictable" is different from "This would minimize the probability of being fenced in by the four ghosts." no?
- jeremysalwen 5y agoNo need to be accusatory. The stories are different, just the learned behavior is the same. And not very surprising, considering your story was pre-empted by Pac-Man speedrunners, who already discovered this technique, which they call "kiting". You can see the paper OP wrote to confirm for yourself that their story is not the same as yours: https://uhra.herts.ac.uk/bitstream/handle/2299/15376/906989.pdf?sequence=2&isAllowed=y https://uhra.herts.ac.uk/bitstream/handle/2299/15376/906989....
- TomAnthony 5y agoHah - thank you for sharing! That is very interesting that this emerged from two different approaches. I published my result years back, and have never heard of this emerging elsewhere before! Didn’t take it as accusatory [but thanks to child for sharing link :)].