Logic loop with no transitions

[ggp-org]

Logic loop with no transitions

[AlexLandau]

I haven't double-checked this specific game's validity, but it is indeed possible for a valid GDL game description to result in cycles in a propnet that don't include transition gates.

The guarantee that stops this from being absurd is that if the GDL is valid, there won't be any NOT gates in the cycle. (This follows from the GDL spec's restrictions on recursion.) As a result, semantics along the following lines will result in correct values:

1. Evaluate everything leading up to the cycle.
2. Set everything in the cycle to false.
3. Reevaluate each node in the cycle according to the usual logic. This can change values from false to true, but not the other way around.
4. Repeat step 3 until nothing changes.

The key is that step 3 will change things from false to true, but not from true to false. Because there are no NOT gates, one node in the cycle becoming true can't cause another node in the cycle to change from true to false.

Why is this something we want to allow? Consider the game hex, where we're trying to determine whether a path connects two edges of the board. One way to express this in a propnet is to add an AND gate for every possible path across the board. This is obviously prohibitively expensive.

Another approach is to have a sentence that answers the question, "Is the space ?x, ?y on a red path that touches the left side of the board?" It's easy to define this recursively: it's true for red spaces on that edge, and it's true for red spaces next to other red spaces where that question is true. The issue is that this path can pass in either direction through any pair of spaces in the middle of the board, so we have to incorporate that logic going both ways, causing a cycle between their nodes in the propnet. (In fact, we end up with a large number of interconnected cycles.) Nonetheless, this representation stays compact, and gives the right answer (if the approach described above is used).

The ongoing GGP course may want to have a guarantee that the games it uses won't have cycles in its propnets, since this is relatively rare and can be difficult to implement correctly.

[SteveDraper]

Thanks for the explanation. I'll check out the game hex as a test case - I assume it's already there on one of the regular repositories? (If not do you happen to have a GDL formulation you could post?)

Sent from my iPad

On Oct 22, 2013, at 5:15 PM, AlexLandau [email protected] wrote:

I haven't double-checked this specific game's validity, but it is indeed possible for a valid GDL game description to result in cycles in a propnet that don't include transition gates.

The guarantee that stops this from being absurd is that if the GDL is valid, there won't be any NOT gates in the cycle. (This follows from the GDL spec's restrictions on recursion.) As a result, semantics along the following lines will result in correct values:

Evaluate everything leading up to the cycle.
Set everything in the cycle to false.
Reevaluate each node in the cycle according to the usual logic. This can change values from false to true, but not the other way around.
Repeat step 3 until nothing changes.
The key is that step 3 will change things from false to true, but not from true to false. Because there are no NOT gates, one node in the cycle becoming true can't cause another node in the cycle to change from true to false.

Why is this something we want to allow? Consider the game hex, where we're trying to determine whether a path connects two edges of the board. One way to express this in a propnet is to add an AND gate for every possible path across the board. This is obviously prohibitively expensive.

Another approach is to have a sentence that answers the question, "Is the space ?x, ?y on a red path that touches the left side of the board?" It's easy to define this recursively: it's true for red spaces on that edge, and it's true for red spaces next to other red spaces where that question is true. The issue is that this path can pass in either direction through any pair of spaces in the middle of the board, so we have to incorporate that logic going both ways, causing a cycle between their nodes in the propnet. (In fact, we end up with a large number of interconnected cycles.) Nonetheless, this representation stays compact, and gives the right answer (if the approach described above is used).

The ongoing GGP course may want to have a guarantee that the games it uses won't have cycles in its propnets, since this is relatively rare and can be difficult to implement correctly.

—
Reply to this email directly or view it on GitHub.

[AlexLandau]

I wrote a version, but never got around to writing a stylesheet for it, so I haven't posted it anywhere. (The Stanford repo has a version that works differently, by tracking connected components turn-by-turn.) Note that test_case_5c should also cause loops in the propnet.

Here's my version:

;;;
;;; A new version of Hex, on a 5x5 grid.
;;; Written by Alex Landau
;;;

(role red)
(role blue)

(init (control red))

(<= (next (control red))
(true (control blue)))
(<= (next (control blue))
(true (control red)))

(<= (legal ?player noop)
(role ?player)
(not (true (control ?player))))

(<= (legal ?player (mark ?x ?y))
(true (control ?player))
(coord ?x)
(coord ?y)
(not (true (cell ?x ?y red)))
(not (true (cell ?x ?y blue))))

(<= (next (cell ?x ?y ?player))
(does ?player (mark ?x ?y)))
(<= (next (cell ?x ?y ?player))
(true (cell ?x ?y ?player)))

(<= (adjacent ?x ?y1 ?x ?y2)
(coord ?x)
(or (succ ?y1 ?y2) (succ ?y2 ?y1)))
(<= (adjacent ?x1 ?y ?x2 ?y)
(coord ?y)
(or (succ ?x1 ?x2) (succ ?x2 ?x1)))
(<= (adjacent ?x1 ?y1 ?x2 ?y2)
(succ ?x1 ?x2)
(succ ?y2 ?y1))
(<= (adjacent ?x1 ?y1 ?x2 ?y2)
(succ ?x2 ?x1)
(succ ?y1 ?y2))

;Calculate which cells are in the path from one side to the other
(<= (redPath 1 ?y)
(true (cell 1 ?y red)))
(<= (redPath ?x2 ?y2)
(true (cell ?x2 ?y2 red))
(adjacent ?x1 ?y1 ?x2 ?y2)
(redPath ?x1 ?y1))
(<= redPathComplete
(redPath 5 ?y))
(<= (bluePath ?x 1)
(true (cell ?x 1 blue)))
(<= (bluePath ?x2 ?y2)
(true (cell ?x2 ?y2 blue))
(adjacent ?x1 ?y1 ?x2 ?y2)
(bluePath ?x1 ?y1))
(<= bluePathComplete
(bluePath ?x 5))

;Terminality and goals
(<= terminal
redPathComplete)
(<= terminal
bluePathComplete)
(<= (goal red 0)
(not redPathComplete))
(<= (goal red 100)
redPathComplete)
(<= (goal blue 0)
(not bluePathComplete))
(<= (goal blue 100)
bluePathComplete)

(coord 1)
(coord 2)
(coord 3)
(coord 4)
(coord 5)
(succ 1 2)
(succ 2 3)
(succ 3 4)
(succ 4 5)

(<= (base (cell ?x ?y ?player))
(coord ?x)
(coord ?y)
(role ?player))
(<= (base (control ?player))
(role ?player))
(<= (input ?player noop)
(role ?player))
(<= (input ?player (mark ?x ?y))
(role ?player)
(coord ?x)
(coord ?y))

[AlexLandau]

It looks like cubicup_3player is indeed valid. Namely, the recursion restriction from section 5.3 in the GDL specification is satisfied: http://logic.stanford.edu/classes/cs227/2013/readings/gdl_spec.pdf

Nothing to fix here, so I'll close this issue.