Explaining How a Neural Network Play the Go Game and Let People Learn
The AI model has surpassed human players in the game of Go, and it is widely
believed that the AI model has encoded new knowledge about the Go game beyond
human players. In this way, explaining the knowledge encoded by the AI model
and using it to teach human players represent a promising-yet-challenging issue
in explainable AI. To this end, mathematical supports are required to ensure
that human players can learn accurate and verifiable knowledge, rather than
specious intuitive analysis. Thus, in this paper, we extract interaction
primitives between stones encoded by the value network for the Go game, so as
to enable people to learn from the value network. Experiments show the
effectiveness of our method.
Huilin Zhou, Huijie Tang, Mingjie Li, Hao Zhang, Zhenyu Liu, Quanshi Zhang
# Explaining How a Neural Network Play the Go Game and Let People Learn

###### Abstract

The AI model has surpassed human players in the game of Go (Fang et al., 2018, Granter et al., 2017, Intelligence, 2016), and it is widely believed that the AI model has encoded new knowledge about the Go game beyond human players. In this way, explaining the knowledge encoded by the AI model and using it to teach human players represent a promising-yet-challenging issue in explainable AI. To this end, mathematical supports are required to ensure that human players can learn accurate and verifiable knowledge, rather than specious intuitive analysis. Thus, in this paper, we extract interaction primitives between stones encoded by the value network for the Go game, so as to enable people to learn from the value network. Experiments show the effectiveness of our method.

## 1 Introduction

The explanation for AI models has gained increasing attention in recent years. However, in this paper, we consider a new problem, _i.e_., if an AI model has achieved superior performance in a task to human beings, then how can we use the explanation of this AI model to provide new insights and teach people to better conduct the task? In this study, we focus on AI models designed for the game of Go. It is because AI models for the Go game are regarded to have surpassed human players, and may learn the inference logic beyond current human understandings of the game of Go (Fang et al., 2018, Granter et al., 2017, Intelligence, 2016). Therefore, we aim to explain the complex inference logic encoded by these AI models to teach human players to play the Go game.

The current AI model usually jointly uses the value network, policy network, and Monte Carlo tree search to play the Go game. To simplify the explanation, in this study, we only explain shape patterns1 encoded by the value network. However, the elaborate strategies for the Go game proposes high requirements for the trustworthiness of the explanation. In particular, the Go game is widely considered as much more complex than most other games (Shin et al., 2020, 2021). In the Go game, even minor alterations to 1-2 stones on the board can fundamentally change the result of the game. Therefore, the explained insights into the value network are supposed to be proved by theories, be verified by experiments, and be accountable for errors, instead of specious intuitive analysis.

Footnote 1: Shape patterns, refer to the various shapes formed by the arrangement of stones on the board.

Specifically, the explanation method needs to address following two new challenges to provide a provable and verifiable explanation for the inference logic of the value network. (1) For models for most other applications, we can explain the model by simply visualizing implicit appearance patterns encoded by the model (Dosovitskiy and Brox, 2016, Simonyan et al., 2014, Yosinski et al., 2015, Zeiler and Fergus, 2014), or estimating attributions of different input variables (Lundberg and Lee, 2017, Selvaraju et al., 2017, Zhou et al., 2016, Zintgraf et al., 2017). However, due to the high complexity of the Go game, we need to explain explicit primitive shape patterns2, which are used by the neural network as primitive logic to play the game. (2) The rigor of the explanation of shape patterns2 must be guaranteed in mathematics. It is because the superior complexity of the Go game can easily lead to specious or groundless explanations that will misguide human players.

Footnote 2: Shape patterns, refer to the various shapes formed by the arrangement of stones on the board.

To this end, (Li and Zhang, 2023, Ren et al., 2023b) have attempted to define and extract interactions encoded by a DNN. Let us consider the Go game shown in Figure 1. Given a game state \(\mathbf{x}\) with \(n\) stones on the board, \(N=\{1,2,...,n\}\), we use interactions to explain the advantage score of white stones estimated by the value network. The value network may encode the
interaction between stones in \(S_{1}=\{1,3,4,5,8\}\). Each interaction \(S\subseteq N\) represents a specific shape corresponding to an AND relationship between stones in \(S\). When all stones in \(S\) are present on the board, the interaction \(S\) is activated and make an effect \(I(S)\) on the output of the value network. The removal of any stone in \(S\) will deactivate the interaction effect from the network output.

However, we find that the previous interaction-based explanation cannot be directly used to discover novel shapes from the value network. We overcome following three major challenges.

\(\bullet\) Besides explaining AND relationships between stones, we need to extend the original definition of interactions to further explain OR relationships between stones encoded by the value network. _I.e._, the presence of any stones in a set of positions \(S\) would make a certain effect \(I_{\text{or}}(S)\).

\(\bullet\) We find that the advantage score estimated the value network is usually shifted/biased, when white stones are far less or far more than black stones in the board. To this end, we develop a method to alleviate the shifting problem to simplify the explanation.

\(\bullet\) We need to show that given a certain state \(\mathbf{x}\) on the Go board, the outputs of the value network can always be mimicked by a small number of AND interactions and OR interactions, no matter how we randomly remove stones from the board.

