CSP (better, ASP) in Clingo to bet FantaSanremo

Preamble

Recently (false) I became nostalgic and fascinated with stuff from the past, but someone told me many times I’m a future-man cause I tend to project everything in my life. So let’s play with the future - TA-DA! Sanremo Festival, precisely the 2023 Edition¹ is coming to town (not mine) so I decided to play for real to FantaSanremo. What is this? Formally, FantaSanremo was born in 2020 from the idea of a group of friends working in the entertainment industry (musicians, music teachers, sound technicians) who are fans of the Sanremo Festival and were inspired by the Fanta-Game of Thrones, a fantasy game based on the TV series of the same name. The FIF (Federazione Italiana FantaSanremo) is created, which consists of 8 people and has the task of drafting the first regulations. The virtual currency with which to buy the artists of one’s team is named Baudo in honor of the famous Pippo, an icon of the Festival with the greatest number of conductions to his credit.

Due to the COVID-19 pandemic, FIF decided to move the conduct of the game to the Internet, with the motto:

One Team, Five Artists, One Captain!

Pretty cool. Initially, the site was set up to host a hundred teams, but interest from highly followed figures on social media gives a lot of visibility to the game, which in just a few days sees the number of teams registered reach more than 40K teams…

Let’s dig into the topic in such a way to better choose our Team!

Rules

These are pretty much the rules reported as seen on the website:

• Each player has 100 Baudi available to purchase 5 of the competing artists;
• It is mandatory to field a team of 5 artists and appoint one of them as captain;
• You can register your team by Monday, Feb. 06, 2023 at 11:59 p.m, CET Time;
• Bonuses and maluses for each artist will be awarded according to the following rules: should the evaluation of a bonus or malus be subjective, the FIF Association will have the final say in evaluating the incident in a professional, unconditional and objective manner;
• The allocation of bonuses and maluses applies to artists from the first minute of the Sanremo Festival until the end of the live broadcast of the final night (everything that happens before and after the Festival will not be counted);
• The bonuses and maluses of the last episode of the artist named captain will be doubled;
• The artist wearing the Jolly bracelet will double the points obtained from his or her placement on the leaderboard or cancel the malus resulting from it. The bracelet can only be used once on any of the evenings of Festival with the exception of the finals. Should the bracelet be worn on the first night the effects of the Jolly will be applied to the ranking of the second night;
• When not expressly specified, bonuses and maluses refer to actions performed by the artist or events involving him/her on stage and/or in the stalls of the Ariston Theater during the episodes of Festival;
• On the evening of the covers - sorry for not-italian readers, this is more related to Sanremo Festival - it will also be considered valid, for the purpose of assigning bonuses and malus related to the competing artist, everything concerning any announced guests who will perform together with the artist himself/herself;
• In the event that a competing artist cannot perform for whatever reason and a pre-recorded performance valid for the purposes of the competition is then used (see Irama Sanremo 2021) bonuses and maluses will still be assigned based on that recording;
• The winner is the one who, at the end of the last episode of Sanremo, has scored the most points;
• The rules may be subject to change until Monday, February 06, 2023 at 11:59 p.m. CET Time and, should the need arise, may also be subject to interpretation and/or clarification by FIF during the week of Festival;

For the bonus/malus part I leave you the link (I’m sorry, it’s Italian but you can translate it quite easily I guess since you are gonna write your Clingo program - so much more hard to do)

Straight to the point: how to decide

So far, what we got is that we have to form a 5-singers team. Moreover, we have a price for each of them. What we don’t know yet is… the effective value of the singer. So, excluding the whole list of bonus/malus rules for now, let’s take into account the very first two couple of them. Here we are:

Bonus: ranking positions

• Final night position points (1st classified +100pt, 2nd +70pt, etc);
• Points position, 2nd, 3rd and 4th night (to be awarded each night) as well defined here;

Bonus: premi della Critica

