Title: ADVERSARIAL POLICY GRADIENT FOR ALTERNATING MARKOV GAMES

Abstract: Policy gradient reinforcement learning has been applied to two-player alternateturn zero-sum games, e.g., in AlphaGo, self-play REINFORCE was used to improve the neural net model after supervised learning. In this paper, we emphasize that two-player zero-sum games with alternating turns, which have been previously formulated as Alternating Markov Games (AMGs), are different from standard MDP because of their two-agent nature. We exploit the difference in associated Bellman equations, which leads to different policy iteration algorithms. As policy gradient method is a kind of generalized policy iteration, we show how these differences in policy iteration are reflected in policy gradient for AMGs. We formulate an adversarial policy gradient and discuss potential possibilities for developing better policy gradient methods other than self-play REINFORCE. The core idea is to estimate the minimum rather than the mean for the "critic". Experimental results on the game of Hex show the modified Monte Carlo policy gradient methods are able to learn better pure neural net policies than the REIN-FORCE variants. To apply learned neural weights to multiple board sizes Hex, we describe a board-size independent neural net architecture. We show that when combined with search, using a single neural net model, the resulting program consistently beats MoHex 2.0, the previous state-of-the-art computer Hex player, on board sizes from 9×9 to 13×13.

1. INTRODUCTION:

Reinforcement Learning (RL) is a trial-and-error paradigm where an agent learns by interacting with an environment. The prediction problem in RL seeks to learn the true value function of a following policy, while the control problem aims to find an optimal policy that maximizes the longterm expected cumulative reward. The environment is assumed to be a Markov Decision Process (MDP) (Bellman, 1957) . Compared to dynamic programming, RL methods have the advantage of being model-free which learn by treating the environment as a black box. Dynamical programming is theoretically fundamental to reinforcement learning (Bertsekas & Tsitsiklis, 1996) , as almost all RL algorithms are a form of generalized policy iteration, which improve the policy while estimating a value function (Sutton & Barto, 2017) .

Model-free reinforcement learning methods have been successfully applied to many domains, including robotics (Kober et al., 2013) , Atari games (Mnih et al., 2015; 2016; Schaul et al., 2016) , and two-player board games (Tesauro, 1995; Silver et al., 2016) . Most RL algorithms fall into one of two categories: value fitting and policy gradient. The value-fitting algorithms try to optimize a value function through iteratively minimizing a sequence of Bellman inconsistencies of observed states or state-action pairs, examples are on-policy SARSA (Rummery & Niranjan, 1994) and off-policy Q-learning (Watkins & Dayan, 1992 ). An optimal deterministic policy is implicitly learned when the value function converges to optimal.

The primary disadvantage of value-fitting methods such as Q-learning (Watkins & Dayan, 1992; Mnih et al., 2015; Wang et al., 2016; Mnih et al., 2016) is that they might be unstable when interacting with function approximation (Bertsekas & Tsitsiklis, 1996; Sutton et al., 2000) . To gain stable behavior, often extra heuristic techniques (Lin, 1992; Schaul et al., 2016) and extensive hyperparameter tuning are required. By contrast, policy gradient methods explicitly represent a policy as a function of parameters: they learn through iteratively adjusting the parameterized policy by fol-lowing estimation of gradients, thus converging to at least a local maximum (Peters & Bagnell, 2011) . Policy gradients are applicable to continuous control (Silver et al., 2014; Schulman et al., 2015; 2017) or domains with large action space (Silver et al., 2016) , whereas action-value learning methods often become infeasible (Lillicrap et al., 2016; Wang et al., 2017) .

Both value and policy based reinforcement learning are well-studied in MDPs, where a single agent learns by exploiting a stationary environment. In this paper, we focus on policy gradient methods for two-player zero-sum games played in alternating turns, i.e., Alternating Markov Games (AMGs) (Littman, 1996) . AMGs are a specialization of Stochastic Games (Shapley, 1953) but a generalization of MDPs by allowing exactly two players pursing diametrical goals. Many popular two-player games are of such kind, such as chess, checkers, backgammon, Hex and Go. The restriction of zero-sum in AMGs makes it possible to define a shared reward function such that one agent tries to maximize while the other agent tries to minimize it. Due to such a property, with a notion of self-play policy, standard reinforcement learning methods have been successfully applied to AMGs (Tesauro, 1995; Silver et al., 2016) by simply negating the reward signal of the opponent's turn.

