Revista de Matema´tica: Teor´ıa y Aplicaciones 2010 17(1) : 53–68
cimpa – ucr issn: 1409-2433
circular chains of chinese dice
cadenas circulares de dados chinos
Eduardo Piza∗ Leo Schubert∗∗
Received: 6 Jan 2009; Revised: 28 Oct 2009; Accepted: 30 Oct 2009
Keywords: Chinese dice, mixed-integer programming, simulated anneal-
ing, combinatorial optimization.
Palabras clave: Dados chinos, programacio´n entera mixta, sobrecalen-
tamiento simulado, recocido simulado, optimizacio´n combinatoria.
Mathematics Subject Classification: 05B99, 90C11, 90C27.
∗CIMPA, Universidad de Costa Rica, 2060 San Jose´, Costa Rica. Email:
eduardo.piza@ucr.ac.cr
∗∗University of Applied Sciences of Konstanz, Postfach 100543, D-78405 Konstanz,
Germany. Email: schubert@htwg-konstanz.de
53
54 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
Abstract
In this paper we study Chinese dice, mathematical objects simi-
lar to ordinary dice but allowing repetition among their face values.
We say that a die A is preferred over a die B (written A  B) if A
wins more frequently than B does. We study first the existence of
circular chains of three dice A, B, C (those that A  B  C  A)
using a mixed integer programming algorithm. Then we generalize
the problem to n-dimensional dice—that is, dice of n faces, with
n ≥ 4—and we search circular chains of length m (with m ≥ 3)
using a simulated annealing algorithm. We compare some differ-
ent objective functions and obtain good solutions to the problem
with very efficient algorithms. Finally we obtain a theoretical result
concerning the existence of circular chains in the general case.
Resumen
En este art´ıculo estudiamos los dados chinos, objetos matema´ticos
similares a los dados ordinarios pero con la diferencia que pueden
repetir algunos de sus lados. Decimos que el dado A es preferido
sobre el dado B si A gana con mayor frecuencia que B. Estudiamos
primero la existencia de cadenas circulares de tres dados A, B, C
(aquellos para los cuales A  B  C  A) utilizando un algoritmo
de programacio´n lineal entera. Luego generalizamos el problema
al caso de dados n-dimensionales, esto es, dados de n caras (con
n ≥ 4) y cadenas circulares de m dados (con m ≥ 3), utilizando
un algoritmo de recocido simulado. Comparamos diversas funciones
objetivas y obtenemos buenas soluciones al problema con algoritmos
eficientes. Finalmente obtenemos un resultado teo´rico acerca de la
existencia de cadenas circulares para el caso general.
1 Introduction
Normal dice have the numbers 1, 2, 3, 4, 5, 6 printed on their faces,
without repetition, each face having the same probability output, and
with opposite faces summing to 7. The Chinese dice also have numbers
from {1, 2, 3, 4, 5, 6} printed on their faces, but allow repetitions. We can
represent Chinese dice as vectors in {1, 2, 3, 4, 5, 6}6 , each coordinate corre-
sponding to a face. For instance, two dice A and B would be (2, 3, 3, 2, 3, 6)
and (2, 2, 5, 5, 6, 1), as shown in Figure 1.
We say that a Chinese die A is preferred over Chinese die B (written
A  B) if after rolling the dice, A wins more frequently than B, that
is, the probability that A wins or ties is greater than 12 . For example,
with the two Chinese dice A = (2, 3, 3, 2, 3, 6) and B=(2, 2, 5, 5, 6, 1) of
circular chains of chinese dice 55
Figure 1, we can compute all the possible outputs (we assume that the
dice outcomes are equally likely) in a matrix, as illustrated in Figure 1.
Figure 1: Comparing the Chinese dice A = (2, 3, 3, 2, 3, 6) and
B=(2, 2, 5, 5, 6, 1). The values in the table have the following meaning:
‘1’ means ‘A wins’, ‘0’ means ‘is a tie’, ‘−1’ means ‘B wins’. In this ex-
ample, A wins 16 times and loses only 15 times, so die A is preferred over
die B: A  B.
Normal dice have the same strength among themselves: when com-
paring two “fair dice” we obtain 15 wins for each die and 6 ties. It is
completely different when dealing with Chinese dice, where we can have
extreme cases, for example A = (6, 6, 6, 6, 6, 6) and B = (1, 1, 1, 1, 1, 1), in
which A wins against B all the time.
In this article we study the existence of circular chains of Chinese
dice, for example three Chinese dice A, B, C such that A  B  C  A.
The existence of these chains is somewhat surprising and seems to be a
paradox, but it is not. We are interested in finding circular chains of
Chinese dice in such a way that the differences in preference between dice
will be as high as possible, but balanced among themselves. Later on, we
formulate a generalization of these circular chains, considering dice with
n ≥ 4 faces and chains of length m ≥ 3.
2 Solutions using mixed-integer programming
Let A,B,C be three Chinese dice. Our first two models for finding
circular chains use the mixed-integer programming technique to maximize
an objective function.
56 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
2.1 First model: maximizing the winning frequency
In this first approach we maximize the following objective function:
max ZAB + ZBC + ZCA − λ · (v1 + v2 + v3 + c1 + c2 + c3), (1)
subject to the following restrictions:
XAi −XBj ≤ (1− δAiBj) ·M, for i, j = 1, . . . , 6, (2a)
XAi −XBj ≥ − δAiBj ·M, for i, j = 1, . . . , 6, (2b)
ZAB +
∑
i,j δAiBj = 36. (3)
The corresponding restrictions for dice B-C and C-A are analogous to the
restrictions in (2a), (2b) and (3). We also have 3 additional restrictions:
(ZAB − ZBC) + v1 − c1 = 0, (4a)
(ZAB − ZCA) + v2 − c2 = 0, (4b)
(ZBC − ZCA) + v3 − c3 = 0, (4c)
so, in total we have 222 different restrictions (73 restrictions in (2a), (2b)
and (3) concerning the dice A-B and the same quantity for the dice B-C
and C-A, plus the 3 restrictions in (4a), (4b), (4c)). The meaning of the
variables and symbols is:
ZAB : is the number of cases (from the 36 total cases) where die A wins
against die B (analogous with the other quantities ZBC and ZCA).
So, ZAB/36 is the probability that A wins against B.
XAi: output value of the face i in die A. Similarly for XBj .
vk, ck: Slack-variables used to avoid a void solution (solution when a die
wins in all 36 cases and other dice do not win in any case), k = 1, 2, 3.
λ: parameter used to avoid a void solution (for example, λ = 100).
δAiBj : 0-1 variable, which has a value 1 in the restrictions (2a) and (2b)
when the die A with the face i cannot win against die B with the
face j (similarly with pairs of dice B-C and C-A).
M : a “big” number (for example, M = 6).
: a “small” positive number (for example,  = 0.5).
circular chains of chinese dice 57
We find the solution (see Figure 2) to this problem in approximately 15
minutes, using Cplex, well-known specialized software for mixed-integer
programming problems [2, 3, 4, 7], using an “average” home computer1.
The solution found is a global optimal, as we can see by other methods.
However, the computer process to formally verify that it is a global optimal
solution was interrupted after more than 2 hours.
Die A = (2, 2, 3, 3, 6, 6), ZAB = 20, ZBA = 16, DA = 4,
Die B = (1, 1, 5, 5, 5, 5), ZBC = 20, ZCB = 16, DB = 4,
Die C = (3, 3, 4, 4, 4, 6), ZCA = 20, ZAC = 10, DC = 10.
Figure 2: The “4-4-10” solution found with our first model.
In Figure 2 the quantity DA is defined as the difference ZAB − ZBA.
Similarly, DB = ZBC −ZCB and DC = ZCA−ZAC . The solution found is
not unique, of course. We refer to this solution as the “4-4-10” solution,
according to the values of DA,DB ,DC .
2.2 Modifications to speed the algorithm
In order to reduce the computer time in the previously mentioned
model, we tried a slight modification of some of the parameters. In spite
of this we did not find a significant reduction, although some reduction was
found when changing the parameters toM = 5 in (2),  = 0.01 in (2b) and
λ = 0.25 in (1). In fact, the computer time was reduced by approximately
10% in finding the same “4-4-10” solution shown in Figure 2, but still the
whole process had to be interrupted after more than 2 hours, without the
confirmation that the solution is a global maximum.
However, we found a significant reduction in computer time when we
considered the following 27 additional restrictions. The idea is to eliminate
some combinations of dice outcomes that do not have enough potential to
win:
XA6 −XB4 ≥ 0, XB6 −XC4 ≥ 0, XC6 −XA4 ≥ 0, (5a)
XA5 −XB3 ≥ 0, XB5 −XC3 ≥ 0, XC5 −XA3 ≥ 0, (5b)
XA4 −XB2 ≥ 0, XB4 −XC2 ≥ 0, XC4 −XA2 ≥ 0, (5c)
XA3 −XB1 ≥ 0, XB3 −XC1 ≥ 0, XC3 −XA1 ≥ 0, (5d)
and for all i < j:
XAi −XAj ≤ 0, XBi −XBj ≤ 0, XCi −XCj ≤ 0. (6)
1A Dell laptop with 512 MB RAM and 2 GHz Intel processor.
58 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
Proposition 1: The quality of the solutions of the model presented in
section 2.1 is the same when we consider the additional 27 restrictions
(5a), (5b), (5c), (5d) and (6).
Proof: The last 15 restrictions in (6) only establish an order in the com-
ponents of the vector, but do not change or restrict the quality of the
solutions in the model. On the other hand, taking the first part of the
restrictions in (5a), (5b), (5c) and (5d) together, we have
(XA6 ≥ XB4) ∧ (XA5 ≥ XB3) ∧ (XA4 ≥ XB2) ∧ (XA3 ≥ XB1).
With this restriction the feasible area is reduced by
¬[(XA6 ≥ XB4) ∧ (XA5 ≥ XB3) ∧ (XA4 ≥ XB2) ∧ (XA3 ≥ XB1)]
= ¬(XA6 ≥ XB4) ∨ ¬(XA5 ≥ XB3) ∨ ¬(XA4 ≥ XB2) ∨ ¬(XA3 ≥ XB1)
= (XA6 < XB4) ∨ (XA5 < XB3) ∨ (XA4 < XB2) ∨ (XA3 < XB1). (7)
Then, with the inequalities in (6), the condition (7) implies:
{XA1, XA2, XA3, XA4, XA5, XA6} < {XB4, XB5, XB6} (8a)
∨{XA1, XA2, XA3, XA4, XA5} < {XB3, XB4, XB5, XB6} (8b)
∨{XA1, XA2, XA3, XA4} < {XB2, XB3, XB4, XB5, XB6}. (8c)
∨{XA1, XA2, XA3} < {XB1, XB2, XB3, XB4, XB5, XB6}. (8d)
These last conditions (8a), (8b), (8c), (8d) show that in at least 18 cases
(from the 36 total cases) the die A has to lose against the die B. In the
condition (8a) three faces from die B have numbers greater than all the
faces of die A. Then, A has to lose against B in at least 18 cases. Conse-
quently, if die A never wins with the solutions that satisfy the restrictions
in (5a)–(5d) and (6), then all the solutions with potential to win were
in the feasible region. But also these restrictions eliminate the situations
when die A cannot win or lose! The corresponding restrictions for the
pairs of dice B-C and C-A yields analogous conditions and results.
With these additional restrictions, the computer time needed to find
the optimal solution was between 1 and 6 seconds. In many cases 3 seconds
were enough.
2.3 Second model: maximizing the winning differences
In order to find a circular of Chinese dice that maximizes the winning
differences between dice (obtaining more “balanced” solutions), let us
consider the following modification of the objective function in (1):
circular chains of chinese dice 59
max (1−α)(ZAB+ZBC+ZCA)−α(ZBA+ZCB+ZAC)−λ·(v1+v2+v3+c1+c2+c3),
(9)
subject to the following restrictions:
XAi −XBj ≤ (1− δAiBj) ·M, for i, j = 1, . . . , 6, (10a)
XAi −XBj ≥ − δAiBj ·M, for i, j = 1, . . . , 6, (10b)
ZAB +
∑
i,j δAiBj = 36. (11)
The corresponding restrictions for dice B-C and C-A are analogous to the
restrictions in (10a), (10b) and (11). We also have 3 additional restrictions:
(ZAB − ZBA)− (ZBC − ZCB) + v1 − c1 = 0, (12a)
(ZAB − ZBA)− (ZCA − ZAC) + v2 − c2 = 0, (12b)
(ZBC − ZCB)− (ZCA − ZAC) + v3 − c3 = 0, (12c)
for a total of 222 restrictions. The meaning of the variables and pa-
rameters are the same as in Section 2.1. The new parameter α (with
0 ≤ α ≤ 1) weighs the relative importance of the winning frequencies of
one die against the losing frequencies of the other corresponding die. By
combining different values of α and λ we obtain the solutions shown in
Table 1. In this figure we show four different complete balanced “5-5-5”
solutions: in some sense these solutions are optimal. Values of λ < 12 leads
to “unbalanced” solutions, in contrast to values of λ ≥ 12 , that produce
“balanced” solutions.
3 General chains of n-dimensional Chinese dice
Our Chinese dice have two interesting sources of generalization:
1. To find circular chains of m Chinese dice A1, A2, . . . , Am, with
m > 3: A1  A2  . . .  Am  A1.
2. To work with general Chinese dice of n faces (n ≥ 4), that is, n-di-
mensional Chinese dice, instead of the regular 6-face dice. In this
case, a die is represented by a vector (x1, x2, . . . , xn), where each
coordinate xi ∈ {1, 2, . . . , n} (this allows repetitions).
In Figure 3 we illustrated some n-dimensional Chinese dice. In order
to find circular chains in these more general context, we need another
60 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
λ = 0.0 λ = 0.1 λ = 0.5 λ = 1.0 λ = 10.0
α
=
0.
0
A: 333333 A: 225555 A: 114446 A: 133366 A: 113555
B: 222222 B: 444444 B: 333336 B: 222555 B: 144444
C: 111466 C: 333366 C: 222555 C: 144444 C: 222266
“36-0-0” sol “12-12-4” sol “5-6-6” sol “6-6-5” sol “4-4-4” sol
20 sec. 79 sec. 153 sec. 156 sec. 220 sec.
α
=
0.
4
A: 555555 A: 444444 A: 333336 A: 122555 A: 122555
B: 222222 B: 222266 B: 222555 B: 144444 B: 144444
C: 111666 C: 115555 C: 114446 C: 123366 C: 123366
“36-0-0” sol “12-4-12” sol “6-6-5” sol “5-5-5” sol “5-5-5” sol
123 sec. 228 sec. 832 sec. 694 sec. 733 sec.
α
=
0.
5
A: 333666 A: 333333 A: 333336 A: 124444 A: 122555
B: 555555 B: 222266 B: 122556 B: 233336 B: 144444
C: 444444 C: 115555 C: 114446 C: 112555 C: 123366
“0-36-0” sol “12-4-12” sol “5-5-5” sol “5-5-5” sol “3-3-3” sol
112 sec. 107 sec. 133 sec. 144 sec. 123 sec.
α
=
0.
6
A: 111666 A: 114555 A: 333466 A: 444455 A: 333345
B: 333333 B: 333333 B: 124555 B: 233556 B: 222555
C: 222222 C: 222266 C: 444444 C: 115555 C: 124446
“0-36-0” sol “12-12-4” sol “5-6-6” sol “4-4-4” sol “4-4-4” sol
510 sec. 349 sec. 450 sec. 500 sec. 528 sec.
Table 1: The principal solutions found with the model of Section 2.3.
kind of algorithm different from mixed-integer programming, because we
experienced a fast increase in restrictions and computer time when m or
n (or both) grew. For this purpose we employed a simulated annealing
algorithm with great success, described in some detail in Section 4
Figure 3: Some n-dimensional Chinese dice.
Givenm Chinese dice of n-dimensions A1, A2, . . . , Am, let us define the
quantities Zi and Z¯i (for i = 1, . . . ,m) in analogous form as in Section 2.1:
Zi: is the number of cases (from the n2 total cases) where Chinese die
Ai wins against Chinese die Ai+1 (or Chinese die A1 when i = m).
circular chains of chinese dice 61
Thus, the probability that Ai wins is Zi/n2.
Z¯i: is the number of cases where Chinese die Ai+1 (or Chinese die A1
when i = m) wins against Chinese die Ai.
Our primary objective is to find Chinese dice A1, A2, . . . , Am such that
the quantities Zi − Z¯i are all positive. Furthermore, we also want to find
optimal solutions, in the sense that these differences Zi − Z¯i are maximal
and balanced (approximately equal among themselves). To achieve these
aims, we study the maximization of two different objective functions, using
a simulated annealing algorithm described in Section 4.
3.1 Maximizing the sum of the differences Zi − Z¯i
We consider the semi-concave function f(x) =
√
x, if x > 0, and
f(x) = x, if x ≤ 0, as shown in Figure 4. In this approach our problem is
to maximize the objective function
f(Z1 − Z¯1) + f(Z2 − Z¯2) + · · ·+ f(Zm − Z¯m), (13)
over all the possible n-dimensional Chinese dice A1, A2, . . . , Am. The se-
lection of this specific function f fits the desire to penalize negative values
of the difference Zi − Z¯i and at the same time to favour the approximate
equality among these quantities. We tested some other similar functions
instead of f , for example fˆ(x) = ln(1+x), if x > 0 and fˆ(x) = x, if x ≤ 0.
In the end we obtained equivalent solutions with all these kinds of semi-
concave functions, and we decided to select the function f described above
due to its simplicity, from the point of view of computer time needed to
evaluated it.
Figure 4: The semi-concave functions f and fˆ of our first approach to find
circular chains of n-dimensional Chinese dice A1, A2, . . . , Am.
Using this approach we find solutions very quickly, some of them are
shown in Table 2.
62 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
n = 4 dimensions n = 5 dimensions n = 6 dimensions
m = 3 m = 4 m = 3 m = 4 m = 3 m = 4
A1: 1144 A1: 3232 A1: 44411 A1: 25225 A1: 622622 A1: 333333
A2: 3313 A2: 2242 A2: 33333 A2: 11555 A2: 115555 A2: 226262
A3: 2242 A3: 4141 A3: 22525 A3: 44444 A3: 343334 A3: 551515
A4: 1333 A4: 33333 A4: 444444
“2-2-2” “2-2-2-2” “5-5-7” “1-5-25-5” “4-12-12” “12-4-12-36”
0.00 sec. 0.27 sec. 11.65 sec. 23.78 sec. 16.59 sec. 52.78 sec.
Table 2: Some solutions obtained by our simulated annealing algorithm,
using the semi-concave functions f . For example, for n = 6 and n = 3
we obtain a “4-12-12” solution: the numbers inside quotes denote the
quantities Zi − Z¯i.
3.2 Finding more balanced solutions
The solutions obtained by the preceding model are not as balanced as
we would like. In order to find more balanced solutions, we changed the
objective function (to be maximized) as follows:
m∑
i=1
λ · (Zi − Z¯i)− (1− λ) · |(Zi − Z¯i)− (Zi+1 − Z¯i+1)|, (14)
where λ ∈ (0, 1) is a fixed parameter. In this way we penalize unbalanced
solutions. Our simulated annealing algorithm quickly produced very bal-
anced solutions using this objective function, as shown in Table 3.
n = 4 dimensions n = 5 dimensions n = 6 dimensions
m = 3 m = 4 m = 3 m = 4 m = 3 m = 4
B1: 1441 C1: 4141 A1: 33333 A1: 33333 A1: 363333 A1: 334332
B2: 3313 C2: 3331 A2: 52225 A2: 33522 A2: 125562 A2: 626222
B3: 2224 C3: 3232 A3: 44115 A3: 11255 A3: 141644 A3: 515512
C4: 2242 A4: 14144 A4: 414144
“2-2-2” “2-2-2-2” “5-5-5” “5-5-3-5” “5-5-5” “8-8-8-8”
0.33 sec. 2.25 sec. 10.49 sec. 15.38 sec. 17.74 sec. 45.92 sec.
Table 3: Modification of the objective function in (14) produces more
balanced solutions. Here we show some results only for λ = 0.5.
circular chains of chinese dice 63
3.3 Theoretical results
Our simulated annealing algorithm can compute good and balanced
circular chains of Chinese dice for a large variety of values of n ≥ 4 and
m ≥ 3, in a relative low time. On the other hand, we have the follow-
ing theoretical result, that guarantees the existence of circular chains of
arbitrary length, for almost all dimensions.
Proposition 2: For all n ≥ 4 and m ≥ 3 there exist circular chains of
n-dimensional Chinese dice of length m: A1  A2  · · ·  Am  A1, with
the only exception being (n,m) = (4, 5), a case which does not admit a
solution at all.
Proof: Let m ≥ 3 be an integer. First notice that if we find m Chinese
dice D1,D2, . . . ,Dm of 4 dimensions (that is, n = 4) that form a circular
chain,
D1  D2  · · ·  Dm  D1,
then we can fill the rest of the coordinates with the number 1 (or any other
fixed number) to form a circular chain of Chinese dice of n dimensions:
(D1, 1, . . . , 1)  (D2, 1, . . . , 1)  · · ·  (Dm, 1, . . . , 1)  (D1, 1, . . . , 1).
Then, it is sufficient to work with n = 4 dimensions. Second, notice that
if B1  B2  B3  B1 is a circular chain of length 3, then we can use it
repetitively p times,
B1  B2  B3 [  B1  B2  B3]p−1,
to form a circular chain of length 3p, for any positive integer p. Analo-
gously, if C1  C2  C3  C4  C1 is a circular chain of length 4, we can
use it repetitively q times,
C1  C2  C3  C4 [  C1  C2  C3  C4]q−1,
to form a circular chain of length 4q, for any positive integer q. If we
are able to “combine” these circular chains in the extremes, then we can
construct circular chains of any arbitrary length of the form 3p + 4q.
Precisely this is the case with the particular circular chains of Chinese
dice B1, B2, B3 and C1, C2, C3, C4 presented in Table 3, because they verify
that B3  C1 by 2 units and C4  B1 also by 2 units, as we can easily
check. We illustrated this in Figure 5. So, all the chains produced with
these particular generators are circular and completely balanced.
64 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
Third, every integer m ≥ 3 if it is not equal to 5 then it can be written
in the form m = 3p + 4q, for some positive integers p and q. We prove
this last assertion by induction on m ≥ 3, as follows: (i) Initial steps: for
m = 3 or m = 4 the affirmation is clear, because 3 = 3 · 1 + 4 · 0 and
4 = 3 · 0 + 4 · 1; (ii) Induction hypothesis: suppose the integer m ≥ 6 has
the form m = 3p + 4q, where p and q are natural numbers, not both of
them null; (iii) Inductive step: by the induction hypothesis, some of the
numbers p or q are positive. Moreover, note that if p = 0 then q ≥ 2.
Thus, we have:
m+ 1 = 3p+ 4q + 1 =
{
3(p− 1) + 4(q + 1) if p > 0,
3 · 3 + 4(q − 2) if p = 0 and q ≥ 2.
That proves the assertion. Fourth, we can find the existence of circular
chains of 5 Chinese dice in 5 or more dimensions with the aim of our
simulated annealing algorithm. In fact, a good semi-balanced “5-5-3-4-
4” particular solution is: D1 = (3, 1, 4, 3, 4), D2 = (3, 3, 3, 3, 3), D3 =
(2, 2, 2, 5, 5), D4 = (5, 1, 5, 4, 1), D5 = (4, 1, 4, 4, 3). Finally, the only case
for which there does not exist a solution at all occurs when (n,m) =
(4, 5). This can be checked by enumeration, using for example the Cplex
software.
•B3
•
B1
•B2
•C1
•
C4
•C2
•
C3
- -
?ff
6
ffQ
QQk

3
?
 
2 2
222
2 2
2
2
Figure 5: The Chinese dice B1, B2, B3 and C1, C2, C3, C4 shown in Table 3
have a perfect match in the extremes that allows producing other circular
chains of arbitrary length. All the dice are preferred to the following die
by exactly 2 units, producing totally balanced circular chains.
4 Simulated annealing algorithm
We successfully implemented a simulated annealing algorithm to work
with circular chains of n-dimensional Chinese dice of length m.
Simulated annealing is a generic probabilistic meta-heuristic algorithm
for the global optimization problem [1, 6], namely locating a good approx-
circular chains of chinese dice 65
imation to the global optimum of a given function in a large search space.
It was independently presented by Kirkpatrick, Gelatt and Vecchi in 1983,
and by Cˇerny´ in 1985. The method is an adaptation of the Metropolis-
Hastings algorithm, a Monte Carlo method to generate sample states of
a thermodynamic system, invented by Metropolis et al. in 1953. The
name and inspiration come from annealing in metallurgy, a technique in-
volving heating and controlled cooling of a material to increase the size
of its crystals and reduce their defects. The heat causes the atoms to
become unstuck from their initial positions (a local minimum of the in-
ternal energy) and wander randomly through states of higher energy; the
slow cooling gives them more chances of finding configurations with lower
internal energy than the initial one.
By analogy with this physical process, each step of the simulated an-
nealing algorithm replaces the current solution by a random “nearby” so-
lution, chosen with a probability that depends on the difference between
the corresponding function values and on a global parameter T (called
the “temperature”), that is gradually decreased during the process. The
dependency is such that the current solution changes almost randomly
when T is large, but increasingly “downhill” as T goes to zero. The al-
lowance for “uphill” moves saves the method from becoming stuck at local
minima—which are the bane of greedier methods.
The algorithm starts selecting at random a collection of m Chinese
dice of n dimensions. A series of iterations begins, modifying the Chinese
dice according to the following rules:
1. Select at random a Chinese die i, with i ∈ {1, . . . ,m}.
2. Select at random the face (or position) j of the i-th Chinese die,
with j ∈ {1, . . . , n}.
3. Select at random a new value k′ ∈ {1, . . . , n} that modifies the actual
value k in the j-th position of the i-th Chinese die.
4. We accept this proposed change with probability min{1, e∆/T }, where
∆ is the change in the value of the objective function (see (13) and
(14)), and T > 0 is the temperature parameter.
In this way, if the newly generated Chinese die increases the actual
value of the objective function, then it is always accepted (with probability
1). On the other hand, if the newly generated Chinese die decreases the
value of the objective function, it may still be accepted, but only with
66 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
probability e∆/T (in this case ∆ < 0). This acceptance criteria is called
the Metropolis rule. Note that when the value of the temperature T is
close to 0 (but positive), then the probability of accepting bad changes is
close to 0.
It is well known (see [1, 6]) that in theory this “random walk” converges
asymptotically to a global maximum of the objective function with prob-
ability 1, when certain conditions are satisfied. The first general condition
is that the temperature T > 0 has to tend to 0 “slowly”. A homogeneous
Markov chain is associated with each value of the temperature T and the
second general condition for convergence to a global maximum is that all
these Markov chains have stationary distributions. That is the case with
the algorithm we implemented, because we have total connectivity and
reversibility among the dice configurations and also the probabilities of
reaching any “neighboring” Chinese die are all equal. In practice we can
destroy the convergence of the algorithm, when we implement convergence
of the temperature parameter T to 0 or when we simulate the convergence
process of each Markov chain to their stationary distribution.
In our simulated annealing algorithm we use the following “cooling
scheme”:
Initial temperature: the initial temperature T0 is selected at the begin-
ning in order to let the Metropolis rule be more tolerant, accepting
nearly χ × 100% of new “bad” Chinese dice. We run a sequence of
preliminary “phantom steps” in order to select χ with this prereq-
uisite.
Decrease of temperature: every certain number of steps the system
is cooled down a little, decreasing the value of the temperature Tk
using the geometrical cooling scheme: Tk+1 = λ · Tk, where λ is a
constant previously chosen empirically between [0.92, 0.98] (λ = 0.95
was a good selection in all our experiments).
Length of the temperature chains: the temperature parameter is up-
dated each nLimit steps, or when it has already accepted nOver
new “bad” changes. We successfully used empirical values of nLimit ∈
[105, 106] and nOver ∈ [10000, 20000], depending on the size of the
problem.
Criteria to stop the algorithm: a maximum of 150 cycles of temper-
ature are completed, because in practice the quantity T150 = (T0)150
is almost null independently of the initial value T0. Nevertheless, if
circular chains of chinese dice 67
for the last nCad temperature steps a new “good” Chinese die does
not appear, then the process is stopped. We used nCad = 3 in our
experiments with good results.
The algorithm extensively used an additive random generation algo-
rithm, recommended by Knuth [5]. The results of our algorithm are very
satisfactory, reaching solutions as good as the ones obtained by mixed-
integer programming, but in less computer time. Some of these solutions
are already presented in Tables 2 and 3. In Figure 6 we present a solution
found by our simulated annealing algorithm for non trivial length of n and
m, as an example.
Die 1: 4, 4, 4, 4, 5, 4, 4, 8 Die 6: 4, 4, 4, 8, 4, 4, 4, 4 Die 11: 4, 4, 4, 4, 4, 4, 4, 8
Die 2: 3, 3, 8, 8, 3, 7, 3, 3 Die 7: 8, 8, 3, 3, 7, 3, 3, 3 Die 12: 3, 3, 3, 3, 3, 7, 8, 8
Die 3: 2, 7, 7, 7, 2, 2, 2, 7 Die 8: 7, 2, 7, 7, 7, 2, 2, 2 Die 13: 7, 2, 7, 2, 7, 7, 2, 2
Die 4: 6, 6, 1, 6, 1, 2, 6, 6 Die 9: 6, 1, 6, 6, 2, 1, 6, 6 Die 14: 6, 6, 1, 6, 1, 2, 6, 6
Die 5: 5, 5, 5, 3, 5, 5, 1, 5 Die 10: 3, 5, 5, 5, 5, 5, 1, 5 Die 15: 5, 4, 5, 5, 5, 1, 5, 5
Figure 6: Solution found in 249 seconds by our simulated annealing algo-
rithm, for n = 8 and m = 15. In this example, all the differences Zi − Z¯i
are equal to 20: it is a “20-20-. . . -20” solution.
5 Final remarks
The popular children’s game “rock, paper, scissors” is an example
of “normal” dice in 3 dimensions: each “die” (a hidden hand) has non-
repetitive values and therefore has the same probability to win against the
other. The non-transitivity of the “face” values (“rock”  “scissors” 
“paper”  “rock”) is the only important mathematical concept involved.
Circular chains do not exist for 3 dimensions.
In art, some famous paintings by Escher remind us of the Chinese
dice. For example his famous “Ascending and Descending” painting (see
Figure 7) has some resemblance to Chinese dice in 4 dimensions. However,
the “random factor” inherent in the concept of Chinese dice is still missing.
We think there are some possible applications of the circular chains of
Chinese dice inside the theory of multi-objective optimization and also in
the utility theory in economics. We are hopeful to find some application
in this context.
68 E. Piza – L. Schubert Rev.Mate.Teor.Aplic. (2010) 17(1)
Figure 7: “Ascending and Descending” by Escher (1960) and the Penrose
stairs optical illusion (1958).
References
[1] Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Ma-
chines. A Stochastic Approach to Combinatorial Optimization and
Neural Computing. John Wiley & Sons, Chichester.
[2] Bixby, R.E. (1992) “Implementing the simplex method: The initial
basis”, ORSA Journal on Computing 4: 267–284.
[3] Bixby, R.E. et al. (2002) ILOG AMPL CPLEX System, Version 8.0.
User’s Guide.
[4] Fourer, R.; Gay, D.M.; Kernighan, B.W. (2002) AMPL: A Modeling
Language for Mathematical Programming. Duxbury Press-Brooks-
Cole Publishing Co.
[5] Knuth, D.E. (1981) Seminumerical Algorithms. Second edition, vol-
ume 2 of the book The Art of Computer Programming. Addison-
Wesley, Reading, Mass.
[6] Laarhoven, P.J.M. van (1988) “Theoretical and computational as-
pects of simulated annealing”, Centrum voor Wiskunde in Informatic,
Tract 57.
[7] Williams, H.P. (1999) Model Building in Mathematical Programming.
John Wiley & Sons, Chinchester.