[Idea] Emergence

[Evanito]

Updates and actual module code will be here: https://github.com/Evanito/screeps-emergence/issues/1

So I watched a documentary on emergence the other day. It discussed how ants know what role they need to be by checking those around them. If they notice a certain role is underrepresented, they change to it.

Now, ants have nothing to do with Screeps directly, but it was enough to get me thinking about a form of "swarm intelligence" of users of the bot.

Terms used:

• Peer: Another user of the bot that supports swarm intelligence.
• Emergence: When enough peers are in an area to create a network that can interact with its environment.
• Swarm: A group of individuals that act independently of each other but in the interest of the swarm.
• Swarm Intelligence: When multiple individuals who do not know much individually pool their knowledge and create a swarm that is smarter than just the sum of its parts.
• Sign: A room's controller sign object, which can be accessed by any user (that is in the room) by simply calling up the room's controller. Fast, allows for small amounts of stored information. Is expected to be human readable. This requires a scout screep to be in the room, however, so this method is sadly unfeasible at medium to long distances. Game.rooms["E32N28"].controller.sign.text
• Public Memory Segment (PMS): A section of memory that has been marked "public" by the owning player. A player can have up to 100 public memory segments, one is set to default. The user loading this segment must take one tick loading it, then can read it on and after the next tick. Slow-ish, allows for large amounts of stored information. Can only read one PMS at a time.
• Swarm Broadcast (SB): The "codeword" the swarm uses to identify that it is a potential peer. Could be customizable so that people can make their own groups. For Example: "broadcast": "angels" will only mesh with other peers who also have their SB set to "angels" and ignore all others. Default should be default because it is easy.
• Peer list: This is a list that every peer keeps to keep track of every peer they have confirmed. It is organized by distance. Near describes peers within ~10 rooms from border; Far will be 20(?); Global will list all known peers. Global is not used during normal operations, since the information they hold is likely irrelevant. This list will be in the form:

  {
  "near": [{"player": "<Peer1>, "rooms": ["<room1>","<room2>"], "confirmed": true}...],
  "far": [{"player": "<Peer2>, "rooms": ["<room1>","<room2>"], "confirmed": true}...],
  "global": [{"player": "<Peer3>, "rooms": ["<room1>","<room2>"], "confirmed": false}...]
  }

• Default PMS: This will contain information about the peer as well as outgoing handshakes. -Alliance describes what alliance the player is in, allowing individual players to respond accordingly (by adding them as an ally or as a hostile, for instance.) -Trespassing describes what setting the player has set for other peers to path through their rooms. Possible: all, peers (confirmed), alliance (peers who share alliance tag), allianceleaders (peers who are marked as leaders of your alliance), friends (manually set), neutrals (players the swarm does not call hostile), scouts (one move part) Multiple can be chosen, or none at all. -The emergency tag will cause any peers checking in to go check on the bot's emergency PMS. (See Swarm Alerts) -The default PMS also contains a heartbeat tick value, which should be updated at least every 500-1000 ticks even if nothing else changes just to show that the player is still alive. Peers/alliance members can use this to detect dead peers who may need a revive, if possible. Will (tentatively) be in the form:

  {
  "player": "<PeerName>", 
  "handshakes": ["<SomeOtherPeer2>", "<SomeOtherPeer3>"], 
  "myrooms": ["<OwnedRoom1>","W24N17"...], 
  "alliance": "The Angels",
  "trespassing": ["alliance", friends", "scouts"],
  "broadcast": "default",
  "friends": ["Evanito","TooAngel"...],
  "readynukes": 0,
  "emergency": false,
  "heartbeat": 1338800,
  "peers": 4
  }

• Potential Peer list: A list of unconfirmed peers that are queued to go into the handshake process. In the form: [{"player": "<PlayerName>", "room": "<RoomName>"}, {"player": "<Player2>"...}] This allows us to tie rooms to the players who own them, but only one room from each player is needed because we can just ask the player what rooms they have after they are confirmed.
• Terminal Message: A unique "push" message that has a transaction cost based on distance to recipient. Cons: This type of message requires a relatively high level room (6+) for both sender and recipient as well as energy to send. 100 Character max. Pros: This type of message is sent instantly to another room and the recipient's bot can instantly react to it instead of having to wait for the next check-in. Could be useful for swarm alerts, where immediacy is important.
• Check-in: Once two peers have confirmed each other, they periodically (async) load each other's PMS to see if there are any updates. If it sees a value has changed that would make its information out of date, it will start an update operation (syncing peers, hostiles, etc.)

I did a little research into the Screeps API and PMSs look like a promising way to transfer large amounts of information, but it has a one tick delay when being read. Signs, however, are a constant value for each room and are quicker and easier to check for small amounts of information, but require a scout to be in the room, so are easier on CPU (even with pathfinding?) but slower.

Emergence roadmap

• Peer discovery
• Peer confirmation
• Peer sharing
• Information sharing
• Hostile/Ally discovery
• Swarm Alerts

Peer Discovery

1) In initial discovery of nearby peers, several nearby rooms will be listed (probably depending on excess cpu) to be checked. 2) Send a scout to the nearest unchecked room. 3) Before the scout enters the room, log that it is about to enter. 4) Scout logs the player's name, the room name, and the controller's sign text (if any). 5) If the scout is not killed after the first tick, assume the room to be neutral, especially if it is owned and has towers. Owned hostile room: The scout dies and the enemy does whatever it does anyway. The room is marked as Hostile and will be avoided in the future unless the trespassing rules change. The bot still checks the name as a potential peer (he might just not allow scouts.) Owned neutral room: The room (if a peer) should log the owner of the scout and add it to it's potential peer list. The scout does the same then leaves to the next queued room. 6) Check the sign text. If it is blank or does not match the swarm broadcast then it will be ignored. (It would be ideal to use PMS for discovery, but we cannot do this because we need to programmatically know the owner of each room, which cannot be done without having a scout be in the room itself at some point.) 7) It will be added to the list of potential peers (See terms above.) Only one room from each player needs to be found to start meshing. 8) Rooms that fail at or before Step 6 will be put onto a (long) timer before being checked again. 9) Check all rooms, expanding outward, until all rooms within a set range are checked, or dead ends are reached. (End of map, hostile rooms, etc.)

Peer Confirmation

1) Select a potential peer from the potential peer list. 2) Load their Default PMS (Needs only name, See above). 3) Assuming our bot sees the peer first, and that our bot's name is NOT on the peer's list first. The bot adds this peer's name to the bot's handshakes list then waits. Around every 100 ticks later the bot should recheck the peer to see if it has replied to the handshake by adding the bot's name to its list. 4) If it has replied, then both the bot and the peer should have each other in their handshakes list. Since the bot initiated the handshake, it now removes the peer's name from the list to show that the reply has been seen and the peer is confirmed. The peer will do the same once it sees its name has been removed. 5) Once confirmed, each bot will add the peer to its peers list based on its distance. (See Peer list in terms above) 6) The bot and peer have confirmed each other and will now check each other periodically for news/updates/alerts. If the other peer doesn't handshake back within 50,000 ticks (several days) cancel the handshake. This allows bots to attempt to confirm far away peers, but they won't get stuck on them.

