11institutetext: LAMSADE, Université Paris Dauphine - PSL, CNRS, Paris, France

# Nested Search versus Limited Discrepancy Search

Tristan Cazenave

###### Abstract

Limited Discrepancy Search (LDS) is a popular algorithm to search a state
space with a heuristic to order the possible actions. Nested Search (NS) is
another algorithm to search a state space with the same heuristic. NS spends
more time on the move associated to the best heuristic playout while LDS
spends more time on the best heuristic move. They both use similar times for
the same level of search. We advocate in this paper that it is often better to
follow the best heuristic playout as in NS than to follow the heuristic as in
LDS.

###### Keywords:

Search Combinatorial Optimization Constraint Satisfaction.

##  1 Introduction

Combinatorial Optimization has many applications in numerous fields. Heuristic
algorithms aim at solving Combinatorial Optimization problems using domain
dependent knowledge without proving the optimality of the solution found. When
the possible decisions can be sorted according to a heuristic, algorithms such
as LDS [26] and NS [41] can leverage the heuristic and find good solutions to
difficult problems much faster than other more complete search algorithms.

Decision problems are a special kind of problems since finding a solution to a
problem is equivalent to finding an optimal solution. Many Constraint
Programming problems fall into this category. For this kind of problems LDS
and NS can be particularly effective compared to complete search algorithms.

LDS is a popular search algorithm. There have been many papers using LDS to
effectively search difficult problems including very recent ones. The base
level performs playouts with a move ordering heuristic. A nice property of LDS
is that it is guaranteed to improve on the previous levels with increasing
levels of search. It has been applied to many difficult problems and it is
currently commonly used for Combinatorial Optimization and Constraint
Programming problems.

For example, LDS has been recently used as a search algorithm to combine Deep
Reinforcement Learning and Constraint Programming in order to solve
Combinatorial Optimization problems such as the Traveling Salesman Problem
with Time Windows (TSPTW), 4-Moments Portfolio Optimization or the 0-1
Knapsack Problem [9].

It has also been recently used in combination with bandits in the Bandit
Limited Discrepancy Search algorithm that was used for optimized algorithm
selection in a fixed Machine Learning pipeline structure [28].

NS is close to LDS but it differs in the choice of the decision that will be
searched more. LDS follows the heuristic prior in order to decide which
decision will be searched more. NS chooses to search more the decision that
scores best according to the lower level playouts.

The paper is organized as follows. The second section recalls LDS. The third
section deals with NS. The fourth section theoretically compares NS and LDS.
The fifth section experimentally compares the two algorithms on four difficult
Combinatorial Optimization problems.

1: LDS ($state$, $level$)

2: if terminal ($state$) then

3: return score ($state$)

4: end if

5: $best=-\infty$

6: sort the possible moves

7: for $m$ in possible moves for $state$ do

8: $s$ $\leftarrow$ play ($state$, $m$)

9: if m is the first move then

10: $score=$ LDS ($s$, $level$)

11: else if $level>0$ then

12: $score=$ LDS ($s$, $level-1$)

13: else

14: continue

15: end if

16: $best=max(best,score)$

17: end for

18: return $best$

Algorithm 1 The LDS algorithm. ptpt ptpt 47 ptpt ptpt Figure 1: A binary
search tree. The heuristic is to choose the left move. The black squares are
the solutions. LDS does not find one of the two solutions using only one
discrepancy since the path to the two solutions requires two discrepancies. A
level 2 LDS solves the problem.

##  2 Limited Discrepancy Search

LDS [26] is given in Algorithm 1. It has applications in Constraint
Programming and Combinatorial Optimization [9]. It is a search strategy
commonly used when a good heuristic on the possible actions is available for
driving the search. The principle is to restrict the number of decisions
deviating from the heuristic choices (i.e. a discrepancy) by a threshold. This
will explore the subset of solutions that are likely to be good according to
the heuristic, but it will also explore solutions where the heuristic has been
reconsidered a given number of times (i.e. the number of discrepancies).

Figure 1 gives an example of a binary search tree requiring a LDS of level 2
to be solved.

1: NS ($state$, $level$)

2: if level == 0 then

3: return playout ($state$)

4: end if

5: while $state$ is not terminal do

6: sort possible moves

7: for $m$ in possible moves for $state$ do

8: $s\leftarrow$ play ($state$, $m$)

9: $s\leftarrow$ NS ($s$, $level-1$)

10: update $bestMove$ using score ($s$)

11: end for

12: $state$ $\leftarrow$ play ($state$, $bestMove$)

13: end while

14: return $state$

Algorithm 2 The NS algorithm.

1: playout ($state$)

2: while $state$ is not terminal do

3: $move$ $\leftarrow$ best heuristic move

4: $state$ $\leftarrow$ play ($state$, $move$)

5: end while

6: return $state$