Furthermore, we notice that shape patterns for the Go game are usually quite complex, _i.e._, each interaction often contains a large number of stones. Too complex shape patterns are usually considered as the specific shapes memorized by the value network for a specific state, instead of a common shape patterns shared by different states. Thus, the complexity of shape patterns boosts the difficulty of understanding the Go game. Thus, we further identify some common combinations of stones that are shared by different interactions/shapes, namely _coalitions_. For example, in Figure 1, the interactions \(S_{1}=\{1,3,4,5,8\},S_{2}=\{1,3,8\},S_{3}=\{1,3,8,9\}\) all contain the coalition T=\(\{1,3,8\}\). We apply [16] to estimate the attribution of each coalition to help human players understand the DNN's logic. We collaborate with professional human Go players to compare the interactions or coalitions encoded by the value network with the human understanding of the Go game, so as to discover advanced shapes beyond human understanding.

We conducted experiments to evaluate attributions of some manually-annotated coalitions, and cooperated with professional human Go players to further explain these attributions. We found many cases that fitted to human understandings of shape patterns, as well as a few cases that conflicted with normal understandings of shape patterns, which provided new insights into the Go game.

## 2 Related work

Many methods have been proposed to visualize the feature/patterns encoded by the DNN [1, 11, 12, 13], or to estimate the attribution/importance of each input variable [10, 11, 12, 14].

Figure 1: Interactions encoded by the value network. Each interaction \(S\) represents a specific shape pattern corresponding to an AND relationship among a set of stones in \(S\). The stones \(x_{6},x_{9},x_{10}\) are removed in the masked board state \(\mathbf{x}_{\text{masked}}\). Because the stone \(x_{9}\) is removed from the board, the interactions \(S_{3}\) and \(S_{4}\) are deactivated in the masked board state \(\mathbf{x}_{\text{masked}}\), _i.e._, \(I(S_{3}|\mathbf{x}_{\text{masked}})=0\), and \(I(S_{4}|\mathbf{x}_{\text{masked}})=0\). The coalition \(T=\{1,3,8\}\) participates in different interactions \(S_{1},S_{2},S_{3}\).
However, the demand to teach human players proposes higher requirements for the explanation method. We need to clarify the explicit logic used by the DNN, which is supposed to be theoretically guaranteed and experimentally verified, instead of a specious understanding. To this end, (1) Ren et al. (2023a) and Ren et al. (2023b) have proven that a well-trained DNN usually encodes a small number of interactions, and the output score of the DNN on a certain input sample can always be well mimicked by numerical effects of a few salient interactions, no matter how the input sample is randomly masked. (2) Li and Zhang (2023) have further found the considerable transferability of interactions over different samples and over different DNNs. (3) Interaction primitives (the Harsanyi interaction) can explain the elementary mechanism of previous explanation metrics, _e.g._, the Shapley value (Shapley, 2016), the Shapley interaction index (Grabisch and Roubens, 1999), and the Shapley Taylor interaction index (Sundararajan et al., 2020a).

Despite of above findings, explaining the DNN for the Go game still proposes new challenges. To this end, we extend the AND interaction to the OR interaction, solve the saturation problem of the advantage score, and compute attributions of common coalitions shared by different interactions, thereby obtaining concise and accurate explanation for shape patterns in the value network.

## 3 Explaining the inference logic of the value network

### Preliminaries: interactions encoded by the DNN

\(\bullet\)**Definitions of the interaction.** In this paper, we use the value network \(v\) for the game of Go as an example to introduce interactions between different stones encoded by the value network. The value network uses the current state \(\mathbf{x}\) on the board to estimate the probability \(p_{\text{white}}(\mathbf{x})\) of white stones winning. To simplify the notation, let us use \(\mathbf{x}=\{x_{1},x_{2},...,x_{n}\}\) to denote both positions and colors of \(n\) stones in the current state. We consider these \(n\) stones, including both white and black stones, as input variables2 of the value network, which are indexed by \(N=\{1,2,...,n\}\). We set a scalar \(v(\mathbf{x})=\log(\frac{p_{\text{white}}(\mathbf{x})}{1-p_{\text{white}}(\mathbf{x})})\in\mathbb{R}\) as the advantage of white stones in the game.

Footnote 2: Although the actual input of the value network is a tensor (Silver et al., 2016), in this paper, we use \(\mathbf{x}=\{x_{1},x_{2},...,x_{n}\}\) to denote the input of the value network for simplicity.

In this way, Harsanyi (1963) has proposed a metric \(I(S)\), namely the _Harsanyi dividend_ or the _Harsanyi interaction_, to measure the interaction between each specific set \(S\subseteq N\) of input variables (stones) encoded by the model \(v\). Each interaction \(S\), _e.g._, \(S_{2}=\{1,3,8\}\) in Figure 1, denotes a certain shape of stones. If all stones in \(S\) are placed on the board, then the interaction will make a numerical effect on the advantage score \(v(x)\). Thus, we can consider the interaction as an AND relationship \(I(S_{2})=w_{S_{2}}\cdot[\textit{exist}(x_{1})\&\textit{exist}(x_{3})\&\textit{exist}(x_{8})]\) encoded by \(v\), where the Boolean function \(\textit{exist}(\cdot)=1\) when the stone is placed on the board; \(\textit{exist}(\cdot)=0\) when the stone is removed. Otherwise, the removal of any stones in \(S\) will deactivate the effect, _i.e._, making \(I(S|\mathbf{x}_{\text{masked}})=0\). Such an interaction effect can be measured from the value network based on the following definition.