Peer Sharing

1) A new bot spawns in and soon finds a neighboring peer. 2) Before, during, or after the two have confirmed each other the new bot can compare peer lists with the existing peer. 3) If the bot sees unknown peers on the other peer's list, then it adds all unknown near and far peers to their Potential Peer list. (Maybe use linear distance function to find only those relevant to bot?) 4) With new nearby potential peers, the bot saves time wasted searching for neighbors (since it already knows there is a peer there, it can skip those.) (Maybe ask the peer how far out it has checked for these peers so that we can save time by eliminating those, too?) 5) This expands among all the peers and a network emerges.

Information Sharing

W.I.P. Share things like player room information (to create a global map), ongoing attacks, how defended a room is (and possibly create actual cross-player borders where the border rooms are more focused on defense while the inner rooms are focused on econ.)

Also considering an information consensus algorithm, such as keeping a dynamic list of members of an alliance updated.

Dynamic Alliance Roster

Alliance officers would add the new alliance member to their roster, which would be shared among the peers who check on them. Alliance leaders have the "official" information list, and all peers look to them for the correct version.

• Leaders have recruiting and ranking power over all roles, including leaders. They also have all diplomatic commands and are able to change the alliance settings. Rarely (Once every 50k) updates the updated value to flush out any malformed rosters accidentally held by officers.
• Officers have recruiting power over Members. They have diplomatic and ranking powers according to the alliance settings. They update rosters much more often than normal members. Periodically checks on members who are peers to make sure they are reporting that they are in the correct alliance. If they are not, then they are removed. Also includes Leaders.
• Members have basic alliance management powers according to settings. Also includes Leaders and Officers.

Each rank also has those below it. Ex: alliance.officers = ["TooAngel", "Player1", "Player2"]

Each member is able to manually execute commands like alliance.add("Evanito"), alliance.remove("Evanito"), alliance.setrank("Evanito", "officer"), alliance.diplomatic("The Live", "ally") etc. but will not have any effect if they are unable to create a consensus (due to their rank, no peers, etc.)

