# Variational Attention for Sequence-to-Sequence Models

Hareesh Bahuleyan 22footnotemark: 2 Lili Mou111This work is licensed under a
Creative Commons Attribution 4.0 International License. License details:
http://creativecommons.org/licenses/by/4.0/ 33footnotemark: 3 Olga
Vechtomova22footnotemark: 2 Pascal Poupart22footnotemark: 2
22footnotemark: 2 University of Waterloo, Canada
{hpallika, ovechtomova<EMAIL_ADDRESS>
33footnotemark: 3 AdeptMind Research, Toronto, Canada
<EMAIL_ADDRESS>
The first two authors contributed equally.

###### Abstract

The variational encoder-decoder (VED) encodes source information as a set of
random variables using a neural network, which in turn is decoded into target
data using another neural network. In natural language processing, sequence-
to-sequence (Seq2Seq) models typically serve as encoder-decoder networks. When
combined with a traditional (deterministic) attention mechanism, the
variational latent space may be bypassed by the attention model, and thus
becomes ineffective. In this paper, we propose a variational attention
mechanism for VED, where the attention vector is also modeled as Gaussian
distributed random variables. Results on two experiments show that, without
loss of quality, our proposed method alleviates the bypassing phenomenon as it
increases the diversity of generated sentences.111Code is available at
https://github.com/HareeshBahuleyan/tf-var-attention

##  1 Introduction

The variational autoencoder (VAE), proposed by ?), encodes data to latent
(random) variables, and then decodes the latent variables to reconstruct the
input data. Theoretically, it optimizes a variational lower bound of the log-
likelihood of the data. Compared with traditional variational methods such as
mean-field approximation [Wainwright et al., 2008], VAE leverages modern
neural networks and hence is a more powerful density estimator. Compared with
traditional autoencoders [Hinton and Salakhutdinov, 2006], which are
deterministic, VAE populates hidden representations to a region (instead of a
single point), making it possible to generate diversified data from the vector
space [Bowman et al., 2016] or even control the generated samples [Hu et al.,
2017].

In natural language processing (NLP), recurrent neural networks (RNNs) are
typically used as both the encoder and decoder, known as a sequence-to-
sequence (Seq2Seq) model. Although variational Seq2Seq models are much
trickier to train in comparison to the image domain, ?) succeed in training a
sequence-to-sequence VAE and generating sentences from a continuous latent
space. Such an architecture can further be extended to a variational encoder-
decoder (VED) to transform one sequence into another with the “variational”
property [Serban et al., 2017, Zhou and Neubig, 2017].

When applying attention mechanisms [Bahdanau et al., 2015] to variational
Seq2Seq models, however, we find the generated sentences are of less variety,
implying that the variational latent space is ineffective. The attention
mechanism summarizes source information as an attention vector by weighted
sum, where the weights are a learned probabilistic distribution; then the
attention vector is fed to the decoder. Evidence shows that attention
significantly improves Seq2Seq performance in translation [Bahdanau et al.,
2015], summarization [Rush et al., 2015], etc. In variational Seq2Seq,
however, the attention mechanism unfortunately serves as a “bypassing”
mechanism. In other words, the variational latent space does not need to learn
much, as long as the attention mechanism itself is powerful enough to capture
source information.

In this paper, we propose a variational attention mechanism to address this
problem. We model the attention vector as random variables by imposing a
probabilistic distribution. We follow traditional VAE and model the prior of
the attention vector by a Gaussian distribution, for which we further propose
two plausible priors, whose mean is either a zero vector or an average of
source hidden states.

We evaluate our approach on two experiments: question generation and dialog
systems. Experiments show that the proposed variational attention yields a
higher diversity than variational Seq2Seq with deterministic attention, while
retaining high quality of generated sentences. In this way, we make VED work
properly with the powerful attention mechanism.

In summary, the main contributions of this paper are two-fold: (1) We discover
a “bypassing” phenomenon in VED, which could make the learning of variational
space ineffective. (2) We propose a variational attention mechanism that
models the attention vector as random variables to alleviate the above
problem. To the best of our knowledge, we are the first to address the
attention mechanism in variational encoder-decoder neural networks. Our model
is a general framework, which can be applied for various text generation
tasks.

##  2 Background and Motivation

In this section, we introduce the variational autoencoder and the attention
mechanism. We also present a pilot experiment motivating our variational
attention model.

###  2.1 Variational Autoencoder (VAE)

A VAE encodes data $\bm{Y}$ (e.g., a sentence) as hidden random variables
$\bm{Z}$, based on which the decoder reconstructs $\bm{Y}$. Consider a
generative model, parameterized by $\bm{\theta}$, as

$p_{\bm{\theta}}(\bm{Z},\bm{Y})=p_{\bm{\theta}}(\bm{Z})p_{\bm{\theta}}(\bm{Y}|\bm{Z})$
(1)

Given a dataset $\mathcal{D}=\\{\bm{y}^{(n)}\\}_{n=1}^{N}$, the likelihood of
a data point is

$\displaystyle\log p_{\bm{\theta}}(\bm{y}^{(n)})\geq\begin{aligned}
&\mathbb{E}_{\bm{z}\sim
q_{\bm{\phi}}(\bm{z}|\bm{y}^{(n)})}\left[\log\left\\{\dfrac{p_{\bm{\theta}}(\bm{y}^{(n)},\bm{z})}{q_{\bm{\phi}}(\bm{z}|\bm{y}^{(n)})}\right\\}\right]\\\
\end{aligned}$ $\displaystyle=\begin{aligned} &\mathbb{E}_{\bm{z}\sim
q_{\bm{\phi}}(\bm{z}|\bm{y}^{(n)})}\left[\log
p_{\bm{\theta}}(\bm{y}^{(n)}|\bm{z})\right]-{\operatorname{KL}}\left(q_{\bm{\phi}}(\bm{z}|\bm{y}^{(n)})\|p(\bm{z})\right)\overset{\Delta}{=}\mathcal{L}^{(n)}({\bm{\theta}},{\bm{\phi}})\end{aligned}$
(2)

VAE models both $q_{\bm{\phi}}(\bm{z}|\bm{y})$ and
$p_{\bm{\theta}}(\bm{y}|\bm{z})$ with neural networks, parametrized by
${\bm{\phi}}$ and ${\bm{\theta}}$, respectively. Figure 1a shows the graphical
model of this process. The training objective is to maximize the lower bound
of the likelihood $\mathcal{L}({\bm{\theta}},{\bm{\phi}})$, which can be
rewritten as minimizing

$\displaystyle
J^{(n)}=J_{\text{rec}}({\bm{\theta}},{\bm{\phi}},\bm{y}^{(n)})+{\operatorname{KL}}\\!\left(\\!q_{\bm{\phi}}(\bm{z}|\bm{y}^{(n)})\|p(\bm{z})\\!\right)$
(3)

The first term, called reconstruction loss, is the (expected) negative log-
likelihood of data, similar to traditional deterministic autoencoders. The
expectation is obtained by Monte Carlo sampling. The second term is the KL-
divergence between $\bm{z}$’s posterior and prior distributions. Typically the
prior is set to standard normal $\mathcal{N}(\bm{0},\mathbf{I})$.

###  2.2 Variational Encoder-Decoder (VED)

In some applications, we would like to transform source information to target
information, e.g., machine translation, dialogue systems, and text
summarization. In these tasks, “auto”-encoding is not sufficient, and an
encoding-decoding framework is required. Different efforts have been made to
extend VAE to variational encoder-decoder (VED) frameworks, which transform an
input $\bm{X}$ to output $\bm{Y}$. One possible extension is to condition all
probabilistic distributions further on $\bm{X}$ [Zhang et al., 2016, Cao and
Clark, 2017, Serban et al., 2017]. In this case, the posterior of $\bm{z}$ is
given by $q_{\bm{\phi}}(\bm{z}|\bm{X},\bm{Y})$. This, however, introduces a
discrepancy between training and prediction, since $\bm{Y}$ is not available
during the prediction stage.

Figure 1: Graphical model representations. (a) Variational autoencoder (VAE).
(b) Variational encoder-decoder (VED). (c) VED with deterministic attention
(VED+DAttn). (d) VED with variational attention (VED+VAttn). Dashed lines:
Encoding phase. Solid lines: Decoding phase.

Another approach is to build a recognition model using only $\bm{X}$ [Zhou and
Neubig, 2017]. Making the assumption that $\bm{Y}$ is a function of $\bm{X}$,
i.e., $\bm{Y}=\bm{Y}(\bm{X})$, we have
$q_{\bm{\phi}}(\bm{z}|\bm{y})=q_{\bm{\phi}}(\bm{z}|\bm{Y}(\bm{x}))\overset{\Delta}{=}q_{\bm{\phi}}(\bm{z}|\bm{x})$.
In this work, we follow ?) and adopt this extension. Figure 1b shows the
graphical model of the VED used in our work.

