Changes in Representation which Preserve Strategies in Games

TL;DR

This paper introduces the concept of an "s-homomorphism" to formally define similarity between games, enabling the transfer of winning strategies. By establishing conditions under which a game can be represented as an s-homomorphic image of a "positional game," the authors provide a framework for applying powerful game-playing methods to a broader class of games.

What Problem Does This Paper Address?

The ease with which a problem can be solved is often heavily dependent on how it's represented. This phenomenon, known as "representation dependence," is a key area of study in artificial intelligence and problem-solving. While changing a problem's representation can sometimes simplify it, it can also make it easier by allowing previously learned problem-solving methods or strategies to be applied. The challenge is to formally define when two different representations of a game are "similar enough" that strategies developed for one can be effectively used for the other. Previous attempts at defining similarity, like homomorphisms, have had limitations, particularly in handling the nuances of game states and strategies. This paper aims to bridge this gap by proposing a new definition of similarity, the s-homomorphism, and exploring its implications for strategy transfer.

Methods

The core contribution of this paper is the definition of the s-homomorphism. Unlike traditional homomorphisms, an s-homomorphism is defined as a relation between the state spaces of two games, rather than a strict mapping. This allows for a more flexible notion of similarity that can accommodate situations where one state in a game might correspond to multiple states in another.

The authors first formally define a game as a 5-tuple (S, R, P, W, L), representing states, moves, player turns, winning states, and losing states, along with a set of postulates to ensure consistent game behavior.

The s-homomorphism (denoted by 'h') is then defined as a subset of the Cartesian product of the state spaces of two games, G and G'. It must satisfy four postulates (H1-H4) that ensure:

  • Symmetric preservation of moves: If a move exists from state 's' to 't' in G, then for any image 's'' of 's' in G', there must be a move from 's'' to some image 't'' of 't' in G' (H1 and H2).
  • Preservation of wins and losses: Winning states in G must map to winning states in G', and losing states to losing states (H3).
  • Preservation of player turns: If a player is on move in state 's', they must also be on move in its image 's'' (H4).

A key theorem (Theorem 1) establishes that if an s-homomorphism exists between two games, a winning strategy in one game can be used to construct a winning strategy in the other.

The paper then introduces "positional games" (defined by N, A, B, representing a set of locations, winning paths for player 1, and winning paths for player 2) and "reducible games" (described by properties). The authors derive sufficient conditions for a game to be an s-homomorphic image of a positional game (Theorem 2), which is crucial for applying existing powerful positional game-playing methods.

Datasets

Not discussed in the paper. The paper uses abstract game definitions and examples like Tic-Tac-Toe, Race, Number Scrabble, and Jam for illustration, rather than specific datasets.

Key Insights and Ideas

  • Similarity is more than just mapping: The s-homomorphism's relational nature is key, allowing for a more nuanced understanding of game similarity than strict mappings, especially when dealing with complex state spaces.
  • Strategies are transferable: The central theorem proves that if two games are s-homomorphic, winning strategies can be transferred between them. This is the primary motivation for defining and studying s-homomorphisms.
  • Bridging game classes: By showing how to represent games as s-homomorphic images of positional games, the paper provides a theoretical basis for applying sophisticated positional game-playing algorithms (like Koffman's) to a wider range of games, including those that might not initially appear positional.
  • Representation matters for strategy: The paper reinforces the idea that the way a problem is represented directly impacts the effectiveness of problem-solving strategies.

Key Results

  • Definition of s-homomorphism: A formal definition of a game similarity that preserves winning strategies.
  • Theorem 1: Establishes the transferability of winning strategies between s-homomorphic games.
  • Theorem 2: Provides conditions under which a reducible game can be an s-homomorphic image of a positional game. This allows existing positional game-playing techniques to be applied to reducible games.
  • Examples: The paper demonstrates the application of these concepts using examples like Race and Tic-Tac-Toe, showing how a race position can have multiple Tic-Tac-Toe images that preserve game strategies.

Limitations and Future Work

  • Scope of Homomorphisms: The authors acknowledge that the s-homomorphism is just one type of homomorphism and that other kinds exist (e.g., graph homomorphisms). They suggest that unifying these into a general class of relations between representations is an open question.
  • Automatic Representation Change: While the theorems provide a foundation, the paper suggests that this work is a "first step towards the automatic change of representation." Further research is needed to fully automate this process.
  • Exhaustive Search: Theorem 1 could potentially lead to an exhaustive search for games with similar strategies, but this would require a repertoire of previously understood games.
  • Generalization of Positional Games: The paper notes that while Theorem 2 establishes a link to positional games, the specific formulation of a game might influence whether it's recognized as positional. The authors surmise that their theorem might be robust enough to recognize positional games regardless of their formulation.
  • Practical Application: The paper focuses on the theoretical underpinnings. While it suggests practical applications for strategy transfer and applying existing algorithms, the direct implementation and empirical validation of these ideas on a large scale are not detailed.

Summary updated

BibTeX
@inproceedings{1971changes,
  title = {{Changes in Representation which Preserve Strategies in Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1971},
}
Figure