DL-BASED PREDICTION OF OPTIMAL ACTIONS OF HU-
Year: 2021

Abstract:
Expert systems have been developed to emulate human experts’ decision-making. Once developed properly, expert systems can assist or substitute human experts, but they require overly expensive knowledge engineering/acquisition. Notably, deep learning (DL) can train highly efficient computer vision systems only from examples instead of relying on carefully selected feature sets by human experts. Thus, we hypothesize that DL can be used to build expert systems that can learn human experts’ decision-making from examples only without relying on overly expensive knowledge engineering. To address this hypothesis, we train DL agents to predict optimal strategies (actions or action sequences) for the popular game ‘Angry Birds’, which requires complex problem-solving skills. In our experiments, after being trained with screenshots of different levels and pertinent 3-star guides, DL agents can predict strategies for unseen levels. This raises the possibility of building DL-based expert systems that do not require overly expensive knowledge engineering.

heading: 1 INTRODUCTION
text: To assist our decision-making, knowledge engineering has been developed to code human experts’ knowledge into artificial expert systems, which have been successfully applied to multiple domains (Buchanan & Smith, 1988; Russell & Norvig, 1995; Kiritsis, 1995). For instance, MYCYN (Buchanan & Shortliffe, 1984) can provide medical advice on infectious diseases, and XCON (McDermott, 1980) can help users to find right computer components. However, knowledge engineering requires expensive and complex engineering, limiting the expert systems’ utilities (Buchanan & Smith, 1988; Kiritsis, 1995). Notably, DL can enable artificial agents to automatically learn general rules essential for complex tasks from examples without human experts’ instructions (LeCun et al., 2015; Hertz et al., 1991). This leads to the hypothesis that we can use DL to build expert systems without expensive knowledge engineering (Tan, 2017). Indeed, a line of study already explores DL agents’ utility in diagnosing diseases based on medical images, for which traditional expert systems were used; see (Litjens et al., 2017) for a review.
However, it should be noted that most humans’ decisions involve a sequence of actions, each of which has a subgoal. Thus, sequence learning can be a key component in building artificial intelligent agents that mimic human experts’ decision-making (Sun & Giles, 2001; Boddy, 1996). Traditionally, symbolic planning is used to mimic humans’ goal-directed high-level planning, which repeatedly creates sub-goals necessary to accomplish higher level goals until a subgoal can be accomplished in a single action, and deploying symbolic planning requires ‘substantial prior knowledge’ and highly computational complexity (Sun & Giles, 2001). That is, the cost of symbolic planning can be as high as that of other expert systems.
In this study, we explored if DL can be used to learn high-level planning essential for human experts’ decision-making. We note that deep Q learning (Mnih et al., 2015) has demonstrated impressive achievements in learning optimal sequences of actions for games (Silver et al., 2016) and that recurrent neural networks have been used to model time series (Hertz et al., 1991). Our goal differs from these traditional DL approaches, in that we aim to model high-level planning more directly. To this end, we asked if deep neural networks (DNNs, agents trained by DL) can learn to predict strategies written by human experts for the popular game ‘Angry Bird’ (AB) (Contributors, 2021; Renz et al., 2019) from examples. To clear each stage, players must destroy all pigs in each stage.
As the pigs within the game are protected by piles of objects or stay inside towers, a single attack is often not enough to destroy all the pigs in each stage. Instead, players must sequentially organize subgoals to destroy all pigs efficiently, making AB an ideal testbed for high-level planning. Thus, we trained DNNs to predict human experts’ AB game strategies available at AB wiki pages (Contributors, 2021); the AB strategies will be referred to as 3-star guides (3SG) hereafter.
In the experiments, we asked three questions. First, can DL learn the functional relationships between screenshots (still images) of the stages and 3SG (human experts’ strategies)? Second, can an attention-based image captioning (ABIC) system, previously proposed (Xu et al., 2015), learn to create verbal strategies, which would sound reasonable to human players? Third, can ABIC predict a sequence of strategies (high-level planning) appropriate to clear a stage? Due to the lack of proper evaluation metric, we qualitatively evaluate the outcomes of the answers after training ABIC; the evaluation metrics of the language model is the topic of active research (Sellam et al., 2020; Papineni et al., 2001; Chen et al., 1998). Our empirical studies suggest that ABIC can learn to create verbal strategies after training and that it can predict a sequence of actions, not just a single action. They also support our hypothesis that DL can learn high-level planning from examples and that it can be used to build expert systems to assist human decision making without relying on overly expensive and complex knowledge engineering. Thus, our study indicates that DL can help us deploy expert systems into more domains.