###  2.3 Seq2Seq and Attention Mechanism

In NLP, sequence-to-sequence recurrent neural networks are typically used as
the encoder and decoder, as they are suitable for modeling a sequence of words
(i.e., sentence). Figure 2a shows a basic Seq2Seq model in the VAE/VED
scenario [Bowman et al., 2016]. The encoder has an input $\bm{x}$, and outputs
$\bm{\mu}_{z}$ and $\bm{\sigma}_{z}$ as the parameters of $\bm{z}$’s posterior
normal distribution. Then a decoder generates $\bm{y}$ based on a sample
$\bm{z}$, drawn from its posterior distribution.

Attention mechanisms are proposed to dynamically align
$\bm{y}=(y_{1},\cdots,y_{|\bm{y}|})$ and $\bm{x}=(x_{1},\cdots,x_{|\bm{x}|})$
during generation. At each time step $j$ in the decoder, the attention
mechanism computes a probabilistic distribution by

$\alpha_{ji}=\frac{\exp\\{\widetilde{\alpha}_{ji}\\}}{\sum_{i^{\prime}=1}^{|\bm{x}|}\exp\\{\widetilde{\alpha}_{ji^{\prime}}\\}}$
(4)

where $\widetilde{\alpha}_{ji}$ is a pre-normalized score, computed by
$\widetilde{\alpha}_{ji}=\bm{h}^{\text{(tar)}}_{j}W^{T}\bm{h}^{\text{(src)}}_{i}$
in our model. Here, $\bm{h}^{\text{(tar)}}_{j}$ and
$\bm{h}^{\text{(src)}}_{i}$ are the hidden representations of the $j$th step
in target and $i$th in the source, and $W$ is a learnable weight matrix.

Then the source information $\\{\bm{h}_{i}^{\text{(src)}}\\}_{i=1}^{|\bm{x}|}$
is summed by weights $\alpha_{ji}$ to obtain the attention vector

$\bm{a}_{j}=\sum_{i=1}^{|\bm{x}|}\alpha_{ji}\bm{h}^{\text{(src)}}_{i}$ (5)

which is fed to the decoder RNN at the $j$th step. Figure 2b shows the
variational Seq2Seq model with such traditional attention.

Input: the men are playing musical instruments
---
(a) VAE w/o hidden state init. (Avg entropy: 2.52) | (b) VAE w/ hidden state init. (Avg entropy: 2.01)
the men are playing musical instruments | the men are playing musical instruments
the men are playing video games | the men are playing musical instruments
the musicians are playing musical instruments | the men are playing musical instruments
the women are playing musical instruments | the man is playing musical instruments

Table 1: Sentences obtained by sampling from the VAE’s latent space. (a) VAE
without hidden state initialization. (b) VAE with hidden state initialization.

###  2.4 “Bypassing” Phenomenon

In this part, we explain the “bypassing” phenomenon in VAE/VED, if the network
is not designed properly; this motivates our variational attention described
in Section 3.

We observe that, if the decoder has a direct, deterministic access to the
source, the latent variables $\bm{Z}$ might not capture much information so
that the VAE or VED does not play a role in the process. We call this a
bypassing phenomenon.

Theoretically, if $p_{\bm{\theta}}(\bm{Y}|\cdot)$ is aware of $\bm{X}$ by
itself, i.e., $p_{\bm{\theta}}(\bm{Y}|\cdot)$ becomes
$p_{\bm{\theta}}(\bm{Y}|\bm{X},\bm{Z})$, it could be learned as
$p_{\bm{\theta}}(\bm{Y}|\bm{X})$ without hurting the reconstruction loss
$J_{\text{rec}}$, but the ${\operatorname{KL}}$ term in Eq. (3) can be
minimized by fitting the posterior to its prior. This degrades a variational
Seq2Seq model to a deterministic one.

The phenomenon can be best shown with a bypassing connection between the
encoder and decoder for hidden state initialization. Some previous studies
using VEDs set the decoder’s initial state to be the encoder’s final state
[Cao and Clark, 2017], shown in Figure 2c. We conducted a pilot study with a
Seq2Seq VAE with a subset ($\sim$80k samples) of the massive dataset provided
by ?), and show generated sentences and entropy in Table 1. We see that the
variational Seq2Seq can only generate very similar sentences with such
bypassing connections (Table 1b), as opposed to generating diversified samples
from the latent space (Table 1a). We also computed the entropy for 10 randomly
sampled outputs for a given input sentence. Quantitatively, the entropy
decreases by 0.5 on average for 1k unseen input sentences. This shows a
significant difference because entropy is a logarithmic metric. Our analysis
sheds light on the design philosophy of neural architectures in VAE or VED.

Since attention largely improves model performance for deterministic Seq2Seq
models, it is tempting to include attention in the variational Seq2Seq as
well. However, our pilot experiment raises the doubt if a traditional
attention mechanism, which is deterministic, may bypass the latent space in
VED, as illustrated by a graphical model in Figure 1c. Also, evidence in ?)
shows the attention mechanism is so powerful that removing other connections
between the encoder and decoder has little effect on BLEU scores in machine
translation. Therefore, a VED with deterministic attention might learn
reconstruction mostly from attention, whereas the posterior of the latent
space can fit to its prior in order to minimize the ${\operatorname{KL}}$
term.

To alleviate this problem, we propose a variational attention mechanism for
variational Seq2Seq models, as is described in detail in the next section.

##  3 The Proposed Variational Attention

Figure 2: (a) Variational Seq2Seq model. (b) Variational Seq2Seq with
deterministic attention. (c) Variational Seq2Seq with hidden state
initialization. (d) Variational Seq2Seq with variational attention.

Let us consider the decoding process of an RNN. At each timestep $j$, it
adjusts its hidden state $\bm{h}^{\text{(tar)}}_{j}$ with an input of a word
embedding $\bm{y}_{j-1}$ (typically the groundtruth during training and the
prediction from the previous step during testing). This is given by
$\bm{h}^{\text{(tar)}}_{j}={\operatorname{RNN}}_{\bm{\theta}}(\bm{h}^{\text{(tar)}}_{j-1},\bm{y}_{j-1})$.
In our experiments, we use long short-term memory units [Hochreiter and
Schmidhuber, 1997] as RNN’s transition. Enhanced with attention, the RNN is
computed by
$\bm{h}^{\text{(tar)}}_{j}={\operatorname{RNN}}_{\bm{\theta}}(\bm{h}^{\text{(tar)}}_{j-1},[\bm{y}_{j-1};\bm{a}_{j}])$.
The predicted word is given by a softmax layer
$p(y_{j})=\operatorname{softmax}(W_{\text{out}}\bm{h}^{\text{(tar)}}_{j})$,
where $W_{\text{out}}$ is a weight matrix. As discussed earlier, traditional
attention computes $\bm{a}_{j}$ in a deterministic fashion by Eq. (5).

To build a variational attention, we treat both the traditional latent space
$\bm{z}$ and the attention vector $\bm{a}_{j}$ as random variables. The
recognition and reconstruction graphical models are shown in Figure 1d.

###  3.1 Lower Bound

Since the likelihood of the $n$th data point decomposes for different time
steps, we consider the lower bound
$\mathcal{L}_{j}^{(n)}({\bm{\theta}},{\bm{\phi}})$ at the $j$th step. The
variational lower bound in Eq. (2) becomes

$\displaystyle\mathcal{L}_{j}^{(n)}({\bm{\theta}},{\bm{\phi}})$
$\displaystyle=\begin{aligned} &\mathbb{E}_{\bm{z},\bm{a}\sim
q_{\bm{\phi}}(\bm{z},\bm{a}|\bm{x}^{(n)})}\left[\log
p_{\bm{\theta}}(\bm{y}^{(n)}|\bm{z},\bm{a})\right]-{\operatorname{KL}}\left(q_{\bm{\phi}}(\bm{z},\bm{a}|\bm{x}^{(n)})\|p(\bm{z},\bm{a})\right)\end{aligned}$
(6) $\displaystyle=\begin{aligned} &\mathbb{E}_{\bm{z}\sim
q^{(z)}_{\bm{\phi}}(\bm{z}|\bm{x}^{(n)}),\bm{a}\sim
q^{(a)}_{\bm{\phi}}(\bm{a}|\bm{x}^{(n)})}\left[\log
p_{\bm{\theta}}(\bm{y}^{(n)}|\bm{z},\bm{a})\right]\\\
&-{\operatorname{KL}}\left(q^{(z)}_{\bm{\phi}}(\bm{z}|\bm{x}^{(n)})\|p(\bm{z})\right)-{\operatorname{KL}}\left(q^{(a)}_{\bm{\phi}}(\bm{a}|\bm{x}^{(n)})\|p(\bm{a})\right)\end{aligned}$
(7)

