\section{Introduction}\label{sec:introduction}
In recent years, the interest in combinatorial games as a challenge in AI has increased after the first AlphaGo program~\cite{silver2016mastering}  defeated the human world champion of Go~\cite{plaat2020learning}. The great success of the AlphaGo and AlphaZero programs~\cite{silver2016mastering,silver2017mastering,silver2018general} in two-player games, has inspired attempts in other domains~\cite{segler2018planning,wang2020warm}. So far, one of the most challenging single player games, Morpion Solitaire~\cite{cboyer2020} has not yet been studied with this promising deep reinforcement learning approach. 

Morpion Solitaire is a popular single player game since 1960s~\cite{cboyer2020,demaine2006morpion}, because of its simple rules and simple equipment, requiring only  paper and  pencil. Due to its large state space it is also an interesting AI challenge in single player games, just like the game of Go challenge in two-player turn-based games. Could the AlphaZero self-play approach, so successful in Go, also work in Morpion Solitaire? For ten years little progress has been made in Morpion Solitaire. It is time to take up the challenge and to see if a self-play deep reinforcement learning approach will work in this challenging game. 

AlphaGo and AlphaZero combine deep neural networks~\cite{schmidhuber2015deep} and Monte Carlo Tree Search~(MCTS)~\cite{browne2012survey} in a self-play framework that learns by curriculum learning~\cite{bengio2009curriculum}. Unfortunately, these approaches can not be directly used to play single agent combinatorial games, such as travelling salesman problems~(TSP)~\cite{rego2011traveling} and bin package problems~(BPP)~\cite{hu2018multi}, where cost minimization is the goal of the game. To apply self-play for single player games, Laterre et al. proposed a Ranked Reward~(R2) algorithm. R2 creates a relative performance metric by means of ranking the rewards obtained by a single agent over multiple games. In two-dimensional and three-dimensional bin packing R2 is reported to out-perform MCTS~\cite{laterre2018ranked}. In this paper we use this idea for Morpion Solitaire. Our contributions can be summarized as follows:
\begin{enumerate}
    \item We present the first implementation\footnote{Source code: https://github.com/wh1992v/R2RRMopionSolitaire} of Ranked Reward AlphaZero-style self-play for Morpion Solitaire.
    \item On this implementation, we report our current best solution, of 67 steps~(see Fig~\ref{fig:67stepsgrid}). 
\end{enumerate} 
This result is very close to the human record, and shows the potential of the self-play reinforcement learning approach in Morpion Solitaire, and other hard single player combinatorial problems.


This paper is structured as follows. 
After giving an overview of related work in Sect.\,\ref{sec:relatedwork}, we introduce the 
Morpion Solitaire challenge in Sect.\,\ref{sec:morpion}. Then we present how to integrate the idea of R2 into  AlphaZero self-play in Sect.\,\ref{sec:R2}. Thereafter, we set up the experiment in Sect.\,\ref{sec:setup}, and show the result and analysis in Sect.\,\ref{sec:result}. Finally, we conclude our paper and discuss future work.


\section{Related Work}\label{sec:relatedwork}
Deep reinforcement learning~\cite{mnih2015human} approaches, especially the AlphaGo and AlphaZero programs, which combine online tree search and offline neural network training, achieve super human level of playing two player turn-based board games such as Go, Chess and Shogi~\cite{silver2016mastering,silver2017mastering,silver2018general}. These  successes spark the interest of creating new deep reinforcement learning approaches to solve  problems in the field of game AI, especially for other two player games~\cite{tian2019elf,wang2020analysis,wang2018monte,wang2018assessing}.

However, for single player games, self-play deep reinforcement learning approaches are not yet well studied since the approaches used for two-player games can not directly be used in single player games~\cite{laterre2018ranked}, since the goal of the task changes from winning from an opponent, to minimizing the solution cost. Nevertheless, some researchers did initial works on single games with self-play deep reinforcement learning~\cite{moerland2018a0c}. The main difficulty is representing single player games in ways that allow the use of a deep reinforcement learning approach. In order to solve this difficulty, Vinyals et al.~\cite{vinyals2015pointer} proposed a neural architecture~(Pointer Networks) to represent combinatorial optimization problems as sequence-to-sequence
learning problems. Early Pointer Networks achieved decent performance on TSP, but this approach is computationally expensive and  requires handcrafted training examples for supervised learning methods. Replacing supervised learning methods by actor-critic methods removed this requirement~\cite{bello2016neural}. In addition, Laterre et al.\ proposed the R2 algorithm through ranking the rewards obtained by a single agent over multiple games to label win or loss for each search, and this algorithm reportedly outperformed plain MCTS in the bin packing problem (BPP)~\cite{laterre2018ranked}. Feng et al.\ recently used curriculum-driven deep reinforcement learning to solve hard Sokoban instances \cite{feng2020solving}.

In addition to TSP and BPP, Morpion Solitaire has long been a  challenge in NP-hard single player problems. Previous works on Morpion Solitaire mainly employ traditional heuristic search algorithms~\cite{cboyer2020}. Cazenave created Nested Monte-Carlo Search and found an 80 moves record~\cite{cazenave2009nested}. After that, a new Nested Rollout Policy Adaptation algorithm achieved a new 82 steps record~\cite{rosin2011nested}. Thereafter, Cazenave applied Beam Nested Rollout Policy Adaptation~\cite{cazenave2012beam}, which reached the same 82 steps record but did not exceed it, indicating the difficulty of making further progress on Morpion Solitaire using traditional search heuristics.

We believe that it is time for a new approach, applying (self-play) deep reinforcement learning  to train a Morpion Solitaire player. The combination of the R2 algorithm with the AlphaZero self-play framework could be a first alternative for above mentioned approaches. 


\section{Morpion Solitaire}\label{sec:morpion}
Morpion Solitaire is a single player game played on an unlimited grid. It is a well know NP-hard challenge~\cite{cboyer2020}. The rules of the game are simple. There are 36 black circles as the initial state~(see Fig~\ref{fig:ruleexample}). A move for Morpion Solitaire consists of two parts: a) placing a new circle on the paper so that this new circle can be connected with four other existing circles horizontally, vertically or diagonally, and then b) drawing a line to connect these five circles~(see action 1, 2, 3 in the figure). A line is allowed to cross over each other~(action 4), but not 
allowed to overlap. There are two versions: the Touching~(5T) version and the Disjoint~(5D) version. For the 5T version, it is allowed to touch~(action 5, green circle and green line), but for the 5D version, touching is illegal~(any circle can not belong to two lines that have the same direction). After  a legal action the circle and the line are added to the grid. In this paper we are interested in the 5D version.

