The Annotated Tic-Tac-Toe

Tic-tac-toe is a classic and widely-understood game. Introductions to GDL typically use it as a sample "first game", as the rules are fairly simple and usually already known by the reader. However, the GDL representation can still be foreign enough to be difficult to understand. This post is my attempt to flesh it out with explanations of what each component of the rules is doing. This isn't my first attempt at an introduction to GDL, but different people will find different approaches better.

There are a number of different GDL representations of Tic-Tac-Toe out in the wild. For this exercise, I've chosen the one that's seen the most use lately, Tiltyard's Tic-Tac-Toe. I've taken some liberties with rearranging the rules and improving the formatting, but the rules themselves are untouched. GDL keywords and language features (aside from the <= operator) are in bold. Enjoy!

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Tictactoe
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Roles
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; There are two roles to be assigned to players in tic-tac-toe: one that plays
; X marks and one that plays O marks. The ordering that we list these roles is
; important to the GDL communication protocol, but has no impact on the rules
; of the game; turn ordering, for example, is defined later. As a game author,
; we could swap these two statements to no effect. 

(role xplayer)
(role oplayer)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Initial State
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; In the initial state of the game, each cell of the game board is blank, and
; xplayer is about to move. (Note that "cell" and "control" don't have intrinsic
; meaning in GDL; their meaning comes from how they affect the game in rules
; below.)

(init (cell 1 1 b))
(init (cell 1 2 b))
(init (cell 1 3 b))
(init (cell 2 1 b))
(init (cell 2 2 b))
(init (cell 2 3 b))
(init (cell 3 1 b))
(init (cell 3 2 b))
(init (cell 3 3 b))
(init (control xplayer))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Dynamic Components
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; If the cell (x, y) is blank, and it's a player's turn, then that player may
; play the move "(mark x y)", which represents drawing their mark in the cell
; (x, y). x and y are variables, so actual examples of moves will look like
; (mark 1 1), (mark 2 3), and so on.

(<= (legal ?w (mark ?x ?y))
    (true (cell ?x ?y b))
    (true (control ?w)))

; If it's oplayer's turn, then xplayer can make a noop move. (Noop comes from the
; phrase "no operation" from assembly language, so a noop move does nothing. Games
; are required to give each player at least one possible move each turn, so players
; with nothing to do are given noop moves.)

(<= (legal xplayer noop)
    (true (control oplayer)))

; If it's xplayer's turn, then oplayer can make a noop move.