Eq. (7) is due to the independence in both recognition and reconstruction
phrases. The posterior factorizes as
$q_{\phi}(\bm{z},\bm{a}|\cdot)=q_{\phi}^{(z)}(\bm{z}|\cdot)\
q_{\phi}^{(a)}(\bm{a}|\cdot)$ because $\bm{z}$ and $\bm{a}$ are conditionally
independent given $\bm{x}$ (dashed lines in Figure 1d), whereas the prior
factorizes because $\bm{z}$ and $\bm{a}$ are marginally independent (solid
lines in Figure 1d). In this way, the sampling procedure can be done
separately and the ${\operatorname{KL}}$ loss can also be computed
independently.

###  3.2 Prior

We propose two plausible prior distributions for $\bm{a}_{j}$.

  * •

The simplest prior, perhaps, is the standard normal, i.e.,
$p(\bm{a}_{j})=\mathcal{N}(\bm{0},\mathbf{I})$. This follows the prior of the
latent space $\bm{z}$ as in a conventional autoencoder [Kingma and Welling,
2014, Bowman et al., 2016].

  * •

We observe that the attention vector has to be inside the convex hull of
hidden representations of the source sequence, i.e.,
$\bm{a}_{j}\in\operatorname{conv}\\{\bm{h}^{\text{(src)}}_{i}\\}$. We impose a
normal prior whose mean is the average of $\bm{h}^{\text{(src)}}_{i}$, i.e.,
$p(\bm{a}_{j})=\mathcal{N}(\bar{\bm{h}}^{\text{(src)}},\mathbf{I})$, where
$\bar{\bm{h}}^{\text{(src)}}=\frac{1}{|\bm{x}|}\sum_{i=1}^{|\bm{x}|}\bm{h}_{i}^{\text{(src)}}$,
making the prior non-informative.

###  3.3 Posterior

We model the posterior of $q_{\bm{\phi}}^{(a)}(\bm{a}_{j}|\bm{x})$ as a normal
distribution $\mathcal{N}(\bm{\mu}_{a_{j}},\bm{\sigma}_{a_{j}})$, where the
parameters $\bm{\mu}_{a_{j}}$ and $\bm{\sigma}_{a_{j}}$ are obtained by a
recognition neural network. Similar to VAEs, we compute parameters as if in
the deterministic attention in Eq. (5) (denoted by $\bm{a}_{j}^{\text{det}}$
in this part) and then transform them by another layer, shown in Figure 2d.

For the mean $\bm{\mu}_{a_{j}}$, we apply an identity transformation, i.e.,
$\bm{\mu}_{a_{j}}\equiv\bm{a}_{j}^{\text{det}}$. The identify transformation
makes much sense as it preserves the spirit of “attention.” To compute
$\bm{\sigma}_{a_{j}}$, we first transform $\bm{a}_{j}^{\text{det}}$ by a
neural layer with $\tanh$ activation. The resulting vector then undergoes a
linear transformation followed by an $\exp$ activation function to ensure that
the values are positive.

###  3.4 Training Objective

The overall training objective of Seq2Seq with both variational latent space
$\bm{z}$ and variational attention $\bm{a}$ is to minimize

$\displaystyle J^{(n)}({\bm{\theta}},{\bm{\phi}})$
$\displaystyle=J_{\text{rec}}({\bm{\theta}},{\bm{\phi}},\bm{y}^{(n)})+\lambda_{\operatorname{KL}}\Big{[}{\operatorname{KL}}\left(q_{\phi}^{(z)}(\bm{z}|\bm{x}^{(n)})\|p(\bm{z})\right)+\gamma_{a}\sum_{j=1}^{|\bm{y}|}{\operatorname{KL}}\left(q_{\phi}^{(a)}(\bm{a}_{j}|\bm{x}^{(n)})\|p(\bm{a}_{j})\right)\Big{]}$
(8)

Here, we have a hyperparameter $\lambda_{\operatorname{KL}}$ to balance the
reconstruction loss and KL losses. $\gamma_{a}$ further balances the
attention’s KL loss and $\bm{z}$’s KL loss. Since VAE and VED are tricky with
Seq2Seq models (e.g., requiring KL annealing), we tie the change of both KL
terms and only anneal $\lambda_{\operatorname{KL}}$. (Training details will be
presented in Section 4.1.)

Notice that if $\bm{a}_{j}$ has a prior of
$\mathcal{N}(\bar{\bm{h}}^{\text{(src)}},\mathbf{I})$, the derivative of the
KL term also goes to $\bar{\bm{h}}^{\text{(src)}}$. This can be computed
straightforwardly or by auto-differentiation tools, e.g., TensorFlow.

###  3.5 Geometric Interpretation

We present a geometric interpretation of both deterministic and variational
attention mechanisms in Figure 3.

Suppose the hidden representations $\bm{h}_{i}^{\text{(src)}}$ is of
$k$-dimensional space (represented as a 3-d space in Figure 3). In the
deterministic mechanism, the attention model is a convex combination of
$\\{\bm{h}_{i}^{\text{(src)}}\\}_{i=1}^{|\bm{x}|}$, as the weights in Eq. (5)
are a probabilistic distribution. The attention vector $\bm{a}_{j}$ is a point
in the convex hull $\operatorname{conv}\\{\bm{h}_{i}^{\text{(src)}}\\}$, shown
in Figure 3a.

For variational attention in Figures 3b and 3c, the mean of posterior is still
in the convex hull, but the sample drawn from the posterior is populated over
the entire space (although mostly around the mean, shown as a ball). The
difference between the two variants is that the standard normal prior
$\mathcal{N}(\bm{0},\mathbf{I})$ pulls the posterior to the origin, whereas
the prior $\mathcal{N}(\bar{\bm{h}}^{\text{(src)}},\mathbf{I})$ pulls the
posterior to the mean of
$\bm{h}_{1}^{\text{(src)}},\bm{h}_{2}^{\text{(src)}},\cdots,\bm{h}_{|\bm{x}|}^{\text{(src)}}$
(indicated by red arrows).

Finally we would like to present a (potential) alternative of modeling
variational attention. Instead of treating $\bm{a}_{j}$ as random variables,
we might also treat $\bm{\alpha}_{j}$ as random variables. Since
$\bm{\alpha}_{j}$ is the parameter of a categorical distribution, its
conjugate prior is a Dirichlet distribution. In this case, the resulting
attention vector populates the entire convex hull (Figure 3d). However, it
relies on a reparametrization trick to propagate reconstruction error’s
gradient back to the recognition neural network [Kingma and Welling, 2014]. In
other words, the sampling of latent variables should be drawn from a fixed
distribution (without parameters) and then transformed to a desired sample
using the distribution’s parameters. This is nontrivial for Dirichlet
distributions and further research is needed to address this problem.

Figure 3: Geometric interpretation of attention mechanisms.

##  4 Experiments

We evaluated our model on two tasks: question generation (Section 4.1) and
dialog systems (Section 4.2).

###  4.1 Experiment I: Question Generation

Model | Inference | BLEU-1 | BLEU-2 | BLEU-3 | BLEU-4 | Entropy | Dist-1 | Dist-2
---|---|---|---|---|---|---|---|---
DED (w/o Attn) [Du et al., 2017] | MAP | 31.34 | 13.79 | 7.36 | 4.26 | - | - | -
DED (w/o Attn) | MAP | 29.31 | 12.42 | 6.55 | 3.61 | - | - | -
DED+DAttn | MAP | 30.24 | 14.33 | 8.26 | 4.96 | - | - | -
VED+DAttn | MAP | 31.02 | 14.57 | 8.49 | 5.02 | - | - | -
Sampling | 30.87 | 14.71 | 8.61 | 5.08 | 2.214 | 0.132 | 0.176
VED+DAttn (2-stage training) | MAP | 28.88 | 13.02 | 7.33 | 4.16 | - | - | -
Sampling | 29.25 | 13.21 | 7.45 | 4.25 | 2.241 | 0.140 | 0.188
VED+VAttn-$0$ | MAP | 29.70 | 14.17 | 8.21 | 4.92 | - | - | -
Sampling | 30.22 | 14.22 | 8.28 | 4.87 | 2.320 | 0.165 | 0.231
VED+VAttn-$\bar{h}$ | MAP | 30.23 | 14.30 | 8.28 | 4.93 | - | - | -
Sampling | 30.47 | 14.35 | 8.39 | 4.96 | 2.316 | 0.162 | 0.228

Table 2: BLEU, entropy, and distinct scores. We compare the deterministic
encoder-decoder (DED) and variational encoder-decoders (VEDs). For VED, we
have several variates: deterministic attention (DAttn) and the proposed
variational attention (VAttn). Variational models are evaluated by both max a
posteriori (MAP) inference and sampling.

