This paper explores the possibility of learning chess game concepts under weak supervision with convolutional neural networks, which is a topic that has not been visited to the best of our knowledge. We put this task in three different backgrounds: (1) deep reinforcement learning has shown an amazing capability to learn a mapping from visual inputs to most rewarding actions, without knowing the concepts of a video game. But how could we confirm that the network understands these concepts or it just does not? (2) cross-modal supervision for visual representation learning has drawn much attention recently. Is this methodology still applicable when it comes to the domain of game concepts and actions? (3) class activation mapping is widely recognized as a visualization technique to help us understand what a network has learnt. Is it possible for it to activate at non-salient regions? With the simplest chess game tic-tac-toe, we report interesting results as answers to those three questions mentioned above. All codes, pre-processed datasets and pre-trained models will be released.
1 INTRODUCTION
1.1 APPLICATION BACKGROUND
Deep reinforcement learning (DRL) has drawn quite much attention since the publication of influential work Mnih et al. (2015). A convolutional neural network (CNN) is used to bridge the gap between video game screen frames and the most rewarding actions. An amazing feature of this kind of systems is that they do not need to know the concepts of these games (e.g. DRL learns to play Breakout without knowing there is a paddle or a ball in Fig 1a). However, how could we confirm that this network really understands these concepts or it just learns a mapping from patterns in the visual inputs to the best actions? This is the first question we are trying to answer here.
Mnih et al. (2015) provides some unsupervised analysis results for visualization, showing that perceptually dissimilar frames may produce close rewards, yet this does not answer the question. We choose another visualization technique called class activation mapping as described in Zhou et al. (2016), which can reveal where the CNN’s attention is. However, directly applying it in tasks like Breakout still cannot answer the question. Imagine one modifies the network described in Mnih et al. (2015) into another version as Zhou et al. (2016) does. The CNN’s attention may be fixed on the ball but it is still not enough to support that the network understands the concept of a ball.
∗This work was done when Hao Zhao was an intern at Intel Labs China, supervised by Anbang Yao who is responsible for correspondence.
We propose to use a simple chess game called tic-tac-toe for case study. In order to answer the question, we propose a protocol as this: to place a piece where the CNN’s attention is, and examine whether it is the right move. Of course, the training has to be done under weak supervision, or say, without telling the network what exactly a right move is. We think if this experiment succeeds we can claim that the network figures out the concepts of: (1) a chess board grid; (2) the winning rule; (3) two sides. Detailed analysis about these three concepts are provided later.
1.2 METHODOLOGY BACKGROUND
There have been some works about representation learning with cross-modal supervision recently. Owens et al. (2016) clusters sound statistics into several categories, and uses them as labels to learn visual representation from images corresponding to these sounds. It quantitatively shows that visual representation learnt in this way is capable of handling challenging computer vision tasks and qualitatively shows that visual and sound representations are consistent (e.g. babies’ faces correspond to baby cry sound samples). Castrejón et al. (2016) goes even further by learning representations across five modalities: RGB images, clip art pictures, sketches, texts and spatial texts. Gupta et al. (2016) learns depth image representation with mid-level features extracted from RGB images as supervision, and reports improved RGB-D object detection performance.
What is the common point among these works? They generate weak supervision from one modality and use it to learn representation from another (e.g. to learn what a train looks like from what a train sounds like or to learn what a chair looks like in depth images from what a chair looks like in RGB images). During training phase, no concepts about a train or a chair are explicitly modeled. Although there are many other modalities not visited by this methodology, we think the basic ideas behind these works are same: an abstract concept like a train can be observed in different modalities and different representations can be connected.
Here comes the question: is this methodology still applicable when it goes beyond the problem of learning representations from different observations of a same concept? Albanie & Vedaldi (2016) is an example, which tries to relate facial expressions with what happened in a TV show (e.g. if a character earns a lot of money, she will be very happy). Although in Albanie & Vedaldi (2016) what happened is explicitly defined, it still can be regarded as a weak supervision for what this expression is.
Although with the same methodology, the problem studied in this paper addresses even higher semantics: to learn what to do under the weak supervision of what will happen (Fig 1b). This is substantially different from cross-modal supervision works mentioned above because there is no longer a certain abstract concept of object or attribute observed in different modalities. Instead, figuring out the relationship between what to do and what will happen needs a higher level of intelligence.
1.3 TECHNIQUE BACKGROUND
The core technique used in this paper is class activation mapping (CAM) as described in Zhou et al. (2016). So leaving out all the backgrounds about playing a chess game or cross-modal supervision, what do our experiments say more than its inventors’? We think we show that CAM can also activate at non-salient regions. CAM helps us to understand where contributes the most to a classification result. As Fig 1c shows, the heatmap reveals that the face contributes the most to the result that the network claims it as a person.
As has already been shown by Krizhevsky et al. (2012), kernels of lower layers of a CNN capture gradients in an image. Existing CAM experiments tend to activate at salient regions, and this is very reasonable because there are more gradients and therefore more information (e.g. the face in Fig 1c). Here comes the question: could CAM activate at non-salient regions like the empty spaces on a chess board? Our answer is positive as the results (Fig 1d) show that in order to predict what will happen in the future, the CNN’s attention is fixed upon texture-free regions.
Since we render chessboards as visual inputs without adding noise, those empty spaces are completely empty meaning that: (1) if we take out the activated patch in Fig 1d, all pixels in this patch have exactly the same value. (2) If we evaluate this patch with quantitative information metric like entropy, there is no information here. Thus the only reason why these regions are activated is that the network collects enough information from these regions’ receptive fields. We argue that this experiment (CAM can activate at non-salient regions) testifies (again) CNN’s ability to hierarchically collect information from visual inputs.
1.4 WHAT THIS PAPER IS ABOUT
After introducing those three backgrounds, we describe our work briefly as: to classify rendered tic-tac-toe chessboards with weak labels and to visualize that the CNN’s attention automatically reveals where the next piece should be placed. Learnt representation shows that: (1) the network knows some concepts of the game that it is not told of; (2) this level of supervision for representation learning is possible; (3) the technique of class activation mapping can activate at non-salient regions.
2 RELATED WORKS
2.1 CONCEPT LEARNING
Concept learning has different meanings in different contexts, and how to confirm a concept is learnt remains an open question. In Jia et al. (2013), a concept is learnt if a generative model is learnt from a small number of positive samples. In Lake et al. (2015), a concept is learnt if a model learnt from only one instance can generalize to various tasks. Higgins et al. (2016) claims a concept is learnt when a model can predict unseen objects’ sizes and positions. To summarize, they evaluate whether a concept is learnt through a model’s generalization ability. In even earlier works like Zhu et al. (2010);Yang et al. (2010), concept learning means a object/attribute classification task dealing with appearance variations, in which a concept is actually already pre-defined.
Unlike these works, we investigate the concepts of game rules instead of object/attribute. Unlike Jia et al. (2013);Lake et al. (2015);Higgins et al. (2016), we claim a concept is learnt through a novel testing protocol instead of generalization ability. Why generalization ability could show a concept is learnt? We think the reason is that a model understands a concept if it can use it in more cases. To this end, we argue that our protocol could also show a concept is learnt because the learnt representations in our experiments can be used to decide what to do though no rule about what need to be done is provided.
2.2 CROSS-MODAL SUPERVISION
The literature of cross-model supervision and the differences between this paper and existing ones are already covered in last section. Here we re-claim it briefly: Owens et al. (2016);Castrejón et al. (2016);Gupta et al. (2016) learn representations across modalities because actually they are different observations of a same (object or attribute) concept. Whether this methodology is applicable for
higher-level concepts like game rules remains an open question and we provide positive answers to this question.
2.3 CLASS ACTIVATION MAPPING
Before the technique of class activation mapping is introduced by Zhou et al. (2016), pioneering works like Simonyan et al. (2014);Zhou et al. (2015) have already shown CNN’s ability to localize objects with image-level labels. Although with different techniques, Simonyan et al. (2014);Zhou et al. (2015)’s activation visualization results also focus on salient regions. Unlike these works, we show that class activation mapping can activate at non-salient regions, or say more specifically, completely texture-free regions. Since the activated patch itself provides no information, all discriminative information comes from its context. This is another strong evidence to prove CNN’s capability to collect information from receptive fields, as a hierarchical visual model.
3 EXPERIMENT I: GAME ENDS IN NEXT MOVE
A tic-tac-toe chessboard is a 3×3 grid, and there are two players (black and white in our case). Due to duality, we generate all training samples assuming the black side takes the first move. The state space of tic-tac-toe is small consisting of totally 39 = 19683 combinations. Among them, many combinations are illegal such as the one in which all 9 pieces are black. We exhaustively search over the space according to a recursive simulation algorithm, in which: (1) the chessboard state is denoted by an integer smaller than 19683. (2) every state corresponds to a 9-d vector, with each element can take a value from this set {0-illegal, 1-black win, 2-white win, 4-tie, 5-uncertain}. We call this 9-d vector a state transfer vector, denoting what will happen if the next legal piece placement happens at according location. (3) generated transfer vectors can predict the existence of a critical move that will finish the game in advance. We will release this simulation code.
After pruning out illegal states, we collect 4486 possible states in total. Among these samples, we further take out 1029 states that a certain side is going to win in the next move. We then transform these chessboard states into visual representations (gray-scale images at resolution (180, 180)). Each of these 1029 samples is assigned a label according to the state transfer vectors. There are totally 18 different labels illustrating 2 (sides) × 9 (locations). As demonstrated by Fig 2, we randomly pick a sample for each label. As mentioned before black side takes the first move, thus if the numbers of
black and white pieces are equal the next move will be black side’s and if there are one more black piece the next move will be white side’s.
Although the concepts of two sides and nine locations are coded into the labels, this kind of supervision is still weak supervision. Because what we are showing to the algorithm is just 18 abstract categories as Fig 2 shows. Could an algorithm figure out what it needs to do by observing these visual inputs? We think even for a human baby it is difficult because no concepts like this is a game or you need to find out how to win are provided. In the setting of deep reinforcement learning there is at least an objective of getting higher score to pursue.
As mentioned before, the method we exploit is to train a classification network on this rendered dataset (Fig 2) and analyze learnt representations with the technique of class activation mapping. As Zhou et al. (2016) suggests, we add one global average pooling layer after the last convolutional layer of a pre-trained AlexNet model. All fully connected layers of the AlexNet model are discarded, and a new fully connected layer is added after the global average pooling layer. After the new classification network is fine-tuned on our dataset, a CAM visualization is generated by weighting the outputs of the last convolutional layer with parameters from the added fully connected layer. Our CAM implementation is built upon Marvin and it will be released.
Due to the simplicity of this classification task, the top one classification accuracy is 100% (not surprisingly). Class activation mapping results are provided in Fig 3 and here we present the reasons why we claim concepts are learnt: (1) We provide 18 abstract categories, but in order to classify visual inputs into these 18 categories the network’s attention is roughly fixed upon chessboard grids.
This means the concept of grid emerges in the learnt representation. (2) If we place a piece at the most activated location in Fig 3, that will be the right (and legal) move to finish the game. On one hand, this means the concept of winning rule emerges in the learnt representation. On the other hand, this means this learnt concept can be used to deal with un-taught task (analogous to Jia et al. (2013);Lake et al. (2015);Higgins et al. (2016) who use generalization ability to illustrate that concepts are learnt). (3) As Fig 3cehijnpq show, both sides can win in the next move if we violate the take-turns rule. However, the network pays attention to the right location that is consistent to the rule. For example, in Fig 3j, it seems that placing a black piece at the left-top location will also end the game. However, this move will violate the rule because there are already more black pieces than white pieces meaning that this is the white side’s turn. This means that the concept of two sides emerges in learnt representation.
Except for learnt concepts, we analyze what this experiment provides for the remaining two questions. To the second question: results in Fig 3 show that the methodology of generating labels from one modality (state transfer vectors in our case) to supervise another modality is still applicable. More importantly, we use images as inputs yet the learnt visual representations contain not only visual saliency information but also untold chess game concepts. To the third question: as Fig 3 shows, most activated regions are empty spaces on the chessboard.
4 EXPERIMENT II: ADDING GRID LINES
Since we claim complicated concepts emerge in learnt visual representations, a natural question will be: if the chessboard’s and pieces’ appearances are changed does this experiment still work? Thus we design this experiment by adding grid lines to the chessboards when rendering synthetic data (Fig 4). The intentions behind this design is three-folded: (1) in this case, the chessboard’s appearance is changed. (2) after these lines are added, the concept that there is a chessboard grid is actually implied. Still, we do not think these lines directly provide the concept of chessboard grid thus we use the word imply. Whether the network can figure out what these lines mean still remain
uncertain. (3) those locations that are completely empty in Experiment I are no longer empty from the perspective of information (still empty from the perspective of game rule).
We train the same network on the newly rendered dataset with grid lines and calculate CAM results in the same way. The results are demonstrated by Fig 4. Generally speaking, the grid lines allow the network to better activate at the location of right move, making them stands out more on the heatmap. What does this mean to the three intentions mentioned in last paragraph? (1) Firstly, it shows that our experiment is robust to chess board appearance variance. (2) Secondly, after implying the concept that there is a chessboard grid, the network performs better at paying attention to the location of right move. Again we compare this phenomenon against how a human baby learns. Although not supported by phycological experiment, we think with a chessboard grid a human baby is more easy to figure out the game rule than without. (3) Thirdly, heatmap changes in Fig 4 is not surprising, because after adding those lines, the empty (from the perspective of game rule) regions contain more gradients for lower layers of a CNN to collect. However, again it supports that activating at non-salient regions is NOT trivial.
5 EXPERIMENT III: PIECE APPEARANCE CHANGE
In this experiment we change the appearance of the piece by: (1) replacing black boxes with white circles; (2) replacing white boxes with black crosses. Note that in this case the white side moves first. Again we train the same network and visualize with CAM. The results comparison is provided in Fig 6. Further we add grid lines to the cross/circle chessboard.
6 EXPERIMENT IV: MODEL BEHAVIOR OVER TIME
In order to further demonstrate the non-triviality of the model behaviors, we design this experiment. We train on the dataset in Experiment I with 1000 iterations and snap-shotted the parameters at 500th iteration. The classification accuracy is 100% at 1000th iteration and 53.13% at 500th iteration. The
CAM results are shown by Fig 5 in which all samples are true positives. We think it shows that there are two ways to achieve this classification task: (1) by paying attention to the visual patterns formed by the existing pieces; (2) by paying attention to where the next piece should be placed. This experiment shows that at an earlier stage of learning the model’s behavior is consistent to the first hypothesis and after the training is completely done the network can finally fire at correct location.
7 QUANTITATIVE EVALUATION
We propose two different quantitative evaluation protocols. The first one is representation accuracy (RAC), for which we select the most activated patch and examine whether it is the correct location to end the game. The second one is representation consistency (RCO), which correlates the normalized representation and a normalized ideal activation map. The quantitative comparisons are shown in Table 1, in which NAC stands for network classification accuracy. These results quantitatively support that: (1) learnt representation can be used to predict the right move at an over 70% accuracy. (2) adding grid lines (implying the concept of a chessboard) dramatically improves localization.
8 CONCLUSION
The core experiment in this paper is to train a classification CNN on rendered chessboard images under weak labels. After class activation mapping visualization, we analyse and interpret the results
in three different backgrounds. Although simple, we argue that our results are enough to show that: (1) a CNN can automatically figure out complicated game rule concepts in this case. (2) cross-modal supervision for representation learning is still applicable in this case of higher-level semantics. (3) the technique of CAM can activate at non-salient regions, testifying CNN’s capability to collect information from context in an extreme case (only context has information).
Summary
===
This paper presents tic-tac-toe as toy problem for investigating CNNs.
A dataset is created containing tic-tac-toe boards where one player is one
move away from winning and a CNN is trained to label boards according
to (1) the player who can win (2 choices) and (2) the position they may move
to win (9 choices), resulting in 18 labels. The CNN evaluated in this paper
performs perfectly at the task and the paper's goal is to inspect how the
CNN works.
The fundamental mechanism for this inspection is Class Activation
Mapping (CAM) (Zhou et. al. 2016), which identifies regions of implicit attention
in the CNN. These implicit attention maps (localization heat maps) are used to
derive actions (which square each player should move). The attention maps  
(1) attend to squares in the tic-tac-toe board rather than arbitrary
blobs, despite the fact that one square in a board has uniform color, and
(2) they can be used to pick correct (winning) actions.
This experiment are used to support assertions that the network understands
(1) chess (tic-tac-toe) boards
(2) a rule for winning tic-tac-toe
(3) that there are two players.
Some follow up experiments indicate similar results under various renderings
of the tic-tac-toe boards and an incomplete training regime.
More Clarifying Questions
===
* I am not quite sure precisely how CAM is implemented here. In the original CAM
one must identify a class of interest to visualize (e.g., cat or dog). I don't
think this paper identifies such a choice. How is one of the 18 possible classes
chosen for creating the CAM visualization and through that visualization
choosing an action?
* How was the test set for this dataset for the table 1 results created?
How many of the final 1029 states were used for test and was the
distribution of labels the same in train and test?
* How is RCO computed? Is rank correlation or Pearson correlation used?
If Pearson correlation is used then it may be good to consider rank correlation,
as argued in "Human Attention in Visual Question Answering: Do Humans and
Deep Networks Look at the Same Regions?" by Das et. al. in EMNLP 2016.
In table 1, what does the 10^3 next to RCO mean?
Pros
===
* The proposed method, deriving an action to take from the result of a
visualization technique, is very novel.
* This paper provides an experiment that clearly shows a CNN relying on context
to make accurate predictions.
* The use of a toy tic-tac-toe domain to study attention in CNNs
(implicit or otherwise) is a potentially fruitful setting that may
lead to better understanding of implicit and maybe explicit attention mechanisms.
Cons
===
* This work distinguishes between predictions about "what will happen"
(will the white player win?) and "what to do" (where should the white
player move to win?). The central idea is generalization from "what will happen"
to "what to do" indicates concept learning (sec. 2.1). Why should an ability to
act be any more indicative of a learned concept than an ability to predict
future states. I see a further issue with the presentation of this approach and
a potential correctness problem:
1. (correctness)
In the specific setting proposed I see no difference between "what to do"
and "what will happen."
Suppose one created labels dictating "what to do" for each example in the
proposed dataset. How would these differ from the labels of "what will happen"
in the proposed dataset? In this case "what will happen" labels include
both player identity (who wins) and board position (which position they move
to win). Wouldn't the "what to do" labels need to indicate board position?
They could also chosen to indicate player identity, which would make them
identical to the "what will happen" labels (both 18-way softmaxes).
2. (presentation)
I think this distinction would usually be handled by the Reinforcement Learning
framework, but the proposed method is not presented in that framework or
related to an RL based approach. In RL "what will happen" is the reward an
agent will receive for making a particular action and "what to do" is the
action an agent should take. From this point of view, generalization from
"what will happen" to "what to do" is not a novel thing to study.
Alternate models include:
    * A deep Q network (Mnih. et. al. 2015) could predict the value of
      every possible action where an action is a (player, board position) tuple.
    * The argmax of the current model's softmax could be used as an action
      prediction.
