How to define multiple penalties to minimise overall in clingo?

Question

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.

Answer 1

Based on NTP's advice, I tried rewriting again and now pretty much all constraints are present and seem to work except for the ranking based penalty which I still have to add.

%%% constants %%%
#const nRounds = 3.
#const nPlayers = 4.
#const nRooms = 3.
#const nDecks = 4.

player(1..nPlayers).
room(1..nRooms).
deck(1..nDecks).
writer(1,1;2,2;3,3;4,4).

{ played(P, R, D) } :- player(P), room(R), deck(D).

% A player can only play a deck in a single room.
:- played(P, R1, D), played(P, R2, D), R1 != R2.
% A player must play nRounds decks overall.
:- player(P), X = #count { R, D: played(P, R, D) }, X != nRounds.
% Any deck in any room must be played by 3-4 players.
legal_player_count(3;4).
:- room(R), deck(D),
  X = #count { P: played(P, R, D) },
  X > 0,
  not legal_player_count(X).
% Writers cannot play their own decks.
:- writer(P, D), played(P, _, D).
% At least one non-playing player per room.
:- deck(D),
  Playing = #count { P, R: played(P, R, D) },
  Rooms = #count { R: played(_, R, D) },
  nPlayers - Playing < Rooms.

% Input points(P, R, D, X) to report points.
% winner(P, R, D) :- points(P, R, D, X), X = #max { Y : points(_, R, D, Y) }.

% Total number of decks played throughout the night (for minimisation?)
decks(X) :- X = #count { D: played(_, _, D) }.
% Total number of games played together by the same players (for minimisation)
% The total sum of this predicate is invariant
% Minimisation should took place by a superlinear value (e.g. square)
common_games(P1, P2, X) :- player(P1), player(P2), P1 != P2,
  X = #count { R, D: played(P1, R, D), played(P2, R, D) }, X > 0.

% For example:
% common_game_penalty(X) :- X = #sum { Y*Y, P1, P2 : common_games(P1, P2, Y) }.

% Another rank-based penalty needs to be added once the rank mechanics are there

% Then the 2 types of penalties need to be combined and / or passed to the optimiser

#show decks/1.
#show played/3.
#show common_games/3.

Answer 2

Writing everything at start and trying to debug afterwards is difficult in answer set programming. In your case it may be better to first define your search space and one by one write constraints to remove unwanted asnwers.

To update inputs after every round you will have to work with "online ASP". You may want to consider looking https://potassco.org/clingo/ as it contains valuable learning material which could help with your learning. Encoding below may be a good starting point for you

%%% constants %%%
#const numberOfRounds = 4.
#const numberOfPlayers = 2.
#const numberOfRooms = 4.
%%% constants %%%

%%% define players and their initial ranks %%%
player(1..numberOfPlayers,1).
%%% define players and their initial ranks %%%

%%% define rooms %%%
room(1..numberOfRooms).
%%% define rooms %%%

%%% define rounds %%%
round(1..numberOfRounds).
%%% define rounds %%%

%%% define search space (all possible values) %%%
search(P,R,S) :- player(P,_), room(R), round(S).
%%% define search space (all possible values) %%%

%%% define played %%%
{played(P,R,S)} :- search(P,R,S).
%%% define played %%%

%%% remove answers that does not satisfy the condition "Each player needs to play 4 rounds" %%%
:- player(P,_), X = #count{S : played(P,_,S)}, X != numberOfRounds.
%%% remove answers that does not satisfy the condition "Each player needs to play 4 rounds" %%%

%%% show output %%%
#show.
#show played/3.
%%% show output %%%