#### Task, Dataset, and Metrics.

We first evaluated our approach on a question generation task. It uses the
Stanford Question Answering Dataset [Rajpurkar et al., 2016, SQuAD], and aims
to generate questions based on a sentence in a paragraph. We used the same
train-validation-test split as in ?). According to ?), the attention mechanism
is especially critical in this task in order to generate relevant questions.
Also, generated questions do need some variety (e.g., in the creation of
reading comprehension datasets), as opposed to machine translation, which is
typically deterministic.

We followed ?) and used BLEU-1 to BLEU-4 scores [Papineni et al., 2002] to
evaluate the quality (in the sense of accuracy) of generated sentences.
Besides, we adopted entropy and distinct metrics to measure the diversity.
Entropy is computed as $-\sum_{w}p(w)\log p(w)$, where $p(\cdot)$ is the
unigram probability in generated sentences. Distinct metrics—used in previous
works to measure diversity [Li et al., 2016]—computes the percentage of
distinct unigrams or bigrams (denoted as Dist-1 and Dist-2, respectively).

#### Training Details.

We used LSTM-RNNs with 100 hidden units for both the encoder and decoder; the
dimension of the latent vector $\bm{z}$ was also 100d. We adopted 300d word
embeddings [Mikolov et al., 2013], pretrained on the SQuAD dataset. For both
the source and target sides, the vocabulary was limited to the most frequent
40k tokens. We used the Adam optimizer [Kingma and Ba, 2015] to train all
models, with an initial learning rate of 0.005, a multiplicative decay of
0.95, and other default hyperparameters. The batch size was set to be 100.

As shown in ?), Seq2Seq VAE is hard to train because of the issues associated
with the ${\operatorname{KL}}$ term vanishing to zero. Following ?), we
adopted ${\operatorname{KL}}$ cost annealing and word dropout during training.
The coefficient of the KL term $\lambda_{{\operatorname{KL}}}$ was gradually
increased using a logistic annealing schedule, allowing the model to learn to
reconstruct the input accurately during the early stages of training. A fixed
word dropout rate of $25\%$ was used.

All the hyperparameter tuning was based on validation performance on the
motivating Seq2Seq VAE discussed in Section 2.4, and the same hyperparameters
were used for all of the models described in Section 3.

#### Overall Performance.

Table 2 represents the performance of various models. We first implemented a
traditional vanilla Seq2Seq model, which we call a deterministic encoder-
decoder (DED), and generally replicated the results on the question generation
task as reported in ?), showing that our implementation is fair. Incorporating
attention mechanism in this model (DED+DAttn) improves BLEU scores, as
expected. In the variational encoder-decoder (VED) framework, we report
results obtained by both max a posterior (MAP) inference as well as sampling.
In the sampling setting, we draw 10 samples ($\bm{z}$ and/or $\bm{a}$) from
the posterior given $\bm{x}$ for each data point, and report average BLEU
scores.

The proposed variational attention model (VED+VAttn) largely outperforms
deterministic attention (VED+DAttn) in terms of all diversity metrics. It
should be noted that entropy is a logarithmic measure, and hence a difference
of 0.1 in Table 2 is significant; VED+VAttn also generates more distinct
unigrams and bigrams than VED+DAttn.

Regarding the prior of variational attention, we propose two variants:
$\mathcal{N}(\bm{0},\mathbf{I})$ and
$\mathcal{N}(\bar{\bm{h}}^{\text{(src)}},\mathbf{I})$, denoted as VED+VAttn-0
and VED+VAttn-$\bar{h}$, respectively. VED+VAttn-0 has slightly lower BLEU but
higher diversity. The results are generally comparable, showing both priors
are reasonable.

We also tried a heuristic of 2-stage training (VED+DAttn 2-stage), in which
the VED is first trained without attention for 6 epochs, and then the
attention mechanism is added to the model. This heuristic is proposed in hopes
of better training the variational latent space at the beginning stages.
However, experiments show that such simple heuristic does not help much, and
is worse than the principled variational attention mechanism in terms of all
BLEU and diversity metrics.

Figure 4: BLEU-2, BLEU-4, Entropy, and Dist-1 calculated on the validation set
as training progresses. Figure 5: BLEU-2, BLEU-4, Entropy, and Dist-1 with
different $\gamma_{a}$ values.

#### Human Evaluation.

In order to assess the quality of the generated text in terms of language
fluency, a human evaluation study was carried out. For each of the two models
under comparison (VED+DAttn and VED+VAttn-$\bar{h}$), a randomly shuffled
subset of 100 generated questions were selected. Six human evaluators were
asked to rate the fluency of these 200 questions on a 5-point scale:
5-Flawless, 4-Good, 3-Adequate, 2-Poor, 1-Incomprehensible, following ?). The
average rating obtained for VED+DAttn was 3.99 and for VED+VAttn-$\bar{h}$ was
4.01, the difference between which is not statistically significant. The human
annotations achieved 0.61 average Spearman correlation coefficient (measuring
order correlation) between any two annotators. According to ?), this indicates
moderate to strong correlation among different annotators. Hence, we conclude
variational attention does not negatively affect the fluency of sentences.

#### Learning curves.

Figure 4 shows the trends of sentence quality (BLEU-2 and BLEU-4) and
diversity (entropy and Dist-1) of all models on the validation set, as
training progresses.222Other metrics are omitted because the trend is the
same. We see that BLEU and diversity are conflicting objectives: a high BLEU
score indicates resemblance to the groundtruth, resulting in low diversity.
However, the variational attention mechanisms (red and green lines in Figure
4) remain high in both aspects, showing the effectiveness of our model.

Source | when the british forces evacuated at the close of the war in 1783 ,
---|---
| they transported 3,000 freedmen for resettlement in nova scotia .
Reference | in what year did the american revolutionary war end ?
VED+DAttn | how many people evacuated in newfoundland ?
how many people evacuated in newfoundland ?
what did the british forces seize in the war ?
VED+Vattn-$\bar{\bm{h}}$ | how many people lived in nova scotia ?
where did the british forces retreat ?
when did the british forces leave the war ?
Source | downstream , more than 200,000 people were evacuated from
---|---
| mianyang by june 1 in anticipation of the dam bursting .
Reference | how many people were evacuated downstream ?
VED+DAttn | how many people evacuated from the mianyang basin ?
how many people evacuated from the mianyang basin ?
how many people evacuated from the mianyang basin ?
VED+VAttn-$\bar{\bm{h}}$ | how many people evacuated from the tunnel ?
how many people evacuated from the dam ?
how many people were evacuated from fort in the dam ?

Table 3: Case study of question generation.

#### Strength of Attention’s KL Loss.

We tuned the KL term’s strength in variational attention, i.e., $\gamma_{a}$
in Eq. (8), and plot the BLEU and diversity metrics in Figure 5. In this
experiment, we used the VED+DAttn-$\bar{h}$ variant. As shown, a decrease in
$\gamma_{a}$ increases the quality of generated sentences at the cost of
diversity. This is expected because a lower $\gamma_{a}$ gives the model less
incentive to optimize the attention’s KL term, which then causes the model to
behave more “deterministic.” Based on this experiment, we chose a value of 0.1
for $\gamma_{a}$, as it yields a learning curve in the middle among those of
different hyperparameters, being a good balance between quality and diversity.

It should be further mentioned that, with a milder $\gamma_{a}$ (e.g., 0.01),
VED+VAttn outperforms VED+DAttn in terms of both quality and diversity (on the
validation set). This is consistent with the evidence that variational latent
space may serve as a way of regularization and improves quality [Zhang et al.,
2016]. However, a small $\gamma_{a}$ only slightly improves diversity, and
hence we did not choose this hyperparameter in Table 2.

#### Case study.

We show in Table 3 two examples of generated sentences by VED+DAttn and
VED+VAttn-$\bar{h}$, each containing three random sentences drawn from the
variational latent space(s) for a given input. In both examples, the
variational attention generates more diversified sentences than deterministic
attention. The quality of generated sentences is close in both models.

###  4.2 Experiment II: Dialog Systems

Model | Inference | BLEU-2 | Entropy | Dist-1 | Dist-2
---|---|---|---|---|---
DED+DAttn | MAP | 1.84 | – | – | –
VED+DAttn | MAP | 1.68 | – | – | –
Sampling | 1.68 | 2.113 | 0.311 | 0.450
VED+VAttn-$\bar{h}$ | MAP | 1.78 | – | – | –
Sampling | 1.79 | 2.167 | 0.324 | 0.467

Table 4: Performance on conversation systems.