The deep Q network approach need not be implemented, but differences between
methods should be explained because of the uniqueness of the proposed approach.
* Comparison to work that uses visualization to investigate deep RL networks
is missing. In particular, other work in RL has used Simonyan et. al.
(arXiv 2013) style saliency maps to investigate network behavior. For example, 
"Dueling Network Architectures for Deep Reinforcement Learning" by Wang et. al.
in (ICML 2016) uses saliency maps to identify differences between their
state-value and advantage networks. In "Graying the black box:
Understanding DQNs" by Zahavy et. al. (ICML 2016) these saliency maps are
also used to analyze network behavior.
* In section 2.3, saliency maps of Simonyan et. al. are said to not be able to
activate on grid squares because they have constant intensity, yet no empirical
or theoretical evidence is provided for this claim.
On a related note, what precisely is the notion of information referenced in
section 2.3 and why is it relevant? Is it entropy of the distribution of pixel
intensities in a patch? To me it seems that any measure which depends only
on one patch is irrelevant because the methods discussed (e.g., saliency maps)
depend on context as well as the intensities within a patch.
* The presentation in the paper would be improved if the results in section 7
were presented along with relevant discussion in preceding sections.
Overall Evaluation
===
The experiments presented here are novel, but I am not sure they are very
significant or offer clear conclusions. The methods and goals are not presented
clearly and lack the broader relevant context mentioned above. Furthermore, I
find the lines of thought mentioned in the Cons section possibly incorrect
or incomplete. As detailed with further clarifying questions, upon closer
inspection I do not see how some aspects of the proposed approach were
implemented, so my opinion may change with further details.