Algorithm 3 The playout algorithm -2 -2 -1 0 47 -3 -2 0 -1 Figure 2: The same
tree as in Figure 1 with scores of the playouts at the leaves. A score of 0
means the problem is solved. A NS of level 1 finds a solution as it uses the
scores of the playouts to direct its search.

##  3 Nested Search

###  3.1 Related Work

NS has its root in Monte Carlo Search [41]. An application then was then a
Backgammon program which was improved thanks to nested rollouts. It was
subsequently used in Combinatorial Optimization [3] and in stochastic
scheduling problems [2]. Nested rollouts combined with a heuristic to choose
the next move at the base level were used to improve a Klondike solitaire
program [42]. Nested rollouts have been used with heuristics that change with
the stage of the game of Thoughtful Solitaire, a version of Klondike Solitaire
in which the locations of all cards is known [4]. They were also used to learn
a control policy for planning [24].

Nested Monte Carlo Search (NMCS) [10] is a related algorithm that works well
for puzzles and optimization problems. It biases its playouts using lower
level playouts. At level zero NMCS adopts a randomized playout policy. The
main improvement of NMCS over NS is the memorization of the best sequence at
each recursion level. Without the memorization of the best sequence the
algorithm does not give good results for levels greater than one. Applications
of NMCS include Single Player General Game Playing [30], Cooperative
Pathfinding [6], Software testing [34], heuristic Model-Checking [35], the
Pancake problem [7], Games [14] and the RNA inverse folding problem [32].
Online learning of playout strategies combined with NMCS has given good
results on optimization problems [36]. Online learning of a playout policy in
the context of nested searches has been further developed for puzzles and
optimization with Nested Rollout Policy Adaptation (NRPA) [37]. NRPA has found
new world records in Morpion Solitaire and crosswords puzzles. Edelkamp,
Cazenave and co-workers have applied the NRPA algorithm to multiple problems:
The TSPTW problem [15, 18], 3D Packing with Object Orientation [20], the
physical traveling salesman problem [21], the Multiple Sequence Alignment
problem [22], Logistics [19, 12], Graph Coloring [13] and Inverse Folding
[11]. The principle of NRPA is to adapt the playout policy reinforcing the
moves of the best sequence of moves found so far at each level.

###  3.2 The Algorithm

At the lowest recursive level of NS, the generation of sequences is driven by
the heuristic on decisions. Sequences are generated with the heuristic as
described in Algorithm 3.

In NS, the base heuristic remains the same throughout the execution of the
algorithm. However, the heuristic is combined with a tree search to improve
the quality over a simple sequence generator. At each step, each possible move
is evaluated by completing the partial solution into a complete one using
moves sampled from the underlying recursion level. Whichever intermediate move
has led to the best completed sequence, is selected and added to the current
sequence. The same procedure is repeated to choose the following move, until
the sequence has reached a terminal state. See Algorithm 2.

Figure 2 gives an example of a binary search tree where the scores of the
playouts enable a level 1 NS to solve the problem.

##  4 Comparison of NS and LDS

###  4.1 Complexity

For a tree of height h and branching factor b, the total number of playout
steps of a NS of level n will be $t_{n}(h,b)=t_{n}(h-1,b)+b\times
t_{n-1}(h-1,b)$. The total number of playout steps of a LDS of level n will be
$t_{n}(h,b)=t_{n}(h-1,b)+(b-1)\times t_{n-1}(h-1,b)$. The difference between
the complexity of two searches is $t_{n-1}(h-1,b)$. The complexity of a NS of
level n is O($b^{n}\times h^{n+1}$) [30]. So $t_{n-1}(h-1,b)$ is small
compared to $t_{n}(h-1,b)$ and therefore NS and LDS have similar complexities
even if LDS can be slightly faster. However if the complexity is also related
to a better move ordering such as in decision problems, NS with high levels
can become faster than LDS with high levels since NS spends much more
resources on the choice of the move to search more.

###  4.2 Analysis

The main difference between NS and LDS is the exploitation of the move
associated to the best playout of the lower level as in NS instead of the
exploitation of the move advised by the static heuristic as in LDS. In NS the
playouts are played with the heuristic as in LDS so NS also benefits from the
heuristic. Moreover, NS uses the scores of playouts.

NS uses the scores at the end of the playouts to exploit the most promising
move. On the contrary LDS does not require a score for playouts but only for
possible moves. For many problems the score of a playout is natural as it is
the value to optimize. For constraint satisfaction problems however the score
has to be designed. A possible scoring function for NS is to count the number
of unassigned variables when reaching an inconsistency and to return the
opposite of the count as NS maximizes the score.

The order in which LDS and NS search the state space is quite different. LDS
starts by going very deep in the part of the search tree where the heuristic
on moves leads. It then backtracks exploring with the maximum exploration the
bottom of this part of the tree. NS has a different behavior. It goes in the
bottom of the tree with playouts and carefully chooses the move that it plays
in the top of the tree before exploring it more.