These are 7 prices of equal value given based on artists/band performance, and that’s it. At this point, there are a few ideas we can already reason on: first, no matter the other things that could or could not happen (see super weird rules), the team has to be a good team, because more points go to the best “singers” - excluding weird. Second, we need to quantify how good is a single singer. What about… the betting system? :) This is the method I’ve chosen.

How much is valued a singer?

By looking online, I found a list of the quotation given for each of the singers that will join the Festival this year. The result is shown below. The value of the quotation is updated on Sunday, the 29th of January, 2023. Keep in mind that the value represents a multiplier on the amount you bet (and you would win) whenever the respective artist wins: of course, a smaller value reflects a higher chance to win - because they pay less. I also multiplied this value by 10 to normalize and have only integers (more about this later on). Last but not least, a third column reports the cost of each of the singers in Baudi (the coin you can use to form your team, see before for rules).

Long story short, one of the first things we can think about is maximizing the amount of Baudi we can use to buy our singers - by minimizing the amount of quotation to maximize the chance to choose the most-likely winner singer(s).

Of course, many things can happen and are not strictly related to the effective skill of the respective singers that belong to our team. However, a good team is a team made of winners, with a winning captain as well. And the Captain is pretty important because - as stated in the site:

The captain will be crucial on the final night when his bonuses and maluses are doubled. So choose very carefully. In the 2022 edition, the team that came in first was identical to the team that came in second, same five artists but a different captain. Choose carefully then

Then I thought what about writing a program to solve this maximization problem properly? And CSP came back to my mind!

CSP

From Wikipedia, Constraint Satisfaction Problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. Additionally, the Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP), and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem. From now on, a bit of “logic reasoning” and previous logic knowledge is required. Forgive me if I will not dig into these topics in detail.

Let’s assume this logic program:

P: c ⇐ a ∧ b
   a

In classical logic we have pretty much 3 models:

{a, b, c}, {a, c}, {a}

Among all models, the minimum is evidently {a} (which also corresponds to everything we can derive). Thus, {a} is a stable model of P.

Excluding all that can be said about a stable model, let us just say that stable models have become the foundation of a new programming technique: we are talking about Answer Set Programming (ASP). The result of a computation of an answer set solver is thus one or more stable models: the computational model is practically nonexistent, it is a matter of applying the definition (TL;DR -> going by trial and error) in order to find the stable model of the input program.

This programming paradigm has proved particularly useful for solving combinatorial problems (such as constraint or planning problems). The answer set solver named Clingo is an excellent tool for working on these kinds of problems.

Let’s put some little theory-things together

The first thing to say about ASP is that there are no variables; the input program must be propositional.

For the sake of convenience, however, most solvers provide the option of writing their own rules through the use of variables, after which a grounding module simply allocates each rule with all the combinations of facts contained in the knowledge base.