The best human
score for the 5D version is 68 moves \cite{demaine2006morpion}. A score of 80 moves was found by means of Nested Monte-Carlo search~\cite{cazenave2009nested}. In addition,~\cite{rosin2011nested} found a new record with 82 steps, and \cite{cazenave2012beam} also found a 82 steps solution. It has been proven mathematically  that the 5D version has an upper bound of 121~\cite{kawamura2013morpion}. 

\begin{figure}[htbp]
\centerline{\includegraphics[width=0.9\columnwidth]{ruleexample.pdf}}
\caption{Moves Example: Moves 1, 2, 3, 4 are legal moves, move 5 is illegal for the 5D version, but legal for the 5T version.}
\label{fig:ruleexample}
\end{figure}

\section{Ranked Reward Reinforcement Learning}\label{sec:R2}
AlphaZero self-play achieved milestone successes in  two-player games, but  can not be directly used for single player cost minimization games. Therefore, the R2 algorithm has been  created to use self-play
for generic single player MDPs. R2 reshapes the rewards according to player's relative performance over recent games~\cite{laterre2018ranked}. The pseudo code of  R2  is given in Algorithm~\ref{alg:r2a0g}.

\begin{algorithm*}[bth!]
\caption{Ranked Reward Reinforcement Learning within AlphaZero-like Self-play Framework}
\label{alg:r2a0g}
\begin{algorithmic}[1]
\footnotesize
\Function{RankedRewardReinforcementLearning}{}
\State Initialize $f_\theta$ with random weights; Initialize retrain buffer $D$ and  reward list $B$ 
\For{iteration=1, $\dots$ $\dots$, $I$}
\Comment self-play curriculum of $I$ tournaments
\For{episode=1,$\dots$, $E$}\Comment{stage 1, 
self-play tournament of $E$ games}
\For{t=1, $\dots$, $T^\prime$, $\dots$, $T$} 
\Comment play game of $T$ moves