(<= (legal oplayer noop)
    (true (control xplayer)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Cell

; If xplayer takes the action (mark m n), and the cell (m, n) is blank this turn,
; then next turn the cell (m, n) will contain an X. 

(<= (next (cell ?m ?n x))
    (does xplayer (mark ?m ?n))
    (true (cell ?m ?n b)))

; If oplayer takes the action (mark m n), and the cell (m, n) is blank this turn,
; then next turn the cell (m, n) will contain an O.

(<= (next (cell ?m ?n o))
    (does oplayer (mark ?m ?n))
    (true (cell ?m ?n b)))

; If the cell (m, n) has a mark w in it this turn, and the mark is not "blank",
; the same mark will still be in cell (m, n) next turn.

(<= (next (cell ?m ?n ?w))
    (true (cell ?m ?n ?w))
    (distinct ?w b))

; If either player takes the action (mark j k) to mark the cell (j, k), and the
; cell (m, n) is blank this turn, and the two cells are different (either m != j
; or n != k), then next turn (m, n) will still be blank.

(<= (next (cell ?m ?n b))
    (does ?w (mark ?j ?k))
    (true (cell ?m ?n b))
    (or (distinct ?m ?j)
        (distinct ?n ?k)))

; If this turn oplayer was in control, then next turn xplayer will be in control.

(<= (next (control xplayer))
    (true (control oplayer)))

; If this turn xplayer was in control, then next turn oplayer will be in control.

(<= (next (control oplayer))
    (true (control xplayer)))


; If the cells (m, 1), (m, 2), and (m, 3) all contain the same mark, then we say
; there's a row of that mark at row m.

(<= (row ?m ?x)
    (true (cell ?m 1 ?x))
    (true (cell ?m 2 ?x))
    (true (cell ?m 3 ?x)))

; If the cells (1, n), (2, n), and (3, n) all contain the same mark, then we say
; there's a column of that mark at column n.

(<= (column ?n ?x)
    (true (cell 1 ?n ?x))
    (true (cell 2 ?n ?x))
    (true (cell 3 ?n ?x)))

; If the cells (1, 1), (2, 2), and (3, 3) all contain the same mark, then we say
; there's a diagonal with that mark.

(<= (diagonal ?x)
    (true (cell 1 1 ?x))
    (true (cell 2 2 ?x))
    (true (cell 3 3 ?x)))

; If the cells (1, 3), (2, 2), and (3, 1) all contain the same mark, then we say
; there's a diagonal with that mark.

(<= (diagonal ?x)
    (true (cell 1 3 ?x))
    (true (cell 2 2 ?x))
    (true (cell 3 1 ?x)))


; If there's a row, column, or diagonal with a mark, then we say there's a line
; with that mark.

(<= (line ?x)
    (row ?m ?x))
(<= (line ?x)
    (column ?m ?x))
(<= (line ?x)
    (diagonal ?x))


; If there's some cell (m, n) on the board that's blank this turn, then we say
; the board is open.

(<= open
    (true (cell ?m ?n b)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; If there's a line of X marks, then xplayer gets a score of 100 (win).

(<= (goal xplayer 100)
    (line x))

; If the board is not open and there is neither a line of Xs nor a line of Os,
; then xplayer gets a score of 50 (draw).

(<= (goal xplayer 50)
    (not (line x))
    (not (line o))
    (not open))

; If there's a line of O marks, then xplayer gets a score of 0 (loss).

(<= (goal xplayer 0)
    (line o))

; If there's a line of O marks, then oplayer gets a score of 100 (win).

(<= (goal oplayer 100)
    (line o))

; If the board is not open and there is neither a line of Xs nor a line of Os,
; then oplayer gets a score of 50 (draw).

(<= (goal oplayer 50)
    (not (line x))
    (not (line o))
    (not open))

; If there's a line of X marks, then oplayer gets a score of 0 (loss).

(<= (goal oplayer 0)
    (line x))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; If there's a line of X marks or a line of O marks, the game is over.

(<= terminal
    (line x))
(<= terminal
    (line o))

; If the board is not open, the game is over.

(<= terminal
    (not open))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Base & Input
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; This is an optional part of the game description listing all the types of things
; that can be part of the state of the game on some turn of the game. These rules
; have no effect on the game rules, but some gamers can take advantage of definitions
; like these.

; Note that we only list things that are part of the game state: things that are
; defined using "init" and "next" and referenced using "true". Things that are
; logical consequences of the state, such as "row", "line", and "open", don't get
; listed here.

; 1, 2, and 3 are possible indices of spaces on the game board. We define "index" here
; as a constant set of possibilities that we can reference elsewhere in the game
; description.

(index 1)
(index 2)
(index 3)

; Here we take advantage of the indices listed above to quickly define a set of true
; statements. (We could have done the same when defining the cells that are initially
; blank.)

; A cell (x, y) can be blank, for any valid index x and any valid index y.

(<= (base (cell ?x ?y b))
    (index ?x)
    (index ?y))

; A cell (x, y) can have an x mark or an o mark, for any valid index x and any valid
; index y.

(<= (base (cell ?x ?y x))
    (index ?x)
    (index ?y))
(<= (base (cell ?x ?y o))
    (index ?x)
    (index ?y))

; For each role, it may be that role's turn.

(<= (base (control ?p))
    (role ?p))

; This is another optional part of the game description. Where "base" relations dealt
; with states of the game, "input" relations deal with possible moves. 

; For any role, it is possible for that role to play (mark x y) for any valid
; index x and any valid index y.

(<= (input ?p (mark ?x ?y))
    (index ?x)
    (index ?y)
    (role ?p))
    
; For any role, it is possible for that role to play the noop move.
    
(<= (input ?p noop)
    (role ?p))