Some Frills for the Modal Tic-Tac-Toe of Davies and Isard: Semantics of Predicate Complement Constructions

Aravind K. Joshi, Ralph M. WeischedelIJCAI 1973

Introduction

In the early 1970s, as Natural Language Processing (NLP) began to move beyond simple keyword matching, researchers faced the daunting task of representing the deep semantic structures of human language. One particularly challenging area involved "predicate complement constructions"—verbs like force, prevent, realize, and pretend that take other actions or propositions as their objects. This paper explores these constructions within the "Modal Tic-Tac-Toe" environment, a formal laboratory proposed by Davies and Isard. By mapping linguistic theories of presupposition and implication onto the discrete states of a game board, the authors demonstrate the sophisticated modal logic required for even basic natural language interaction.

The Problem of Predicate Complements

The primary difficulty with these verbs lies in their "logical baggage," specifically their presuppositions. In linguistics, a presupposition is an implicit assumption about the world that must be true for an utterance to be appropriate. For example:

  • "I realized it was raining" presupposes that it was, in fact, raining.
  • "I prevented you from winning" presupposes that the opponent was in a position to win.

Mapping these nuances into a computational model is non-trivial. The truth or validity of a sentence depends not just on the current state of the world, but on the intentions of the actors and the set of possible future outcomes.

Methodology: The Tic-Tac-Toe Universe

To study these effects, the authors utilize a restricted "universe of discourse": a 3x3 Tic-Tac-Toe board. In this environment, every possible state, move, and strategy is mathematically defined, allowing for a rigorous evaluation of semantic claims.

The authors categorize verbs into four primary logical classes based on the work of contemporary linguists like Karttunen and the Kiparskys:

  1. Implicative Verbs (e.g., manage): Asserting the verb implies the truth of the complement (e.g., "I managed to win" implies "I won").
  2. Factive Verbs (e.g., realize): The complement is assumed true regardless of whether the main verb is asserted or negated.
  3. Counterfactive Verbs (e.g., pretend): The complement is assumed to be false.
  4. If-Verbs and Only-If Verbs (e.g., force, be in a position to): These create conditional requirements based on the game's state-space.

To evaluate these verbs, the system performs state-space searches. To answer a question like "Could I have prevented you from winning?", the machine must backtrack to a previous board state, generate all possible branching move sequences, and determine if any path existed where the opponent's victory was impossible.

Key Insights

Presupposition Checking

A significant finding is that the AI's most critical task is often not calculating the next move, but verifying the "hidden" assumptions in a user's input. If a player asks, "Why did you prevent me from winning?" when they never actually had a winning strategy, the AI cannot simply answer "I didn't." It must address the failed presupposition directly to maintain a coherent dialogue.

Compositionality and Goal Simulation

The paper highlights the complexity of "stacking" these verbs. A sentence like "I realize I could have prevented you from winning" requires the system to compose the logic of a factive verb (realize) with a negative-if construction (prevent). Furthermore, to understand verbs like help or pretend, the machine must simulate a "theory of mind," temporarily swapping its own goal (winning) for another (losing or playing sub-optimally) to evaluate the opponent's perspective.

Contextual Synonymy

In the narrow world of Tic-Tac-Toe, certain verbs that are distinct in general language become computationally synonymous. For instance, "helping me win" and "allowing me to win" both trigger the same search for a winning strategy, even though they carry different social connotations in human interaction.

Conclusion and Limitations

While the Tic-Tac-Toe environment provides a valuable sandbox, the authors acknowledge its "sterile" nature. Real-world language contains ambiguities that a discrete game board cannot capture. Interestingly, they note a "paradox of definition": as the environment becomes more strictly defined, it becomes harder to interpret certain nuances because the human elements of intent and social context are stripped away.

Ultimately, the paper suggests that studying "local synonymies"—how different verbs converge in meaning within specific, specialized tasks—is a promising path forward for understanding how humans and machines can communicate effectively within complex domains.

Summary updated

BibTeX
@inproceedings{joshi1973some,
  author = {Aravind K. Joshi and Ralph M. Weischedel},
  title = {{Some Frills for the Modal Tic-Tac-Toe of Davies and Isard: Semantics of Predicate Complement Constructions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1973},
}
Figure