Example 4.5
In two players, perfect-information games, such as chess, checkers and GO, there are two adversary players who alternate in making moves. At each turn, each player makes one move according to the rules of the game which define both what moves are legal and what effect each possible move will have. Each player has complete information about his opponent’s position and all available choices, viewing the opponent’s failure as his own success. The game begins from a specified initial state and ends in a position that can be defined as a win for one player and a loss for the other, or possibly as a draw based on the same criterion.
An AND/OR tree, or game tree, is a representation of whole possible plays of the game. The root node denotes the initial position of the game, its successors are the positions that the first player can reach in one move, and their successors are the second player’s replies, and so on. Terminal or leaf nodes are labeled as WIN (1), LOSS (–1) or DRAW (0). Each path from the root to a leaf node represents a different complete play of the game, as shown in
Fig. 4.2.
The moves available to one player from a given position can be represented by OR links, whereas the moves available to his opponent are AND links, since each of them must be considered in response.
We call the first player MAX and his opponent MIN. Correspondingly, the game positions where it is MAX’s or MIN’s turn to move are named as MAX and MIN positions, respectively. We distinguish between MAX and MIN positions using a different node shape: the former is represented by squares and the latter by circles. The leaf nodes are labeled as WIN, LOSS or DRAW, depending on whether they represent a win, loss or draw position from MAX’s viewpoint.
At the root node, player MAX has three choices. If MAX chooses 0 → 1, MIN 1 → 4, and MAX only 4 → 10, terminal node 10 marked ‘1’, MAX win. If after MAX chooses 0 → 1, MIN chooses 1 → 5 rather than 1 → 4, then MAX has 2 choices: either 5 → 11 or 15 → 12, if the former, MAX reaches terminal node 11 marked ‘0’-draw, otherwise, MAX reaches node 11,…
Once the leaf nodes are assigned their WIN–LOSS–DRAW status, each node in the game tree can be labeled as WIN, LOSS, or DRAW by a bottom-up labeling procedure. The labeling procedure is the following.
As shown in
Fig. 4.3, let’s walk through the analysis of the game tree from left to right and from bottom to top. Terminal node 10 is assigned as ‘1’, then node 4 is assigned as ‘1’ as well, since MAX only has one choice at node 4. Terminal nodes 19 and 20 are assigned as ‘–1’ and ‘1’, respectively. At node 12, MIN has two choices, 12 → 19 and 12 → 20, and has assignments ‘–1’ and ‘1’, respectively. MIN chooses the minimal one ‘–1’, i.e., 12 → 19. Then, the assignment of node 12 is ‘–1’. At node 5, MAX has two choices, 5 → 11 and 5 → 12, and has assignment ‘0’ and ‘–1’, respectively. MAX chooses the maximal one ‘0’, i.e., 5 → 11. Then, the assignment of node 5 is ‘0’. Finally, we have the overall assignments as shown in
Fig. 4.3. The root node is assigned as ‘0’. This means that MAX has a strategy such that he does not lose the game no matter what
strategy MIN used. Similarly, MIN has a strategy such that he does not lose the game no matter what strategy MAX used.
Figure 4.3 The Assignment of a Game Tree A strategy for MAX is to explore a sub-graph T∗ (or sub-tree) of graph T which is rooted at s and contains one successor of every non-terminal MAX node in T∗ and all successors of every non-terminal MIN node in T∗. The sub-graph T∗ is called a solution graph.
As mentioned in
Chapter 1, many reasoning processes can be explicitly represented by AND/OR graphs (or trees). AND/OR graphs and OR graphs differ only in the relations between nodes and their successors. The former has two kinds of nodes. The MAX positions are OR nodes which are identical to the nodes in OR graphs. The MIN’s positions are AND nodes which are unique to AND/OR graph since a response must be contemplated to each of them. If
T∗ is a solution sub-graph, all its leaf nodes have been assigned. The assignment of a non-terminal OR node is the minimal one among assignments of all its successors. The assignment of a non-terminal AND node is the maximal one among assignments of all its successors. The assignment process going through from bottom to up, finally, we have the assignment of root node. It is called the assignment of solution graph
T∗.
Solution graph T∗ having the maximal assignment at root node is called the optimal solution graph or the optimal strategy for player MAX. Therefore, the optimal strategy of a finite game can be transformed into solving the optimal solution graph of a corresponding AND/OR graph.
In a rule-based first-order logic deductive system, if axioms and reasoning rules are given, the verification of a goal formula can be transformed into whether the formula belongs to
a solution graph of an AND/OR graph. Certainly, the backward reasoning can be used as well, i.e., whether there is a solution graph with the given goal formula as its root and given facts as its leaves.
A backward reasoning example is given below.
Example 4.6
From known facts and reasoning rules, infer whether TEACHER (zhang) has retired or not.
Known Facts:
PROFESSION (zhang) = TEACHER
EDUCATION-AGE (zhang) = 45
Reasoning Rules
R
1: TEACHER (
x)
AGE (
x) ≥ 60
SEX (
x) = MALE → RETIRE
R
2: TEACHER (
x) → UNDERGRADUATE (
x)
R
3: UNDERGRADUATE (
x) → AGE (
x) ≥ 20
R
4: EDUCATION-AGE (
x) → AGE (
x) ≥
y + 20,…
The known facts are assigned as ‘1’ as shown in
Fig. 4.4. If
b is an AND node and has successors
, the assignment
of
b is
, where
is an assignment of
. If
b is an OR node and has successors
, the assignment
of
b is
. Finally, the assignment of root node is ‘1’, i.e., the confirmation of RETIRE (zhang).
Figure 4.4 Backward Reasoning The above discussion is confined to deterministic cases, i.e., both facts and reasoning rules are certainty. The problem is that when both known facts and reasoning rules are uncertain, how can a reasoning model be established? As discussed in Section
4.3, uncertain information can be represented at different grain-size worlds. And a reasoning function defined on a set of edges
D depicts the uncertainty of causal relations.
In the next section, our discussion will focus on the projection and synthesis problems of AND/OR reasoning model.