We present another experiment on generative conversation systems. The goal is
to generate a reply based on a user-issued utterance. We used the Cornell
Movie-Dialogs Corpus333https://www.cs.cornell.edu/~cristian/Cornell_Movie-
Dialogs_Corpus.html [Danescu-Niculescu-Mizil and Lee, 2011] as our dataset,
which contains more than 200k conversational exchanges. All the settings in
this experiment were the same as in Subsection 4.1 except that we had 30k
words as the vocabulary for both the encoder and decoder. We evaluated the
quality of generated replies with BLEU-2, as it has been observed to be more
or less correlated with human annotators among the BLEU metrics [Liu et al.,
2016].

Table 4 shows the performance of our model (VED-VAttn-$\bar{h}$) compared with
two main baselines. We see that VEDs are slightly worse than the deterministic
encoder-decoder (DED) in this experiment. However, variational attention
outperforms deterministic attention in terms of both quality and diversity,
showing that our model is effective in different applications. However, we
find the improvement is not so large as in the previous experiment. We
conjecture that in conversational systems, there is a weaker alignment between
the source and target information. Hence, the attention mechanism itself is
less effective.

##  5 Related Work

The variational autoencoder (VAE) was proposed by ?) for image generation. In
NLP, it has been used to generate sentences [Bowman et al., 2016]. ?) propose
a variational encoder-decoder (VED) model to generate better (more diverse and
thus meaningful) replies in a dialog system. VED frameworks have also been
applied to knowledge base reasoning [Zhang et al., 2018]. Another thread of
VAE/VED applications is to control some characteristics of generated data,
such as the angle of a face image [Kumar et al., 2017], and the sentiment of a
sentence [Hu et al., 2017].

In this paper, the focus is on the scenario where VED is combined with
attention mechanism. We show that the variational attention space is
effective, in terms of the diversity of sampled sentences (since VEDs are
probabilistic models). Although previous studies have addressed diversity
using diversified beam search [Vijayakumar et al., 2016] and determinantal
point processes [Song et al., 2018], we would like to point out that our paper
is “orthogonal” to those studies. The diversity in our approach arises through
probabilistic modeling, as opposed to a manually specified heuristic function
of the diversity metric. It is to be noted that our approach can be naturally
combined with the above methods.

##  6 Conclusion and Future Work

In this paper, we proposed a variational attention mechanism for variational
encoder-decoder (VED) frameworks. We observe that, in VEDs, if the decoder has
direct access to the encoder, the connection may bypass the variational space.
Traditional attention mechanisms might serve as bypassing connection, making
the output less diverse. Our variational attention mechanism imposes a
probabilistic distribution on the attention vector. We also proposed different
priors for the attention vector. The proposed model was evaluated on two
tasks: question generation and dialog systems, showing that variational
attention yields more diversified samples while retaining high quality.

In future work, it would be interesting to investigate VEDs that model the
attention probability with Dirichlet distributions (see Figure 3d). Our
framework also provides a principled methodology for designing variational
encoding-decoding models without the bypassing phenomenon.

## Acknowledgments

We thank Hao Zhou for helpful discussions. The Titan Xp GPU used for this
research was donated by the NVIDIA Corporation to Olga Vechtomova.

## References

  * [Bahdanau et al., 2015]  Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  2015\.  Neural machine translation by jointly learning to align and translate.  In Proceedings of the International Conference on Learning Representations.
  * [Bowman et al., 2015]  Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning.  2015\.  A large annotated corpus for learning natural language inference.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 632–642.
  * [Bowman et al., 2016]  Samuel R. Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio.  2016\.  Generating sentences from a continuous space.  In Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning, pages 10–21.
  * [Cao and Clark, 2017]  Kris Cao and Stephen Clark.  2017\.  Latent variable dialogue models and their diversity.  In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pages 182–187.
  * [Danescu-Niculescu-Mizil and Lee, 2011]  Cristian Danescu-Niculescu-Mizil and Lillian Lee.  2011\.  Chameleons in imagined conversations: A new approach to understanding coordination of linguistic style in dialogs.  In Proceedings of the Workshop on Cognitive Modeling and Computational Linguistics, pages 76–87.
  * [Du et al., 2017]  Xinya Du, Junru Shao, and Claire Cardie.  2017\.  Learning to ask: Neural question generation for reading comprehension.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1342–1352.
  * [Hinton and Salakhutdinov, 2006]  Geoffrey E Hinton and Ruslan R Salakhutdinov.  2006\.  Reducing the dimensionality of data with neural networks.  Science, 313(5786):504–507.
  * [Hochreiter and Schmidhuber, 1997]  Sepp Hochreiter and Jürgen Schmidhuber.  1997\.  Long short-term memory.  Neural Computation, 9(8):1735–1780.
  * [Hu et al., 2017]  Zhiting Hu, Zichao Yang, Xiaodan Liang, Ruslan Salakhutdinov, and Eric P. Xing.  2017\.  Toward controlled generation of text.  In Proceedings of the 34th International Conference on Machine Learning, pages 1587–1596.
  * [Kingma and Ba, 2015]  Diederik Kingma and Jimmy Ba.  2015\.  Adam: A method for stochastic optimization.  In Proceedings of the International Conference on Learning Representations.
  * [Kingma and Welling, 2014]  Diederik P Kingma and Max Welling.  2014\.  Auto-encoding variational Bayes.  In Proceedings of the International Conference on Learning Representations.
  * [Kumar et al., 2017]  Abhishek Kumar, Prasanna Sattigeri, and Avinash Balakrishnan.  2017\.  Variational inference of disentangled latent concepts from unlabeled observations.  arXiv preprint arXiv:1711.00848.
  * [Li et al., 2016]  Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan.  2016\.  A diversity-promoting objective function for neural conversation models.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 110–119.
  * [Liu et al., 2016]  Chia-Wei Liu, Ryan Lowe, Iulian Serban, Mike Noseworthy, Laurent Charlin, and Joelle Pineau.  2016\.  How NOT to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2122–2132.
  * [Mikolov et al., 2013]  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  2013\.  Distributed representations of words and phrases and their compositionality.  In Advances in Neural Information Processing Systems, pages 3111–3119.
  * [Papineni et al., 2002]  Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  2002\.  BLEU: A method for automatic evaluation of machine translation.  In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pages 311–318.
  * [Rajpurkar et al., 2016]  Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang.  2016\.  SQuAD: 100,000+ questions for machine comprehension of text.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383–2392.
  * [Rush et al., 2015]  Alexander M. Rush, Sumit Chopra, and Jason Weston.  2015\.  A neural attention model for abstractive sentence summarization.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 379–389.
  * [Serban et al., 2017]  Iulian Vlad Serban, Alessandro Sordoni, Ryan Lowe, Laurent Charlin, Joelle Pineau, Aaron C Courville, and Yoshua Bengio.  2017\.  A hierarchical latent variable encoder-decoder model for generating dialogues.  In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 3295–3301.
  * [Song et al., 2018]  Yiping Song, Rui Yan, Yansong Feng, Yaoyuan Zhang, Zhao DongYan, and Ming Zhang.  2018\.  Towards a neural conversation model with diversity net using determinantal point processes.  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 5932–5939.
  * [Stent et al., 2005]  Amanda Stent, Matthew Marge, and Mohit Singhai.  2005\.  Evaluating evaluation methods for generation in the presence of variation.  In Proceedings of International Conference on Intelligent Text Processing and Computational Linguistics, pages 341–351.
  * [Swinscow, 1976]  TD Swinscow.  1976\.  Statistics at square one: Xviii-correlation.  British Medical Journal, 2(6037):680.
  * [Vijayakumar et al., 2016]  Ashwin K Vijayakumar, Michael Cogswell, Ramprasath R Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra.  2016\.  Diverse beam search: Decoding diverse solutions from neural sequence models.  arXiv preprint arXiv:1610.02424.
  * [Wainwright et al., 2008]  Martin J Wainwright, Michael I Jordan, et al.  2008\.  Graphical models, exponential families, and variational inference.  Foundations and Trends® in Machine Learning, pages 1–305.
  * [Zhang et al., 2016]  Biao Zhang, Deyi Xiong, jinsong su, Hong Duan, and Min Zhang.  2016\.  Variational neural machine translation.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 521–530.
  * [Zhang et al., 2018]  Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J Smola, and Le Song.  2018\.  Variational reasoning for question answering with knowledge graph.  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence.
  * [Zheng et al., 2018]  Zaixiang Zheng, Hao Zhou, Shujian Huang, Lili Mou, Xinyu Dai, Jiajun Chen, and Zhaopeng Tu.  2018\.  Modeling past and future for neural machine translation.  Transactions of the Association for Computational Linguistics, pages 145–157.
  * [Zhou and Neubig, 2017]  Chunting Zhou and Graham Neubig.  2017\.  Morphological inflection generation with multi-space variational encoder-decoders.  In Proceedings of the CoNLL SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection, pages 58–65.


