Fischer vs. Kasparov vs. Karpov

On a long flight back to the US I had a few hours to kill. So, I decided to implement one of my favorite modeling tests that I used to give to my students and they always enjoyed it. This time I wanted to try it myself with the newest OpenRules Decision Modeling facilities (see Rule Solver).

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
Is it really possible? Does this problem have a solution? If yes, what is the final score? Are there other possible solutions?

Before you continue to read, you may try first to solve this problem using your favorite programming language or any rule engine or constraint solver.  It would be interesting to compare your solution with what is described below. You may find a Java-based solution among JSR-331 samples.  I was more interested in validating if OpenRules really allows a business analyst (not a programmer) to build a decision model for this problem without programming. So, I limited my decision modeling tools to Excel tables that are based on OpenRules templates. Read below and judge yourself.

Problem Definition

To define the problem, we need to do the following:

  1. State that each pair of players played exactly 7 games
  2. Define personal victories, losses, and draws for each player
  3. Define collected points for each player
  4. Express the problem’s main constraints about total wins, loses, and points.

Thus, I started with the following top-level table of the type “Decision”:

The first sub-decision should express the facts that Kasparov played exactly 7 games against Karpov and against Fisher, and that Karpov played exactly 7 games against Fisher.

Like with any decision model, one of the crucial parts of the modeling is to correctly decide what the decision variables (unknowns) of the problem are. The first impulse is to start with variables “Kasparov played against Karpov”, “Kasparov played against Fisher”, and “Karpov played against Fisher”.  However, these variables would not allow us to express variables that correspond to the number of games won by Fisher or lost by Karpov. Thus, we need to go to a lower level and use the variables that represent how each player played against his opponents. So, I decided to define 9 basic decision variables:

  • Kasparov won against Karpov
  • Kasparov lost against Karpov
  • Kasparov drew against Karpov
  • Kasparov won against Fisher
  • Kasparov lost against Fisher
  • Kasparov drew against Fisher
  • Karpov won against Fisher
  • Karpov lost against Fisher
  • Karpov drew against Fisher

Using these decision variables we would be able to express all other problem variables. So, I created my initial Glossary as follows:

I decided that all my variables will belong to a business concept “Tournament”, gave brief names to technical attributes, and defined the variable’s domains as “0-7”. We still do not know what the actual values of these variables will be, but we expect that our constraints will help us to figure them out. Now, we may express other decision variables using these variables as they were known. In particular, I added 3 more variables to the glossary:

We know that these variables may accept only value 7, so I defined their domain as “7-7”. And now, I am ready to specify our first sub-decision using the following decision table:

Here I used the predefined action “ActionSum” that defines a variable in the first column as a sum of variables listed (via comma) in the second column.

Now we are ready to define personal victories, draws, and losses for each player. Here is the proper decision table:

Here I used the predefined action “ActionXoperYcompareZ”. I hope this table is intuitive enough, e.g. the first rule states that the variable “Kasparov won” is equal to the sum of variables “Kasparov won against Karpov” and “Kasparov won against Fisher”.   Of course, we need to add new 9 variables to our glossary:

As each player played total 14 games, the maximal value for all these variables is 14 (and obviously the minimal value is 0). This completes the implementation of the second sub-decision.

Now we need to define the numbers of points collected by each player. As we’ve already defined numbers of victories, losses, and draws for each player, we may use the following table for the third sub-decision (Chess 7):

Here we used the predefined action “ActionScalProd”, that defines variables in the first column as scalar products of numbers listed in the second column and variables listed in the third column. For example, the first rule states:

Kasparov points = (2 * Kasparov won)  + (1 * Kasparov drew)

When I added 3 new “point”-variables to the glossary, the final glossary started to look as below:

The reader will easily guess why I defined the domain for point-variables as “0-28”: even if a player won all 14 games he would not get more than 2*14=28 points.

And finally, the fourth sub-decision may be naturally expressed in the following decision table:

Hope this table does not require additional explanations. This completes the definition of our problem.

Problem Resolution

A nice thing about OpenRules Rule Solver is that it allows you to concentrate on “WHAT” and do not worry about “HOW”. It means that when a problem is defined you may rely on the default solution search.  We may simply run the default Java launcher for this problem. Here are the results:

I did not create a special printing method for a found solution (while it is easy to do) – I simply used a bold font for numbers of points. But even from this default output, we can see that OpenRules engine has found a solution where Fisher got 15 points, Kasparov 14 points, and Karpov 13 points. We also can see the values of all other decision variables, for example: Kasparov lost against Fisher 4 games and Kasparov won against Fisher 3 games.

Does this problem has more than one solutions? How to find them? To do that we may simply add a parameter “MaxSolutions” to our decision. So far, we used the default Java launcher that looked as below:

Now we may add a line that specifies a maximal number of solutions we are interested in (probably 10 is enough):

If we execute this launcher, we will receive the following output:

As you can see, there is another solution when Kasparov came third – note changes in other decision variables too. Thus, we found two solutions. More than that, we are guaranteed that there are no more other solutions for this problem.

Conclusion

Of course, my actual development of this decision model was not as smooth as I described above. Of course, initially I made several errors while defining the Glossary and the above decision tables. But Rule Solver helped me to quickly fix syntax errors, and produced a reasonably good diagnostics when I made some structural errors. Still, I did receive all solutions before my airplane landed in Newark. I hope the reader would also appreciate the power and simplicity of OpenRules Rule Solver.  You may learn more about modeling and solving constraint satisfaction problems in this User Manual.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Constraint Programming, Decision Management, Optimization, Rule Engines. Bookmark the permalink.

One Response to Fischer vs. Kasparov vs. Karpov

  1. Tom Mollison says:

    It’s Fischer. Not Fisher.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s