So LDS backtracks from the bottom while NS searches with decreasing levels at
the top of the search tree. When the heuristic does not fail at the top of the
search tree LDS can be faster since it backtracks first in the most
interesting parts of the search tree. However for difficult problems, high
levels of search are often required and the heuristic is more difficult to
design near the root than near the leaves. So NS which more carefully chooses
its moves near the root can prove better.

##  5 Experimental Results

In this section we present experiments comparing NS and LDS for four difficult
combinatorial problems. All experiments were done on AMD EPYC-Rome 2 GHz
processors with 512 KB of cache.

###  5.1 TSPTW

The TSPTW is a practical problem that has everyday applications. It has time
constraints represented as time intervals during which cities are to be
visited. In LDS and NS paths with violated constraints can be generated. As
presented in [36] , a new score $Tcost(p)$ of a path $p$ can be defined as
follow:

$Tcost(p)=-cost(p)-10^{6}*\Omega(p),$

with, $cost(p)$ the sum of the distances of the path $p$ and $\Omega(p)$ the
number of violated constraints. $10^{6}$ is a constant chosen high enough so
that the algorithm first optimizes the constraints then the sum of the
distances.

We experiment with NS and LDS for the TSPTW problem with most of the problems
of the standard test set [33]. Problems that took a very long time for LDS(3)
and NS(3) were removed. The results are given in Table 1. We can observe that
for level 1, LDS is strictly better than NS 8 times while NS is strictly
better than LDS 15 times. At level 3 NS becomes strictly better 17 times while
LDS is strictly better only twice. When the level increases NS makes a better
use of the lower level playouts to direct its choices than LDS since LDS still
uses the heuristic to order moves and to choose the best move that will
benefit from the intensification of the search.

Instance | LDS (1) | Nested (1) | LDS (2) | Nested (2) | LDS (3) | Nested (3)
---|---|---|---|---|---|---
rc_201.1 | -1000451.06 | -1000461.69 | -445.38 | -447.29 | -444.54 | -444.54
rc_201.4 | -4000771.50 | -1000796.44 | -2000781.75 | -1000770.19 | -1000778.44 | -793.64
rc_202.3 | -10000946.00 | -4000886.00 | -4000862.25 | -4000878.75 | -2000853.50 | -859.53
rc_203.2 | -3000892.25 | -4000880.00 | -1000833.31 | -948.24 | -854.54 | -850.68
rc_205.1 | -353.17 | -1000370.56 | -343.36 | -379.48 | -343.21 | -343.21
rc_205.4 | -13000789.00 | -9000761.00 | -9000741.00 | -1000808.56 | -3000775.00 | -1000757.69
rc_206.3 | -15000839.00 | -7000676.00 | -3000656.75 | -597.70 | -1000609.25 | -592.83
rc_207.2 | -17000822.00 | -25000838.00 | -13000822.00 | -12000796.00 | -11000883.00 | -827.96
rc_201.2 | -18000820.00 | -6000777.50 | -9000754.00 | -733.85 | -1000738.00 | -733.85
rc_202.1 | -8000814.00 | -6000811.00 | -5000802.00 | -3000849.00 | -3000759.00 | -802.87
rc_202.4 | -8000809.50 | -2000818.62 | -5000866.50 | -846.50 | -3000858.00 | -816.09
rc_203.3 | -8000855.00 | -4000920.50 | -5000861.00 | -2000884.25 | -3000865.50 | -848.09
rc_205.2 | -18000944.00 | -10000778.00 | -6000756.00 | -1000798.56 | -2000737.75 | -755.93
rc_206.1 | -117.85 | -117.85 | -117.85 | -117.85 | -117.85 | -117.85
rc_206.4 | -16000943.00 | -10000930.00 | -13000922.00 | -6001000.00 | -10000873.00 | -889.23
rc_207.3 | -20000940.00 | -15000885.00 | -12000857.00 | -818.64 | -6000798.00 | -713.89
rc_201.3 | -20000848.00 | -13000891.00 | -14000837.00 | -7000819.00 | -7000823.50 | -6000851.50
rc_202.2 | -309.94 | -310.59 | -305.76 | -304.14 | -304.14 | -304.14
rc_203.1 | -1000463.44 | -1000463.44 | -461.39 | -467.69 | -458.93 | -459.54
rc_203.4 | -316.19 | -314.29 | -314.29 | -314.29 | -314.29 | -314.29
rc_204.3 | -486.88 | -1000495.88 | -463.43 | -473.12 | -459.03 | -461.93
rc_205.3 | -5000917.50 | -2000835.88 | -3000832.25 | -2000822.75 | -2000837.25 | -867.33
rc_206.2 | -21001112.00 | -16000962.00 | -15000968.00 | -10000882.00 | -5000882.00 | -1000871.25
rc_207.1 | -7000871.00 | -8000913.50 | -2000790.00 | -849.65 | -1000767.50 | -781.54
rc_207.4 | -119.64 | -119.64 | -119.64 | -119.64 | -119.64 | -119.64
Better | 8 | 15 | 5 | 17 | 2 | 17
Table 1: Results for the TSPTW problem instances

