ortools-clone/examples/contrib/nontransitive_dice.cs

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections;
using System.Linq;
using System.Text.RegularExpressions;
using Google.OrTools.ConstraintSolver;

public class NonTransitiveDice
{
    /**
     *
     * Nontransitive dice.
     *
     * From
     * http://en.wikipedia.org/wiki/Nontransitive_dice
     * """
     * A set of nontransitive dice is a set of dice for which the relation
     * 'is more likely to roll a higher number' is not transitive. See also
     * intransitivity.
     *
     * This situation is similar to that in the game Rock, Paper, Scissors,
     * in which each element has an advantage over one choice and a
     * disadvantage to the other.
     * """
     *
     * Also see http://www.hakank.org/or-tools/nontransitive_dice.py
     *
     *
     */
    private static void Solve(int m = 3, int n = 6, int minimize_val = 0)
    {
        Solver solver = new Solver("Nontransitive_dice");

        Console.WriteLine("Number of dice: {0}", m);
        Console.WriteLine("Number of sides: {0}", n);
        Console.WriteLine("minimize_val: {0}\n", minimize_val);

        //
        // Decision variables
        //

        // The dice
        IntVar[,] dice = solver.MakeIntVarMatrix(m, n, 1, n * 2, "dice");
        IntVar[] dice_flat = dice.Flatten();

        // For comparison (probability)
        IntVar[,] comp = solver.MakeIntVarMatrix(m, 2, 0, n * n, "dice");
        IntVar[] comp_flat = comp.Flatten();

        // For branching
        IntVar[] all = dice_flat.Concat(comp_flat).ToArray();

        // The following variables are for summaries or objectives
        IntVar[] gap = solver.MakeIntVarArray(m, 0, n * n, "gap");
        IntVar gap_sum = gap.Sum().Var();

        IntVar max_val = dice_flat.Max().Var();
        IntVar max_win = comp_flat.Max().Var();

        // number of occurrences of each value of the dice
        IntVar[] counts = solver.MakeIntVarArray(n * 2 + 1, 0, n * m, "counts");

        //
        // Constraints
        //

        // Number of occurrences for each number
        solver.Add(dice_flat.Distribute(counts));

        // Order of the number of each die, lowest first
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n - 1; j++)
            {
                solver.Add(dice[i, j] <= dice[i, j + 1]);
            }
        }

        // Nontransitivity
        for (int i = 0; i < m; i++)
        {
            solver.Add(comp[i, 0] > comp[i, 1]);
        }

        // Probability gap
        for (int i = 0; i < m; i++)
        {
            solver.Add(gap[i] == comp[i, 0] - comp[i, 1]);
            solver.Add(gap[i] > 0);
        }

        // And now we roll...
        // comp[] is the number of wins for [A vs B, B vs A]
        for (int d = 0; d < m; d++)
        {
            IntVar sum1 = (from r1 in Enumerable.Range(0, n) from r2 in Enumerable.Range(0, n)
                               select(dice[d % m, r1] > dice[(d + 1) % m, r2]))
                              .ToArray()
                              .Sum()
                              .Var();

            solver.Add(comp[d % m, 0] == sum1);

            IntVar sum2 = (from r1 in Enumerable.Range(0, n) from r2 in Enumerable.Range(0, n)
                               select(dice[(d + 1) % m, r1] > dice[d % m, r2]))
                              .ToArray()
                              .Sum()
                              .Var();

            solver.Add(comp[d % m, 1] == sum2);
        }

        //
        // Search
        //
        DecisionBuilder db = solver.MakePhase(all, Solver.INT_VAR_DEFAULT, Solver.ASSIGN_MIN_VALUE);

        if (minimize_val > 0)
        {
            Console.WriteLine("Minimizing max_val");

            OptimizeVar obj = max_val.Minimize(1);

            // Other experiments:
            // OptimizeVar obj = max_win.Maximize(1);
            // OptimizeVar obj = gap_sum.Maximize(1);

            solver.NewSearch(db, obj);
        }
        else
        {
            solver.NewSearch(db);
        }

        while (solver.NextSolution())
        {
            Console.WriteLine("gap_sum: {0}", gap_sum.Value());
            Console.WriteLine("gap: {0}",
                              (from i in Enumerable.Range(0, m) select gap[i].Value().ToString()).ToArray());
            Console.WriteLine("max_val: {0}", max_val.Value());
            Console.WriteLine("max_win: {0}", max_win.Value());
            Console.WriteLine("dice:");
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write(dice[i, j].Value() + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine("comp:");
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    Console.Write(comp[i, j].Value() + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine("counts:");
            for (int i = 1; i < n * 2 + 1; i++)
            {
                int c = (int)counts[i].Value();
                if (c > 0)
                {
                    Console.Write("{0}({1}) ", i, c);
                }
            }
            Console.WriteLine("\n");
        }

        Console.WriteLine("\nSolutions: {0}", solver.Solutions());
        Console.WriteLine("WallTime: {0}ms", solver.WallTime());
        Console.WriteLine("Failures: {0}", solver.Failures());
        Console.WriteLine("Branches: {0} ", solver.Branches());

        solver.EndSearch();
    }

    public static void Main(String[] args)
    {
        int m = 3;            // number of dice
        int n = 6;            // number of sides of each die
        int minimize_val = 0; // minimizing max_max (0: no, 1: yes)

        if (args.Length > 0)
        {
            m = Convert.ToInt32(args[0]);
        }

        if (args.Length > 1)
        {
            n = Convert.ToInt32(args[1]);
        }

        if (args.Length > 2)
        {
            minimize_val = Convert.ToInt32(args[2]);
        }

        Solve(m, n, minimize_val);
    }
}