# Eternal Picaria

Urban Larsson  and  Israel Rocha

###### Abstract.

Picaria is a traditional board game, played by the Zuni tribe of the American
Southwest and other parts of the world, such as a rural Southwest region in
Sweden. It is related to the popular children’s game of Tic-tac-toe, but the 2
players have only 3 stones each, and in the second phase of the game, pieces
are slided, along specified move edges, in attempts to create the three-in-a-
row. We provide a rigorous solution, and prove that the game is a draw;
moreover our solution gives insights to strategies that players can use.

Urban Larsson<EMAIL_ADDRESS>(partly supported by the Killam Trust) and
Israel Rocha<EMAIL_ADDRESS>Department of Mathematics and Statistics,
Dalhousie University, Halifax, Canada.

##  1\. Introduction

Picaria is a traditional board game, played by the Zuni tribe of the American
Southwest and other parts of the world, such as in a rural Southwest region in
Sweden111The ‘first’ author played this game as a child with his grandparents
in the village Rångedala close to the Swedish city Borås, and the game was
called “luffarschack”.. The game is related to the popular children’s game of
Tic-tac-toe, but it is even more related to other three-in-a-row games such as
Three men’s morris, Tapatan, Nine Holes, Achi, Tant Fant and Shisma. These
latter games are sometimes played in two phases, the first phase being
placement of stones, and the second part being sliding of stones along
prescribed ‘move edges’. In either case, the possibility of infinite play puts
Picaria in a different class than Tic-tac-toe.

The ‘blockade’ games of Pong Hau K’i, from China, and Mu Torere, played by the
Māori people from the east coast of New Zealand’s North Island, are also
related (in these games, if a player cannot move, he loses); with quite few
positions, only 16 and 46 respectively, these games are solved [2] by
depicting the position graphs.

In Picaria, there are two players who alternate turns, and the goal is to be
the first player to place 3 game pieces of a kind in a row, vertically,
horizontally or diagonally. Each player has their own type of pieces, say, to
use the convention of Tic-tac-toe, X and O. In our study, we assume that
player X starts. The players alternate turn to (in phase 1) place their stones
in an open space in a 3 by 3 grid. When each piece has been played in the
first phase (and assuming a non-loss so far), then player X begins the second
phase by sliding one of the three Xs to an empty adjacent node; then O slides
a stone, and so on. Adjacency here means a neighboring node, horizontally,
vertically or diagonally. A game position is declared a draw if periodicity of
a pattern is forced by one of the players. In this paper we give a
constructive proof that the opening position (the empty board) is a draw222The
historical popularity of the game is probably due to the fact that it is very
easy to make a single mistake and then there is a human player winner. As a
children’s game, by the author’s experience, the outcome is rarely a draw.
After many plays though, over several years, there is a kind of certainty that
both players should be able to draw, and here we show how. By this play
heuristics we believe that any proof would be non-trivial..

Picaria was described in the literature for the first time in 1907 by the
ethnographer Stewart Culin [1]. The original board of Picaria is displayed in
Figure 1.1. The players place stones on the vertices of the graph and slide
along the edges. In this paper we play the game in an equivalent manner using
instead a Tic-tac-toe board.

Figure 1.1. The original Picaria board and a Tic-tac-toe board

Before all stones are on the board, the number of positions coincide with
those of Tic-tac-toe. Subsequently there are 456 positions modulo symmetries
(see Section 3 for details) and many of those positions could be revisited
during the course of a game, so notably play is very different from Tic-tac-
toe. Even though a computer could be used to solve Picaria, this would not
provide a full understanding on how to play a succesful strategy. In this
paper we give the explicit strategies of optimal play, which means that
perfect information players will not play to draw if they can win and they
will not play to lose if they can avoid loss. The latter idea will be useful
at particular stages of our play proofs. In optimal play, if a player revisits
a position, then the game is a draw. It turns out that both players are able
to draw from the initial position. As a consequence, efficient strategies to
win by for example using Fork-, Trap-, Race-, or Zugzwang-positions (as
illustrated), will not occur in optimal play

$\xrightarrow{x}$ x o x o x o Fork $\xrightarrow{o}$ x o o x x o Trap
$\xrightarrow{o}$ o x o x o x Race $\xrightarrow{o}$ x o o o x x Zugzwang

Note here that a game position is depicted as a game board together with a
flag for who just moved. Often however we omit the move-flag, because it is
clear by the context which play position we discuss (for example in the
placement phase of the game). For example, play just before the Trap-position
involves a bad move by X

| x | o |
---|---|---|---
o | x |  |
x | o |  |

$\xrightarrow{x}$ x o o x x o $\xrightarrow{o}$ x o o x x o Trap

Such play does not belong to X’s strategy, and similar ideas are commonly
applied inside proofs.

##  2\. A Rigorous Play-analysis of Picaria

In our convention X is the first player. We show that player O can prevent X
from winning, by forcing X to play a periodic sequence of moves. That would
prove that the game is a draw if X can prevent O from winning too. We begin by
proving that it is easy for X to avoid loss.

###  2.1. The second player cannot win Picaria

######  Theorem 1.

Player $O$ cannot win.

###### Proof.

Player X starts by playing in the center and then there are two cases to
consider

|  |  | o |
---|---|---|---|---
|  | x |  |
(i)

and  x o (ii)

For game (i)

|  |  | o |
---|---|---|---|---
|  | x |  |
(i)

$\xrightarrow{x}$ o x x $\xrightarrow{o}$ o o x x $\xrightarrow{x}$ o x o x x

$\xrightarrow{o}$ o x o x o x (A) $\xrightarrow{x}$ o x o x x o

Thus, X can force a return to the game (A), depicted above, by

$\xrightarrow{o}$ x o o x x o $\xrightarrow{x}$ x o o x o x $\xrightarrow{o}$
o x o x o x

On the other hand, game (ii)  x o is losing for player O, since

|  | x | o |
---|---|---|---|---
(ii)

$\xrightarrow{x}$ x o x $\xrightarrow{o}$ o x o x $\xrightarrow{x}$ o x o x x
$\xrightarrow{o}$ o x o x o x

and this is a Race-position, from which player X wins in two moves. ∎

###  2.2. The first player cannot win playing from a Loop position

Next we analyse a special configuration which is quite recurring in the game,
called a Loop position:

$\xrightarrow{o}$ o o x x x o Loop

Any other symmetric position (a rotation or reflection; see for example game
(A) in the proof of Theorem 1) is also called a Loop position333We use loop in
the sense of something reappearing, although in graph theoretical terms it
would be more correct to call this a cycle.. The reason for this will be clear
in the next result, Theorem 5, where we show that O prevents X from winning
the game by means of a periodic sequence of moves. Consider that player X
holds the center. This restricts the possibilities for X in that only the two
outer stones can be moves. In particular if X starts from the Loop position,
then player X cannot win, which constitutes our next lemma. When Picaria is
played by human (non-optimal) players, a player holding the center often
appears to enjoy a certain advantage. The next results also revolve around the
idea of a player either holding or leaving the center.

######  Lemma 2.

If player X is to move and it refuses to leave the center starting from a Loop
position, then player O can force a return to this position.

###### Proof.

There are only three possible moves from a Loop-position for X, since it holds
the center.

|  |  | o |
---|---|---|---|---
| o | x |  |
| x | x | o |
(A)
|  | x | o |
---|---|---|---|---
| o | x |  |
| x |  | o |
(B)
|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x | o |
(C)

For game (A), player X gets trapped by

|  |  | o |
---|---|---|---|---
| o | x |  |
| x | x | o |
(A)

$\xrightarrow{o}$ o x o x x o

So X would have no option but give up the center and clearly loses the game.
Therefore, the game (A) does not belong to X’s strategy.

Now, player O can force either of the following sequences

|  | x | o |
---|---|---|---|---
| o | x |  |
| x |  | o |
(B)

$\xrightarrow{o}$ x o x x o o $\xrightarrow{x}$ o x x x o o $\xrightarrow{o}$
o o x x x o

or

|  | x | o |
---|---|---|---|---
| o | x |  |
| x |  |  |
(B)

$\xrightarrow{o}$ x o o x x o $\xrightarrow{x}$ o o x x x o $\xrightarrow{o}$
o o x x x o

which is the initial (Loop) position. Note that in the second diagram X does
not move into the Trap position. Finally,

|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x | o |
(C)

$\xrightarrow{o}$ o o x x x o

Now by symmetry X moves to

$\xrightarrow{x}$ o x o x x o $\xrightarrow{o}$ o x x o x o

which returns to the initial Loop-position. ∎

The next lemma concerns a ‘dual’ result for a Loop-position.

######  Lemma 3.