###  5.2 RNA Inverse Folding

The design of molecules with specific properties is an important topic for
health related research. RNA molecules are long molecules composed of four
possible nucleotides. Molecules can be represented as strings composed of the
four characters A, C, G, U. For RNA molecules of length N, the size of the
state space of possible strings is exponential in N. It can be very large for
long molecules. The sequence of nucleotides folds back on itself to form what
is called its secondary structure. It is possible to find in a polynomial time
the folded structure of a given sequence. However, the opposite, which is the
RNA inverse folding problem, is much harder and is supposed to be NP-complete.

We compare LDS and NS on the Eterna100 benchmark which contains 100 RNA
secondary structure puzzles of varying degrees of difficulty. A puzzle
consists of a given structure under the dot-bracket notation. This notation
defines a structure as a sequence of parentheses and points each representing
a base. The matching parentheses symbolize the paired bases and the dots the
unpaired ones. The puzzle is solved when a sequence of the four nucleotides
A,U,G and C, folding according to the target structure, is found. In some
puzzles, the value of certain bases is imposed. Figure 3 gives an example of
an Eterna100 problem.

Where human experts have managed to solve the 100 problems of the benchmark,
no program has so far achieved such a score. The best score so far is 95/100
by NEMO, NEsted MOnte Carlo RNA Puzzle Solver [32] and by GNRPA [11].

We use a the NEMO heuristic to order moves for LDS and NS. It mainly consists
in probabilities for pair of bases.

Table 2 gives the number of problems solved by LDS and NS for levels 1 to 3.
NS is much better than LDS for all levels.

Since NS solves RNA inverse folding problems faster than LDS and since inverse
folding is a decision problem, the total execution time for all the problems
of NS is smaller than that of LDS.

Figure 3: Example of a RNA design puzzle from Eterna. LDS (1) | NS (1) | LDS (2) | NS (2) | LDS (3) | NS (3)
---|---|---|---|---|---
24 | 32 | 30 | 59 | 39 | 75
Table 2: Number of problems solved for the Eterna100 benchmark.

###  5.3 The Snake-in-the-Box

The Snake-in-the-Box is a problem from graph theory with applications in
coding theory, disjunctive normal form simplification, electrical engineering,
analog-to-digital conversion, electronic combination locking, and computer
network topologies [29].

The problem is to find the longest possible path in a N-dimensional hypercube
so that any vertex has at most two other neighboring vertices that are also in
the graph. For example in dimension 3, the graph is a cube with 8 vertices:
000, 001, 010, 011, 100, 101, 110 and 111. The longest path is 000, 001, 011,
111, 110. It has a length of 4, so the best score for dimension 3 is 4. For
dimensions greater than 9 the exact scores are still unknown and only lower
bounds are known.

Kinny broke world records at the Snake-in-the-Box applying Nested Monte Carlo
Search [27]. He used a heuristic to order move in the playouts. The heuristic
is to favor moves that lead to a state where there is only one possible move.
Nested Rollout Policy Adaptation combined to beam search also reached high
scores at the Snake-in-the-Box [17].

In our experiments we use a heuristic similar to the heuristic used by Kinny.
We sort the moves according to the number of possible moves after the move. If
there are no possible moves the move is associated to a large penalty,
otherwise the score of a move is the number of possible moves after the move.
Moves are sorted by ascending scores.

Table 3 give the results for LDS and NS of levels 1 to 3. We can observe that
for simple problems LDS of level 1 is better than NS of level 1 but for
dimensions 10 and 11 that are harder NS gets better. At level 3 NS is always
better than LDS. This is probably due to the fact that at the top level NS of
level 3 uses level 2 playouts to order moves when LDS still uses the
heuristic.

