5.1 Introduction

A propositional net (propnet) is a directed bipartite graph consisting of nodes representing propositions connected to connectives (boolean gates and transitions). Propnets serve as a graph representation of Game Description Language (GDL), which expresses the dynamics of a world in terms of the logical relationships of between different propositions. PNs are useful because they allow us to apply our intuitions about graphs to game representations.

A propositionÕs truth value is either a function of incoming transition or set by an agent. The truth value of boolean gates are a function of their inputs. Transitions are identity gates, used to control the flow of information from one state to the next. Propositions can be partitioned into three classes: base propositions, whose truth values are a function of incoming transitions; input propositions, whose truth values are set by agents; and view propositions, whose truth values are a function of incoming boolean gates. The state of a PN is the truth assignment of its base propositions. State update is performed by setting base propositions to true if and only if their incoming transition is true in the current state. Because transitions serve as inputs to base propositions, they define the dynamics of a PN [6].

5.2 GGP With Propnets

5.3 Factoring Propnets

We first formally define what it means for a General Game Playing Propositional Automaton (GGPA) to be conjunctively factorable, and then prove conditions under which a PA is conjunctively factorable. We begin by constructing an appropriate vocabulary for formalizing the equivalence and conjunction of PA. Using this vocabulary, we give a formal definition of conjunctive factorability and prove conditions under which a PA is conjunctively factorable. A General Game Player that can successfully detect these conditions can therefore detect independent conjoined sub-games, and analyze them independently using a preexisitng evaluation technique.

The conjoining of games is an intuitive concept. The conjoining of n >= 2 independent games is the game where the goal of each player is to win all n subgames. A game is conjunctively factorable or decomposable when it is the conjunction of n >= 2 independent sub-games. Truth-functional relationships of propositions in a PN are represented by the connectivity relation. A component pÕs truth value in a PN, except for input propositions, is determined by the component(s) q from which an edge exists from q to p. Here we can apply a graph intuition to a PN to yield an interesting result. Since edges represent truth functional dependency, if a directed path exists from a proposition q to a proposition p then the truth assignment of p depends on the truth assignment of q.

Using the notion of a directed path we can formalize what it means for propositions to be truth-functionally independent of each other. If there is not a directed path from a proposition p to a proposition q then the truth assignment of q in any state is irrelevant to the truth assignment of p.

Corollary 5.3. If there is no directed path from a proposition p to a proposition q then then the truth value of q is not a function of p.

