Virtual Chess Tournament

This example is another challenge posted by the dmcommunity.org as a challenge. It is the December 2020 challenge. Its specification is as follows:

Virtual Chess Tournament

Three world champions Fischer, Kasparov, and Karpov played in a virtual chess tournament. Each player played 7 games against two other opponents. Each player received 2 points for a victory, 1 for a draw, and 0 for a loss. We know that Kasparov, known as the most aggressive player, won the most games. Karpov, known as the best defensive player, lost the least games. And Fischer, of course, won the tournament.

Questions

  1. Is it really possible? Does this problem have a solution?
  2. If yes, what is the final score?
  3. Are there other possible solutions?

This is quite a cool problem to model in cDMN. As always, we start by creating the glossary. We first need to create types to represent the following concepts:

  • Person (Fischer, Kasparov, Karpov)
  • Game (1 through 7)
  • Score
  • Result (win, loss, draw)

Thus, we create a glossary table as such:

Type
Name Type Values
Person String Fischer, Kasparov, Karpov
Game Int [1..7]
Score Int [1..28]
Result String Win, Loss, Draw

Now we need to think about what other concepts we need to express. First of all, we need a way to keep track of the result of games between two players. This could be represented by a function, as every game has exactly one result. To keep track of the final scores of a player, we will also use a function, for the same reason (every player has exactly one final score). Lastly, we will want to count the total number of wins and losses of every player, and again we can perfectly use functions here.

Function
Name Type
result of Game between Person and Person Result
score of Person Score
games won of Person Score
games lost of Person Score

And that’s all we need for this specific challenge. Now that our glossary is done, we can move on to implementing the logic. We start by implementing the table to count the score. To do this, we “loop over” every game played, we check the result and we set the score accordingly. The first rule in the table table below can be read as “For every person p1 and person p2 (that is not p1) and game, if the result of the game was a Win, then we add 2 to the score of the first person.

Score
C+ Person called p1 Person called p2 Game result of Game between p1 and p2 score of p1
1 - not(p1) - Win 2
2 - not(p1) - Draw 1
3 - not(p1) - Loss 0

One important caveat is that we must not forget to express the asymmetry within the result of Game between p1 and p2 function. Indeed, if p1 has won from p2, then p2 must always have lost from p1. To do this, we can add a constraint table to make sure that this is always the case.

Rule 2
E* Person called p1 Person called p2 Game result of Game between p1 and p2 result of Game between p2 and p1
1 - not(p1) - Win Loss
2 - not(p1) - Draw Draw
3 - not(p1) - Loss Win

Next, we still need a way to count the number of wins and losses for every player. This can easily be done by introducing count tables. It works similarly to the table to count the scores: we loop over every game, and add 1 to the number of games won if the result was a win.

Count Wins
C+ Person called p1 Person called p2 Game result of Game between p1 and p2 games won of p1
1 - not(p1) - Win 1

Count Losses
C+ Person called p1 Person called p2 Game result of Game between p1 and p2 games lost of p1
1 - not(p1) - Loss 1

Now all that remains is creating the score, wins and losses constraints. To express that “Fischer has won”, we want to express that he always has the highest score. We express “Kasparov wins the most games” and “Karpov loses the fewest games” similarly, all in one constraint table (although it could as easily be expressed in three different ones).

Final constraints
E* score of Fischer games won of Kasparov games lost of Karpov
1 > score of Kasparov > games won of Fischer < games lost of Fischer
2 > score of Karpov > games won of Karpov < games lost of Kasparov

We can now run our model using the cDMN solver. For example, this is one of the solutions found by the solver:

Number of models: 1
Model 1
=======
structure  : V {
  games_lost_of_Person = { Fischer->3; Karpov->2; Kasparov->5 }
  games_won_of_Person = { Fischer->4; Karpov->1; Kasparov->5 }
  result_of_Game_between_Person_and_Person = { 1,Fischer,Fischer->Loss; 1,Fischer,Karpov->Draw; 1,Fischer,Kasparov->Win; 1,Karpov,Fischer->Draw; 1,Karpov,Karpov->Draw; 1,Karpov,Kasparov->Draw; 1,Kasparov,Fischer->Loss; 1,Kasparov,Karpov->Draw; 1,Kasparov,Kasparov->Loss; 2,Fischer,Fischer->Win; 2,Fischer,Karpov->Draw; 2,Fischer,Kasparov->Win; 2,Karpov,Fischer->Draw; 2,Karpov,Karpov->Draw; 2,Karpov,Kasparov->Win; 2,Kasparov,Fischer->Loss; 2,Kasparov,Karpov->Loss; 2,Kasparov,Kasparov->Loss; 3,Fischer,Fischer->Loss; 3,Fischer,Karpov->Draw; 3,Fischer,Kasparov->Loss; 3,Karpov,Fischer->Draw; 3,Karpov,Karpov->Loss; 3,Karpov,Kasparov->Loss; 3,Kasparov,Fischer->Win; 3,Kasparov,Karpov->Win; 3,Kasparov,Kasparov->Win; 4,Fischer,Fischer->Loss; 4,Fischer,Karpov->Draw; 4,Fischer,Kasparov->Loss; 4,Karpov,Fischer->Draw; 4,Karpov,Karpov->Win; 4,Karpov,Kasparov->Draw; 4,Kasparov,Fischer->Win; 4,Kasparov,Karpov->Draw; 4,Kasparov,Kasparov->Draw; 5,Fischer,Fischer->Win; 5,Fischer,Karpov->Draw; 5,Fischer,Kasparov->Loss; 5,Karpov,Fischer->Draw; 5,Karpov,Karpov->Win; 5,Karpov,Kasparov->Draw; 5,Kasparov,Fischer->Win; 5,Kasparov,Karpov->Draw; 5,Kasparov,Kasparov->Draw; 6,Fischer,Fischer->Win; 6,Fischer,Karpov->Draw; 6,Fischer,Kasparov->Win; 6,Karpov,Fischer->Draw; 6,Karpov,Karpov->Loss; 6,Karpov,Kasparov->Draw; 6,Kasparov,Fischer->Loss; 6,Kasparov,Karpov->Draw; 6,Kasparov,Kasparov->Draw; 7,Fischer,Fischer->Win; 7,Fischer,Karpov->Draw; 7,Fischer,Kasparov->Win; 7,Karpov,Fischer->Draw; 7,Karpov,Karpov->Loss; 7,Karpov,Kasparov->Loss; 7,Kasparov,Fischer->Loss; 7,Kasparov,Karpov->Win; 7,Kasparov,Kasparov->Draw }
  score_of_Person = { Fischer->15; Karpov->13; Kasparov->14 }
}

Elapsed Time:
6.214157

And there is our answer to question one and two.

  1. It is really possible
  2. The final score is Fischer: 15, Karpov: 13 and Kasparov: 14.

The answer for the third question is a bit more difficult. Because the search space is rather big, the internal solver has difficulties finding all the solutions. Therefore, it is unable to conclude in reasonable time that there exist solutions in which there is a different result for the final scores.