\[I(S)\stackrel{{\text{def}}}{{=}}\sum\nolimits_{T\subseteq S}(-1) ^{|S|-|T|}\cdot v(\mathbf{x}_{T}) \tag{1}\]

where \(\mathbf{x}_{T}\) denotes the state when we keep stones in the set \(T\) on the board, and remove all other stones in \(N\setminus T\). Thus, \(v(x_{T})\) measures the advantage score of the masked board state \(\mathbf{x}_{T}\).

\(\bullet\)**Sparsity of interactions and interaction primitives.** Although we can sample \(2^{n}\) different subsets of variables from \(N\), _i.e._, \(S_{1},S_{2},S_{3},...,S_{2^{n}}\subseteq N\), Li and Zhang (2023), Ren et al. (2023b) have discovered and proved that a well-trained DNN usually only encodes a small number of interactions in some common conditions3. In other words, most interactions \(S\subseteq N\) defined in Equation (1) usually have almost zero effect, \(I(S)\approx 0\). Only a few interactions \(S\in\Omega_{\text{salient}}\) have considerable effects, _s.t._\(|\Omega_{\text{salient}}|\ll 2^{n}\). In this paper, we set a threshold \(\xi=0.15\cdot\max_{S}|I(S)|\) to select salient interactions, \(\Omega_{\text{salient}}=\{S:|I(S)|>\xi\}\).

Footnote 3: Please see Appendix B for more detailed introductions of common conditions.

We can consider the small number of salient interactions \(S\in\Omega_{\text{salient}}\) as primitive inference patterns encoded by the value network, namely **interaction primitives**, because Theorem 1 shows that these interaction primitives can always well mimic the network outputs no matter how we randomly mask the input sample \(\mathbf{x}\).

**Theorem 1** (proved by Ren et al. (2023a)).: _Let us randomly mask a given input sample \(\mathbf{x}\) to obtain a masked sample \(\mathbf{x}_{T}\). The output score of the DNN on all \(2^{n}\) randomly masked samples \(\mathbf{x}_{T}\) w.r.t. \(\forall T\subseteq N\) can all be approximated by the sum of effects of a small number of salient interactions._

\[v(\mathbf{x}_{T})=\sum\nolimits_{S\subseteq T}I(S)\approx\sum\nolimits_{S\in\Omega_ {\text{salient}},S\subseteq T}I(S) \tag{2}\]
Theorem 1 shows that when we remove stones in a random set \(N\setminus T\) from the board state \(\mathbf{x}\) and obtain a masked state \(\mathbf{x}_{T}\), the output score \(v(\mathbf{x}_{T})\) of the value network on \(\mathbf{x}_{T}\) can be explained by a small number of salient shape patterns encoded by the value network.

\(\bullet\)**Complexity of the interaction primitive.** The complexity of an interaction primitive \(S\) is defined as the order of the interaction, _i.e._, the number of stones in \(S\), \(\text{order}(S)=|S|\). An interaction primitive of a higher order represents a more complex interaction with more stones.

### Extracting sparse and simple interaction primitives

To teach people about new patterns to play the game of Go, we first extract interaction primitives encoded by the value network. We consider them as shape patterns used by the value network to estimate the winning probability. To this end, we need to address the following three challenges.

\(\bullet\)**Challenge 1. Extending AND interactions to OR interactions.** The original Harsanyi interaction just represents the AND relationship between a set of stones encoded by the network. However, compared to most other applications, the game of Go usually applies much more complex logic (Shin et al., 2020, 2021), so we extend AND interactions in Equation (1) to OR interactions. We simultaneously use these two types of interactions to explain the Go game.

Logically, an OR relationship can be represented as the combination of binary logical operations "AND" and "NOT." For example, we represent the effect of an AND interaction \(S=\{1,2,3\}\) as \(I_{\text{and}}(S)=w_{S}^{\text{and}}\cdot[\textit{exist}(x_{1})\&\textit{exist}(x_{2})\&\textit{exist}(x_{3})]\), where \(\&\) represents the binary logical operation "AND." In comparison, the effect of an OR interaction \(S=\{1,2,3\}\) is represented as \(I_{\text{or}}(S)=w_{S}^{\text{or}}\cdot[\textit{exist}(x_{1})|\textit{exist}(x_{2})| \textit{exist}(x_{3})]=w_{S}^{\text{or}}\cdot\{-[(\textit{-exist}(x_{1}))\&( \text{-exist}(x_{2}))\&(\text{-exist}(x_{3}))]\}\), where \(|\) represents the binary logical operation "OR," and the Boolean function \(\neg\textit{exist}(\cdot)=1\) when the stone is removed, \(\neg\textit{exist}(\cdot)=0\) when the stone is placed on the board.

Therefore, we consider the advantage score of the value network \(v(\mathbf{x}_{T})\)_w.r.t._ any masked sample, \(\forall T\subseteq N\), intrinsically contains the following two terms.

\[\forall T\subseteq N,v(\mathbf{x}_{T})=v_{\text{and}}(\mathbf{x}_{T})+v_{\text{or}}( \mathbf{x}_{T}) \tag{3}\]