If O is to move from  x x o o o x then O can force a Loop.

###### Proof.

Player O begins with

|  | x |
---|---|---|---
x | o | o |
o |  | x |

$\xrightarrow{o}$ o x x o o x

Now X has two defense possibilities

$\xrightarrow{x}$ o x o o x x (A) or $\;\;\xrightarrow{x}$ o x x o o x (B)

For game (A)

|  | o | x |
---|---|---|---|---
|  | o |  |
| o | x | x |
(A)

$\xrightarrow{o}$ x o o o x x $\xrightarrow{x}$ x x o o o x which is the
original position.

Similarly, for game (B)

|  | o | x |
---|---|---|---|---
| x | o |  |
| o | x |  |
(B)

$\xrightarrow{o}$ x x o o o x $\xrightarrow{x}$ x x o o o x

which is again the original position.

∎

######  Lemma 4.

If X is to move from Loop position, and it leaves the center, then X cannot
win.

###### Proof.

Suppose first that X leaves the center in the first move. There are the
following possibilities

|  | x | o |
---|---|---|---|---
| o |  | x |
| x |  | o |
(A)
|  |  | o |
---|---|---|---|---
| o |  | x |
| x | x | o |
(B)
| x |  | o |
---|---|---|---|---
| o |  | x |
| x |  | o |
(C)

For game (A), O can force the sequence

|  | x | o |
---|---|---|---|---
| o |  | x |
| x |  | o |
(A)

$\xrightarrow{o}$ x o o x x o $\xrightarrow{x}$ x o o x x o

Now by Lemma 3, player X cannot win. If X creates game (B), then it Loses
since O can do

|  |  | o |
---|---|---|---|---
| o |  | x |
| x | x | o |
(B)

$\xrightarrow{o}$ o o x x x o $\xrightarrow{x}$ x o o x x o $\xrightarrow{o}$
x o o o x x

So game (B) does not happen. For game (C), player O moves

| x |  | o |
---|---|---|---|---
| o |  | x |
| x |  | o |
(C)

$\xrightarrow{o}$ x o o x x o

If player X moves $\xrightarrow{x}$ o x o x x o $\xrightarrow{o}$ o x o x x o

by which player O wins the game. So instead X plays

$\xrightarrow{x}$ x o o x x o and O responds by forcing X

$\xrightarrow{o}$ x o o x x o $\xrightarrow{x}$ x o o x o x

Now by Lemma 3, player X cannot win.

Suppose next that player X leaves the center but not in the first move. Now we
use the games (A), (B) and (C) from Lemma 2, and note that the only missing
case is that X leaves the center in the second move after the Loop-position
(this follows because otherwise O has already returned to Loop). Case (A) is
not in X’s strategy, and case (B) becomes instead

|  | x | o |
---|---|---|---|---
| o | x |  |
| x |  | o |
(B)

$\xrightarrow{o}$ x o x x o o $\xrightarrow{x}$ x o x x o o $\xrightarrow{o}$
x o o x x o $\xrightarrow{x}$ x o o x o x

from which player O has a non-losing strategy by Lemma 3. In case (C), we get

|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x | o |
(C)

$\xrightarrow{o}$ o o x x x o $\xrightarrow{x}$ x o o x x o

or

|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x | o |
(C)

$\xrightarrow{o}$ o o x x x o $\xrightarrow{x}$ o x o x x o

In the first case O creates a Zugzwang by moving into the center, and in the
second case, O can trap X.

∎

######  Theorem 5.

Player X cannot win moving from a Loop position.

###### Proof.

The proof follows from Lemmas 2 and 4. ∎

###  2.3. Games with two stones on the board

There are three positions with exactly two stones modulo symmetries. We begin
by ruling out that player O gets to start in the center.

######  Lemma 6.

For game  x o X cannot win.

###### Proof.

We have the following possibilities for player X

|  |  | x |
---|---|---|---|---
|  | o | x |
(A)
|  |  | x |
---|---|---|---|---
|  | o |  |
|  |  | x |
(B)
|  |  | x |
---|---|---|---|---
|  | o |  |
|  | x |  |
(C)
|  |  | x |
---|---|---|---|---
|  | o |  |
| x |  |  |
(D)

For game (A), player O can force a Loop by

|  |  | x |
---|---|---|---|---
|  | o | x |
(A)

$\xrightarrow{o}$ x o x o $\xrightarrow{x}$ x x o x o $\xrightarrow{o}$ x o x
o x o $\xrightarrow{x}$ x o x o x o

For game (B), player X must respond

|  |  | x |
---|---|---|---|---
|  | o |  |
|  |  | x |
(B)

$\xrightarrow{o}$ x o o x $\xrightarrow{x}$ x x o o x

and now player O can draw the game by

|  | x |
---|---|---|---
x | o | o |
|  | x |

$\xrightarrow{o}$ x x o o o x (E) $\xrightarrow{x}$ x x o o o x
$\xrightarrow{o}$ x x o o o x

$\xrightarrow{x}$ x x o o o x which is a Loop.

For game (C), if player O forces the sequence of positions

|  |  | x |
---|---|---|---|---
|  | o |  |
|  | x |  |
(C)

$\xrightarrow{o}$ x o o x $\xrightarrow{x}$ x x o o x $\xrightarrow{o}$ o x x
o o x $\xrightarrow{x}$ o x x o o x

then, by Lemma 3 $X$ cannot win. Similarly, for game (D), if O forces the
sequence

|  |  | x |
---|---|---|---|---
|  | o |  |
| x |  |  |
(D)

$\xrightarrow{o}$ x o x o $\xrightarrow{x}$ x x o x o $\xrightarrow{o}$ x x o
o x o $\xrightarrow{x}$ x o o x x o

Then by Lemma 3 player X cannot win. ∎

######  Lemma 7.

For game o x X cannot win.

###### Proof.

Here player X has the possibilities

|  |  | x |
---|---|---|---|---
|  | o | x |
(A)
|  | x |  |
---|---|---|---|---
|  | o | x |
(B)
| x |  |  |
---|---|---|---|---
|  | o | x |
(C)
| x | o | x |
---|---|---|---|---
(D)

Games (A) and (C) are the same games as (A) and (C) in the proof of Theorem 6.

For game (B), player O can force X’s moves by

|  | x |  |
---|---|---|---|---
|  | o | x |
(B)

$\xrightarrow{o}$ x o o x $\xrightarrow{x}$ x o o x x $\xrightarrow{o}$ x o o
x x o $\xrightarrow{x}$ x o o x o x

Then by Lemma 3, X cannot win. For game (D), player O can force X’s moves by

| x | o | x |
---|---|---|---|---
(D)

$\xrightarrow{o}$ x o x o $\xrightarrow{x}$ x x o x o $\xrightarrow{o}$ x o x
o x o

$\xrightarrow{x}$ x o o x x o $\xrightarrow{o}$ x o o o x x $\xrightarrow{x}$
x o o o x x

Then, by Lemma 3, player X cannot win.

∎

The next result deals with the most delicate position. There are some ideas
that are very interesting, that did not appear so far.

######  Lemma 8.

For game o x X cannot win.

###### Proof.

We have the cases to check

|  |  | o |
---|---|---|---|---
|  | x | x |
(A)
|  |  | o |
---|---|---|---|---
|  | x |  |
|  |  | x |
(B)
|  |  | o |
---|---|---|---|---
|  | x |  |
|  | x |  |
(C)
|  |  | o |
---|---|---|---|---
|  | x |  |
| x |  |  |
(D)

For position (A),

|  |  | o |
---|---|---|---|---
|  | x | x |
(A)

$\xrightarrow{o}$ o o x x and X has the possibilities

|  |  | o |
---|---|---|---|---
| o | x | x |
|  |  | x |
(1)
|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x |  |
(2)
|  |  | o |
---|---|---|---|---
| o | x | x |
| x |  |  |
(3)
| x |  | o |
---|---|---|---|---
| o | x | x |
(4)
|  | x | o |
---|---|---|---|---
| o | x | x |
(5)

For position 1,

|  |  | o |
---|---|---|---|---
| o | x | x |
|  |  | x |
(1)

$\xrightarrow{o}$ o o o x x x

Now if

o |  | o |
---|---|---|---
o | x | x |
|  | x |

$\xrightarrow{x}$ o x o o x x $\xrightarrow{o}$ x o o o x x and X cannot avoid
a loss,

and if

o |  | o |
---|---|---|---
o | x | x |
|  | x |

$\xrightarrow{x}$ o x o o x x $\xrightarrow{o}$ o x o x o x player O creates a
Loop.

For position 2,

|  |  | o |
---|---|---|---|---
| o | x | x |
|  | x |  |
(2)

$\xrightarrow{o}$ o o o x x x $\xrightarrow{x}$ x o o o x x $\xrightarrow{o}$
x o o o x x

