Advertisement
Published in:
2013 | OriginalPaper | Chapter
Investigating Monte-Carlo Methods on the Weak Schur Problem
Authors : Shalom Eliahou, Cyril Fonlupt, Jean Fromentin, Virginie Marion-Poty, Denis Robilliard, Fabien Teytaud
Published in: Evolutionary Computation in Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Nested Monte-Carlo Search (NMC) and Nested Rollout Policy Adaptation (NRPA) are Monte-Carlo tree search algorithms that have proved their efficiency at solving one-player game problems, such as morpion solitaire or sudoku 16x16, showing that these heuristics could potentially be applied to constraint problems. In the field of Ramsey theory, the
weak Schur number
WS
(
k
) is the largest integer
n
for which their exists a partition into
k
subsets of the integers [1,
n
] such that there is no
x
<
y
<
z
all in the same subset with
x
+
y
=
z
. Several studies have tackled the search for better lower bounds for the Weak Schur numbers
WS
(
k
),
k
≥ 4. In this paper we investigate this problem using NMC and NRPA, and obtain a new lower bound for
WS
(6), namely
WS
(6) ≥ 582.