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))

Thank you very much for this, it has been very useful so far.

ReplyDeleteJust one thing though, your multiplication example doesn't work:

1) It's missing a bracket to close the first implication

2) Even with that bracket filled in, I still can't get it to work all the time. In all but a few situations, running it hangs indefinitely, and I have no idea why.

I'm really struggling with this second issue, and I've been trying to solve it for a couple of days now with no luck. Any hints?

(It might be helpful to know that the only cases I've found where the multiplication doesn't hang are:

- with the second argument being 0, e.g. (mult 2 0 ?z) --> ?z = 0

- with the second argument being 1, e.g. (mult 2 1 ?z) --> ?z = 2

- with a complete sum, e.g. (mult 2 2 4) --> this is true)

Thanks for the information.

DeleteHow it runs is going to depend on what kind of interpreter/rule engine you're using. In a backward-chaining context, it can also depend on what the "query" is, i.e. which variables are bound vs. unbound when the rules are invoked.

However, looking at it again, assuming a backward-chaining theorem prover approach like the GGP-Base ProverStateMachine, it would probably benefit from reordering the conjuncts in the second rule:

(<= (mult ?x ?y ?z)

(succ ?ym1 ?y) ; read as "y minus 1"

(mult ?x ?ym1 ?zmx)

(add ?x ?zmx ?z)) ; read as "z minus x"

And if the "add" rule you're using is the one listed in the article, it will be faster (in uncached situations) when the second argument is the smaller one, so this should be even faster:

(<= (mult ?x ?y ?z)

(succ ?ym1 ?y) ; read as "y minus 1"

(mult ?x ?ym1 ?zmx)

(add ?zmx ?x ?z)) ; read as "z minus x"

I didn't have as good an intuition about prover performance when I first wrote this article. If ?z isn't specified, the original approach would iterate over each possible combination of ?z and ?zmx in "add", and then check if each works in the recursive call to mult. This reordering, by contrast, will work its way down to a y=0 query in linear time, then add its way back to the full value. (This is still slow when dealing with large numbers, but the ProverStateMachine and possibly other interpreters can permanently cache the results of queries with unchanging results; gradually the arithmetic queries get filled out and these become fast.)

That said, this approach could still have problems if ?y is unbound. I guess that's another lesson about GDL arithmetic (where backwards-chaining is used); different combinations of bound and unbound variables can call for different formulations of rules.

If you can get back to me about what interpreter you're using and whether this change works, I can update the post.

Oh wow, thank you for all your help. It worked wonderfully!

DeleteI'm not trying to run it in anything overly complicated, I was just testing a game I was trying to write, in Stanford's Gamestepper.

Now, it works almost all the time. The only two cases in which the new version hangs are when both the first and second variables are unbound (and the last is either bound or unbound). All the other cases terminate nicely with the right answer. This goes for both of your new versions - though I haven't tested which one is quicker.

Thank you again for your help.

I wonder about GDL-II and the representation of card game, especially with Deck and Hand. As far as I know GDL doesn't support list natively. Do you know some information about this?

ReplyDelete