In this paper, we reexamine the justifications of adapting standard reinforcement learning methods to AMGs. We begin by reviewing the fundamental differences in their corresponding Bellman equations, from which we show how the resulting policy iteration algorithms are disparate. We formulate an adversarial policy gradient objective specifically for AMGs, based on which we develop new policy gradient methods for AMGs. Specifically, we apply our approach to the game of Hex. We show that by modifying REINFORCE to estimate the minimum rather than the mean return of a self-play policy, stronger pure neural net players are obtained.

2. FINITE MDP:

A finite MDP is a tuple (S, A, R, P, γ) where S is finite set of states, A is a set of actions, R : S × A → R is a reward function, and P defines the probabilistic transitions among states. An agent lives in an environment characterized by the Markov property, i.e., Pr(s t+1 |s 1 , a 1 , . . . , s t , a t ) = Pr(s t+1 |s t , a t ). The agent learns by receiving reward signals from interacting with the environment. The goal is to maximize the expected discounted cumulative reward:

E ∞ k=t γ t-k R t-k+1

, where γ is a discounting factor 0 < γ ≤ 1 that controls the contribution of long-term and short-term rewards; γ = 1 is only possible in episodic tasks.

The basis for reinforcement learning in MDP is a set of Bellman Equations. For a given policy π:

EQUATION

where p(s |s, a) is the transition function and r(s, a, s ) is the reward of taking a at s, leading to s .

It is also popular to use an action-value function:

EQUATION

The above Bellman equations are the basis for policy evaluation, which computes the true value function for a given π. This corresponds to the prediction problem in RL. The Optimal Bellman Equation is a recursive relation for the optimal policy:

EQUATION

EQUATION

A value iteration procedure derived by the above optimal Bellman equation converges to optimal (Bellman, 1957) . Alternatively, it is also possible to derive a policy iteration (Howard, 1960; Bertsekas & Tsitsiklis, 1996) by combining Equation ( 1) and (3). In reinforcement learning, the precise model is usually assumed to be unknown. Learning typically interleaves policy evaluation and policy improvement, which is summarized as generalized policy iteration (Sutton & Barto, 2017) . 

3. ALTERNATING MARKOV GAMES:

Action-value functions can also be defined: q π1 (s, a) = s p(s |s, a)(r(s, a, s ) + γ a π 2 (a |s )q π2 (s , a )), s ∈ S 1 and s ∈ S 2 q π2 (s, a) = s p(s |s, a)(r(s, a, s ) + γ a π 1 (a |s )q π1 (s , a )), s ∈ S 2 and s ∈ S 1 (6)

Let π 1 be the max player and π 2 be the min player. Assuming the π 2 is an optimal "counter policy" with respect to π 1 , we may rewrite the above equation as:

q π1 (s, a) = s p(s |s, a) r(s, a, s ) + γ min a s p(s |s , a ) r(s , a , s ) + a π 1 (a |s )q π1 (s , a ) ,

where s ∈ S 1 , s ∈ S 2 and s ∈ S 1 .

The replacement of π 2 with a min operator is caused by the observation that, since π 1 is fixed, the problem reduces to a single-agent MDP where an agent tries to minimize the recevied rewards.

The optimal Bellman equation (also implies Nash equilibrium) can be expressed as: v * (s) = max a s p(s |s, a)(r(s, a, s ) + γv * (s )), s ∈ S 1 and s ∈ S 2 , v * (s) = min a s p(s |s, a)(r(s, a, s ) + γv * (s )), s ∈ S 2 and s ∈ S 1 ,

assuming that states in S 1 belongs to the max player, the other one is the min player. A value iteration algorithm according to this minimax recursion converges to optimal (Condon, 1992) . However, because the policy evaluation in AMGs consists of two policies π 1 , π 2 , the policy iteration, which alternates between policy evaluation and policy improvement, could have the following four formats:

Algo.1 Fix π t 1 , compute the optimal counter policy π t 2 , then fix π t 2 , compute the optimal counter policy π t+1 1 , alternating this procedure repeatedly, Algo.2 Policy evaluation with π t 1 , π t 2 , switch both π t 1 and π t 2 to greedy policies with respect to current state-value function, continue this procedure repeatedly, Algo.3 Policy evaluation with π t 1 , π t 2 , switch π t 1 to greedy policy with respect to the current statevalue function and then compute the optimal counter policy for π t 2 , continue this procedure repeatedly, Algo.4 Policy evaluation with π t 1 , π t 2 , switch π t 2 to greedy policy with respect to the current statevalue function and then compute the optimal counter policy for π t 1 , continue this procedure repeatedly.