which is a zugzwang, so no matter what player X does, it loses the game. For
position 3, player O creates a Loop by

|  |  | o |
---|---|---|---|---
| o | x | x |
| x |  |  |
(3)

$\xrightarrow{o}$ o o x x x o

Position 4 forces player O to create a Loop by

| x |  | o |
---|---|---|---|---
| o | x | x |
(4)

$\xrightarrow{o}$ x o o x x o

For position (5)

|  | x | o |
---|---|---|---|---
| o | x | x |
(5)

$\xrightarrow{o}$ x o o x x o

and now player X has 3 options, disregarding symmetries

|  | x | o |
---|---|---|---|---
| o | x |  |
|  | o | x |
(i)
|  | x | o |
---|---|---|---|---
| o |  | x |
|  | o | x |
(ii)
|  | x | o |
---|---|---|---|---
| o |  | x |
| x | o |  |
(iii)

For (i), player O is forced to create a Loop by

|  | x | o |
---|---|---|---|---
| o | x |  |
|  | o | x |
(i)

$\xrightarrow{o}$ o x o x o x

For (ii), player X is trapped by

|  | x | o |
---|---|---|---|---
| o |  | x |
|  | o | x |
(ii)

$\xrightarrow{o}$ x o o x o x $\xrightarrow{x}$ x o o x o x $\xrightarrow{o}$
x o o x o x

So X does not create game (ii). Finally, game (iii) allows player O to win by
a Zugzwang

|  | x | o |
---|---|---|---|---
| o |  | x |
| x | o |  |
(iii)

$\xrightarrow{o}$ x o o x x o

Thus player X does not create game (iii). That finishes game (A). For game
(B), all moves are forced, which creates a Loop as follows

|  |  | o |
---|---|---|---|---
|  | x |  |
|  |  | x |
(B)

$\xrightarrow{o}$ o o x x $\xrightarrow{x}$ o x o x x $\xrightarrow{o}$ o x o
x o x

For game (C), there are the following forced moves

|  |  | o |
---|---|---|---|---
|  | x |  |
|  | x |  |
(C)

$\xrightarrow{o}$ o o x x $\xrightarrow{x}$ x o o x x $\xrightarrow{o}$ x o o
x x o

Now player X must choose one of the options

| x | o | o |
---|---|---|---|---
|  |  | x |
|  | x | o |
(i)
| x | o | o |
---|---|---|---|---
|  | x | x |
|  |  | o |
(ii)

For game (i), player O forces a Loop by

| x | o | o |
---|---|---|---|---
|  |  | x |
|  | x | o |
(i)

$\xrightarrow{o}$ x o o x x o $\xrightarrow{x}$ x o x o x o

For game (ii) player O creates a Loop by

| x | o | o |
---|---|---|---|---
|  | x | x |
|  |  | o |
(ii)

$\xrightarrow{o}$ x o o x x o which finishes game (C).

For game (D), player O forces a Loop by

|  |  | o |
---|---|---|---|---
|  | x |  |
| x |  |  |
(D)

$\xrightarrow{o}$ o x x o $\xrightarrow{x}$ o x x x o $\xrightarrow{o}$ o o x
x x o

which concludes the proof. ∎

###  2.4. Summing up the results

######  Theorem 9.

Player X cannot win.

###### Proof.

This follows by combining Lemmas 7, 6 and 8.

∎

######  Corollary 10.

Picaria is a draw.

###### Proof.

This is a consequence of Theorems 1 and 9. ∎

##  3\. The number of positions in the second phase

To count the number of positions we apply Burnside’s Lemma to count equivalent
classes of positions. Besides, we only count the number of positions for the
second phase, i.e., when all six pieces are placed on the board. We consider
the set $P$ the possible positions in the game and $G$ the group acting on
$P$. Denote by $\mathrm{Fix}(g)$ the set of positions in $P$ that are fixed by
$g$. Burnside’s Lemma states that the number of orbits is

$\\#\mathrm{{orb}}=\frac{1}{\left|G\right|}\sum_{g\in
G}\left|\mathrm{Fix}(g)\right|.$

The elements in $G$ are composed by the identity, denoted by $e$, three
rotations of the board of $90$, $180$, and $270$ degrees denoted by $R_{90}$,
$R_{180}$, and $R_{270}$. Besides, there are four reflections, one horizontal
$H$, one vertical $V$, and two diagonal $D_{1}$ and $D_{2}$. Thus

$\displaystyle\\#\mathrm{{orb}}$ $\displaystyle=$
$\displaystyle\frac{1}{8}(\left|\mathrm{Fix}(e)\right|+\left|\mathrm{Fix}(R_{90})\right|+\left|\mathrm{Fix}(R_{180})\right|+\left|\mathrm{Fix}(R_{270})\right|$
$\displaystyle+\left|\mathrm{Fix}(H)\right|+\left|\mathrm{Fix}(V)\right|+\left|\mathrm{Fix}(D_{1})\right|+\left|\mathrm{Fix}(D_{2})\right|).$

For the identity $e$ we have $\binom{9}{3,3,3}=\frac{9!}{3!3!3!}$ positions.
For $R_{90}$ and $R_{180}$ rotations with a fixed position the board is of the
respective form

b | a | d |
---|---|---|---
a | e | c |
b | c | d |

and d b c a e a c b d

Here the letters can be X, O, or empty. Notice that
$\left|R_{90}\right|=\left|R_{270}\right|$. If we put all pieces on one of
these boards, there would be 4 pairs, each pair with the same symbol, which is
not possible. Thus, the rotations do not fix any position.

For diagonal reflections the number of fixed positions are the same for
$D_{1}$ and $D_{2}$. Consider the diagonal $D_{1}$ and horizontal reflections
with a fixed position of the respective forms

b | c | f |
---|---|---|---
a | e | c |
d | a | b |

and a b c d e f a b c

These are the only fixed positions by these group actions. Here the letters
can be X, O, or empty. It follows that a,b, and c are presicely one each of X,
O, or empty, and the same is true for d,e, and f. Thus, there are $3!3!$ such
positions of each kind. Since there are four reflections, we have in total
$3!3!4$ fixed positions.

Finally, we have

$\displaystyle\\#\mathrm{{orb}}$ $\displaystyle=$
$\displaystyle\frac{1}{8}(\left|\mathrm{Fix}(e)\right|+\left|\mathrm{{Fix}}(R_{90})\right|+\left|\mathrm{{Fix}}(R_{180})\right|+\left|\mathrm{{Fix}}(R_{270})\right|$
$\displaystyle+\left|\mathrm{{Fix}}(H)\right|+\left|\mathrm{{Fix}}(V)\right|+\left|\mathrm{{Fix}}(D_{1})\right|+\left|\mathrm{{Fix}}(D_{2})\right|)$
$\displaystyle=$
$\displaystyle\frac{1}{8}\left(\frac{9!}{3!3!3!}+3!3!4\right)=228.$

Finally, we counted three positions that do not occur. Namely

| o | x |
---|---|---|---
| o | x |
| o | x |
o |  | x |
---|---|---|---
o |  | x |
o |  | x |
| x | o |
---|---|---|---
| x | o |
| x | o |

Thus we get $225$ orbits. Now, the position graph for the second phase of the
game contains positions where player X or O is to move. Thus, the position
graph for this game contains $450$ positions.

##  4\. Final Remarks

Consider the following natural generalizations of Picaria. We use the same set
of rules and only change the number of sides of the board as depicted.

Figure 4.1. Relatives of Picaria, with three, five, six and seven sides
respectively.

Following this pattern, there are infinitely many different board games in
this family. One can show that all these games are first player win in a few
moves, except for Picaria, and we invite the reader to find the play-proofs of
this fact. We find it compelling that the Zuni tribe played the only
insteresting game in this family for centuries.

###  4.1. Open problems

What happens if we increase the number of stones for each player, say that
game parameters, $k\geq 3$ stones each and $s\geq 3$ sides, are given
(otherwise the same rules). Is there any combination $(k,s)$, other than
$(3,4)$, for which the game is a draw (provided that the total number of
stones is less than the number of nodes)? Is it true that the second player
never wins? If we give the second player a one stone advantage (handicap), for
which combination $(k,s)$ can he draw/win the $((k,k+1),s)$ game (that is the
second player places his last placement stone after the first slide-along-edge
move by ther first player)? In general, how many stones advantage $l>0$ does
he require to draw/win a generalized Picaria?

## References

  * [1] Culin, Stewart. Games of North American Indians. Washington DC: US gov Printing Office. 846 pp. (1907).
  * [2] Philip D. Straffin, Jr. Position Graphs for Pong Hau K’i and Mu Torere. Mathematics Magazine Vol. 68, No. 5 (Dec., 1995), pp. 382-386.