where the advantage term \(v_{\text{and}}(\mathbf{x}_{T})\) is exclusively determined by AND interactions, and the advantage term \(v_{\text{or}}(\mathbf{x}_{T})\) is exclusively determined by OR interactions. Later, in Equation (6), we will introduce how to automatically learn/disentangle \(v_{\text{and}}(\mathbf{x}_{T})\) and \(v_{\text{or}}(\mathbf{x}_{T})\) from \(v(\mathbf{x}_{T})\).

Just like in Equation (1), the AND interaction is redefined on the advantage term \(v_{\text{and}}(\mathbf{x}_{T})\), and is given as \(I_{\text{and}}(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\cdot v_{\text{and}}(\mathbf{x}_ {T})\). Similarly, an OR interaction \(S\) is measured to reflect the strength of an OR relationship between stones in the set \(S\) encoded by the model \(v_{\text{or}}\). If any stone in \(S\) appears on the board, then the OR interaction \(S\) makes an effect \(I_{\text{or}}(S)\) on the score \(v_{\text{or}}(\mathbf{x})\). Only all stones in \(S\) are removed from the board, the effect \(I_{\text{or}}(S)\) is removed. Thus, we can define the effect \(I_{\text{or}}(S)\) of an OR interaction \(S\) on the model output \(v_{\text{or}}(\mathbf{x})\), as follows.4.

Footnote 4: Please see Appendix D for the proof.

\[I_{\text{or}}(S)=-\sum\nolimits_{T\subseteq S}(-1)^{|S|-|T|}v_{\text{or}}(\bm {x}_{N\setminus T}),\quad S\neq\emptyset \tag{4}\]

**Theorem 2** (proved in Appendix C).: _The OR interaction effect between a set \(S\) of stones, \(I_{\text{or}}(S)\) based on \(v(\mathbf{x}_{T})\), can be computed as a specific AND interaction effect \(I_{\text{and}}^{\prime}(S)\) based on the dual function \(v^{\prime}(\mathbf{x}_{T})\). For \(v^{\prime}(\mathbf{x}_{T})\), original present stones in \(T\) (based on \(v(\mathbf{x}_{T})\)) are considered as being removed, and original removed stones in \(N\setminus T\) (based on \(v(\mathbf{x}_{T})\)) are considered as being present._

**Theorem 3** (proved in Appendix E).: _Let the input sample \(\mathbf{x}\) be randomly masked. There are \(2^{n}\) possible masked samples \(\{\mathbf{x}_{T}\}\) w.r.t. \(2^{n}\) subsets \(T\subseteq N\). The output score on any masked sample \(\mathbf{x}_{T}\) can be represented as the sum of effects of both AND interactions and OR interactions._

\[v(\mathbf{x}_{T})=v(\mathbf{x}_{\emptyset})+v_{\text{and}}(\mathbf{x}_{T})+v_{\text{or}}( \mathbf{x}_{T})=v(\mathbf{x}_{\emptyset})+\sum\nolimits_{S\subseteq T,S\neq\emptyset }I_{\text{and}}(S)+\sum\nolimits_{S\cap T\neq\emptyset,S\neq\emptyset}I_{ \text{or}}(S) \tag{5}\]

To automatically learn the disentanglement of AND interactions and OR interactions, we set \(\forall T\subseteq N,v_{\text{and}}(\mathbf{x}_{T})=\frac{1}{2}v(\mathbf{x}_{T})+p_{T}\) and \(v_{\text{or}}(\mathbf{x}_{T})=\frac{1}{2}v(\mathbf{x}_{T})-p_{T}\), which satisfies \(\forall T\subseteq N,v(\mathbf{x}_{T})=v_{\text{and}}(\mathbf{x}_{T})+v_{\text{or}}( \mathbf{x}_{T})\), so that the learning of the disentanglement of \(v_{\text{and}}(\mathbf{x}_{T})\) and \(v_{\text{or}}(\mathbf{x}_{T})\) is equivalent to the learning of \(\{p_{T}\}_{T\subseteq N}\). \(p_{T}\in\mathbb{R}\) denotes a learnable bias term. Furthermore, we notice that small unexplainable noises in the network output can be enlarged in interactions5. To overcome this problem, we slightly revise the original network output \(v(\mathbf{x}_{T})\) as \(v(\mathbf{x}_{T})+q_{T}\), where \(q_{T}\in\mathbb{R}\) is a small scalar contained within a small range, \(|q_{T}|<\tau\)6. The parameter \(q_{T}\) is learned to represent the unavoidable noises in the network
output, which cannot be reasonably explained by AND interactions or OR interactions. According to the Occam's Razor, we use the following loss function to learn the sparse decomposition of AND interactions and OR interactions.

\[\min_{\mathbf{p},\mathbf{q}\in\mathbb{R}^{2n}}\|\mathbf{I}_{\text{and}}\|_{1}+\|\mathbf{I}_{\text {or}}\|_{1}\quad\text{s.t.}\quad\forall S\subseteq N,|q_{S}|<\tau \tag{6}\]

where \(\|\cdot\|_{1}\) represents L-1 norm function, \(\mathbf{p}=[p_{S_{1}},p_{S_{2}},...,p_{S_{2^{n}}}]^{\top}\) denotes the bias terms for all masked boards. \(\mathbf{q}=[q_{S_{1}},q_{S_{2}},...,q_{S_{2^{n}}}]^{\top}\). \(\mathbf{I}_{\text{and}}=[I_{\text{and}}(S_{1}),I_{\text{and}}(S_{2}),...,I_{\text {and}}(S_{2^{n}})]^{\top}\) and \(\mathbf{I}_{\text{or}}=[I_{\text{or}}(S_{1}),I_{\text{or}}(S_{2}),...,I_{\text{or }}(S_{2^{n}})]^{\top}\) denote AND interactions and OR interactions, respectively. AND interactions \(\{I_{\text{and}}(S)\}_{S\subseteq N}\) are computed by setting \(v_{\text{and}}(\mathbf{x}_{T})=\frac{1}{2}\cdot[v(\mathbf{x}_{T})+q_{T}]+p_{T}\), and OR interactions \(\{I_{\text{or}}(S)\}_{S\subseteq N}\) are computed by setting \(v_{\text{or}}(\mathbf{x}_{T})=\frac{1}{2}\cdot[v(\mathbf{x}_{T})+q_{T}]-p_{T}\) in Equation (4).

\(\bullet\)**Challenge 2. Verifying that the inference logic of the value network can be explained as sparse interaction primitives.** Although Ren et al. (2023) have proved that a well-trained DNN usually just encodes a small number of AND interactions between input variables for inference under some common conditions3, it is still a challenge to strictly examine whether the value network fully satisfies these conditions. Although according to Theorem 2, the above OR interaction can be considered as a specific AND interaction, in real applications, we still need to verify the sparsity of interactions encoded by the value network for the Go game.

Footnote 3: Please see Appendix G for the reason why the saturation problem causes high-order interactions.

Therefore, we experimentally examine the sparsity of interactions on the KataGo Wu (2019), which is a free open-source neural network for the game of Go and has defeated top-level human players. We extract interactions encoded by the value network of the KataGo. Specifically, we use KataGo to generate a board state by letting KataGo take turns to play the moves of black stones and those of white stones. Let there be \(m\) stones on the board. Considering the exponentially large cost of computing interactions, we just select and explain \(n=10\) stones (\(n\leq m\)), including \(\frac{n}{2}\) white stones and \(\frac{n}{2}\) black stones, and limit our attention to interactions between these \(n\) stones. All other stones on the board can be considered as constant background, whose interactions are not computed. Figure 2 shows the strength \(|I(S)|\) of effects of different AND interactions and OR interactions in a descending order. It shows that only a few interactions have salient effects, 80\(\%\)-85\(\%\) interactions have negligible effects. It verifies that interactions encoded by the value network are sparse.

\(\bullet\)**Challenge 3. How to ensure that the inference logic of the value network can be explained as simple interaction primitives?** We find a problem that most interaction primitives extracted from the KataGo are high-order interaction primitives (see Figure 4). The high order of interaction primitives significantly boosts the difficulty of extracting common shape patterns widely used in different games. It is because high-order interactions are usually considered to be "special shapes" in a specific game, instead of simple (low-order) shape patterns frequently used in different games. For example, as Figure 3 (b) shows, 3-order interaction primitives \(S_{1},S_{2},S_{3}\) extracted from the board state \(\mathbf{x}^{(1)}\) can be transferred to another board state \(\mathbf{x}^{(2)}\). However, the 8-order interaction primitive \(S_{4}\) extracted from \(\mathbf{x}^{(1)}\) cannot be transferred to another board state \(\mathbf{x}^{(2)}\).

The reason for the emergence of high-order interactions is that most training samples for the value network are usually biased to states with similar numbers of white stones and black stones, because in real games, the board always contains similar numbers of white stones and black stones. Such a bias leads to the following saturation problem, which makes most interaction primitives be high-order primitives7. We use \(\Delta n(T)=n_{\text{while}}(T)-n_{\text{black}}(T)\in\{-n/2,-n/2+1,...,n/2\}\) to measure the unbalance level of the masked state \(\mathbf{x}_{T}\), where \(n_{\text{while}}(T)\) and \(n_{\text{black}}(T)\) denote the number of white stones and that of black stones on \(\mathbf{x}_{T}\), respectively. As Figure 3 (a) shows, we compute the average advantage score over all masked states \(\mathbf{x}_{T}\) with the same unbalance level \(k\in\{-n/2,-n/2+1,...,n/2\}\), \(A_{k}=\mathbb{E}_{\mathbf{x}}\mathbb{E}_{T\subseteq N:\Delta n(T)=k}\log(\frac{p_{ \text{shift}}(\mathbf{x}_{T})}{1-p_{\text{shift}}(\mathbf{x}_{T})})\). We find that

Figure 2: Strength of effects of all AND interactions and OR interactions in descending order. Only a small number of interactions have salient effects on the output of the value network.
this average advantage score \(A_{k}=\mathbb{E}_{\mathbf{x}}\mathbb{E}_{T\subseteq N:\Delta n(T)=k}\log(\frac{p_{ \text{white}}(\mathbf{x}_{T})}{1-p_{\text{white}}(\mathbf{x}_{T})})\) is not roughly linear with the \(k\) value, but is saturated when \(|k|\) is large. This is the main reason for high-order interactions [7].

In order to alleviate the above saturation problem, we revise the advantage score \(v(\mathbf{x}_{T})\) in Equation (1) to remove the value shift caused by the saturation problem, _i.e._, \(u(\mathbf{x}_{T})=v(\mathbf{x}_{T})-a_{k}\). Given a masked state \(\mathbf{x}_{T}\), we compute its unbalance level \(k=\Delta n(T)=n_{\text{white}}(T)-n_{\text{black}}(T)\in\{-n/2,-n/2+1,...,n/2\}\). \(a_{k}\) is initialized as the average advantage score \(A_{k}\). We extend the loss function in Equation (6) as follows to learn the parameters \(\mathbf{a}=[a_{-\frac{n}{2}},a_{-\frac{n}{2}+1},...,a_{\frac{n}{2}}]^{\top}\in \mathbb{R}^{n+1}\).

\[\min_{\mathbf{p},\mathbf{q}\in\mathbb{R}^{2^{n}},\mathbf{a}\in\mathbb{R}^{n+1}}\|\mathbf{I}_{ \text{and}}\|_{1}+\|\mathbf{I}_{\text{or}}\|_{1}\quad\text{s.t.}\quad\forall S \subseteq N,|q_{S}|<\tau \tag{7}\]

We learn parameters \(\mathbf{p}\), \(\mathbf{q}\), and \(\mathbf{a}\) to obtain the sparse decomposition of AND interactions \(\mathbf{I}_{\text{and}}=[I_{\text{and}}(S_{1}),I_{\text{and}}(S_{2}),...,I_{\text{ and}}(S_{2^{n}})]^{\top}\), and OR interactions \(\mathbf{I}_{\text{or}}=[I_{\text{or}}(S_{1}),I_{\text{or}}(S_{2}),...,I_{\text{or }}(S_{2^{n}})]^{\top}\). AND interactions \(\{\mathbf{I}_{\text{and}}(S)\}_{S\subseteq N}\) are computed by setting \(v_{\text{and}}(\mathbf{x}_{T})=\frac{1}{2}\cdot[u(\mathbf{x}_{T})+q_{T}]+p_{T}\), and OR interactions \(\{I_{\text{or}}(S)\}_{S\subseteq N}\) are computed by setting \(v_{\text{or}}(\mathbf{x}_{T})=\frac{1}{2}\cdot[u(\mathbf{x}_{T})+q_{T}]-p_{T}\) in Equation (4). The small threshold \(\tau=0.38\) is set to be the same as in Equation (6)

_Penalizing high-order interactions._ Besides, we can further add another loss to Equation 7 to penalize high-order interactions, _i.e._, \(Loss=\|\mathbf{I}_{\text{and}}\|_{1}+\|\mathbf{I}_{\text{or}}\|_{1}+r\cdot\|\mathbf{I}_{ \text{and}}^{\text{high}}\|_{1}+\|\mathbf{I}_{\text{or}}^{\text{high}}\|_{1}\), where \(\mathbf{I}_{\text{and}}^{\text{high}}\) denotes a 386-dimension vector that corresponds to 386 interactions of the 6-th-10-th orders in the vector \(\mathbf{I}_{\text{and}}\). In this loss, we set \(r=5.0\) to boost the penalty of high-order interactions.

_Experiments._ We conduct experiments to check whether above methods can reduce the complexity (order) of the extracted interactions, compared with the original interactions extracted by methods in Equation (6). Specifically, we follow experimental settings in Challenge 2 to generate a board, and compute AND-OR interactions between selected \(n\) stones. Then, we compute the average strength of AND-OR interactions of different orders, \(\mathbb{E}_{S:|S|=m}[|I_{\text{and}}(S)|]\) and \(\mathbb{E}_{S:|S|=m}[|I_{\text{or}}(S)|]\), respectively. Figure 4 shows the average strength of interaction effects. For both AND interactions and OR interactions, we observe that the revised method generates much weaker high-order interactions than the original method in Equation (6). This verifies the effectiveness of the revised method to reduce the complexity of the extracted interactions.

_Sparsity of interactions extracted by the revised method._ We follow experimental settings in Challenge 2 to generate 50 game states, and visualize the strength of all AND interactions and all OR interactions of all these 50 game states in a

Figure 4: Average strength of effects for interactions of different orders. For different games, the revised method extracts weaker high-order interactions than the original method.
descending order. Figure 5 (a) shows that only a few interactions have salient effects, more than 90\(\%\) interactions have small effects, which verifies the sparsity of interactions extracted by the revised method.

_Still satisfying the universal matching property in Theorem 3._ Theoretically, the AND-OR interactions extracted by our revised method can still satisfy the universal matching property in Theorem 3. Furthermore, given a board state \(\mathbf{x}\), we conduct experiments to examine whether we can use the extracted AND-OR interactions to approximate the network outputs \(v(\mathbf{x}_{T})\) on all different randomly masked board states \(\{\mathbf{x}_{T}\}_{T\subseteq N}\). To this end, for each arbitrarily masked board states \(\mathbf{x}_{T}\), we measure the approximation error \(\Delta v_{T}=|v^{\text{real}}(\mathbf{x}_{T})-v^{\text{approx}}(\mathbf{x}_{T})|\) of using AND-OR interactions to mimic the real network output \(v^{\text{real}}(\mathbf{x}_{T})\), where \(v^{\text{approx}}(\mathbf{x}_{T})=v(\mathbf{x}_{\emptyset})+\sum_{S\subseteq T,S \neq\emptyset}I_{\text{and}}(S)+\sum_{S\cap T\neq\emptyset,S\neq\emptyset}I_{ \text{or}}(S)\) represents the score approximated by AND-OR interactions according to Theorem 3. In Figure 6, the solid curve shows the real network outputs on all \(2^{n}\) randomly masked board states when we sort all \(2^{n}\) network outputs in an ascending order. The shade area shows the smoothed approximation error, which is computed by averaging approximation errors of neighboring 50 masked board states. Figure 6 shows that the approximated outputs \(v^{\text{approx}}(\mathbf{x}_{T})\) can well match with the real outputs \(v^{\text{real}}(\mathbf{x}_{T})\) over different randomly masked states, which indicates that the output of the value network can be explained as AND-OR interactions.

### Discovering novel shapes from the value network

In the above section, we have extracted sparse and simple interaction primitives from the value network. In this section, we aim to discover novel shapes from these interaction primitives, and use the discovered novel shapes to teach people about the game of Go.

We have examined the sparsity of interaction primitives in experiments. We can usually extract about 100-250 interaction primitives to explain the output score of a single board state. However, the number of primitives is still too large to teach people, and we need a more efficient way to discover novel shapes encoded by the value network. Therefore, we visualize all interaction primitives, and then identify some specific combinations of stones that frequently appear in different interaction primitives. We refer to these combinations as "_common coalitions_." For example, given a board state \(\mathbf{x}\) with \(n\) stones, indexed by \(N=\{1,2,...,n\}\) in Figure 1, we can extract some salient interactions from the board state \(\mathbf{x}\), such as \(S_{1}=\{1,3,4,5,8\},S_{2}=\{1,3,8\},S_{3}=\{1,3,8,9\}\), _etc_. The coalition \(T=S_{1}\cap S_{2}\cap S_{3}=\{1,3,8\}\) participates in different interactions \(T\subseteq S_{1},S_{2},S_{3}\). We can consider this coalition \(T\) as a _classical shape pattern_ encoded by the value network.

Therefore, we further compute the attribution \(\varphi(T)\) of each coalition \(T\) to the advantage score \(v(\mathbf{x})\) estimated by the value network. In this way, a positive attribution \(\varphi(T)>0\) means that the shape pattern of the coalition \(T\) tends to enhance the advantage of white stones. In comparison, a negative attribution \(\varphi(T)<0\) means that the shape pattern of the coalition \(T\) tends to decrease the advantage score. \(\varphi(T)\approx 0\) means that although the coalition \(T\) is well modeled by the value network, the coalition \(T\) has contradictory effects when it appears in different interactions, thereby not making a significant effect on the advantage score.

There are a lot of attribution methods (Lundberg and Lee, 2017; Selvaraju et al., 2017; Zhou et al., 2016; Zintgraf et al., 2017) to estimate the attribution/importance score of different input variables of an AI model, _e.g._, estimating the attributions of

Figure 5: (a) Strength of all revised AND interactions and revised OR interactions of all 50 games in a descending order. Only a few interactions have salient effects on the output of the value network. (b) Interaction context of the coalition.
different image patches to the image-classification score, or the attributions of different tokens in natural language processing. However, there is no a widely accepted method to estimate the attribution of a coalition of input variables, because most attribution methods cannot generate self-consistent attribution values8. Therefore, we apply the method [Xinhao Zheng, 2023] to define the attribution of a coalition \(T\). This method extends the theory of the Shapley value and well explains the above inconsistency problem. Specifically, the attribution score \(\varphi(T)\) of the coalition \(T\) is formulated as the weighted sum of effects of AND-OR interactions, as follows.

Footnote 8: We use the following example to introduce the inconsistency problem. We can simply consider a coalition \(T\) (_e.g._, \(T=\{1,2,3\}\)) of input variables as a singleton variable \([T]\), then we have a total of \(n-2\) input variables in \(N^{\prime}=\{[T],4,5,...,n\}\). Let \(\varphi([T])\) denote the attribution of \([T]\) computed on the new partition \(N^{\prime}\) of the \(n-2\) variables. Alternatively, we can also consider \(x_{1}\), \(x_{2}\), \(x_{3}\) as three individual variables, and compute their attributions \(\varphi(1)\), \(\varphi(2)\), \(\varphi(3)\) given the original partition of input variables \(N=\{1,2,...,n\}\). However, for most attribution methods, \(\varphi([T])\neq\varphi(1)+\varphi(2)+\varphi(3)\). This is the inconsistency problem of attributions.

\[\varphi(T)=\sum\nolimits_{S\supseteq T}\frac{|T|}{|S|}[I_{\text{and}}(S)+I_{ \text{or}}(S)] \tag{8}\]

\[\varphi(T)-\sum\nolimits_{i\in T}\phi(i)=\sum\nolimits_{S\subseteq N,S\cap T \neq\emptyset,S\cap T\neq T}\frac{|S\cap T|}{|S|}[I_{\text{and}}(S)+I_{\text{or }}(S)] \tag{9}\]

Let there be some AND interactions and OR interactions containing the coalition \(T\). Then, Equation (8) shows that for each interaction \(S\supseteq T\) containing the coalition \(T\), we must allocate a ratio \(\frac{|T|}{|S|}\) of its interaction effect as a numerical component of \(\varphi(T)\). In addition, Appendix H shows a list of theorems and properties of the attribution of the coalition defined in Equation (8), which theoretically guarantee the faithfulness of the attribution metric \(\varphi(T)\). For example, Equation (9) explains the difference \(\varphi(T)-\sum_{i\in T}\phi(i)\) between the coalition's attribution \(\varphi(T)\) and the sum of Shapley values \(\phi(i)\) for all input variables \(i\) in \(T\). The difference comes from those interactions that only contain partial variables in \(T\), not all variables in \(T\). Please see Appendix H for more theorems.

_Experiments._ Given a board state, we extract interaction primitives encoded by the value network, _i.e._, \(\{S:|I(S)|>\xi\}\), where \(\xi=0.15\cdot\text{max}_{S}|I(S)|\). Then, we manually annotate 50 coalitions based on the guidance from professional human Go players. Figure 7 visualizes sixteen coalitions selected from four game states. Figure 5 (b) shows the interaction context of the coalition. Please see Appendix I.3 for more details about the computation of the attribution of the interaction context.

Figure 7: Estimated attributions of different coalitions (shape patterns). Stones in the coalition are high-lighted by red circles.
### Human players' interpretation of the classic shapes/coalitions

In order to interpret shape patterns (coalitions) encoded by the value network, we collaborate with the professional human Go player9. Based on Figure 7, they find both shape patterns that fit common understandings of human players and shape patterns that conflict with human understandings.

Footnote 9: During the review phase, the Go players are anonymous, because they are also authors.

**Cases that fit human understandings.** For the Game 1 in Figure 7 (1.a - 1.d), \(\varphi(\{1,2,3,8\})<\varphi(\{2,3,8\})\) and \(\varphi(\{1,2,3,7\})<\varphi(\{2,3,7\})\). It means that when the white stone \(x_{1}\) participates in the combination of white stones \(x_{2},x_{3}\), the advantage of white stones become lower, _i.e_., the stone \(x_{1}\) is a low-value move. Go players consider that the effect of the combination of white stones \(x_{1},x_{2},x_{3}\) is low. For the Game 2 in Figure 7 (2.a, 2.b), \(\varphi(\{1,5,8\})>\varphi(\{1,2,8\})\) means that the value network considers that the white stone \(x_{5}\) has higher value than \(x_{2}\). Go players consider that in this game state, the white stone \(x_{5}\) protects the white stones \(x_{1},x_{2},x_{3},x_{4}\), and the white stones \(x_{1},x_{3}\) attack the black stones \(x_{6},x_{7}\), but the white stone \(x_{2}\) has much less value than other stones. For the Game 3 in Figure 7 (3.a - 3.c), \(\varphi(S_{1}=\{1,3,8\})>\varphi(S_{3}=\{1,2,3,8\})\) and \(\varphi(S_{2}=\{2,3,8\})>\varphi(S_{3}=\{1,2,3,8\})\), subject to \(S_{3}=S_{1}\cup S_{2}\). Go players consider that the existence of the local shape \(S_{1}=\{1,3,8\}\) makes the move of the stone \(x_{2}\) have a low value, _i.e_., given the context \(S_{1}\), the stone \(x_{2}\) wastes a move, thereby losing some advantages. Figure 7 shows some strange shape patterns that go beyond the understandings of human Go players.

**Cases that conflict with human understandings.** For Game 3 in Figure 7 (3.d, 3.e), \(\varphi(\{6,7,8\})=1.00\) and \(\varphi(\{3,6,7\})=-1.15\), Go players are confused that the coalition \(\{6,7,8\}\) is advantageous for white stones, and the coalition \(\{3,6,7\}\) is advantageous for black stones. For Game 4 in Figure 7 (4.a, 4.b), \(\varphi(\{1,2,3,4\})=1.34\) and \(\varphi(\{1,2,3,9\})=-1.71\). It means that the coalition \(\{1,2,3,4\}\) is advantageous for white stones, and the coalition \(\{1,2,3,9\}\) is advantageous for black stones.

## 4 Conclusion

In this paper, we extract sparse interactions between stones memorized by the value network for the game of Go. We regard common coalitions shared by different interactions as shape patterns, and estimate attribution values of these common coalitions. Then, we examine the fitness and conflicts between the automatically extracted shape patterns and conventional human understanding of the game of Go, so as to help human players learn novel shapes from the value network. We collaborate with professional human Go players to provide deep insights into shape patterns that are automatically extracted from the value network.

## Ethic Statement

This paper aims to extract sparse and simple interaction primitives between stones encoded by the value network for the game of Go, thereby teaching people to learn from the value network. Previous methods usually extract AND-OR interactions to represent the primitives encoded by the AI model. However, we discover that although AND-OR interactions have some good mathematical properties, the interaction primitives (shape patterns) extracted by this method are usually extremely complex, _i.e_., the shape patterns usually contain many stones. Such complexity of the extracted shape patterns makes it difficult for people to learn from the value network. Thus, we propose a method to extract sparse and simple interactions encoded by the value network. There are no ethic issues with this paper.

## Reproducibility Statement

We have provided proofs for the theoretical results of this study in Appendix A, B, C, D, E, F, G, H. We have also provided experimental details in Appendix I and more experimental results in Appendix J. Furthermore, we will release the code when the paper is accepted.
