Logic game: maximising (or minimising) the chances for two agents to meet

Question

Note: this question is tagged both language-agnostic and python as my primary concern is finding out the algorithm to implement the solution to the problem, but information on how to implement it efficiently (=executing fast!) in python are a plus.

Rules of the game:

• Imagine two teams one of A agents (An) and one of B agents (Bn).
• In the game space there are a certain number of available slots (Sn) that can be occupied.
• At each turn each agent is given a subset of slots he/she can occupy.
• One agent can occupy only one slot at at time, however each slot can be occupied by two different agents, provided they are each from a different team.

The question:

I am trying to find an efficient way to compute the best possible move for A agents, where "best possible move" means either maximising or minimising the chances to occupy the same slots occupied by team B. The moves of team B are not known in advance.

Example scenario:

This scenario is deliberately trivial. It is just meant to illustrate the game mechanics.

A1 can occupy S1, S2
A2 can occupy S2, S3
B1 can occupy S1, S2

In this case the solution is obvious: A1 → S1 and A2 → S2 is the option that will guarantee meeting with B1 [as B1 cannot avoid to occupy either S1 or S2], while A2 → S3 and A1 → random(S1, S2) is the one that will maximise the chances to avoid B1.

Real-life scenarios:

In real-life scenarios, the slots can be hundreds and the agents in each team various dozens. The difficulty in the naïve implementation I tried so far is that I basically consider every single possible set of moves for the team B, and score each of the possible alternative set of moves for A. So, my computation time increases exponentially.

Still, I'm not sure this is a problem that can be solved only by "brute force". And even if this is the case I wonder:

1. If the optimal brute force solution necessarily grows exponentially (time-wise).
2. If there is a way to compute an non-optimal, locally-best solution.

Thank you!

Answer 1

The members of the two teams and the slots define a tripartite graph A-S-B, with edges given by the possible moves. The bipartite subgraphs consisting of the slots and members of just one team are of interest; call these A-S for the graph with team A members and S-B for team B members. You can use the S-B graph to assign values to the slots, and then the S-A graph to select moves that maximize or minimize the value for team A.

An appropriate choice for the value of a slot is the likelihood of finding a member of team B in that slot. With that, the value for a set of moves for team A is the sum of the slot values, i.e., the expected number of slots where a team B member will be found. Note that the moves of the members of a team are not independent, so both stages present some challenge.

Given the values for the slots, choosing the moves for team A becomes a standard problem: the assignment problem. This is related to the maximal bipartite matching suggested in missingno's answer, but the value of the slots needs to be accounted for; the edges can be given weight equal to the value of the slot on which the edge is incident, with a maximum weighted bipartite matching equivalent to the assignment problem. Use standard algorithms to solve (or approximate) this part of the problem.

So how can we assign values to the slots? I'd suggest just generating random moves for the members of team B, counting how often the slots are occupied, and dividing the counts by the number of sample moves you consider. It's not really clear from the question how hard it will be to generate a random set of moves; assuming that each team member has the option to stay in place, it is easy to do just by randomly selecting moves for each member in random order.

A simplifying factor in both stages is that there is an easy way to decompose the problem into independent sub-problems. The connected components of the bipartite graphs show which team members can move in a way that interferes with which others, e.g., if the team members are split into two groups on different parts of the board, the groups can be treated independently. This applies in both stages, both probabilistically evaluating the slots with the S-B graph and optimizing the assignment in the A-S graph. Of course, if any component is small enough, you could always enumerate the possibilities and solve the subproblem exactly.