Comments (4)
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.
from ggp-base.
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.
from ggp-base.
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))
from ggp-base.
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.
from ggp-base.
Related Issues (20)
- Error Loading Project: Cannot load facet Scala (ggp-base-master) HOT 2
- Fix HumanNewMovesEvent constructor HOT 1
- "and" operator not a recognized literal in GdlFactory.createLiteral(Symbol symbol) HOT 1
- Better support for testing visualizations in browsers
- Move to Java 8 HOT 1
- Add option to select all gamers in kiosk HOT 3
- Question: Where can I find more GGP domains (kif files) ? HOT 2
- DeORer does not correctly handle `not` literals HOT 1
- OPNF bug in test case 5d
- Javadoc has errors HOT 2
- Automatic detection of player connection HOT 3
- Bad JVM arg in build.xml/build.gradle HOT 3
- Make StaticValidator use Griddle validation library HOT 1
- A GGP game HOT 1
- Add ability to abandon running games in the Server app HOT 3
- Expose game versioning in GameRepository HOT 2
- Add explicit versioning and publish versioned .jars HOT 12
- ClassCastException when constructing Gdl programmatically HOT 5
- HTML parsing library for visualizations messes up divs HOT 4
- Server app: Case-insensitivity can pollute XML output to subsequent games
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ggp-base.