It is important to keep in mind the presence of this preprocessing step, because if we wrote something like g(f(X)), we could ground it as g(f(a)) or as g(f(f(a)) and so on. Thus, there is a risk that the grounding phase will go into a loop (while the user might be left waiting believing that the solver is solving his problem). The rules must be safe: if we write g(X) somewhere, there must be a fact of the type g(a) for g(X) to be ground.

ASP programs are sets of logic programming rules (exactly as in Prolog). Such rules are thus in the form:

$$ B \vdash A_1, A_2, …, A_n $$

As always, the tail of the rule represents the preconditions while the head is what we can infer thanks to the consequences.

Integrity constraint

Since answer set solvers return a stable model, if we write such a rule (without head):

$$ \vdash A_1, A_2, …, A_n $$

it is as if we are saying that any stable model containing A_1, A_2, …, A_n must be discarded. The absence of a head is in fact interpreted as false, so when all the various A_i’s are true, there is an inference of false and thus a failure with regard to the particular answer set assignment that was being considered (and we will proceed with a new iteration, which will have different assignments).

In addition, the rules used in ASP are extended from those of Prolog. In fact, we have the possibility of expressing classical negation (which is denoted by -, the corresponding of the symbol ¬). There is thus a great difference between writing:

cross :- -auto

and

cross :- not auto

The first rule is stronger: it tells us that we can cross only if -auto is deducible. In the second case, on the other hand, we have the classic negation by failure and so we do not have the fact auto, the rule is activated (thus telling us to cross).

Actually a negated literal -p has no special property, it is considered exactly as a positive atom but the integrity constraint :- p, -p is automatically added (so the two facts are inconsistent if co-present).

Let’s write our program

Ok, the first two constraints we must respect are exactly 5 singers, and no more than 100 Baudi.

#const max_singer = 5.
#const max_baudi = 100.

With the #const statement we can define a const inside the Clingo program. Afterward, we need to do a minimum of copy-past and build our facts:

singer(marco_mengoni,30,26).
singer(giorgia,35,25).
singer(ultimo,35,27).
singer(lazza,100,22).
singer(elodie,120,24).
singer(madame,120,22).
singer(colapesce_dimartino,150,20).
singer(mara_sattei,200,21).
singer(gianluca_grignani,250,20).
singer(gianmaria,250,17).
singer(tananai,250,22).
singer(ariete,330,21).
singer(levante,330,20).
singer(articolo_31,500,21).
singer(colla_zio,500,16).
singer(coma_cose,500,20).
singer(moda,500,18).
singer(paola_e_chiara,500,22).
singer(lda,750,21).
singer(leo_gassman,750,18).
singer(mr_rain,750,19).
singer(anna_oxa,1000,18).
singer(rosa_chemical,1000,19).
singer(i_cugini_di_campagna,1500,21).
singer(olly,1500,16).
singer(sethu,1500,16).
singer(shari,1500,17).
singer(will,1500,16).

The reason I multiplied by 10 the quotation of the singer is that Clingo only knows Integers :). Until now everything should be pretty clear. Let’s dig into something more interesting know…

Aggregate

As stated in the Clingo Guide on page 18, an aggregate is an operation on a multiset of weighted literals that evaluates to some value. In combination with comparisons, we can extract a truth value from an aggregate’s evaluation, thus, obtaining an aggregate atom. We consider aggregate atoms of the form:

$$l\space op [ L1 = w_1, …, Ln = w_n ]\space u$$

So far, an aggregate has a lower bound l, an upper bound u, an operation op, and a multiset of literal L_i each assigned to a weight w_i. An aggregate is true if operation op applied to the multiset of weights of true literals is between the bounds (inclusive). Currently, Clingo supports the aggregates #sum (the sum of weights), #min (the minimum weight), #max (the maximum weight), and #avg (the average of all weights).

Consider this, and assuming the sum is the default, let’s add a new line to the program:

max_singer { selected(N, Q, B) : singer(N, Q, B) } max_singer.

This line represents an aggregate. The first thing to notice is the use of a curly bracket: this implies we are gonna create a set - not a multiset as stated above, thus repetition is not allowed, since we cannot take two times the same artist. The second is, we didn’t specify any weights: this is because we only want 5 selected singers - no matter the costs, we are not considering this at the moment. The lower and upper bound are the same and fixed to the max_singer const to strictly specify the fixed amount of selected.

Costs

Ok, we need to know to put a bit of optimization. Let’s add a new element:

operation_cost(S) :- S = #sum{ I, N, Q : singer(N, Q, I), selected(N, Q, I) }.

With this statement, we are adding a new fact - operation_cost(S) - that actually holds the value of the sum of the amount to be paid - Baudi. I wasn’t able to understand the reason, but actually, the sum doesn’t sum equal things anymore: more in detail, I wasn’t able to create a multi-set in Clingo major > v3.x.x. Thus, I need to use curly and explicitly bind the whole literal - in such a way as to avoid duplicating and thus not counting the right amount. So, the sum is matching the selected singer and adds the amount incrementally in the I variable.

No maximization is defined about this value, but it’s pretty normal (I guess) have this feeling we would like to actually maximize this value: this is an assumption made by reasoning. Even if actually we don’t necessarely want to maximize Baudi, we must choose exactly five artists and… let’s say that