Intuitively speaking, all of those procedures are somewhat sensible, and perhaps would yield practical success. However, Condon (1990) showed that oscillation could be a problem that prevents Algo.1 and Algo.2 from converging, only Algo.3 and Algo.4 are correct, guaranteed to converge in general (Hoffman & Karp, 1966) . Algo.3 and Algo.4 are duals. Variants of Algo.3 or Algo.4, such as only switching one node to greedy every iteration then optimize the other player's strategy, are also correct, although they may have slower convergence rate (Condon, 1990) .

4. ADVERSARIAL POLICY GRADIENT:

We first review policy gradient in single agent MDP. In MDP, the strength of a policy π can be measured by (for brevity, we implicitly state that the policy is parameterized by θ):

EQUATION

where d π (s) is a state distribution under π. The gradient of J(π) is:

EQUATION

The above formula is the Policy Gradient Theorem in MDP (Sutton et al., 2000) , which implies that the gradient of the strength of a policy can be estimated by sampling according to π. The requirements are 1) π is differentiable, and 2) q π (s, a) can be estimated. This theorem can also be interpreted as a kind of generalized policy iteration, where the gradient ascent corresponds to policy improvement (Kakade, 2002) , and q π (s, a) is obtained by some policy evaluation. Depending on how q π (s, a) is estimated, policy gradient algorithms can be categorized into two families: Monte carlo policy gradients that use Monte carlo to estimate q π , e.g., REINFORCE (Williams, 1992) and actor-critic methods (Sutton et al., 2000; Wang et al., 2017) that use another parameter to approximate the action-value under π. Recent approaches (Gu et al., 2017) interpolate both.

Analogously, in AMGs, the joint strength for a pair of parameterized policies π 1 and π 2 may be defined as:

EQUATION

where d π1,π2 (s) is the state-distribution given π 1 and π 2 . A natural question is what is the gradient of J(π 1 , π 2 ) with respect to π 1 and π 2 respectively? One tempting derivation is to calculate the the gradient for both π 1 and π 2 simultaneously by treating the other policy as the "environment". Similar to the mutual greedy improvement in Algo.2, such a method tries to adapt based on the value function under current π 1 , π 2 , ignoring the fact that the opponent is a dynamic adversary who will also adapt its strategy for better counter-payoffs. Another possible algorithm is to fix π 1 and do a fix number of iterations to optimize π 2 by normal policy gradient as in MDP, and then fix π 2 for optimizing π 1 , repeat such alternatively. However, this algorithm is an analog to Algo.1, which was shown to be non-convergent in general.

Following Algo.3 and Algo.4, given the action-value function under π 1 , π 2 , a more reasonable approach for policy improvement is thus to switch π 2 to "greedy" (not necessary every node of π 2 ) and optimize π 1 by policy gradient. Therefore, assuming π 1 is the max player, we advocate the following objectives

EQUATION

Consequently, the gradients can be estimated by

EQUATION

)

The above formulation implies that, when computing the gradient for one policy, the other policy is simultaneously switched to "greedy". This joint-change forces the current player to adjust the action preferences according to the worst-case response of the opponent, which is desirable due to the adversarial nature of the game.

4.1. ADVERSARIAL MONTE CARLO POLICY GRADIENT:

A straightforward implementation of Equation ( 12) is to obtain separate Monte carlo estimates for each next-action, and then apply the min or max operator. However, this may not be practically feasible when the action space is large. We introduce a parameter k, by which only a subset of actions are considered in our adversarial Monte-Carlo policy gradient design.

As a minimal modification on self-play REINFORCE, the algorithm works as follows: after a batch of n games is generated by a self-play policy with game results, for each game, a single stateaction pair (s, a) is sampled uniformly as a training example. However, instead of directly using the observed return z in batch as the estimated action-value for (s, a), we perform extra Monte carlo simulations to estimate the minimum return for (s, a). In below are two methods we propose:

AMCPG-A: Run k self-play games from (s, a) using self-play policy π, then take the minimum of the k additional returns and z. AMCGP-B: Sample a s from (s, a) according to state-action transition p(•|s, a), select top k actions suggested by π, for each selected action, obtain an Monte carlo estimate using self-play policy π, then take the minimum of the k additional returns and z.

Note that only "minimum" is used, because we assume the game result is with respect to the player to play at state s. It is easy to see that in AMCPG-A, if mean operator is used rather than minimum, a self-play REINFORCE variant is recovered. When k = |A(s )|, AMCPG-B becomes a genuine implementation of Equation ( 12), but in this situation, even though each action-value's estimation is unbiased, bias could still be incurred when applying the min or max. This is known as the "winner's curse" problem (Capen et al., 1971; Smith & Winkler, 2006) .