heading: 2 DL AGENTS TO PREDICT OPTIMAL STRATEGIES OF ANGRY BIRDS (AB)
text: To clear each level of AB, players use birds to destroy the pigs that are scattered around and protected by towers or piles of wood, glass (or ice) and stone blocks. Each level provides a fixed sequence of birds and a unique challenging environment, and the players need to find an effective sequence of actions that can destroy all pigs in each level. The scores are estimated using various factors such as incurred damages and the number of birds used. When players obtain sufficiently high scores, they receive 3 stars. Any experienced game player (i.e., an expert) can devise good strategies (i.e., sequence of actions) to clear even the unseen levels, and conversely, the accuracy/efficiency of the plans can indicate the players’ ability/efficiency. Therefore, we ask if DL could predict optimal actions (or action sequence) from given screenshots of levels. We use the 3SG available at the wiki page (Contributors, 2021) as optimal strategies for DL to predict them.

heading: 2.1 FUNCTIONAL CORRELATIONS BETWEEN SCREENSHOTS AND 3SG
text: In principle, we can consider an expert system as an unknown functional mapping function that can identify an optimal relationship between problems/situations (i.e., screenshots in this study) to decisions/solutions (i.e., 3SG in this study); see Fig. 1A. If the mapping does exist, it would be possible to build expert systems. Thus, we first investigate functional correlations between screenshots and 3SG. Since a multilayer perceptron (MLP) has been considered a universal problem solver (Hertz et al., 1991), we assume that a trained MLP can predict the embeddings of 3SG (word embeddings) from the embeddings of screenshots (image embeddings), if the functional mappings from the screenshots to 3SG exist.
Based on this assumption, we train MLPs, which contain 100 hidden neurons in single hidden layers, with 80% levels (out of 327) randomly selected and test them with the remaining (test) levels. The image embeddings are created using the ResNet18 (Safka, 2021), and the word embeddings are generated using Hugging Face’s BERT model (Wolf et al., 2020). We first use image embeddings as inputs and word embeddings as outputs (Fig. 1B) and train MLP to minimize the mean squared error (MSE). A open-source ML library Pytorch (Paszke et al., 2017) is used to construct MLPs, and its built-in function (MSELoss) is used to estimate MSE. The word embeddings are projected to the PCA space, which is spanned by various numbers of principal axes, using a python package ‘Scikit-learn’ (Pedregosa et al., 2011). In the experiments, we repeat the same experiment 5 times with different random seeds and display the mean and standard deviations of them in Fig. 1C. As the number of principal axes increases, MLPs’ errors are reduced, and the magnitudes of reduction grow bigger; see the blue line in Fig. 1C. Interestingly, when the word and image embeddings are used as inputs and outputs, MLP cannot predict the outputs anymore (the orange line in Fig. 1C). These results suggest that functional mappings from screenshots to 3SG exist, but not vice versa.

heading: 2.2 EXPERT SYSTEMS OF AB
text: Encouraged by the results above, we ask if DL can directly predict human instructions from screenshots. Here, we train the attention-based image-captioning system (ABIC) (Xu et al., 2015) to predict 3SG from the screenshots. In the original form, ABIC uses convolutional networks as an encoder and recurrent networks as a decoder. The encoder extracts 14-by-14 annotation vectors, and the decoder uses annotation vectors to predict word sequences after training. They further proposed that the attention network, which determines the region of interest, can help the encoder-decoder system learn to produce captions. We refer to the original study for more details (Xu et al., 2015).
In this study, we adopted Pytorch implementation of ABIC from a public github repository (Vinodababu, 2021) and train it to predict 3SG from the screenshots using the default setting of the implementation. This adopted Pytorch implementation uses ResNet101 (He et al., 2015) as a encoder and the long short term memory (LSTM) (Hochreiter & Schmidhuber, 1997) as a decoder. Specifically, ResNet101 produces 2048 annotation vectors (14-by-14 pixels), the attentional network transforms annotation vectors using weighted sum, and LSTM selects the best word with previously selected word and weighted annotation vectors. In the experiments, we randomly select 70% of the levels as training examples, 15% as validation examples, and 15% as test examples. The number of total levels used here is 359. ResNet101 was adopted from TorchVision (Marcel & Rodriguez, 2010) and frozen during training, whereas both LSTM and the attentional network were trained.

