Limiting agent interactions to once per step - updating both agents

[zeyus]

I've changed up what I want to do with the ABM, and basically we're going to do some variants on the prisoner's dilemma (with environmental and reproduction costs).

What I'm wondering is how conceptually to best limit agent pair interactions to once per step. I'm using flamegpu::MessageArray2D and the moore wrap (currently radius 1).

Each agent will output a message with its strategy, both agents should be affected by the interaction, but two agents in adjacent positions should play each other once, yet be updated with the reward or penalty for the interaction.

I'm trying to avoid keeping a second copy of the array in a macro property and host function to track interactions, but maybe this is the only way?

I guess the problem I'm facing is fully wrapping my head around the scope of all the variables and where they're allowed to be updated, for example if these were objects, I'd just keep a list of interactions per agent for the current step, and, once they played together they would not attempt again.

Here's the basic outline of what I'm doing:

FLAMEGPU_AGENT_FUNCTION(interact, flamegpu::MessageArray2D, flamegpu::MessageNone) {
    const unsigned int my_x = FLAMEGPU->getVariable<unsigned int>("x_a");
    const unsigned int my_y = FLAMEGPU->getVariable<unsigned int>("y_a");
    const unsigned int interaction_radius = FLAMEGPU->environment.getProperty<unsigned int>("max_play_distance");
    
    const float reproduction_threshold = FLAMEGPU->environment.getProperty<float>("reproduce_min_energy");
    const float reproduction_cost = FLAMEGPU->environment.getProperty<float>("reproduce_cost");

    float my_energy = FLAMEGPU->getVariable<float>("energy");
    
    // iterate over all cells in the neighbourhood
    // this also wraps across env boundaries.
    for (auto &message : FLAMEGPU->message_in.wrap(my_x, my_y, interaction_radius)) {
        flamegpu::id_t local_competitor = message.getVariable<flamegpu::id_t>("id");
        // play with the competitor

    }
    if (my_energy <= 0.0) {
        return flamegpu::DEAD;
    }
    if (my_energy > reproduction_threshold) {
        // spawn child in a free adjacent cell
        FLAMEGPU->setVariable<float>("energy", my_energy - reproduction_cost);
        return flamegpu::ALIVE;
    }
    return flamegpu::ALIVE;
}

[zeyus]

Continuing to think about this, it may help (but I still can't imagine the way to stop race conditions) to increase the number of layers, and make the appropriate layers conditional, as well as adding a couple of extra agent states, (e.g. ready, played_neighbours...)

And the layer structure something like:

1. Send out search messages
2. Play with nearby players and die if energy is too low
3. conditionally move if no play occurred (i.e. no neighbours)
4. conditionally reproduce if energy is high enough

[zeyus]

How would the sugarscape model scale (using an agent for each grid space, even if it's unoccupied) compared to representing each cell as an individual agent?

[Robadob]

That's a question of how GPUs operate.

A quick summary of GPU theory is that they follow the Single Instruction Multiple Thread (SIMT) paradigm. When you launch 1000 threads, they're grouped into 'warps' of 32 neighbouring threads. Each instruction is issued for a a single warp of 32 threads simultaneously. (GPUs have multiple streaming multiprocessors, which can each operate on 10s of warps concurrently to hide latencies which is how modern GPUs can support 50,000+ threads in flight concurrently, but that's kind of irrelevant to this point)

A thread in that warp either executes the instruction or goes inactive and ignores it (e.g. if there's divergence, such as an if-statement branching).

Optimal GPU code therefore, has every thread within a warp following the exact same code without divergence. Whereas, the worst case would be all 32 threads following completely different code paths (things will take ~32x longer!).

I would therefore expect that having a thread per agent, rather than a thread per grid cell is optimal in terms of performance as it would minimise divergence and achieve better device utilisation. If the agents are sorted to maximise memory locality/reduce divergence you might get a slight improvement too (this makes a big difference with our spatial messaging).

In the case of SugarScape however, the grid cells all(?) contain sugar which much grow back each step, and the agents are treated as 'virtual agents' living in the grid cells and able to move about. Ideally you would model the sugar grid and the 'agents' as two separate agents, but then alot more communication would be required (we could alternatively store the sugar in an environment macro property with flamegpu2). Given the simplicity of the model, we made the decision to keep the agents 'virtual'.

The example models are small 'toy' models, they've not been heavily calibrated or optimised.

Furthermore, we don't yet have a proper way to visualise cellular automata (the current visualisations are a bunch of stacked cubes). So it's necessary to have an agent per cell if you want all cells to be visualised (a 1 sided plane square + clear colour code work though tbh).

[Robadob]

Have just invited you to private repo with a 2D discrete example of the Bonding model I described above. It's a bit different to your use-case as every cell is currently occupied (and in the C++ API), but should give you something to work from.

Regardless of the agent count it seems to resolve all bonds in 9-11 iterations of the submodel.
Edit: I fixed some bugs, and applied a more random (but agreed upon) bond_score algorithm. It now resolves in 7-8 steps (I haven't bothered updating the speeds below, so should be ~20% faster than stated).

Will probably make it public (or move it to the main repo's examples) once I've had a chance to discuss it with the wider team.

On my old laptop's 980m, and a (Release/Seatbelts=OFF/Visualisation=ON build).
65,000 agents is running at 2.0 steps/second (bit slower than I would expect), but so is 1 million agents 🤷‍♂️. So much faster than I expect NetLogo would be at that scale,
Edit:: Just realised, the vis code I copypasted locks speed to 2 steps/second. 1 million agents actually runs at 9.4 steps/second, and 65k agents ~56 steps/second.

(a step is all agents bonding and then playing rock-paper-scissors with their partner)

A couple of screenshots to crudely show that bonds change each step (red means the cell failed to bond).

[zeyus]

Hey @Robadob thanks, this is amazing, I think I'll implement a variant of that bonding algorithm in my code, and it should actually address the issue I am facing in #894 , as the requests will come from the space where the agent is, rather than trying to output a message at the opponent's space (even though it should be possible in theory)...Also I think the random number is a good idea, rather than relying on the agent's ID. Right now I'll just try and get it done, and not stress too much about optimization, although it's one of my favorite parts of coding haha. I think with the method you've outlined for bonding, it wouldn't even be necessary to have a movement submodel, making the initial neighbour broadcast also redundant, but I'll leave them for now, and hopefully the function condition will prevent too much unnecessary overhead, though it would probably be worth removing 2x message out/in steps if it's not needed at some point.

[Robadob]

I wouldn't worry too much about overheads (especially until you have it working, and know whether you need more performance).

Discrete models are incredibly cheap compared to continuous space models. This is largely a consequence of a significantly reduced volume of communication (e.g. messages read) and a more balanced workload.