Dimension | LDS (1) | NS (1) | LDS (2) | NS (2) | LDS (3) | NS (3)
---|---|---|---|---|---|---
8 | 84.00 | 79.00 | 85.00 | 84.00 | 89.00 | 91.00
9 | 149.00 | 148.00 | 159.00 | 166.00 | 161.00 | 167.00
10 | 266.00 | 271.00 | 283.00 | 298.00 | 301.00 | 310.00
11 | 467.00 | 493.00 | 515.00 | 543.00 | 532.00 | 570.00
Table 3: Results for the Snake-in-the-Box. 0,0 | 1,2 | 2,5 | 3,9 | 4,8 | 5,4 | 6,3 | 7,1 | 8,10 | 9,7 | 10,6
---|---|---|---|---|---|---|---|---|---|---
1,1 | 2,3 | 3,6 | 4,10 | 5,9 | 6,5 | 7,4 | 8,2 | 9,0 | 10,8 | 0,7
2,2 | 3,4 | 4,7 | 5,0 | 6,10 | 7,6 | 8,5 | 9,3 | 10,1 | 0,9 | 1,8
3,3 | 4,5 | 5,8 | 6,1 | 7,0 | 8,7 | 9,6 | 10,4 | 0,2 | 1,10 | 2,9
4,4 | 5,6 | 6,9 | 7,2 | 8,1 | 9,8 | 10,7 | 0,5 | 1,3 | 2,0 | 3,10
5,5 | 6,7 | 7,10 | 8,3 | 9,2 | 10,9 | 0,8 | 1,6 | 2,4 | 3,1 | 4,0
6,6 | 7,8 | 8,0 | 9,4 | 10,3 | 0,10 | 1,9 | 2,7 | 3,5 | 4,2 | 5,1
7,7 | 8,9 | 9,1 | 10,5 | 0,4 | 1,0 | 2,10 | 3,8 | 4,6 | 5,3 | 6,2
8,8 | 9,10 | 10,2 | 0,6 | 1,5 | 2,1 | 3,0 | 4,9 | 5,7 | 6,4 | 7,3
9,9 | 10,0 | 0,3 | 1,7 | 2,6 | 3,2 | 4,1 | 5,10 | 6,8 | 7,5 | 8,4
10,10 | 0,1 | 1,4 | 2,8 | 3,7 | 4,3 | 5,2 | 6,0 | 7,9 | 8,6 | 9,5
Table 4: Example of a Graeco-Latin square of size 11 found by LDS in 0.00 seconds. 0,0 | 1,1 | 2,2
---|---|---
1,2 | 2,0 | 0,1
2,1 | 0,2 | 1,0
Table 5: Example of a Graeco-Latin square of size 3.

###  5.4 Graeco-Latin Squares

A Latin square is a $n\times n$ matrix containing $n$ symbols such that each
symbol occurs only once in each row and each column. A Graeco-Latin square is
the association of two Latin squares of the same dimension such that when they
are superimposed every pair of symbols occurs only once. Table 5 gives an
example of a small Graeco-Latin square.

Graeco-Latin squares have a long history [39]. They are also called Euler
squares since Euler proposed a famous conjecture about these squares. Euler
first considered the problem of the 36 officers [23]. This problem is
equivalent to constructing a $6\times 6$ Graeco-Latin square. Euler
conjectured in 1779 it is not possible, and Tarry [40] proved it in 1900.
Euler also conjectured that there are no Graeco-Latin squares of order 10, 14,
18, and so on. This conjecture was proved false in 1959 [5].

Graeco-Latin squares are used for designing experiments in biology, medicine,
sociology and even marketing [25]. Graeco-Latin squares have even been used in
literature: Georges Perec used a $10\times 10$ Graeco-Latin square as a basis
for his novel "La Vie mode d’emploi" [31].

In order to model the problem for LDS and NS we maintain the possible values
of each cell after each move. A move is the assignment of a value to a
variable. We remove the assigned value from the domains of the variables in
the same row and in the same column as the variable being assigned. We also
remove the value from variables in the same square that are associated in the
other square to the same value as the value associated to the variable being
assigned. We also perform the symmetrical removal of the values in the other
square that are associated in the current square to the value being assigned.

We tested two variable ordering heuristics. The dom heuristic that was found
effective for Latin Squares [16]. It selects the variable with the smallest
number of possible values. The deg heuristic that selects the variable that is
connected to the least number of other free variables in the same row and the
same column. The deg heuristic keeps more possible values overall but it also
has a greater branching factor than dom.

A possible move is an assignment of a value to the chosen variable. The list
of possible moves is the list of values that can be assigned to the chosen
variable. Move ordering is done sorting the moves from the moves that remove
the smallest number of possible values from other variables to the moves that
removes the greatest number of possible values from other variables.

We also use an algorithm we call MAC, since it is related to arc consistency,
to prune more values and to detect inconsistencies earlier. The algorithm uses
channeling constraints as for Latin Squares [16]. The algorithm stops the
search if a variable has an empty domain and recursively assign variables that
only have one possible value. It also calculates for each color and each row
the number of times the color is present in the row and assigns the color if
it is present only once or stops the search if it is not present. It does the
same for the columns. This algorithm is usually effective for solving Latin
Squares since it reduces a lot the search space.

A state is terminal either if all variables have been assigned or if a non
assigned variable has an empty domain. The score function is simply the
opposite of the number of free variables.

We also tested symmetry breaking as described in [1, 38]. To do so, we fix the
first row of every square to be in lexicographic order which eliminates the
permutations of the columns and fixes the symbol permutations to be the same
in each square. We also fix the first column of the first square to be in
lexicographic order which eliminates permutations of the rows and perform
domain reduction of entries in the first column of the second square.