We note that, as in MDPs, another possible direction is to implement Equation ( 12) in an adversarial actor-critic framework. The difference is that a min operator will be used when estimating the "critic". In practice, when neural net is used as a function approximator, the minimum action-value would be easier to obtain by employing an architecture with both policy and action-value outputs. More desirably, as in Q-learning (Fox et al., 2016) , bias might be alleviated by certain soft min operators.

5. RELATED WORK:

Games are studied by different disciplines, including game theory, reinforcement learning and computational complexity. Shapley (1953) introduced the notion of Stochastic Games, which is a multiplayer framework that generalizes both Markov Decision Process (only one player) and repeated games (only one state). Condon (1990; 1992) initiated the study of Simple Stochastic Games, which are two-player games played on a directed graph with min, max and restricted probabilistic transition nodes. While her concern was largely from a computational complexity perspective, Condon (1990) showed that several variants of Hoffman-Karp's algorithms are incorrect. Littman (1996) formulated the notion of Alternating Markov Games, which is more general than Simple Stochastic Games by removing the restriction in action sets and probabilistic transitions. Littman (1994) proposed a minimax-Q learning algorithm that is applicable to Alternating Markov Games as well as two-player zero-sum games played with matrix payoffs.

One of the most noticeable study that uses reinforcement learning to play AMGs is by Tesauro (1995) , who trained multi-layer neural network to play backgammon. Tesauro's program takes advantage of the symmetric (due to alternating and zero-sum) property of AMGs and learns the optimal value function by "greedy" self-play, relying on the stochastic environment for exploration. It was conjectured that the smoothness of the value function is one major factor for the particular success of TD-Gammon (Tesauro, 1995) .

The recent advances of reinforcement learning are arguably primarily due to the use of deep neural networks (LeCun et al., 2015) as a much more expressive function approximator. Deep neural nets have been applied the game of Go (Maddison et al., 2015; Tian & Zhu, 2016; Clark & Storkey, 2015) , leading to super-human Go-playing system AlphaGo (Silver et al., 2016) . AlphaGo consists of several components including supervised learning for move prediction, reinforcement learning and Monte Carlo Tree Search (MCTS) (Coulom, 2006) . Most recent AlphaGo Zero uses a "heavy" self-play based on MCTS to improve its parameterized neural net (Silver et al., 2017b) . A similar approach is Expert Iteration (Anthony et al., 2017) . One drawback of such methods is their huge computational cost when using MCTS self-play for data generation. For example, when applied to Shogi and chess, 5000 TPUs were used (Silver et al., 2017a) .

Policy gradient reinforcement learning is a conventional fast RL method that can be used to refined a neural net policy by pure neural net self-play. In AlphaGo (Silver et al., 2016) , policy gradient RL is used to improve the neural network model obtained by supervised learning. The improved model was less useful in search, much because its strong bias towards a single move. However, due to its better playing strength and fast speed, it was used to generate training data for a value net (Silver et al., 2016) , which can be integrated into Monte carlo tree search. The policy gradient employed by AlphaGo is a variant of self-play REINFORCE that resembles Algo.2. A practical innovation is to select an opponent from a pool of previous parameters, so as to increase the stability of the training. Policy gradient has also been applied to train a balanced policy (Silver & Tesauro, 2009) ; however, the requirement of an optimal supervision makes it less useful in practice (Huang et al., 2010) .

Adversarial methods have also been adopted in MDP (Pinto et al., 2017) , since errors may occur in simulated models, maximizing a worst-case return will generally produce more robust results. The alternating procedure proposed by Pinto et al. (2017) resembles Algo.1. The idea of adversarial learning is also used in generative models (Goodfellow et al., 2014) , which leverage adversarial examples to train a more robust classifier.

6. EXPERIMENTS:

In this section, we present experimental results of the proposed adversarial Monte carlo policy gradient algorithms of Section 4. We first introduce the game of Hex as a testbed, then present experimental results.

6.1. GAME OF HEX:

The game of Hex is played on a N × N rhombus board, where black and white alternately place a stone on an unoccupied hexagonal cell. The goal is to connect two opposite sides of the board. Since its invention, the game of Hex has been an active research problem for mathematicians (Nash, 1952) and computer scientists (Shannon, 1953) . Nash (1952) proved by strategy stealing argument that from the empty board, the game theoretic value is a first-player win. However, an explicit winning strategy is unclear -after an arbitrary opening move on the board, the theoretical result become unknown. Hex board can also be mapped into a Go-style grid, on which stones are played at intersections, as shown in Figure 1 (left). Usually 11×11 is considered as a regular board size; 13×13 is also played at computer Olympiad Hex tournaments.