If there are multiple alliance officers, they compare their own roster to other officers relatively frequently so that they all have the most up-to-date version. This could cause race conditions if multiple officers make roster changes within a couple hundred ticks of each other, the change that was made most recently will overwrite the other.

At some point, a member wants to check if his roster is up to date. The following happens: 1) The member loads the alliance PMS from a random officer (this includes leaders). If he cannot find a single officer, he will check other Members for their alliance PMS instead. 2) If the updated value is newer, he begins the updating process. 3) The member checks the alliance settings to make sure the peer he pulled from has the permissions to make these changes. 4) If he does not: The process is repeated, this time selecting only from those of one rank higher (Member->Officer->Leader). If all above ranks are empty, continue as if he does have permission. If he does: The local alliance roster is overwritten with the remote one. This step is crucial to make sure that all Leader-rank changes must originate from a leader. This way, if a leader has the changes, that must mean he knows it came from a leader. If a role has no superiors, then allow that role to do whatever it wants. 5) The process is repeated after several thousand ticks for the average member.

I like the process described above, seems effective in every situation I can think of.

This roster will be in its own PMS and will be in the form: (Parenthesis are comments)

{
"tag": "The Angels",
"leader": ["TooAngel"],
"officer":["Player1" ,"Player2"],
"member":["Player3", "Player4"...],
"protectorate": ["Player5"...], (Players who are friendly to the alliance and protected as if an alliance member. Is allowed to be in another alliance. Overrides alliance suspect, but not enemy)
"annoyance": ["Player6"...], (Players who have been aggressive to alliance members, declares enemy status against just this player and not their whole alliance.)
"ally": ["The Jive"], (Allied alliances who are considered slightly below alliance members.)
"suspect": ["redefined"], (Alliances considered slightly less than neutral, will cause members to have stronger defenses when near their rooms.)
"enemy": ["The Bore"], (Alliances considered at war, allows alliance members to hit their rooms.)
"updated": 1338800,
"settings": { (Pick the minimum role to have each permission)
     "rolerank": ["leader", "officer", "member"] (Allows creation of modular ranking systems, I think it's cool.)
     "changeprotectorate": "member",
     "changeannoyance": "officer",
     ... more diplomatic stuff
     "changeofficers": "leader",
     "changesettings": "leader",
     "addrank": "leader",
}
}

Needs refining. Help appreciated.

Hostile/Ally Discovery

W.I.P. Peers share who is aggressive in the area, as well as those who are good neighbors/alliance members/friends.

Swarm Alerts

There are two ways to deliver a Swarm Alert:

• A terminal message to a nearby peer. Near-instant reaction from recipient.
• Changing the emergency Default PMS tag to true. May have several hundred tick delay. Both methods will be attempted during each emergency. If the room is unable to send the terminal message due to not being the right RCL, being too energy poor, or not having a specific peer to ask, the emergency tag in the default PMS will be used alone.

Both of these alerts will cause the recipient to check for a different PMS on the sender, the emergency PMS, for the details of their alert.

This emergency PMS would deliver some of the following situations:

• News of passing enemy claimers
• I AM GETTING NUKED PLEASE HELP
• Counterattack requests to distract an enemy who is besieging an ally to split their CPU and resources.
• Requests for help, such as for a revive if their last room falls, or just some more fighters during a siege.
• Orders for coordination of nukes onto a target room ("This room, launch a nuke at that room at this tick, etc.")
• Orders to siege another player or alliance.
• Requests to reserve a nearby room until tick X for them

The receiving peer can react according to set rules they have. These rules could be included in the default PMS so others can see them. For example:

"emergencyresponses": {
"allownukes": ["allianceleaders"],
"revive": ["neutrals", "alliance", "friends"],
"counterattack": ["alliance", "friends"],
"reinforce": ["alliance"],
"siege": ["allianceleaders"],
"hitcaravan": [],
"reserveroom":[]
}

W.I.P. (Low on free time)

[samogot]

I like

• It should be combined with quests and reputation somehow
• I think it should be implemented as separate module, so other bots, not only tooangels, can easily use it if they wants

[Evanito]

Fantastic ideas @samogot I just put in a huge paragraph about how alliances can use it for dynamic rosters that distribute themselves, so I would love if multiple bots could/would use this!

I was going to wait to get to the Hostile/Ally discovery because it should be separate from alliances. The reputation system we have right now is kind of incomplete so I'm not 100% sure how much I want to integrate into it at the moment. But I do love the idea of a reputation system, then peers can tell each other about how they think of other bots, and if a bot is well-hated in an area then you might even be able to just step in and wipe it out without anyone stopping you!

I will be putting some time aside in the next few weeks to make some of these ideas into a prototype, until then it would be awesome if you could critique/make some more suggestions!