Table 6 compares LDS and NS for different dimensions, levels and parameters of
the search algorithms. The timeout is fixed at 10 000 seconds. The var column
indicates the heuristic used to select the next variable to assign, the sym
column indicates if symmetry breaking is used or not, the MAC column indicates
if arc-consistency is used or not. We ran the different combination of the
algorithms for levels 3 to 6 and dimensions 5 to 11 (except 6 since it is not
solvable). If a time is given it means the problem was solved within this
time. If a score and a time are given it means the problem was not solved, the
score is the score resulting from the search (the opposite of the number of
free variables) and the time is the time taken for the search. A bold cell
mean this is the best result for this dimension.

Overall NS and LDS solve immediately all dimensions, except dimension 10, when
called with the appropriate parameters. It is noticeable that in previous work
some dimensions took much more time to be solved. For example a SAT solver
take 45 minutes to solve size 9 [8]. Integer Programming with the Gurobi
solver, which is the state of the art solver, solves size 9 in 344 seconds
[38] and Constraint Programming takes from 1 552 to 50 753 seconds for size 9
[38]. However for the more difficult problem of size 10 we do not find a
solution within 10 000 seconds when SAT finds it in 23 hours, Integer
Programming finds it in 3 046 seconds and Constraint Programming finds it in
11 971 seconds.

We can also observe that the deg variable ordering heuristic is much better
than the dom variable ordering heuristic in all cases. The principle here is
to constrain less the problem and let as much freedom as possible to the
algorithm, reducing less the number of possible values. This is interesting
since when the goal is to prove that a state is not possible to solve it is
better to constrain as much as possible the possible value in order to save
search time. Here the principle when looking for a solution is the opposite:
let as many options as possible. This opposition of principles can also be
seen for the symmetry breaking option. Breaking symmetries reduces the options
which is good for a complete search but which is here harmful when looking for
an unique assignment. We also see for dimension 11 that NS solves immediately
the problem without MAC but fails to solve it with MAC. This is another
illustration of this principle. However MAC can be useful as can be seen from
dimension 8 where the best results for NS and LDS were obtained with MAC.

Dimension | Algorithm | var | sym | MAC | level 3 | level 4 | level 5 | level 6
---|---|---|---|---|---|---|---|---
5 | NS | deg | yes | yes | 0.00s | 0.00s | 0.00s | 0.00s
5 | LDS | deg | yes | yes | 0.00s | 0.00s | 0.00s | 0.00s
7 | NS | deg | yes | yes | -5 in 0.91s | 0.76s | 0.94s | 1.10s
7 | NS | dom | yes | yes | -9 in 1.52s | 6.55s | 14.51s | 81.93s
7 | NS | deg | no | yes | 0.00s | 0.00s | 0.00s | 0.00s
7 | NS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
7 | LDS | deg | yes | yes | 0.32s | 0.80s | 1.03s | 2.63s
7 | LDS | dom | yes | yes | -13 in 0.50s | -9 in 2.62s | 11.60s | 4.23s
7 | LDS | deg | no | yes | 0.00s | 0.00s | 0.00s | 0.00s
7 | LDS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
8 | NS | deg | yes | yes | -7 in 12.62s | -5 in 242.95s | 3172.59s | 1493.77s
8 | NS | dom | yes | yes | -14 in 13.71s | -10 in 275.11s | -9 in 4360.04s | Timeout
8 | NS | deg | no | yes | -7 in 177.00s | 5.45s | 277.91s | 9609.19s
8 | NS | deg | no | no | -14 in 84.77s | -10 in 4041.90s | 3553.67s | 2992.09s
8 | LDS | deg | yes | yes | -8 in 6.00s | -6 in 86.46s | -5 in 1000.00s | 4311.28s
8 | LDS | dom | yes | yes | -16 in 4.90s | -13 in 61.31s | 439.10s | 3446.18s
8 | LDS | deg | no | yes | 63.03s | 46.84s | 512.79s | 4561.50s
8 | LDS | deg | no | no | -14 in 22.74s | 239.25s | 272.16s | 2531.84s
9 | NS | deg | yes | yes | -10 in 100.59s | -9 in 2745.83s | Timeout | Timeout
9 | NS | dom | yes | yes | -19 in 105.17s | -15 in 3149.61s | Timeout | Timeout
9 | NS | deg | no | yes | 0.00s | 0.00s | 0.00s | 0.00s
9 | NS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
9 | LDS | deg | yes | yes | 0.03s | 0.09s | 0.18s | 0.13s
9 | LDS | dom | yes | yes | -22 in 38.04s | -15 in 831.53s | Timeout | Timeout
9 | LDS | deg | no | yes | 0.00s | 0.00s | 0.00s | 0.00s
9 | LDS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
10 | NS | deg | yes | yes | -12 in 557.21s | Timeout | Timeout | Timeout
10 | NS | dom | yes | yes | -24 in 578.75 | Timeout | Timeout | Timeout
10 | NS | deg | no | yes | -9 in 4036.96s | Timeout | Timeout | Timeout
10 | NS | deg | no | no | -16 in 1626.02s | Timeout | Timeout | Timeout
10 | LDS | deg | yes | yes | -14 in 281.58s | Timeout | Timeout | Timeout
10 | LDS | dom | yes | yes | -25 in 227.21s | -21 in 7892.41s | Timeout | Timeout
10 | LDS | deg | no | yes | -7 in 2315.48s | Timeout | Timeout | Timeout
10 | LDS | deg | no | no | -19 in 419.67s | Timeout | Timeout | Timeout
11 | NS | deg | yes | yes | -15 in 2504.20s | Timeout | Timeout | Timeout
11 | NS | dom | yes | yes | -33 in 2653.31s | Timeout | Timeout | Timeout
11 | NS | deg | no | yes | Timeout | Timeout | Timeout | Timeout
11 | NS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
11 | LDS | deg | yes | yes | -12 in 1376.73s | 39.68s | 17.83s | 61.69s
11 | LDS | dom | yes | yes | -36 in 1050.09s | Timeout | Timeout | Timeout
11 | LDS | deg | no | yes | 0.01s | 0.00s | 0.00s | 0.00s
11 | LDS | deg | no | no | 0.00s | 0.00s | 0.00s | 0.00s
Table 6: Results for the Graeco-Latin squares.

