Title: CHESS GAME CONCEPTS EMERGE UNDER WEAK SU-PERVISION: A CASE STUDY OF TIC-TAC-TOE

Abstract: 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.

Figure 1 : We raise three questions from application, methodology and technique perspectives respectively and provide our answers with a case study of the simplest chess game tic-tac-toe.

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). Castrejó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) 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. 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. RELATED WORKS:



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) ; Castrejó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 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 3 9 = 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 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. 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 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 

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 

Experiment:



:



Figures and Tables:

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.

2.1 CONCEPT LEARNINGConcept learning has different meanings in different contexts, and how to confirm a concept is learnt remains an open question. InJia 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 likeZhu 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. UnlikeJia et al. (2013);Lake et al. (2015);Higgins et al. (

Figure 2: 18 different types of chessboard states and corresponding labels.

Figure 3: Class activation mapping results on our dataset.

Figure 4: Class activation mapping results after grid lines are added.

Figure 5: Class activation mapping results after piece appearance is changed.

Figure 6: Class activation mapping results on true positive samples at 500 iterations (left, 53.13% accuracy) and 1000 iterations (right, 100% accuracy).

Figure 7: We propose two quantitative evaluation protocols: (a) by selecting the most activated patch, we calculate how frequent the representation fire at the correct location; (b) we correlate the representation with an ideal activation map.

Quantitative 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).

Table content: <table><tr><td/><td>I</td><td>II</td><td>III</td><td>III</td><td>IV</td></tr><tr><td/><td>original</td><td>grid</td><td>piece</td><td>piece+grid</td><td>500th</td></tr><tr><td>NAC (%)</td><td>100.00</td><td>100.00</td><td>100.00</td><td>100.00</td><td>53.13</td></tr><tr><td>RAC (%)</td><td>71.82</td><td>97.25</td><td>83.77</td><td>99.00</td><td>27.87</td></tr><tr><td>RCO (10 3 )</td><td>-8.096</td><td>-5.115</td><td>-7.751</td><td>-4.9321</td><td>-10.610</td></tr></table>

Peer review (iclr2017):
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.