There’s no math way to actually choose them without “take the most out the Baudi”.

But I’m going to give you more about this later on.

Another constraint we need to put is around the quotation: I assume that given a quote over an artist, the more a quotation is low, the more betting on it is an easy choice - less paying bet. Since I want to maximising the chance to get the most promising talents, I think I want this overall quotation value to be minimal. Moreover, I’m not winning anything, I’m just increasing the chance to put into my team the singers considered best for the competition. So I surely need to get the sum of quotation first:

quotation_cost(Q) :- Q = #sum{ I, N, B : singer(N, I, B), selected(N, I, B) }.

Notice that I is bound to the quotation value of the predicates. Afterward, let’s put together minimize operator:

#minimize{Q : quotation_cost(Q)}.

This way, I’m asking Clingo to actually minimize the quotation - choosing the less paid artist, the one I’m assuming (actually, the goverment is assuming) are gonna win the competition.

Maximize use of Baudi?

It’s required - meaning, for real?

#maximize{S : operation_cost(S)}.

This is something that doesn’t change the results - it would be most probably “wrong” since no rules are saying anything about Baudi. We just want to maximize our chance to win, but something is still missing… and it’s still about baudi.

Something is still missing…

#const max_singer = 5.
#const max_baudi = 100.

singer(marco_mengoni,30,26).
singer(giorgia,35,25).
singer(ultimo,35,27).
singer(lazza,100,22).
singer(elodie,120,24).
singer(madame,120,22).
singer(colapesce_dimartino,150,20).
singer(mara_sattei,200,21).
singer(gianluca_grignani,250,20).
singer(gianmaria,250,17).
singer(tananai,250,22).
singer(ariete,330,21).
singer(levante,330,20).
singer(articolo_31,500,21).
singer(colla_zio,500,16).
singer(coma_cose,500,20).
singer(moda,500,18).
singer(paola_e_chiara,500,22).
singer(lda,750,21).
singer(leo_gassman,750,18).
singer(mr_rain,750,19).
singer(anna_oxa,1000,18).
singer(rosa_chemical,1000,19).
singer(i_cugini_di_campagna,1500,21).
singer(olly,1500,16).
singer(sethu,1500,16).
singer(shari,1500,17).
singer(will,1500,16).

max_singer { selected(N, Q, B) : singer(N, Q, B) } max_singer.
operation_cost(S) :- S = #sum{ I, N, Q : singer(N, Q, I), selected(N, Q, I) }.
quotation_cost(Q) :- Q = #sum{ I, N, B : singer(N, I, B), selected(N, I, B) }.
#minimize{Q : quotation_cost(Q)}.
% We saw this is not only not required, but most probably wrong with domain fluctuation higher than the one listed above in the table.
% #maximize{S : operation_cost(S)}. 

#show selected/3.
#show operation_cost/1.
#show quotation_cost/1.

The program as written at the moment is listed above, and as I said it’s not complete. If you want that’s the moment to think about why, otherwise, go ahead!

### Run the program

If you cat the content of the above into a file and run the Clingo inside your cli (brew install clingo) or online the result you are gonna have back a list of possible models until the stable one is found:

clingo version 5.6.2
Reading from fantasanremo
Solving...
Answer: 1
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(lazza,100,22) selected(will,1500,16) quotation_cost(1700) operation_cost(116)
Optimization: 1700
Answer: 2
selected(madame,120,22) selected(mara_sattei,200,21) selected(gianluca_grignani,250,20) selected(levante,330,20) selected(coma_cose,500,20) quotation_cost(1400) operation_cost(103)
Optimization: 1400
Answer: 3
selected(ultimo,35,27) selected(madame,120,22) selected(mara_sattei,200,21) selected(gianmaria,250,17) selected(lda,750,21) quotation_cost(1355) operation_cost(108)
Optimization: 1355
Answer: 4
selected(ultimo,35,27) selected(elodie,120,24) selected(madame,120,22) selected(mara_sattei,200,21) selected(lda,750,21) quotation_cost(1225) operation_cost(115)
Optimization: 1225
Answer: 5
selected(giorgia,35,25) selected(ultimo,35,27) selected(madame,120,22) selected(mara_sattei,200,21) selected(lda,750,21) quotation_cost(1140) operation_cost(116)
Optimization: 1140
Answer: 6
selected(marco_mengoni,30,26) selected(ultimo,35,27) selected(madame,120,22) selected(mara_sattei,200,21) selected(lda,750,21) quotation_cost(1135) operation_cost(117)
Optimization: 1135
Answer: 7
selected(giorgia,35,25) selected(ultimo,35,27) selected(madame,120,22) selected(gianluca_grignani,250,20) selected(tananai,250,22) quotation_cost(690) operation_cost(116)
Optimization: 690
Answer: 8
selected(marco_mengoni,30,26) selected(ultimo,35,27) selected(madame,120,22) selected(gianluca_grignani,250,20) selected(tananai,250,22) quotation_cost(685) operation_cost(117)
Optimization: 685
Answer: 9
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(elodie,120,24) selected(mara_sattei,200,21) selected(gianmaria,250,17) quotation_cost(635) operation_cost(113)
Optimization: 635
Answer: 10
selected(marco_mengoni,30,26) selected(lazza,100,22) selected(elodie,120,24) selected(madame,120,22) selected(colapesce_dimartino,150,20) quotation_cost(520) operation_cost(114)
Optimization: 520
Answer: 11
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(elodie,120,24) selected(madame,120,22) selected(mara_sattei,200,21) quotation_cost(505) operation_cost(118)
Optimization: 505
Answer: 12
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(madame,120,22) selected(mara_sattei,200,21) quotation_cost(420) operation_cost(121)
Optimization: 420
Answer: 13
selected(giorgia,35,25) selected(ultimo,35,27) selected(lazza,100,22) selected(elodie,120,24) selected(madame,120,22) quotation_cost(410) operation_cost(120)
Optimization: 410
Answer: 14
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(madame,120,22) selected(colapesce_dimartino,150,20) quotation_cost(370) operation_cost(120)
Optimization: 370
Answer: 15
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(elodie,120,24) selected(madame,120,22) quotation_cost(340) operation_cost(124)
Optimization: 340
Answer: 16
selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(lazza,100,22) selected(madame,120,22) quotation_cost(320) operation_cost(122)
Optimization: 320
OPTIMUM FOUND

Models       : 16
  Optimum    : yes
Optimization : 320
Calls        : 1
Time         : 40.579s (Solving: 40.12s 1st Model: 0.00s Unsat: 26.47s)
CPU Time     : 40.544s

By looking at the last result, you can confirm our theory:

selected(marco_mengoni,30,26) selected(giorgia,35,25) selected(ultimo,35,27) selected(lazza,100,22) selected(madame,120,22) quotation_cost(320) operation_cost(122)

is the optimum (minimum, stable model of P, recalling the first paragraph). The artists are chosen between the first and paying less than the other, but the cost of choosing the selected artists is not taken into account, in fact, the operation cost is 122 Baudi.

We cannot spend more than 100 Baudi

To avoid this, we have add one more constraint:

:- operation_cost(S), S > max_baudi.

Since answer set solvers return a stable model, if we write a rule like this we are actually defining an integrity constraint - that is actually saying the S bounded-to-operation_cost variable should be discarded if its value is higher than the max_baudi const. The result is that Clingo will proceed with another computation, discarding the set of selected artists chosen until that moment.

Conclusion

The more you get into this, the more you understand that you can actually do so much more. By only taking care of bonus/malus rules, you could assign a chance of things happening by knowing the nature of your favorite artist or by following him on social. That is… if you can quantify properly each of the possible things that are awarded or vice versa, you can put much more maximization/minimization constraints and better decide your team!

If something is wrong, please let me know, in the end… I’m still learning.

Thank you everybody for reading!