heading: 2.2.1 ABIC CAN BE AN AB EXPERT
text: We note that ABIC was trained to produce a single sentence caption after being trained with multiple captions for a single image (Xu et al., 2015). To test the potential of AIBC as an AB expert, we mimic this baseline training of AIBC by ignoring the fact that 3SG describe the sequence of actions. Instead, we treat them as independently generated guides for the same stage and use them to train AIBC as an expert system of Angry Birds (EAB) to predict a single action. With this setting, we also effectively increase the number of training examples.
In AB and its wiki page (Contributors, 2021), levels are grouped into multiple stages, and the two consecutive numbers are used to refer to each level. For instance, level ‘12-03’ refers to the third level in the 12th stage, and the same type of reference is used to clarify the levels below. In the
experiments, 253 levels are randomly chosen as training and 50 levels as test examples (i.e., levels). We edit the guides slightly for clarification and remove irrelevant descriptions. Many instructions explain the bird types, while most screenshots do not include the birds. Thus, we augment the screenshots by inserting the circles that represent the first birds in the levels via colors in the top-left corners (Fig. 2).
With the edited guides and augmented screenshots, we train EAB and evaluate its predicted actions for test (unseen) screenshots. Fig. 2B shows an example of EAB outputs. As shown in the figure, the model utilizes attention to create a strategy (sentence). Table 1 shows some examples of EAB’s predicted actions/strategies for the unseen test levels (i.e., screenshots). Here, we make a few observations. First, although the guides describe the sequence of actions, most EAB outputs appear to describe only the first action. Second, EAB selects the correct birds to create predictions on strategies for 10 test levels. Third, a few of the predicted strategies are consistent with the guides. Fourth, the 3SG have diverse writing styles, making the quantitative evaluation of predicted strategies extremely difficult.
These results raise the possibility that DL can learn to predict an optimal action from examples only. Due to EAB’s low precision, we tested if EAB’s performance can be further improved..

heading: 2.2.2 EAB BECOMES MORE ACCURATE WITH BETTER OBJECT DETECTION UNITS
text: In the experiments mentioned above, the screenshots are fed to the image encoder (ResNet101) trained with ImageNet (Xu et al., 2015; Vinodababu, 2021). However, it should be noted that the visual objects used in AB are abstract and substantially different from real world objects in the ImageNet, which could reduce the quality/precision of visual embeddings of the ResNet101 and consequently the precision of EAB. Thus, we ask if better image embeddings can improve EAB’s accuracy. In doing so, we build customized detectors of the objects in the game, which use color templates of pigs, glass/ice, wood and stone blocks. Specifically, we use OpenCV’s ‘inRange’ function (Itseez, 2015; Its, 2014) to find candidate areas for the objects and scipy.ndimage’s ’find object’ (Virtanen et al., 2020) to test if the areas contain actual objects. For more accurate detection, we manually adjust the templates of individual stages and use a few simple error correction rules. After detecting the objects, we use them to synthesize functional screenshots of the stages (Fig. 3B).
After training EAB with synthesized (reconstructed) screenshots and 3SG of 249 training levels, we qualitatively evaluate EAB’s predictions for 58 test levels. We first select the predictions that articulate the correct birds and categorize them into 3 different categories, not-related strategy (NRS), probable strategy (PS), consistent strategy (CS). NRS indicates strategies not relevant to the levels,
PS indicates strategies reasonable (not necessarily good) for the levels, and CS indicates strategies consistent with 3SG. We note that some CS do not specify targets and thus code them as CS-ND (consistent strategies without detailed targets).
We found that 41 levels have the correct birds. 6 levels are evaluated as CS; 16 levels as PS, 5 levels as CS-ND amd 14 levels as NRS. Table 2 shows the examples of all 4 categories.