\State$\pi_{t} \leftarrow$ perform MCTS based on  $f_\theta$ or directly get policy from  $f_\theta$
\Comment with or without tree search enhancement \label{mctsenhancement}
\State $a_t=$randomly select on $\pi_t$ before $T^\prime$ or $\arg\max_a(\pi_t)$ after $T^\prime$ step
\State executeAction($s_t$, $a_t$)
\EndFor

\State Calculate game reward $r_{T}$ and store it in $B$\label{line:calreward}
\State Calculate threshold $r_\alpha$ based on the recent games rewards in $B$

\State Reshape the ranked reward $z$ following Equation~\ref{equ:reshape}\label{line:reshape}\Comment{Ranked Reward}

\State Store every $(s_t,\pi_t,z_t)$ with ranked rewards $z_t$ ~($t\in[1,T]$) in $D$
\EndFor
\State Randomly sample  minibatch of examples~($s_j$, $\pi_j$, $z_j$) from $D$ \Comment{stage 2}
\State Train $f_{\theta^\prime}\leftarrow f_\theta$ 
\State Play once with MCTS enhancement on $f_{\theta^\prime}$\label{mctsplay} \Comment{stage 3}
\State Replace $f_{\theta}\leftarrow f_\theta^\prime$ 

\EndFor
\State \Return $f_\theta$;
\EndFunction
\end{algorithmic}
\end{algorithm*}

Following  AlphaZero-like self-play~\cite{wang2019alternative}, we demonstrate the typical three stages as shown in the pseudo code. For self-play in Morpion Solitaire MCTS  is too time consuming due to the large state space. Thus, we rely on the policy directly from $f_\theta$ without tree search~(line~\ref{mctsenhancement}). For stage 3, we directly replace the previous neural network model with the newly trained model. and we let the newly trained model play a single time with MCTS enhancement~(line~\ref{mctsplay}).  The R2 idea is integrated~(see line~\ref{line:calreward} to line~\ref{line:reshape}). The reward list $B$ stores the recent game rewards. According to a ratio $\alpha$, the threshold of $r_\alpha$ is calculated. We then compare  $r_\alpha$ to the game reward $r_T$ to reshape the ranked reward $z$ according to Equation~\ref{equ:reshape}.

\begin{equation}\label{equ:reshape}
    z=
\begin{cases}
1& r_T > r_\alpha\\
-1& r_T < r_\alpha\\
random(1, -1) & r_T = r_\alpha
\end{cases}
\end{equation}
where $r_\alpha$ is the stored reward value in $B$ indexed by $L\times \alpha$, $L$ is the length of $B$, $\alpha$ is a ratio parameter. 

\section{Experiment Setup}\label{sec:setup}
We perform our experiments on a GPU server with 128G RAM, 3TB local storage, 20 Intel Xeon E5-2650v3 cores~(2.30GHz, 40 threads), 2 NVIDIA Titanium GPUs~(each with 12GB memory) and 6 NVIDIA GTX 980 Ti GPUs~(each with 6GB memory). 

The hyper-parameters of our current R2 implementation are as much as possible equal to previous work. In this work, all neural network models share the same structure as in~\cite{wang2019alternative}. The hyper-parameter values for Algorithm~\ref{alg:r2a0g} used in our experiments are given in Table~\ref{defaulttab}. Partly, these  values are set based on the work reported in~\cite{wang2019hyper} and the R2 approach for BPP~\cite{laterre2018ranked}. $T'$ is set to half of the current best record. $m$ is set to 100 if using MCTS in self-play, but 20000 for MCTS in stage 3. Furthermore, as there is an upper bound of the best score~(121), we did experiments on 16$\times$16, 20$\times$20 and 22$\times$22 boards respectively. Training time for every algorithm is about a week.

