4 ms·

Could you explain a little bit more about how that works - you used words I don't understand :) It seems as though something as simple as a random selection whe

by aidos 14y ago

Could you explain a little bit more about how that works - you used words I don't understand :) It seems as though something as simple as a random selection when presented with intersections is better than the behaviour here. I guess there should just be a weight on the streets though, right?

carlob 14y ago
Let me translate this to physics talk for you: when you use a greedy algorithm with no interaction between agents and no randomness, it's effectively like bosons at zero temperature, they will all fall in the lowest energy state and form a Bose-Einstein condensate. This can be avoided in one of two ways, make them aware of each other, so that they can't all be in the same state (like fermions) or raise the temperature, i.e. add randomness. Probably you'll need to do both and find an energy function that's less retarded than choose the first branch you see…
- skore 14y ago
  Apologies for going meta, but - Only on Hacker News will you see a "simpler" explanation involve the mention of Bose-Einstein condensate.
fgdsfgds 14y ago
In a nutshell: Make very agent a bit different in the sense that they all won't make the exact same choices. i.e. Rather than have a human always choose the first source, vary this and have some humans that go for the fifth and others for the sixth, etc. etc. Your random selection would also work I guess. Although how well? I don't know. Then, have a global pattern of how everything should be working, more or less. When a major deviation is found from the global pattern, adjust. How exactly? Those are implementation details.
zevyoura 14y ago
I'm not the person you're responding to, but I think this is how what the poster said applies to a SimCity-like model: >heterogeneity is your guardian angel - varying the path-finding model a little bit from agent to agent hedges against the resonance structures on display here. Adding a small amount of randomness (occasional 'wrong' turns) reduces congestion on the major paths that would be the dominant route for agents. >Additionally, you periodically check the accumulated micros against a macro model and correct gross deviations. Neither step is computationally strenuous. Every once in a while, check and make sure those wrong turns didn't add up to some agents being way far away from their destinations; if so, turn them in the right direction.
- chc 14y ago
  AFAIK it doesn't even have to be wrong turns. You can just have some agents prefer to turn more often and others to drive straight for longer stretches, or have some prefer to approach things from the left and others from the right. They won't be randomly turning the wrong direction, but they'll prefer different paths.
  - Total_Meltdown 14y ago
    Or to put it in a more socioeconomic context, consider a low-wealth actor that might prefer to avoid toll roads, versus a high-wealth actor that would rather pay a little bit to save some time. Those are the kinds of motivations I was hoping to see in this game.
aqme28 14y ago
In a nutshell: In some situations, a greedy algorithm works well but a totally random one works terribly, in other situations a random algorithm works well but a greedy one works terribly. Combine the two, and everything works out well enough to be plausible under all circumstances.
- sirclueless 14y ago
  Case in point: The Heroku load-balancing issue is a nasty one. The random algorithm (the one they went with) leads to really nasty queues in some places, it's super inefficient. On the other hand, a greedy algorithm doesn't scale well. You get one Heroku dyno (or SimCity road) swamped by all the agents making the same decision. A popular load-balancing strategy that finds a middle ground is "best-of-two" routing where you choose two servers at random and route to the one with lower load. There are probably similarly simple ways to introduce variety and randomness into the SimCity agents.

by aidos 14y ago

carlob 14y ago

Let me translate this to physics talk for you: when you use a greedy algorithm with no interaction between agents and no randomness, it's effectively like bosons at zero temperature, they will all fall in the lowest energy state and form a Bose-Einstein condensate. This can be avoided in one of two ways, make them aware of each other, so that they can't all be in the same state (like fermions) or raise the temperature, i.e. add randomness. Probably you'll need to do both and find an energy function that's less retarded than choose the first branch you see…

skore 14y ago
Apologies for going meta, but - Only on Hacker News will you see a "simpler" explanation involve the mention of Bose-Einstein condensate.

fgdsfgds 14y ago

In a nutshell: Make very agent a bit different in the sense that they all won't make the exact same choices. i.e. Rather than have a human always choose the first source, vary this and have some humans that go for the fifth and others for the sixth, etc. etc. Your random selection would also work I guess. Although how well? I don't know. Then, have a global pattern of how everything should be working, more or less. When a major deviation is found from the global pattern, adjust. How exactly? Those are implementation details.

zevyoura 14y ago

I'm not the person you're responding to, but I think this is how what the poster said applies to a SimCity-like model: >heterogeneity is your guardian angel - varying the path-finding model a little bit from agent to agent hedges against the resonance structures on display here. Adding a small amount of randomness (occasional 'wrong' turns) reduces congestion on the major paths that would be the dominant route for agents. >Additionally, you periodically check the accumulated micros against a macro model and correct gross deviations. Neither step is computationally strenuous. Every once in a while, check and make sure those wrong turns didn't add up to some agents being way far away from their destinations; if so, turn them in the right direction.

chc 14y ago
AFAIK it doesn't even have to be wrong turns. You can just have some agents prefer to turn more often and others to drive straight for longer stretches, or have some prefer to approach things from the left and others from the right. They won't be randomly turning the wrong direction, but they'll prefer different paths.
- Total_Meltdown 14y ago
  Or to put it in a more socioeconomic context, consider a low-wealth actor that might prefer to avoid toll roads, versus a high-wealth actor that would rather pay a little bit to save some time. Those are the kinds of motivations I was hoping to see in this game.

aqme28 14y ago

In a nutshell: In some situations, a greedy algorithm works well but a totally random one works terribly, in other situations a random algorithm works well but a greedy one works terribly. Combine the two, and everything works out well enough to be plausible under all circumstances.

sirclueless 14y ago
Case in point: The Heroku load-balancing issue is a nasty one. The random algorithm (the one they went with) leads to really nasty queues in some places, it's super inefficient. On the other hand, a greedy algorithm doesn't scale well. You get one Heroku dyno (or SimCity road) swamped by all the agents making the same decision. A popular load-balancing strategy that finds a middle ground is "best-of-two" routing where you choose two servers at random and route to the one with lower load. There are probably similarly simple ways to introduce variety and randomness into the SimCity agents.