(a) A regular Hex board in Go-style representation. Stones are played at intersections. A player wins by connecting their two sides by a group of their stones.

raw input, boardsize × boardsize

(boardsize + 2 ) × (boardsize + 2 ) × 12

. . . Hex is challenging to play primarily because of its large and near-uniform branching factor and the difficulty of constructing a reliable evaluation function. One character that makes Hex simpler is that perfect play can sometimes be achieved whenever winning virtual connections are found by H-Search (Anshelevich, 2002) .

Similar to the previous work in Go, we use deep convolutional neural networks as a function approximator. Figure 1 (right) shows our architecture. Instead of fixing the board size, we design an architecture that receives multiple board size inputs. This can be achieved by having multiple parallel inputs with different shape when building the computation graph using Tensorflow (Abadi et al., 2016) . Our architecture allows board sizes 8 ≤ N ≤ 15. After padding, each raw board state is processed into 12 binary feature planes, which are: black stones, white stones, empty points, to-play, black bridge endpoints, white bridge endpoints, to-play save bridge points, to-play makeconnection points, to-play form bridge points, opponent save bridge points, opponent form bridge points, opponent make-connection points.

6.2 RESULTS

6.2.1. PURE NEURAL NET POLICY GRADIENT:

We apply policy gradient reinforcement learning to improve a policy net which was trained by supervised learning. In addition to our proposed adversarial Monte carlo policy gradient algorithms, for comparison purposes, we implement three REINFORCE variants:

• REINFORCE-V: Vanilla REINFORCE using a parameterized self-play policy. After a batch of n self-played games, each game is then replayed to determine batch policy gradient update α n n i Ti t ∇ log π(s i t , a i t ; θ)z i t , where z i t is either +1 or -1. • REINFORCE-A: An "AlphaGo-like" REINFORCE. It differs from REINFORCE-V by randomly selecting a set of previously saved parameter weights from former iterations as the opponent for self-play. • REINFORCE-B: For each self-played game, only one state-action pair is uniformly selected for policy gradient update. It differs from AMCPG-A by using the mean of all k + 1 observed returns.

All methods are implemented using Tensorflow, sharing the same code base. They only differ in a few lines of code. A self-play policy is employed for all algorithms, which is equivalent to forcing π 1 and π 2 to share the same set of parameters. The game batch size n is set to 128. For each selfplay game, the opening move is played uniform randomly. Learning rate is set to 0.001 after a grid search, vanilla stochastic gradient ascent is used as the optimizer. The reward signal z ∈ {+1, -1} only appears after a complete self-play game; no discounting is used. For all algorithms, the same neural net architecture is adopted. The initial parameter weights were obtained from supervised learning on a dataset generated by MoHex (Henderson, 2010) self-play on board size 9 × 9. This supervised learning is only on 9×9 Hex. Because there is no board-size dependent fully connected layers in our architecture, the parameter weights can be reused on other board sizes as the starting policy.

We run policy gradient reinforcement learning for 400 iterations for each method, on two different board sizes, 9 × 9 and 11 × 11, varying k ∈ {1, 3, 6, 9}. We use the improved Wolve (Henderson, 2010; Pawlewicz et al., 2015) as a benchmark to measure the relative performance of our learned models. After every 10 iterations, model weights are saved and then evaluated by playing against 1-ply Wolve. The primary strength of Wolve comes from its inferior cell analysis augmented H-Search, enabling it to discover winning strategies for perfect play much earlier than unenhanced H-Search. Wolve uses position evaluation with electric resistance evaluation (Anshelevich, 2002; Henderson, 2010; Pawlewicz et al., 2015) if no winning virtual connection can be found. Starting from trivial virtual connections (e.g., bridge pattern), H-Search (Anshelevich, 2002) computes larger virtual connections by iteratively applying an AND-OR combination rule, such a process is orders of magnitude slower than a pure neural net evaluation using GPU. The tournaments with Wolve are played by iterating all opening moves, each repeated 5 times with Wolve as black or white. former algorithm is significantly less. This is perhaps because the reward signal in the same game is too much correlated. Consistent with the finding in Go (Silver et al., 2016) , REINFORCE-A obtained small performance improvements on both 9 × 9 and 11 × 11 Hex. However, the newly developed algorithms AMCPG-A and AMCPG-B are able to learn better polices. They tend to learn faster, and generally achieve better results even when k = 1. The better performances are more clear on regular board size 11 × 11. Those results confirm the benefit of estimating the minimum, rather than mean return, when applying policy gradient methods to Alternating Markov