heading: 2.2.3 EAB CAN PROPOSE MULTIPLE ACTIONS
text: In AB, players can obtain optimal results by strategically organizing sequential actions. Thus, as the final test, we ask if EAB can learn to create a sequence of actions. Specifically, we remove the ‘end’ token from 3SG to build embeddings of action sequences. After training EAB with 253 training levels, we evaluate the predicted sequence for 50 test levels and make a few observations (Table 3). First, EAB predicts multiple actions for most levels—1 action in 10 levels, 36 actions in and 3 actions for 4 levels. Second, EAB can choose a sequence of birds properly in some levels. Specifically, it selects two first birds correctly for 13 levels, 3 first birds correctly for 2 levels, and 2 birds for 5 levels. Third, the accuracy of the predicted sequence of actions is low, but EAB still predicts action sequences consistent with 3SG for 3 levels. EAB also suggests probable action sequences for 6 levels. For 5 levels, one of the predicted actions includes some minor errors. For instance, EAB proposes to aim ‘wooden triangle’ for level ‘4-04’, but it does not exist in this level. We also found some predicted actions do not specify the targets for 3 levels. We categorize them into CS, PS, PS without targets (PS-ND) PS with minor errors (CS-me). Table 3 list the examples of CS, PS, PS-ND, PS-me and NRS.

heading: 3 DISCUSSION
text: In this study, we used the popular game Angry Bird to study the plausibility of DL-based expert systems. Specifically, we trained an off-shelf model (ABIC) to predict human players’ strategies (i.e., experts). Even though the strategies are written by many players, and thus they are heterogeneous in styles and vocabularies, ABIC was able to predict optimal strategies for given screenshots of stages. This result raises the possibility that DL can be used to build expert systems without overly expensive knowledge engineering and make the expert systems more affordable and deployable to more domains.
Further, our results suggest that DL can encode human experts’ knowledge/skills from their verbal explanations, leading us to speculate that DL can be used to quantify or better understand human behaviors. Below we briefly discuss two possible scenarios.

heading: 3.1 IMPLICATION FOR INTENTION DETECTION
text: By predicting others’ intentions, we can make decisions and take actions. When we detect dangerous behavioral cues from someone approaching us, we natively predict hostility and coordinate our actions accordingly. If an advanced surveillance camera can detect hostile intentions in public, they may proactively alert authorities to prevent criminal activities or neutralize threats. However, the behavioral cues that we rely on remain poorly understood, making the explicit design of intention detectors extremely challenging. Based on our experiments suggesting that DL can learn to predict humans’ decision-making process from examples, we argue that DL can be used to build intention detectors such as advanced surveillance systems.

heading: 3.2 IMPLICATION FOR TRAINING
text: To become experts, students need extensive training and experience. However, teaching requires experts to translate their experience/knowledge into standard and quantifiable languages. This remains a challenging process in many domains. Our results (Fig. 1C) suggest that we could build functional mappings between experts’ behaviors and tasks. If we could build DL agents to capture functional relationships between expert’s decisions and tasks’ components, we could use them to translate experts’ knowledge into quantifiable forms, which can facilitate students’ learning. For instance, we can build an expert system that can faithfully predict veteran pilots’ decisions and use it to analyze the influence of aircrafts’ sensors on their decisions. The discovered correlations between aircrafts’ sensors and pilots’ decisions will prepare student pilots more effectively.

heading: 3.3 LIMITATION AND FUTURE DIRECTION
text: Our EAB is trained to predict the optimal strategy (either a single action or a sequence of actions) for the level, but multiple strategies can be used to accomplish the same goal, and the best or optimal choice varies depending on contexts. Therefore, real world expert systems must learn various types of strategies to choose the optimal strategy. To this end, we need to build multiple agents specializing in individual strategies and develop dynamic evaluation systems that can flexibly choose the best agent from the available pool. In the future, we plan to seek such multi-agent expert systems.

Review summaries:
This paper suggests using deep learning to learn expert decision-making from game strategy guides. They focus on the task of Angry Birds, for which they have natural language descriptions of what actions to take to pass a given level. Given a visual representation of an Angry Birds screenshot, they train an LSTM to model the natural language guides. They claim that their model generalizes well.

The paper proposes an approach for building an expert system for sequential decision making problems from image-represented states and instruction-represented actions.  The authors reuse pretrained image- and word embeddings to train a MLP for predicting instructions from game frames. The paper specifically addresses the game angry birds and reports good results for mapping image embeddings to word embeddings.

The paper aims to study the training of Deep Learning (DL) models from examples and to this end trains a DL agent to predict actions given screenshots of the game "Angry Birds" and observe that the trained model is able to predict actions for test samples and concludes that possibly DL expert systems can learn only by examples. The contributions are three-fold:  1- First, they train an MLP model to learn the mapping from screenshots of the game to the word embeddings which correspond to the guide provided by a player on that stage of the game.    2-Trains an Attention Based Image Captioning System (ABIC) to predict human strategies from the screenshots of the game.  3- Trains ABIC to learn the sequence of strategies necessary to pass a stage.