Relational Structures and Logic

Relational structures are used to represent the state of the game in Toss, and logic is used to define move constraints, payoffs and also heuristic position evaluation functions and dynamics. It is therefore essential to get a feeling for relational structures and logic before starting to work on new games. To make it easier to understand and play with these concepts, we created the Relational Structures Explorer. Go there, click on the examples, especially the 3x3 grid, and test your formulas before moving on to create a new game.

Creating Games

Games in Toss are stored in .toss files that consist of a sequence of move rules and then the game locations with payoffs. These files might not be easy to read at first, but if you already explored relational structures and logic it should not be too hard. Start with reading the definition of Tic-Tac-Toe and then look below to see how a few standard games are defined in Toss. You can use these files as a starting point for your own definitions.

• Breakthrough
• Checkers
• Chess
• Connect4
• Gomoku
• Tic-Tac-Toe

Game Grammar

In this section we introduce the grammar used for writing games in Toss. A complete game is a relatively complex object, so we proceed step by step.

Formulas and terms are used in Toss to define the winning condition and the preconditions of the rules. An example formula is ex u (C(x, u) and R (u, y)). It says that there exists an element u which is in relation C with x and R with y. This might not sound like much, but if C is the next-in-column relation and R is the next-in-row relation, then this formula defines the diagonal. The grammar for formulas and terms is as follows.

  f := t > 0 | t = 0 | R(x,...,y) | not f | f and f | f or f | ex x f | all x f 
  t := :(f) | g(x) | t + t | t * t | t ^ t | Sum (x | f : t) 
    

Note that we also defined terms — they are like formulas but evaluate to numbers, not just to true and false. The term :(f) evaluates to 1 if the formula f holds and to 0 otherwise. You can also write terms of the form g(x), where g is a real-valued function defined in the structure.

Structures are used in Toss to represent the state of the game in any single moment of time. They consist of a number of elements, relations beween elements, and functions from elements to real numbers. Here is an example of a structure with three elements, a, b, c, with a and b connected by the relation E, and with a function x with values 1, 2, 3 for a, b, c.

    [ c | E { (a, b) } | x { a -> 1, b -> 2, c -> 3 } ]
    

Note that elements that are anyway in the relations do not need to be specified in the first part (but they can). The general grammar for structures is [ comma-sepatared elements list | semicolon-separated relation list | semicolon-separated function list ], where relations are given by name { semicolon-separated tuple list } and functions by name { comma-separated list of element -> value }.

Rules in Toss games are structure rewriting rules and are specified in the following way.

    RULE name: structure -> structure emb relations with embedding
      pre formula post formula update eq-system
    

In the above, relations is just a comma-separated list of names, embedding is [comma-separated list of elem <- elem] and specifies the partial function, and update is a semicolon-separated list of equations of the form :g(e) := t where g is a function (in the new structure, after applying the rule) and t is a term that will be evaluated in the old structure.

Locations are the states in which the game can be (besides the current structure) and they specify which moves are possible and which payoffs the players get if they cannot move. They have the following form.

    LOC number { list of PLAYER number { PAYOFF t MOVES
      semicolon-separated list [rule-name, params -> loc-number] }
    

The params can specify additional parameters the player can choose, e.g. the time interval for a rule, and can be omitted. MOVES should be omitted if there are none.

Games, finally, have the following form.

    PLAYERS comma-separated number list
    list of REL name (args) = formula
    list of rules
    list of locations
    START structure
    

The REL name(args) = formula part in front allows to define relations that are later used in formulas and shorten the notation. START says which is the starting structure. Refer to the examples above for more!