1.1 Problem description

A DSPI instance is parameterized by a directed graph $G(𝒩,𝒜)$, a source node $$$ s $$$ and terminal node $$$ t $$$, and a budget $$$ b\in \mathbb{N} $$$. Each arc $(i,j)\in 𝒜$ possesses a cost $$$ {c}_{ij} $$$ and an interdiction cost increment $$$ {d}_{ij} $$$.

The evader seeks to traverse the graph from the source to the terminal at the minimum possible cost. The interdictor seeks to maximize the evader's minimum cost by attacking arcs. The game starts with the evader's position at the source and unfolds in turns. The interdictor moves first and is allowed to attack any subset of arcs (or possibly none at all); then the evader traverses an arc, and the players keep making turns until the evader reaches the terminal. The total number of arcs that the interdictor can attack during the course of the game cannot exceed the budget $$$ b $$$.

Sefair and Smith [32] demonstrate that the decision variant of this problem is NP-hard and proposed an exact dynamic programming (exponential-time) algorithm for the case of a general graph $$$ G $$$, a polynomial-time algorithm for a directed acyclic graph (DAG), and several approaches to find upper and lower bounds on the optimal objective. We build upon these results by designing a heuristic algorithm based on the MCTS approach, and demonstrating its performance on a set of randomly generated and pre-defined instances.

1.2 Background

The foundation for our work is the shortest-path interdiction (SPI) problem, wherein the interdictor first chooses a set of arcs to attack, and then the evader minimizes its path cost given the attacker's decision [11, 14]. Many variants of the problem have been discussed in the literature. One common fortification variation allows the evader to act prior to the interdictor by protecting a subset of arcs from attack. Methodologically, fortification studies tend to approach these problems using a variation of Benders decomposition [5] or using more general cutting-plane approaches [8, 10, 29, 35]. There have recently been several contributions in asymmetric interdiction problems, that is, those in which one player has an information advantage over the other. Most assume that the interdictor owns the network and has better information than the evader, as done by Bayrak and Bailey [4] and Sullivan et al. [37]. Salmerón [30] considers the case in which decoys can be placed by the interdictor to induce the evader to take a path advantageous to the interdictor. Nguyen and Smith [20, 21] study a variation of the problem in which some cost data is known to the interdictor only according to a probability distribution, though the evader acts with full knowledge of all cost data. Finally, note that the objective function value of an SPI instance is a nondecreasing function of the interdiction budget. We may therefore wish to model SPI as a multi-objective optimization problem with (interdictor) objectives of minimizing budget while maximizing the evader's shortest-path cost [26-28]. We refer to the survey [36] on network interdiction for a more thorough overview.