The policy gradient training on both 9×9 and 11×11 Hex is very fast. On an Intel i7-6700 CPU computer with single GTX 1080 GPU, most took only a few hours. The longest training runs by AMCPG-A, AMCPG-B and REINFORCE-B (k = 9, 11×11 Hex) took about 12 hours. For k = 3 case, AMCPG-A, AMCPG-B and REINFORCE-B are about twice slower than REINFORCE-V and REINFORCE-A.

6.2.2. COMBINE NEURAL NET WITH MCTS FOR MULTIPLE BOARD SIZE HEX:

Unlike previous work in Go (Silver et al., 2017b) or Hex (Anthony et al., 2017) , the neural net we proposed has no board size dependent fully connected layers. This makes it possible to easily reuse the trained neural network on board sizes other than 9 × 9. To see the generalization ability across different board sizes in search, we incorporate the trained neural net to MoHex 2.0, the resulting program is MoHex-CNN 9 , where we use subscript to reflect the nature that the CNN was optimized on 9×9 games and to distinguish it from another recently available player (Gao et al., 2017) . The difference between MoHex-CNN 9 and MoHex 2.0 is that it replaces the prior probability of MoHex 2.0 with the policy neural net trained on 9 × 9 Hex games, i.e., the neural net model before policy gradient learning. Table 1 shows the winrates of MoHex-CNN 9 on board sizes from 9×9 to 13×13. We note that board sizes smaller than 9 are not investigated because they can easily be solved by virtual connection computation or tree based proof number search (Henderson, 2010) . MoHex 2.0 was not designed to play board size > 13, so we stop at board size 13. MoHex-CNN 9 defeats MoHex 2.0 on every board size, which is remarkable since the neural net model was only trained on 9×9 Hex games for a few hours on a single GPU. The computation overhead is not significantly big, because in our implementation, neural net evaluation is computed in parallel with prior pruning1 when expanding a node. We note that when giving the same computation time per move, MoHex-CNN 9 could still beat MoHex 2.0, detailed results are shown in Appendix. (Hayward et al., 2012) .

We further note that, the state-of-art for 9×9 Hex is that all openings have been solved (Pawlewicz & Hayward, 2013) 4 . This parallel solver has been embedded into MoHex 2.0, but in default setting, it is turned off.

7. CONCLUSIONS:

We reviewed MDP and AMG, and proposed a new adversarial policy gradient paradigm that uses the worst-case return as the "critic". We introduced two practical adversarial Monte carlo policy gradient methods. We evaluated our algorithms on game of Hex, the experimental comparisons show that the new algorithms are notably better than routinely adopted self-play REINFORCE variants. We also applied minimum return to Monte carlo tree search, and observed better performance on 13×13 Hex. Another contribution we made is a multi-boardsize neural net architecture, we demonstrated that a single neural net model trained on smaller board size can effectively generalize to larger board sizes. As a result, using it as a prior knowledge, we are able to improve MoHex 2.0 consistently from 9×9 to 13×13 Hex. Since in practice, expert data is often scarce, difficult to generate with limited computation resources, in this paper we provided a more feasible approach for high-performance playing for multi-boardsize Hex.

On the other hand, based on the adversarial policy gradient formulation in AMGs, the Monte carlo policy gradients, either self-play REINFORCE-V or others, are not unbiased anymore, yet still have the drawback of being sample-inefficient, and may exhibit high variance. In this sense, an adversarial actor-critic framework is perhaps more appealing. As expected, the results show that on smaller board size like 9 × 9, due to the DFPN solver in both players, there is a significant decrease of MoHex-CNN 9 's winrate. However, on larger board sizes, the influence of DFPN solver is small. We note that, in (Anthony et al., 2017) , on 9×9 board size, ExIt's winrate against 4s-MoHex2011 with DFPN solver is 55.6%. MoHex 2.0's solver is also stronger than MoHex 2011 due to improved virtual connections (Pawlewicz et al., 2015) .

:

Used by MoHex to prune proven inferior nodes whenever expanding a node

In(Huang et al., 2013), MoHex 2.0 has been demonstrated to be stronger than MoHex 2011 on 11×11 and 13×13 Hex, but playing results on 9×9 board size were never presented.

Under this similar setting, MoHex 2.0 won about 56% against MoHex 2011, although with several times less time consumption.

The solver shows that among all 81 openings on 9×9 board,