Extending this notion to sets, we can formalize what it means for a set of propositions to be truth-functionally independent of another set of propositions. If two sets of propositions are independent of each other, then they can be reasoned about independently of one another. Definition 5.4. A subseteq (P U G U T), B subseteq (P U G U T) are disconnected iff there is no directed path from any proposition in A to any proposition in B. C subseteq (P U G U T), is independent iff ~(EaEb(a in C & b/ in C & bWa) An independent set , D is action independent if D intersection NI = phi.

The truth values of sets that are disconnected from one another can be reasoned about independently of one another in the current state of a PA. However, this might not be true for reasoning continuously about the disconnected sets, as other propositions outside of the two sets may be affect their truth values. Independent sets (ISs) are connected sub-graphs in a PN, where no outside components serve as inputs to any members of the IS. The truth values of action independent sets (AIS) are functionally independent of the truth assignments of input propositions, whose analogue are actions of agents. Their truth assignments are directly computable given a number of base marking updates and the initial base marking. Since no edges exist from the rest of a PN to an IS, the markings of ISs of a PN can be fully simulated independently of the remaining network. The lack of connection to a PN means that the truth values of the propositions in an IS can be determined regardless of the current or past states of the rest of a PN. Because an IS represents an independent physics within the larger network, an IS represents its own independent PN.

Theorem 5.5. An IS of a PN, C, along with connectivity function wC = w with domain restricted to C, of a PN, N can be represented as an isomorphic PN.

Detecting classes of games that represent independent simultaneous sub-games hinges upon this idea. A necessary condition for conjunctive factorability is the representation of multiple independent physics within the network itself. In order to represent independent sub-games, there need to be separate physics for each of those games. However, it is not a sufficient condition. The Legal proposition itself may cause the separate physics to become joined in determining what actions are legal for a given physics represented as a PN. Consider the conjoining of chess and checkers where a player is only allowed to move their queen after they have captured two pieces. While the physics of the two games are separable, the state of checkers affects the legality of chess, and cannot be considered separately.

We now define equivalence between PNs and PAs. Follow- ing that we provide a definition for equivalence between a single PA and multiple conjoined PA. The notion of equivalence between PNs is straightforward. If there exists a mapping be- tween states of two distinct games that respects the next state operation, them the two games are equivalent. Accordingly there must be a mapping between the set of facts that define a state or NB , that respects next state or base marking update operation in order for two PNs to be considered equivalent. We extend the notion of homomorphism to PNs in order to capture the intended requirements for equivalence.

5.4 Latches

5.5 Reformulation

No matter how we choose to conceptualize the world, it is important to realize that there are other conceptualizations as well. Furthermore, there need not be any correspondence between the objects, functions, and relations in one conceptualization and the objects, functions, and relations in another.

In some cases, changing one's conceptualization of the world can make it impossible to express certain kinds of knowledge. A famous example of this is the controversy in the field of physics between the view of light as a wave phenomenon and the view of light in terms of particles. Each conceptualization allowed physicists to explain different aspects of the behavior of light, but neither alone sufficed. Not until the two views were merged in modern quantum physics were the discrepancies resolved.

In other cases, changing one's conceptualization can make it more difficult to express knowledge, without necessarily making it impossible. A good example of this, once again in the field of physics, is changing one's frame of reference. Given Aristotle's geocentric view of the universe, astronomers had great difficulty explaining the motions of the moon and other planets. The data were explained (with epicycles, etc.) in the Aristotelian conceptualization, although the explanation was extremely cumbersome. The switch to a heliocentric view quickly led to a more perspicuous theory.

This raises the question of what makes one conceptualization more appropriate than another for knowledge formalization. Currently, there is no comprehensive answer to this question. However, there are a few issues that are especially noteworthy.

One such issue is the grain size of the objects associated with a conceptualization. Choosing too small a grain can make knowledge formalization prohibitively tedious. Choosing too large a grain can make it impossible.

As an example of the former problem, consider a conceptualization of the scene in Figure 1 in which the objects in the universe of discourse %% are the atoms composing the blocks in the picture. Each block is composed of enormously many atoms, so the universe of discourse is extremely large. Although it is in principle possible to describe the scene at this level of detail, it is senseless if we are interested in only the vertical relationship of the blocks made up of those atoms. Of course, for a chemist interested in the composition of blocks, the atomic view of the scene might be more appropriate. For this purpose, our conceptualization in terms of blocks has too large a grain.

Finally, there is the issue of reification. Reification is the process of adding new objects to a schema and new relations on those objects to represent information previously expressed entirely with relations.

Consider a schema with three unary relations red, green, and blue. Each of these relations holds of an object if and only if the object has the corresponding color. Using this formulation, we might have a database like the one shown below.

Another way to represent color information is to reify colors as objects and to replace the various unary relations with a single binary relation color that associates objects with their colors. In this formulation, the data above would be rewritten as shown below.

Note that it is possible to take this process one step farther, reifying the concept of color as well and capturing data using a ternary relation property that relates a property (like color), an object, and a value (the color value). This formulation allows us to use a single relation to capture multiple properties (such as color, size, material, and so forth).

Note that, in this discussion, no attention has been paid to the question of whether the objects in one's conceptualization of the world really exist. We have adopted neither the standpoint of realism, which posits that the objects in one's conceptualization really exist, nor that of nominalism, which holds that one's concepts have no necessary external existence. Conceptualizations are our inventions, and their justification is based solely on their utility. This lack of commitment indicates the essential ontological promiscuity of AI: Any conceptualization of the world is accommodated, and we seek those that are useful for our purposes.

Exercises

1. Modify your game player so that it plays games using the propositional net representation rather than the state machine representation. Hint: Redefine the state machine access methods in our basic player in terms of the propositional net access methods provided with our basic player. This way, all of the code you have built using the state machine methods will continue to work.


2. Make sure your new player is ready to compete. We will test your player in timed mode on various games. Okay to lose; lots of points off if your player fails to play for whatever reason.