We consider a specific complication of SPI, namely, a dynamic version of the game introduced by [32]. As opposed to SPI, the DSPI is a multi-stage game. An exact dynamic-programming based algorithm proposed in the aforementioned paper finds an optimal solution in polynomial time for a DAG. However, the authors show that for the general case, no polynomial-time algorithm exists (unless $𝒫=𝒩𝒫$). To the best of our knowledge, while [32] proposed bounds on the optimal objective, no heuristic algorithm exists in the literature that yields high-quality solutions (valid sequences of moves corresponding to the objective values, supplied by the bounds, or the players' policies). We seek to fill in this gap with the algorithm proposed in this work.

From the methodological perspective, we draw inspiration from areas of machine learning (ML) and, in particular, reinforcement learning (RL). There is growing literature on using ML for combinatorial optimization; see, for example, [6] for a general overview and [19] for one emphasizing RL. We build our algorithm using the MCTS framework. Sutton and Barto [38] give a thorough introduction to RL, while surveys by Browne et al. [9] and Świechowski et al. [39] briefly describe the method and summarize ideas for improving different components of the algorithm. These ideas include a specific way for encouraging exploration during the selection process using the ideas from the multi-armed bandit literature, introduced in [17, 18]. There are numerous examples of using MCTS for solving various problems, both within the area of game playing and beyond, including [15, 25, 34].

Several recent studies apply ML methods to games involving graphs. Xue et al. [42] propose an MCTS-based approach to network security games, which leverages three deep neural networks to drive the game tree growth. Baycik [3] focuses on maximum flow network interdiction using decision tree regression and random forest regression methods. Finally, Huang et al. [13] approach the (two-stage) SPI using reinforcement learning based on pointer networks [40].

2.1 Implementation overview

Our algorithm builds a game tree whose nodes correspond to a partial game that has been played between the two players. The relevant information pertaining to the game is captured by state information, summarized in Table 1. We record state information pertaining to each node of the game tree. For a given node $$$ j $$$, the children of node $$$ j $$$ in the game tree correspond to the new game state after an action is made at node $$$ j $$$.

Our approach is a decision-time algorithm in the sense that it is designed to start from some current state of the game, represented by the root game tree node, and determine the next action to be taken by the corresponding player. After a decision is made, the child node corresponding to that decision becomes the new root node. All nodes not reachable from the new root node can be discarded, while information pertaining to nodes reachable from the new root node is retained.

Specifying all subsets of attacks for the interdictor can be computationally prohibitive. To avoid enumerating all possible attack subsets at each node corresponding to the interdictor's move, we impose the restriction that the interdictor can attack only one arc at each game tree node, while allowing the interdictor to retain its turn until the interdictor chooses to attack no further arcs (i.e., passes). We call these single-arc attack actions virtual turns for the interdictor. The evader's turn consists of a single arc to traverse; hence, there is no need to include virtual turns for the evader. We remove unnecessary symmetry from the interdictor's virtual turns by requiring that arcs can be attacked consecutively only in the increasing order of the tail node numbers. For example, arc $$$ \left(2,5\right) $$$ must be attacked before $$$ \left(2,7\right) $$$ within an uninterrupted sequence of single-arc attacks.

Algorithm 1 presents a high-level description of our approach. We initialize the game tree, evader position ($$$ p $$$), and game cost $$$ \Delta $$$ in the first two lines. Then, the algorithm repeatedly recommends the next action $$$ a $$$ in line 4, leading to game tree node $$$ m $$$, until the evader reaches the terminal node. Line 5 updates the cost of the game, where cost $$$ {\tilde{C}}_{ij} $$$ is associated with an arc $$$ \left(i,j\right) $$$ in the game tree. If game tree node $$$ i $$$ corresponds to an interdictor's move, then $$$ {\tilde{C}}_{ij}=0 $$$; else, $$$ {\tilde{C}}_{ij} $$$ is the cost of traversing arc $$$ \left(\mathrm{p}(i),\mathrm{p}(j)\right) $$$. Hence, $$$ \Delta $$$ accumulates the total cost for the evader for the corresponding sequence of moves for both players. Lines 6 and 7 update the evader's position and the root node of the game tree, respectively.

Algorithm 1. MCTS-play-instance

The key function, MCTS-next-move, that finds the next action using MCTS appears in line 4 of Algorithm 1. We now give an overview of this critical function before describing the details.

Algorithm 2 provides pseudocode for MCTS-next-move. This function executes a sequence of $$$ K $$$ MCTS iterations, which we call learning episodes, before deciding the next move to make. We break each learning episode into four stages, summarized in Figure 1. The Selection phase spans lines 2–20 of Algorithm 2. In this phase we start from the root node and recursively choose child nodes that are more promising according to our estimates, until we reach a leaf node of the game tree (not necessarily implying the end of the game). We also prune the tree as necessary during this stage. Then, during the Expansion phase (lines 21–41), we create child nodes for the selected node, corresponding to all possible actions that the current player can execute. We build an estimate for the future game cost (cost-to-go) for each new node during the Roll-outs phase by calling a procedure in line 42. In particular, starting from each new node $$$ n $$$ we simulate a game by choosing player actions at random and record the resulting objective as the cost-to-go estimate, denoted $$$ {\hat{Q}}_n $$$. Finally, we propagate this new information back from the selected leaf node towards the root during the Backpropagation phase in lines 43–55. We traverse the tree backwards and update the cost-to-go estimates along with the bounds for each parent node to make them consistent with the information contained in the child nodes.

Algorithm 2. MCTS-next-move

Finally, after $$$ K $$$ learning episodes have been executed, the last two lines of the algorithm recommend an action depending on which player is acting at the root node. The evader will choose among the least-cost children of the root node, while the interdictor will choose from among the highest-cost children, given the arc traversal costs and the cost-to-go estimates established thus far.

The next four subsections provide algorithmic details for the four learning episode phases given above. Section 2.6 then discusses the correctness of our algorithm and its asymptotic convergence properties.

2.2 Selection

The result of the Selection phase is a path from the root node to a leaf node in the game tree. Node $$$ n $$$ denotes the current game tree node in this path as we iterate from the root to a leaf node. We keep track of the selected nodes in ordered list $$$ P $$$ (which initially contains only root), and the cumulative cost of the selected path in $$$ \pi ={\sum}_{l=1}^{\mid P\mid -1}{\tilde{c}}_{\mathrm{p}\left({P}_l\right),\mathrm{p}\left({P}_{l+1}\right)}\left({S}_{P_l}\right)={\sum}_{l=1}^{\mid P\mid -1}{\tilde{C}}_{P_l,{P}_{l+1}} $$$. The while-loop in line 5 iterates until node $$$ n $$$ has no more children and no more unexplored actions that would generate more children. Given $$$ n $$$, the selection phase performs three tasks: pruning, node choice, and symmetry breaking.

Pruning. We employ alpha–beta pruning [16] to mitigate the growth of the game tree. Recall that every game tree node $$$ j $$$ is associated with a lower bound, $$$ \mathrm{LB}(j) $$$, and an upper bound, $$$ \mathrm{UB}(j) $$$, on the cost-to-go from node $$$ j $$$. These bounds are obtained in the expansion phase and are discussed in Section 2.3.

The corresponding pseudocode is presented in Algorithm 3. After updating these $$$ \alpha $$$ and $$$ \beta $$$ bounds, for every child node $$$ j $$$ we calculate the lower bound $$$ {\hat{\alpha}}_j $$$ and the upper bound $$$ {\hat{\beta}}_j $$$ on the total game cost assuming an optimal play starting from this child node. Then, we prune any child node $$$ j $$$ of parent node $$$ n $$$ such that $$$ \beta <{\hat{\alpha}}_j $$$ or $$$ {\hat{\beta}}_j<\alpha $$$. Appendix A provides an illustration of alpha–beta pruning.

Algorithm 3. prune-child-nodes

Node choice. One trade-off arising in our node choice task is one of exploration (exploring parts of the tree that have not yet been thoroughly examined) versus exploitation (searching areas of the tree that appear most promising). We employ the ideas of upper confidence bounds [17, 18] and $$$ \varepsilon $$$-greedy search [38] to facilitate the exploration-exploitation trade-off.

An auxiliary variable $$$ {\sigma}_j $$$ takes the value of $$$ 1 $$$ if $$$ \tau (j)= $$$ “Interdictor,” and $$$ -1 $$$ otherwise, and is used to accommodate the fact that the evader minimizes the game cost, while the interdictor maximizes it. Therefore, the first term represents our estimate for the additional game cost if we start from game tree node $$$ i $$$ and proceed to node $$$ j $$$.

The second term is designed to make under-explored nodes more attractive. Note that as the total number of visits for the parent node $$$ {N}_i $$$ increases, if children other than $$$ j $$$ are selected more often, then $$$ \log \left({N}_i\right)/{N}_j $$$ will increase, making node $$$ j $$$ relatively more attractive. The constant parameter $$$ {C}_p $$$ regulates the degree of exploration and is chosen empirically. This term with the logarithm under the square root is inspired by research concerning the multi-armed bandit problem, as it captures the variance in the estimate of the action's value.

Multi-armed bandit research stems from the following problem. A user seeks to maximize expected profits in a sequential, repeated choice among $$$ K $$$ discrete actions. Each action yields a (random) reward, but its distribution is unknown beforehand. Therefore, after several plays the user is faced with the exploration versus exploitation dilemma: one could either exploit actions for which much information is already known, or explore the action space in hope of finding one with a better expected reward, at a cost of experiencing actions with lower reward as well. A simple policy that achieves certain desirable theoretical properties for the $$$ K $$$-armed bandit problem, called UCB1, was proposed by [2].

In MCTS, despite its fully deterministic setting, the choice of a child node during our selection phase is a choice among a finite number of actions with uncertain rewards. (Uncertainty here arises from the lack of information regarding the consequences of the chosen strategy.) This analogy to the multi-armed bandit problem was exploited by [17, 18], who proposed an adaptation of UCB1 score to the MCTS setting (under the name Upper Confidence Bound for Trees, or UCT). A $$$ K $$$-armed bandit problem is discussed, for example, in [38, Section 2.1], and in the context of MCTS in [9, Sections 2.4 and 3.3].

Based on preliminary experiments, to speed up the procedure we also implement $$$ \varepsilon $$$-greedy selection modification as follows. With probability $$$ \varepsilon $$$ we pick a child node uniformly at random. Otherwise (with probability $$$ \left(1-\varepsilon \right) $$$) we choose a node having the best score as described above. Note that this $$$ \varepsilon $$$-greedy adjustment allows the algorithm to potentially consider any node within the game tree for exploration. We provide additional insights on selection strategies in Appendix C.

Symmetry breaking. Lines 13–17 ensure that no symmetric virtual turns are created for the interdictor. Here min-int tracks the to-node of the most recent arc that was interdicted, enforcing the anti-symmetry conditions stated previously for virtual turns. Lines 18 and 19 update the number of evader turns, costs, partial path, and current node.

2.3 Expansion

The expansion phase is described in lines 21–41 in Algorithm 2. We create child nodes of the current node $$$ n $$$ corresponding to actions that can be taken from node $$$ n $$$. All such child nodes are placed in a list, $$$ E $$$.

To generate these child nodes, line 22 ensures that there are unexplored actions and that $$$ n $$$ is not in fact the terminal node of the DSPI instance. Lines 23–25 create a new node $$$ j $$$, initializing the appropriate parameters and updating the unexplored actions from node $$$ n $$$. Lines 26–36 set up possible further actions for the new game tree node, ensuring that the tail node of an interdicted arc is always greater than that of the previous interdiction turn in an uninterrupted sequence of virtual attacks to avoid symmetry. Note that once we select a node, we create all possible child nodes at once.

Next, recall that our algorithm tracks the number of evader's turns $$$ {T}_e $$$ in lines 4 and 18. We use this counter to limit the maximum tree depth in line 37. To justify this check, we establish the following lemma.

Therefore, in our heuristic we discard any solution that implies more than $$$ \left(b+1\right)N $$$ evader's turns as follows. For the node corresponding to the first excessive evader's turn, we set upper bounds of all its child nodes to $$$ -\infty $$$ (line 37). By doing so, this node will be pruned during the next selection (involving this node) with any finite values of $$$ \alpha $$$ and $$$ \beta $$$.

Finally, assuming that a new node $$$ j $$$ is not marked for deletion by Lemma 1, we establish lower and upper bounds on the cost-to-go from node $$$ j $$$. To do this, we adapt polynomial-time bounding strategies introduced in [32].

In particular, to obtain the lower bound, the interdictor is restricted by assuming that its attacks expire (i.e., are reset to their original, unattacked values) after the next evader's turn. Therefore, we need not keep track of the specific interdiction decisions $$$ S $$$, but just the residual budget. The corresponding polynomial-time algorithm in [32] is called DP-DSPI-EXP. Thus, our lower-bounding procedure, described in Algorithm 4, first incorporates the interdiction decisions already made from the path of the root node to node $$$ n $$$ in the game tree, and then calls the dynamic programming algorithm DP-DSPI-EXP, which returns a matrix of the optimal objective values for each combination of the interdictor's remaining budget and evader's position.

Algorithm 4. MCTS-LB

For the upper bound, we restrict the evader by removing arcs from the graph until it becomes a DAG. The removal of these arcs allows us to use the polynomial-time algorithm (which we denote DP-DSPI-DAG) given in [32] to solve the resulting auxiliary instance. The implementation is presented in Algorithm 5. We execute this algorithm NTRIALS=100 times (with each run removing possibly different arcs to form a DAG), and retain the best bound obtained.

Algorithm 5. MCTS-UB

2.4 Roll-outs

The prior expansion phase results in a list of newly created nodes having valid bounds, but with undefined cost-to-go estimates $$$ \hat{Q} $$$. To obtain cost-to-go estimates for the new nodes, the roll-out procedure is called in line 42 of Algorithm 2. The implementation described in Algorithm 6 plays out a game with uniformly random turns for both players. We track the game as it changes states in temporary variables that describe cost $$$ \left(\Delta \right) $$$, the current evader's position $$$ p $$$, current budget $$$ {b}_{\mathrm{RO}} $$$, interdiction decisions $$$ S $$$, and turn $$$ \tau $$$.

Algorithm 6. MCTS-roll-out

2.5 Backpropagation

Note that given our approach to backpropagation, the algorithm is closely related to a minimax search [16], but uses the ideas of Monte Carlo simulations to estimate game costs and drive the search through the game tree.

2.6 Algorithm correctness and asymptotic properties

The MCTS algorithm we propose yields a valid sequence of turns and a heuristic objective estimate by construction. In this section we discuss some asymptotic properties pertaining to this algorithm. First, observe that the resulting game tree size is bounded in the following sense.

In the foregoing proof, note in particular that the bound on the maximum size of the game tree depends only on $$$ G $$$, and is independent of the number of iterations, $$$ K $$$.

3.1 Pre-defined instances and scaling

First, we run the MCTS algorithm against the dataset of pre-defined instances. Figure 2 depicts the known optimal value, calculated lower and upper bounds, and the objective obtained by our MCTS play-out for each instance. The bounds proposed by Sefair and Smith are very tight: in fact, they close the gap immediately for most instances. Although their bounds do not reveal the actual optimal policy, they direct our algorithm to find either optimal or near-optimal solutions in just $$$ K=10 $$$ learning episodes per move.

These instances were used to validate the exact approach, and are relatively easy to solve. The exact DP algorithm typically solved each instance in under 10 s (under 1 s most of the time), and was actually faster than our proposed heuristic on each instance. As one might expect, the exact and heuristic approaches scale in fundamentally different ways. To illustrate this fact, we modified each instance to consider the cases of $$$ b=1 $$$, 2, and 3. We solved each of these new instances with the exact DP algorithm and using our MCTS procedure, keeping records of the runtime (in seconds) and the objective values obtained. The results are summarized in Table 2.

First, note that for the majority of the cases the objective values coincide for both methods (except for a few larger instances). Therefore, 10 episodes per move was enough for the proposed algorithm to identify an optimal game play for both players in many cases on our dataset. This confirms our intuition that for larger instances, it would be prudent to allow larger computational budgets (increasing the value of $$$ K $$$) to obtain better solutions.

Runtimes vary greatly but exhibit an expected pattern. When $$$ b=1 $$$ or 2, the MCTS was almost always significantly slower than the exact DP algorithm. However, even for $$$ b=3 $$$ the situation is reversed, as the state space of the DP grows exponentially, while the MCTS limits the game tree size via pruning and strategic move selection. Also as we would expect, these effects grow stronger as we move from the 10-node instances to the 20-node instances.

To further illustrate how the MCTS algorithm scales with the instance size, we generated three random fifty-node instances and varied the budget from $$$ b=1 $$$ to $$$ 10 $$$. The results are summarized in Figure 3. We still see that the MCTS approach often finds an actual sequence of turns leading to the optimal (or near-optimal) objective. The runtimes for these larger instances are under 100 s, which indicates that the MCTS-based approach is scalable for instances of this size, as opposed to the exact algorithm. The figure also suggests that for larger instances, we could trade off additional runtime for better solutions by increasing the maximum number of iterations $$$ K $$$, as the algorithm sometimes yielded play-out objectives outside of the calculated bounds. Note that obtaining objective values outside of the bounds is technically possible, because the algorithm chooses the actions based on our cost-to-go estimates. The bounds are not tight enough to cut off all suboptimal solutions. Also, note that the MCTS runtime does not grow as fast as $$$ b $$$ increases from $$$ 1 $$$ to $$$ 10 $$$ as the exact DP algorithm would. The growth of the tree is evidently highly dependent on the instance structure.

3.2 MCTS convergence profile

Note that a naive implementation of our MCTS algorithm could ultimately construct a full minimax tree, which would inevitably find an optimal strategy given enough time and space. This section explores the ability of the MCTS heuristic to limit the exploration of the game tree while still obtaining high-quality solutions. To accomplish this analysis, we constructed a convergence profile of our heuristic as follows.

We generated a random instance having $$$ 100 $$$ nodes, $$$ 2424 $$$ arcs, budget $$$ b=2 $$$, arc costs between zero and $$$ 30 $$$, and an optimal objective between $$$ 15 $$$ and $$$ 17 $$$ (as determined by the procedures in [32]). We performed learning episodes from the same root node, varying $$$ \varepsilon $$$ between 0.05, 0.5, and 1.0. For each choice of $$$ \varepsilon $$$, we executed Algorithm 2 from the original root node of the game tree, using $$$ K=1000 $$$ learning episodes. We then recorded how four items changed as the algorithm iterated over each learning episode. These items are (a) the game tree size, (b) the iterations at which nodes are added to and pruned from the game tree, (c) the stability of the recommended action to take from the root node, and (d) the estimate of the game value. The results are summarized in Figure 4, where the four metrics are illustrated in each row, and the three columns correspond to the choice of $$$ \varepsilon $$$. In particular, the “Added/pruned” charts show how many nodes were added (above the horizontal axis, in blue) or pruned (below the horizontal axis, in red) at each iteration. Also, for “Best action,” we arbitrarily index each possible action with a number and plot a dot corresponding to the action recommended at the current episode number (so that long horizontal lines indicate stability in the recommended action from the root node). Rows for the first and last metric are self-explanatory.

On the left panel, corresponding to $$$ \varepsilon =0.05 $$$, the tree grows very actively until around the 600th iteration. Pruning happens frequently as well, but at a slower rate than nodes are added. As the algorithm collects more information, the pruning starts to dominate and the game tree starts to shrink, until its size hits a plateau. In fact, we observe several plateaus interrupted by moments when valuable node discovery allows the algorithm to prune several game tree nodes. The tree size stops changing frequently after approximately 750 episodes, which is the point where the algorithm converges to a relatively stable cost estimate $$$ \hat{Q} $$$ (at the root node) and a recommended action.

The nature of backpropagation with the minimum or maximum function makes the process unstable in terms of cost estimates: the cost-to-go at the root node varies from $$$ 0 $$$ to about $$$ 15\kern0.3em 000 $$$ until around 600th episode. Recommended actions from the root node also change significantly, until they stabilize after around the 250th episode.

These four items vary significantly as we modify $$$ \varepsilon $$$. For $$$ \varepsilon =0.5 $$$ new node creation and pruning continue to occur regularly throughout all of the episodes, and while the game tree remains smaller on the average, the cost estimate at the root node struggles to converge to the optimum game value, only starting to achieve stability around episode 1000. Next, in the extreme case of a purely random exploration mode ($$$ \varepsilon =1.0 $$$) the tree is kept even smaller, but our cost estimate never approaches its true value over the course of the first 1000 episodes. Therefore, deliberately excluding the mechanism of heuristic selection significantly deteriorated the performance of our algorithm.

We next verified that the difference in these convergence profiles is not simply due to the randomness employed in those algorithms. To do so, we performed three independent runs for each set of parameters, and observed the corresponding tree size dynamics as a function of the number of episodes. The results depicted in Figure 5 demonstrate that the algorithm behaves in roughly the same qualitative manner depending on the value of $$$ \varepsilon $$$. That is, we see the same growth-and-pruning pattern when $$$ \varepsilon =0.05 $$$, and a more uniform growth pattern when $$$ \varepsilon =0.5 $$$ or 1.0.

Note that when $$$ \varepsilon =0.05 $$$, our estimate $$$ {\hat{Q}}_{\mathtt{root}} $$$ stabilized around the optimum after more than 500 iterations. However, making turns and updating the root node itself seems to introduce another benefit of (heuristically) focusing the search process. We illustrate this effect in the following experiment.

3.3 The value of a play-out

Note that in the third row of panels in Figure 4, the next action recommendation stopped varying significantly earlier than the cost estimate, regardless of our choice of $$$ \varepsilon $$$. Actually committing this move would have caused the algorithm to focus the analysis on a more promising alternative, ignoring the (now impossible) other moves. To investigate this effect, we generated $$$ 250 $$$ random instances having 50 nodes each, with $$$ b=5 $$$. We discarded any instance for which the initial optimality gap was positive, so that for all 250 instances, we know the optimal objective (but not an optimal sequence of moves). Each such instance was solved by the usual MCTS play-out algorithm, but this time we recorded the total number of learning episodes across all moves until the end of the game. After that, we re-solved the same instance starting from an empty game tree, allowing the algorithm to run for exactly the same number of episodes, but without making any moves. That is, in the latter case the algorithm started the selection every time from the initial root node. The results are summarized in Figure 6. The first row represents the full-tree approach, that is, trying to build an estimate for the best cost without making any moves. The bottom row represents the play-out strategy, when we run ten learning episodes followed by a turn repeatedly until the end of the game. The left column shows the histograms of the objective values obtained by the algorithms, relative to the true optimum. The right column presents the histograms of runtimes per instance, in seconds.

As one might expect, focusing the search by making a move after a limited number of learning episodes yielded improvements both in terms of objective value and runtime. (Mean runtimes, indicated by vertical dashed lines in the figure, differ by more than ten seconds per instance.) For our class of instances, we thus recommend updating the root node as a practical way to speed up the heuristic without significantly compromising solution quality.