\begin{table}[!bth]
\small
\centering
\caption{Default Parameter Settings}\smallskip
\resizebox{1\columnwidth}{!}{
\smallskip\begin{tabular}{|c|c|c|}
\hline
Parameter	& Brief Description& Default Value\\
\hline
\emph{I}	&number of iterations 	&100	\\
\hline
\emph{E}    &number of episodes   &50\\
\hline
\emph{T'}	&step threshold	&41\\
\hline
\emph{m}	&MCTS simulation times &20000\\
\hline
\emph{c}    &weight in UCT  &1.0\\
\hline
\emph{rs}	& number of retrain iterations &10\\
\hline
\emph{ep}	& number of epochs	&5	\\
\hline
\emph{bs}	& batch size	&64\\
\hline
\emph{lr}	& learning rate	&0.005\\
\hline
\emph{d}    & dropout probability  &0.3\\
\hline
\emph{L}    & length of $B$ &200\\
\hline
\emph{$\alpha$}	& ratio to compute $r_\alpha$	&0.75 \\
\hline
\end{tabular}
}
\label{defaulttab}
\end{table}


\section{Result and analysis}\label{sec:result}

As we mentioned above, the best score for Morpion Solitaire of 82 steps has been achieved by Nested Rollout Policy Adaptation in 2010. The best score achieved by human is 68. Our first attempt with limited computation resources on a large size board~(22$\times$22) achieved a score of 67, very close to the best human score. The resulting solution is  shown in Fig~\ref{fig:67stepsgrid}.

Based on these promising results with  Ranked Reward Reinforcement Learning we identify  areas for further improvement. First,  parameter values for the Morpion Solitaire game can be fine-tuned using results of small board games. Especially the parameter  $m=100$ seems not sufficient for large boards. Second, the neural network could be changed to Pointer Networks and the size of neural network should be deeper.  

Note that the tuning of parameters is critical; if the reward list $B$ is too small,  the reward list can be easily filled up by scores close to 67. The training will then be stuck in a locally optimal solution. As good solutions are expected to be sparsely distributed over the  search space, this increases the difficulty to get rid of a locally optimal solution once the algorithm has focused on it.

\begin{figure}[htbp]
\centerline{\includegraphics[width=0.9\columnwidth]{67steps.pdf}}
\caption{Detailed Steps of Our Best Solution}
\label{fig:67stepsgrid}
\end{figure}


\section{Conclusion and Outlook}\label{sec:conclusion}
In this work, we apply a Ranked Reward Reinforcement Learning AlphaZero-like approach to play Morpion Solitaire,  an important NP-hard  single player game challenge. We train the player on 16$\times$16, 20$\times$20 and 22$\times$22 boards, and find a near best human performance solution with 67 steps.  As a first attempt of utilizing self-play deep reinforcement learning approach to tackle Morpion Solitaire, achieving near-human performance is a promising result.  

Our first results give us reason to believe that there remain ample possibilities to improve the approach by investigating the following aspects:
\begin{enumerate}
    \item Parameter tuning: such as the Monte Carlo simulation times. Since good solutions are  sparse in this game, maybe more exploration is beneficial?
    \item Neural Network Design: It is reported that Pointer Networks perform better on combinatorial problems. A next step could be to also make the neural network structure deeper.
    \item Local Optima: Through monitoring the reward list $B$, we can adjust in time by enlarging more exploration once it gets stuck in a locally optimal solution. 
    \item Computation resources and parallelization: enhanced parallelization may improve the results.
\end{enumerate}

To summarize, although the problem is difficult due to its large state space and sparsity of good solutions, applying a Ranked Reward self-play Reinforcement Learning approach to tackle Morpion Solitaire is a promising and learns from \textit{tabula rasa}.  We present our promising near-human result to stimulate future work on Morpion Solitaire and other single agent games with self-play reinforcement learning. 

\section*{Acknowledgment}

Hui Wang acknowledges financial support from the China Scholarship Council (CSC), CSC No.201706990015.

\bibliographystyle{./IEEEtran}
