I am trying to use clingo to generate tournament player-room allocations:
player(1..20).
room(1..4).
played(1..20, 0).
rank(1..20, 1).
played(1..20, 1..20, 0).
0 { used_room(R) } 1 :- room(R).
3 { game(P, R) } 4 :- used_room(R), player(P).
:- game(P, R1), game(P, R2), R1 != R2.
penalty(Y) :- Y = #sum {
X: game(P1, R), game(P2, R), played(P1, P2, X);
X: game(P1, R), game(P2, R), rank(P1, R1), rank(P2, R2), abs(R1-R2) = X;
4 - X: played(P, X), not game(P, _)
}.
#minimize { X: penalty(X) }.
The first 5 lines are supposed to be the "input":
- The number of players present is variable
- So is the number of rooms available
- Each player needs to play 4 rounds throughout the night so we record the number of rounds played by each player so far
- Each player has a rank (in the league table), which is updated after every round - ideally players in every room should have similar levels (think ELO)
- To discourage the algorithm from putting the same players together all the time, we also keep track of the number of rounds any given pair of players spent together in the same room
The idea is to update these inputs after every round (once the points are in) and feed them back into the solver to produce the next round's allocation.
Then, I tried to add some constraints:
- There is a certain number of rooms available but they do not all have to be used. Each room can be either used or unused each round
- For any room that is used, it has to have either 3 or 4 players assigned to it (due to the mechanics of the game - 4 is always preferred, 3 is for dealing with edge cases)
- No player can be assigned to more than one room for any given round
Finally, I tried defining some "penalties" to guide the solver to pick the best allocations:
- For every pair of players P1, P2 that were placed in the same room add X to the penalty where X is the number of times they already played together.
- For every pair of players P1, P2 that were placed in the same room add the (absolute) difference in their rank to the penalty.
- For every player that still has to play in X more rounds but hasn't been selected for this round, add X to the penalty.
What I meant to do was for this penalty to accumulate so that each player who has 4 rounds to go (so every player at the beginning) adds 4 points to the penalty and not just one (which is what happened with this code). In practice, running this gets penalty(4). and no game(player, room). allocations whatsoever.
Also, I'd like to have some constraint so that I cannot end up in a situation where some players still have rounds left to play but there are not enough players left (e.g. if you have 1, 2 or 5 players left who just need to play one round). I am not sure what the right invariant is which could guarantee that this would not happen even several rounds ahead. This is more of an actual logic question than clingo. In practice, you have around 3-4 rooms available and around 20-30 players - importantly, there is never a guarantee that # players is a factor of 4.
Something else that's missing from my current "implementation" is a constraint such that for a specific subset of players (let's call them "experts"), at least one of them has to stay out of the current round (and lead it). And in general for each room used, at least one player has to stay out (including the one expert). This should be a hard constraint.
Finally, we'd like to maximise utilisation for the rooms i.e. maximise the number of players per round and minimise the number of rounds overall. This should be a weak constraint (just like the constraints to do with ranks and games played so far together).
Many thanks in advance for any help or advice! Unfortunately, the documentation does not give so many sophisticated examples so I couldn't figure out what the right syntax for my use cases is.