##  6 Conclusion

We have theoretically compared NS and LDS, finding the two search algorithms
have similar complexities. We also have analyzed them, conjecturing that for
high levels of search NS can have a better behavior than LDS due to a better
choice of the move to intensify at every node.

Experimental results on four difficult combinatorial optimization problems
that have quite different properties confirm that for high levels of search NS
often performs better than LDS.

## References

  * [1] Appa, G., Magos, D., Mourtos, I.: Searching for mutually orthogonal latin squares via integer and constraint programming. European journal of operational research 173(2), 519–530 (2006)
  * [2] Bertsekas, D.P., Castanon, D.A.: Rollout algorithms for stochastic scheduling problems. Journal of Heuristics 5(1), 89–108 (1999)
  * [3] Bertsekas, D.P., Tsitsiklis, J.N., Wu, C.: Rollout algorithms for combinatorial optimization. Journal of Heuristics 3(3), 245–262 (1997)
  * [4] Bjarnason, R., Tadepalli, P., Fern, A.: Searching solitaire in real time. ICGA Journal 30(3), 131–142 (2007)
  * [5] Bose, R.C., Shrikhande, S.S.: On the falsity of euler’s conjecture about the non-existence of two orthogonal latin squares of order 4t+ 2. Proceedings of the National Academy of Sciences 45(5), 734–737 (1959)
  * [6] Bouzy, B.: Monte-carlo fork search for cooperative path-finding. In: Computer Games Workshop at IJCAI. pp. 1–15 (2013)
  * [7] Bouzy, B.: Burnt pancake problem: New lower bounds on the diameter and new experimental optimality ratios. In: SOCS. pp. 119–120 (2016)
  * [8] Bright, C., Gerhard, J., Kotsireas, I., Ganesh, V.: Effective problem solving using sat solvers. In: Maple Conference. pp. 205–219. Springer (2019)
  * [9] Cappart, Q., Moisan, T., Rousseau, L.M., Prémont-Schwarz, I., Cire, A.A.: Combining reinforcement learning and constraint programming for combinatorial optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 3677–3687 (2021)
  * [10] Cazenave, T.: Nested Monte-Carlo Search. In: Boutilier, C. (ed.) IJCAI. pp. 456–461 (2009)
  * [11] Cazenave, T., Fournier, T.: Monte Carlo inverse folding. In: Monte Search at IJCAI (2020)
  * [12] Cazenave, T., Lucas, J., Triboulet, T., Kim, H.: Policy adaptation for vehicle routing. Ai Communications (2021)
  * [13] Cazenave, T., Negrevergne, B., Sikora, F.: Monte Carlo graph coloring. In: Monte Search at IJCAI (2020)
  * [14] Cazenave, T., Saffidine, A., Schofield, M.J., Thielscher, M.: Nested monte carlo search for two-player games. In: AAAI. pp. 687–693 (2016)
  * [15] Cazenave, T., Teytaud, F.: Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows. In: Learning and Intelligent Optimization - 6th International Conference, LION 6. pp. 42–54 (2012)
  * [16] Dotú, I., Val, A.d., Cebrián, M.: Redundant modeling for the quasigroup completion problem. In: International Conference on Principles and Practice of Constraint Programming. pp. 288–302. Springer (2003)
  * [17] Edelkamp, S., Cazenave, T.: Improved diversity in nested rollout policy adaptation. In: KI 2016: Advances in Artificial Intelligence - 39th Annual German Conference on AI, Klagenfurt, Austria, September 26-30, 2016, Proceedings. pp. 43–55 (2016)
  * [18] Edelkamp, S., Gath, M., Cazenave, T., Teytaud, F.: Algorithm and knowledge engineering for the tsptw problem. In: Computational Intelligence in Scheduling (SCIS), 2013 IEEE Symposium on. pp. 44–51. IEEE (2013)
  * [19] Edelkamp, S., Gath, M., Greulich, C., Humann, M., Herzog, O., Lawo, M.: Monte-Carlo tree search for logistics. In: Commercial Transport, pp. 427–440. Springer International Publishing (2016)
  * [20] Edelkamp, S., Gath, M., Rohde, M.: Monte-Carlo tree search for 3d packing with object orientation. In: KI 2014: Advances in Artificial Intelligence, pp. 285–296. Springer International Publishing (2014)
  * [21] Edelkamp, S., Greulich, C.: Solving physical traveling salesman problems with policy adaptation. In: Computational Intelligence and Games (CIG), 2014 IEEE Conference on. pp. 1–8. IEEE (2014)
  * [22] Edelkamp, S., Tang, Z.: Monte-Carlo tree search for the multiple sequence alignment problem. In: Proceedings of the Eighth Annual Symposium on Combinatorial Search, SOCS 2015. pp. 9–17. AAAI Press (2015)
  * [23] Euler, L.: Recherches sur un nouvelle espéce de quarrés magiques. Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen pp. 85–239 (1782)
  * [24] Fern, A., Yoon, S.W., Givan, R.: Learning domain-specific control knowledge from random walks. In: ICAPS. pp. 191–199 (2004)
  * [25] Gardner, M.: Euler’s spoilers: the discovery of an order-10 graeco-latin square. New Mathematical Diversions pp. 162–172 (1995)
  * [26] Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: IJCAI. pp. 607–615. Morgan Kaufmann (1995)
  * [27] Kinny, D.: A new approach to the snake-in-the-box problem. In: ECAI 2012. Frontiers in Artificial Intelligence and Applications, vol. 242, pp. 462–467. IOS Press (2012)
  * [28] Kishimoto, A., Bouneffouf, D., Marinescu, R., Ram, P., Rawat, A., Wistuba, M., Palmes, P., Botea, A.: Bandit limited discrepancy search and application to machine learning pipeline optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 10228–10237 (2022)
  * [29] Krafka, K., Potter, W., Horton, T.: The snake-in-the-box problem. In: Proceedings of the 48th Annual Southeast Regional Conference. pp. 1–4 (2010)
  * [30] Méhat, J., Cazenave, T.: Combining UCT and Nested Monte Carlo Search for single-player general game playing. IEEE Transactions on Computational Intelligence and AI in Games 2(4), 271–277 (2010)
  * [31] Perec, G.: La Vie mode d’emploi (1978)
  * [32] Portela, F.: An unexpectedly effective Monte Carlo technique for the RNA inverse folding problem. BioRxiv p. 345587 (2018)
  * [33] Potvin, J.Y., Bengio, S.: The vehicle routing problem with time windows part ii: genetic search. INFORMS journal on Computing 8(2), 165–172 (1996)
  * [34] Poulding, S.M., Feldt, R.: Generating structured test data with specific properties using nested Monte-Carlo search. In: GECCO. pp. 1279–1286 (2014)
  * [35] Poulding, S.M., Feldt, R.: Heuristic model checking using a Monte-Carlo tree search algorithm. In: GECCO. pp. 1359–1366 (2015)
  * [36] Rimmel, A., Teytaud, F., Cazenave, T.: Optimization of the Nested Monte-Carlo algorithm on the traveling salesman problem with time windows. In: EvoApplications. LNCS, vol. 6625, pp. 501–510. Springer (2011)
  * [37] Rosin, C.D.: Nested rollout policy adaptation for Monte Carlo Tree Search. In: IJCAI. pp. 649–654 (2011)
  * [38] Rubin, N., Bright, C., Cheung, K., Stevens, B.: Improving integer and constraint programming for graeco-latin squares. In: 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI). pp. 604–608. IEEE (2021)
  * [39] Styan, G.P., Boyer, C., Chu, K.L.: Some comments on latin squares and on graeco-latin squares, illustrated with postage stamps and old playing cards. Statistical Papers 50(4), 917–941 (2009)
  * [40] Tarry, G.: Le problème d’euler des 36 officiers. Comptes-Rendus de l’Association Française pour l’Avancement des Sciences 29(2), 170–203 (1900)
  * [41] Tesauro, G., Galperin, G.: On-line policy improvement using monte-carlo search. Advances in Neural Information Processing Systems 9 (1996)
  * [42] Yan, X., Diaconis, P., Rusmevichientong, P., Roy, B.: Solitaire: Man versus machine. Advances in Neural Information Processing Systems 17 (2004)