Arithmetic in GDL

As a rather minimalist language, GDL doesn't have any native support for arithmetic. This hasn't stopped games from making use of arithmetic as needed.


In practice, arithmetic is built up in games from a successor function. Everything in GDL has to work on a limited range of values (so we don't end up with an infinite number of true sentences), so the successor function defines the range our arithmetic will work over. It's usually given the name succ (and in practice, is often copied from game to game). It looks like this:

(succ 0 1)
(succ 1 2)
(succ 2 3)
; etc.

Once we have our successor function defined, we can use recursive rules to build up the other arithmetic functions we need, in much the same way they're built up in set theory or analysis courses. Most of these have already been created for various games.

From Reversi, we get a lessThan function:

(<= (lessThan ?x ?y)
    (succ ?x ?y))
(<= (lessThan ?x ?z)
    (succ ?x ?y)
    (lessThan ?y ?z))

And from ad_game_2x2, we get a summation function:

(<= (add ?x 0 ?x)
 (number ?x))
(<= (add ?x ?y ?z)
 (succ ?x ?x1)
 (succ ?y1 ?y)
 (add ?x1 ?y1 ?z))
; number can look like this:
(number 0)
(<= (number ?y)
    (succ ?x ?y))

I don't know of any games that currently use multiplication, but it's not much different from summation:

(<= (mult ?x 0 0)
    (number ?x)
(<= (mult ?x ?y ?z)
    (succ ?ym1 ?y) ; read as "y minus 1"
    (add ?x ?zmx ?z) ; read as "z minus x"
    (mult ?x ?ym1 ?zmx))

Note that these are generally constant throughout a game, so a good rules engine should be able to precompute these values once and avoid the costs associated with recursion. GGP-Base has pre-built functionality that works particularly well with recursive arithmetic rules like these: see the ConstantCheckerFactory.

The one place where arithmetic gets complicated is counting. There is no keyword to find the number of currently true sentences that match a given template, such as the number of one player's pieces on the board. It's easy to check if this number is 0 or not, but for any other comparison it gets harder. (This is the one place where I might advocate adding functionality to GDL to make arithmetic easier. It's an open question how this could be added while keeping recursion in check.)

The first approach that can be used for counting a turn-dependent value is keeping track of the value each turn and modifying it according to the expected change in value each turn. Here's an example from checkers-newgoals (adding some comments to explain):

; Each player starts with twelve pieces. 
(init (piece_count red c12))
(init (piece_count black c12))

; The active player's piece count doesn't change. 
; (This could have been written more simply by
; checking against (true (control ?player)).) 

(<= (next (piece_count ?player ?n))
(or (does ?player (move ?p ?u ?v ?x ?y))
(does ?player (doublejump ?p ?u ?v ?x3 ?y3 ?x ?y))
(does ?player (triplejump ?p ?u ?v ?x3 ?y3 ?x4 ?y4 ?x ?y)))
(true (piece_count ?player ?n)))

; If black made a non-capture move, red's piece count stays the same.
(<= (next (piece_count red ?n))
(does black (move ?p ?x1 ?y1 ?x2 ?y2))
(kingmove black ?x1 ?y1 ?x2 ?y2)
(true (piece_count red ?n)))

; If black made a single capture, red's piece count drops by one.
(<= (next (piece_count red ?lower))
(does black (move ?p ?x1 ?y1 ?x2 ?y2))
(single_jump_capture black ?x1 ?y1 ?x ?y ?x2 ?y2)
(true (piece_count red ?higher))
(minus1 ?higher ?lower))

; If black made a double capture, red's piece count drops by two.
(<= (next (piece_count red ?lower))
(does black (doublejump ?p ?u ?v ?x3 ?y3 ?x ?y))
(true (piece_count red ?higher))
(minus2 ?higher ?lower))

; If black made a triple capture, red's piece count drops by three.
(<= (next (piece_count red ?lower))
(does black (triplejump ?p ?u ?v ?x3 ?y3 ?x4 ?y4 ?x ?y))
(true (piece_count red ?higher))
(minus3 ?higher ?lower))

; ... and similarly for black. We could have used variables for the player names with (opponent _ _) sentences to keep this shorter.

The second approach can do the counting within a single turn. The idea here is that we have some ordering over the possible sentences that can be true: for example, if we want to count the pieces of a certain color on a board, we order all the spaces on the board. Then, we write rules for a class of sentences that basically says, for each possible n, "Of the sentences 0 through n, m of them are true." It's easy to tell for sentence 0, and given the value for n - 1, it's easy to tell the value for n. Then we can just ask for the value once all have been determined.

I used this approach in Reversi, partly due to the fact that many pieces can change colors in a given turn, so the amount to change values in a given turn is already hard to determine. Here's how it looked there (with some extra comments):

; The count starts out at either 0 or 1 at space (1, 1), depending on if it's occupied by our color.
(<= (pieceCount 1 1 ?color 1)
    (true (cell 1 1 ?color)))
(<= (pieceCount 1 1 ?color 0)
    (role ?color)
    (not (true (cell 1 1 ?color))))

; Add one more space along the current column. Add one to n if it's occupied by our color.
(<= (pieceCount ?x ?yp1 ?color ?np1)
    (add ?y p1 ?yp1)
    (pieceCount ?x ?y ?color ?n)
    (succ ?n ?np1)
    (true (cell ?x ?yp1 ?color)))
(<= (pieceCount ?x ?yp1 ?color ?n)
    (add ?y p1 ?yp1)
    (pieceCount ?x ?y ?color ?n)
    (not (true (cell ?x ?yp1 ?color))))

; When we get to the end of a column (y = 8), go to the first space in the next column.
(<= (pieceCount ?xp1 1 ?color ?np1)
    (add ?x p1 ?xp1)
    (pieceCount ?x 8 ?color ?n)
    (succ ?n ?np1)
    (true (cell ?xp1 1 ?color)))
(<= (pieceCount ?xp1 1 ?color ?n)
    (add ?x p1 ?xp1)
    (pieceCount ?x 8 ?color ?n)
    (not (true (cell ?xp1 1 ?color)))) 

; The total count is the value at the last space, (8, 8). 
(<= (totalCount ?player ?n)
    (pieceCount 8 8 ?player ?n))