are first player win.

Figures and Tables:

Neural network architecture: It accepts different board size inputs, padded with an extra border using black or white stones.

Figure 1: Hex board (left) and neural network design (right)

Figure2compares the strength of these five different algorithms. REINFORCE-B is able to achieve similar performance with REINFORCE-V, even though the number of training samples used in the

Alternating Markov Games (AMG) are a specialization of Stochastic Games with only two players: an AMG is a tuple (S 1 , S 2 , A 1 , A 2 , R, P, γ) where S 1 and S 2 are respectively this and other agent's states, A 1 and A 2 are the actions at each player's states. MDPs can be viewed as a special case of AMGs by restricting |S 2 | = 0.

Table content: <table><tr><td>Since there are two players in AMGs, policy evaluation involves two policies, i.e., π 1 and π 2 . Bell-</td></tr><tr><td>man equations for policy evaluation are:</td></tr><tr><td>v π1 (s) = a π 1 (a|s) s p(s |s, a)(r(s, a, s ) + γv π2 (s )), s ∈ S 1 and s ∈ S 2 v π2 (s) = a π 2 (a|s) s p(s |s, a)(r(s, a, s ) + γv π1 (s )), s ∈ S 2 and s ∈ S 1</td></tr></table>

Winrates of MoHex-CNN 9 against MoHex 2.0 with same number of simulations. All programs use the same default parameters as MoHex 2.0. Every opening was tried twice with each player as black or white. Column 6 and 7 are respectively the average consumed time per game for each corresponding program.

Table content: <table><tr><td>Player</td><td>#Simulations</td><td>MoHex2.0</td><td>MoHex2.0</td><td>Overall</td><td>Average time</td><td>Average time of</td><td>Board size</td></tr><tr><td/><td/><td>was white</td><td>was black</td><td>winrate</td><td>of MoHex-2.0</td><td>MoHex-CNN</td><td/></tr><tr><td>MoHex-CNN9</td><td>10 4</td><td>77.8%</td><td>59.3%</td><td>68.5%</td><td>4.5</td><td>6.8</td><td>9×9</td></tr><tr><td>MoHex-CNN9</td><td>10 4</td><td>83%</td><td>58.0%</td><td>70.5%</td><td>12.3</td><td>17.1</td><td>10×10</td></tr><tr><td>MoHex-CNN9</td><td>10 4</td><td>75.2%</td><td>48.8%</td><td>62.0%</td><td>13.4</td><td>18.2</td><td>11×11</td></tr><tr><td>MoHex-CNN9</td><td>10 4</td><td>78.5%</td><td>55.6%</td><td>67%</td><td>29.4</td><td>36.0</td><td>12×12</td></tr><tr><td>MoHex-CNN9</td><td>10 4</td><td>69.8%</td><td>45.6%</td><td>57.7%</td><td>41.7</td><td>49.9</td><td>13×13</td></tr></table>

CNN 9 played against MoHex 2011 on 9×9 Hex 2 . We show the results with 10 4 and 10 5 simulations in Table2. It should be noted that MoHex 2011 uses an expansion threshold of 1, while MoHex 2.0 and MoHex-CNN 9 adopt a threshold of 10, so when the same number of simulations are given, MoHex 2.0 and MoHex-CNN 9 expands much fewer nodes than MoHex 2011. Results of ExIt, MoHex 2.0 and MoHex-CNN 9 against MoHex 2011 on 9 × 9 Hex. All MoHex programs use the same default parameters, with 10 4 simulations (left) or 10 5 simulations (right). Every opening was tried twice with each player as black or white. ExIt used 10 4 simulations(Anthony et al., 2017). simulations is used, both MoHex 2.0 and MoHex-CNN 9 has similar winrates as ExIt. However, the 10 5 simulations MoHex 2.0 and MoHex-CNN 9 obtain much better winrates than 59.3%. Since ExIt was sticking on 10 4 simulations, we conduct another experiments that use 10 4 simulations MoHex-CNN 9 compete against MoHex 2011, in which setting, MoHex-CNN 9 won 62.3%, still better than ExIt, though MoHex-CNN 9 's node expansion is significantly less than that of MoHex 2011 and ExIt due to expansion threshold of 10 3 . Indeed, as shown in Table1, MoHex 2.0 and MoHex-CNN 9 consumes around 5s per game on 9×9 board size, indicating that with 10 4 simulations per move they are playing super fast games. MoHex 2011's worse performance is not a surprise, under default settings, MoHex 2011 is even slighter weaker than Wolve

Table content: <table><tr><td>6.2.3 COMPARISON WITH EXIT</td></tr><tr><td>ExIt competed against MoHex 2011 (Arneson et al., 2010) on 9×9 Hex. To have a grasp of the</td></tr><tr><td>relative strengths of ExIt, MoHex 2011, MoHex 2.0 and MoHex-CNN 9 , we present results of Mo-</td></tr><tr><td>Hex 2.0 and MoHex-</td></tr></table>

WITH THE SAME COMPUTATION TIME AND DFPN SOLVER TURNED ONIn computer Hex Olympiad tournament, MoHex is usually played with the parallel solver turned on. To demonstrate the full strength of MoHex-CNN 9 compared to MoHex 2.0, we perform another experiments by limiting both programs with the same thinking time 5s per move, all with the DFPN solver turned on. Winrates of MoHex-CNN 9 against Mohex 2.0 with the same time per move. All programs use the default parameters the same as MoHex 2.0 with parallel solver on. Every opening was tried twice with each player as black or white.

Table content: <table><tr><td>6 7</td><td colspan="2">π t 1 ← π 0 1 ; stable ← f alse; while not stable do</td></tr><tr><td>8</td><td>Fix π t 1 ;</td><td/></tr><tr><td>9</td><td colspan="3">Compute the optimal counter strategy for player 2 given player 1's stragy is fixed;</td></tr><tr><td>10 11</td><td colspan="3">Let π t 2 be the computed optimal counter strategy; Fix π t 2 ;</td></tr><tr><td>12</td><td colspan="3">Compute the optimal counter strategy for player 1 given player 2's strateg is fixed;</td></tr><tr><td>13 14 15 16</td><td colspan="3">Let π t+1 1 t ← t + 1; be the computed optimal counter strategy; if π t-1 1 = π t 1 and π t-2 2 = π t-1 then 2 stable ← true;</td></tr><tr><td>20</td><td colspan="2">Initialize π 0 1 , π 0 2 arbitrarily;</td></tr><tr><td>29 30</td><td colspan="2">if π t 1 = π t-1 1 stable ← true; and π t 2 = π t-1 2</td><td>then</td></tr><tr><td>34 35 36 37</td><td colspan="2">Initialize π 0 1 , π 0 2 arbitrarily; t ← 0; stable ← f alse; while not stable do</td></tr><tr><td>38 39</td><td colspan="3">Fix π t 1 , π t 2 ; Compute the value function V t under π t 1 , π t 2 by policy evaluation;</td></tr><tr><td>40</td><td>Let π t+1 1</td><td colspan="2">be the greedily (max) modified policy w.r.t V t ;</td></tr></table>

Peer review (iclr2018):
 The paper makes the simple but important observation that (deep) reinforcement learning in alternating Markov games requires a min-max formulation of the Bellman equation as well as careful attention to the way in which one alternates solving for both players* policies in a policy iteration setting. While some of the core algorithmic insights regarding Algorithms 3 & 4 in the paper stem from previous work (Condon, 1990; Hoffman & Karp, 1966), I was not actually aware of these previous results until I reviewed this paper. A nice corollary of Algorithms 3 & 4 is that they make for a straightforward adaptation of policy gradient algorithms since when optimizing one policy, the other is fixed to the greedy policy. In general, it would be nice to have the algorithms specified as formal algorithms as opposed to text-based outlines. I found myself reading and re-reading descriptions to make sure I understood what math was being implied by the descriptions. Section 6 > Hex is simpler than Go in the sense that perfect play can > often be achieved whenever virtual connections are found > by H-Search It is not clear here what virtual connections are, what H-Search is, and how these imply perfect play, if perfect play as previously discussed is unknown. Overall, the results on Hex for AMCPG-A and AMCPG-B vs. standard REINFORCE variants currently used are very encouraging. That said, empirically it is always a question of whether these results are specific to Hex. Because this paper is not proposing the best Hex player (i.e., the winning rate against Wolve never exceeds 0.5), I think it is quite reasonable to request the authors to compare AMCPG-A and AMCPG-B to standard REINFORCE variants on other games (they do not need to be as difficult as Hex). Finally, assuming that the results do generalize to other games, I am left wondering about the significance of the contribution. On one hand, the authors have introduced me to literature I was not aware of, but on the other hand, their actual novel contribution is a rather straightforward adaptation of ideas in the literature to policy gradients (that could be formalized in a more technically precise way) with an evaluation on a single type of game. This is a useful contribution no doubt, but I am concerned with whether it meets the significance level that I am used to with accepted ICLR papers in previous years.