Picturing the propnet of a game using code from GGP Base

Lars Ericson
Junior Member

Posts: 67

Picturing the propnet of a game using code from GGP Base Jul 19, 2015 19:00:10 GMT -8

Quote

Post by Lars Ericson on Jul 19, 2015 19:00:10 GMT -8

GGP Base has the parts necessary to picture the propnet of a game. Consider for example onestep:

(role white)

(role black)

(init o1)

(legal white a)

(legal white b)

(legal black a)

(<= (next o2)

(does white a)

(true o1))

(<= (next o3)

(does white b)

(true o1))

(<= (goal white 0) (true o1))

(<= (goal white 10) (true o2))

(<= (goal white 90) (true o3))

(<= (goal black 0) (true o1))

(<= (goal black 90) (true o2))

(<= (goal black 10) (true o3))

(<= terminal (true o2))

(<= terminal (true o3))

The propnet for this is:

PROPNET FOR ONESTep

This notation doesn't conform precisely to that used in the GGP course text, but for free it's still something. To get this, we define PropNetDiagram.java:

package org.ggp.base.player.gamer.statemachine.sample;

import org.ggp.base.util.game.CloudGameRepository;

import org.ggp.base.util.game.Game;

import org.ggp.base.util.game.GameRepository;

import org.ggp.base.util.propnet.architecture.PropNet;

import org.ggp.base.util.propnet.factory.OptimizingPropNetFactory;

public class PropnetDiagram{

public static void main(String[] args) throws Exception {

GameRepository repo = new CloudGameRepository("games.ggp.org/base");

String gameKey = "onestep";

Game theGame = repo.getGame(gameKey);

PropNet propnet = OptimizingPropNetFactory.create(theGame.getRules());

String gv_file="c:/Users/Lars/Desktop/moves/aha.gv";

String svg_file="c:/Users/Lars/Desktop/moves/aha.gv.jpg";

propnet.renderToFile(gv_file);

RunCmd dot = new RunCmd();

dot.runCmd("dot", "-Tjpg", gv_file, "-O");

dot.runCmd("C:\\Program Files (x86)\\Google\\Chrome\\Application\\chrome.exe", svg_file, "", "");

}

}

This calls pre-existing stuff in GGP and also this function RunCmd (class? everything in Java is a class) I defined:

package org.ggp.base.player.gamer.statemachine.sample;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

public final class RunCmd {

public static void runCmd(String cmd, String arg1, String arg2, String arg3) throws IOException {

Process process = new ProcessBuilder(cmd, arg1, arg2, arg3).start();

InputStream is = process.getInputStream();

InputStreamReader isr = new InputStreamReader(is);

BufferedReader br = new BufferedReader(isr);

String line;

System.out.printf("Output of running %s is:", cmd);

while ((line = br.readLine()) != null) {

System.out.println(line);

}

}

}

I was hoping to experience some epiphany about propnets when I looked at the picture for onestep, which is the simplest game in the base repository. I think I need another donut though, because it isn't calling to me yet.

donuts

Steve Draper
Global Moderator

Posts: 143

Picturing the propnet of a game using code from GGP Base Jul 20, 2015 4:22:36 GMT -8

Quote

Post by Steve Draper on Jul 20, 2015 4:22:36 GMT -8

My experience has been, that when I want to understand what's going on with the generated propnet it's usually on a real game, and the propnet size of nearly all of them precludes being able to render the diagram (with any tool I have found so far - ideally a tool that could render in local parts would be nice, but of course the propnet may not exhibit well-defined locality). Often I just want to look at the logic behind a class of propositions (say the setting of a cell state) and I have tended to resort to manually drawing out the connected logic around one grounded instance by directly reading the DOT file and following id links there (yuck - super-tedious). I think what we really need is some sort of propnet-thinner that takes a full propnet and (probably guided by a template you provide in some way) removes everything that is not within some connection range of one or more starting points (say you might specify the starting point '(true (cell a b x y))' for example, or 'terminal'). Such a tool could probably allow for rendering of interesting 'example' parts of the full grounded propnet in a useful illustrative manner quickly and generally.

Jarrod Torriero
New Member

Posts: 11

Picturing the propnet of a game using code from GGP Base Jul 20, 2015 16:21:11 GMT -8

Quote

Post by Jarrod Torriero on Jul 20, 2015 16:21:11 GMT -8

You haven't specified what it is that you don't understand, so I apologize if this explanation is a bit rudimentary, but here goes:
In order to calculate the values of the components in a propnet, you first need to set the base propositions (technically any proposition that contains a transition as its input, so ( true o1 ), ( true o2 ) and ( true o3 ) in the network pictured) and the input propositions (ie the 'does' propositions, corresponding to the moves chosen by each player). Once these are set, their values are propagated through the network, or, put another way, a mapping is calculated from components to boolean values such that every component maps to a value which satisfies the value of its inputs and the logic operation implemented by the component in question. However, transitions are treated a little differently here. You do not propagate past transition boundaries, and for the final network it isn't necessary that a base proposition's input have the same value as itself. This is because transitions correspond to the values the base propositions will hold in the next step. Whilst the input propositions correspond to chosen moves and thus depend on input from the search (getNextState takes a joint move as an argument, and each move in that joint move corresponds to a different input proposition that should be set to true, whilst all other input propositions should be set to false), the values of the base propositions are deterministically determined by the game description and the moves played so far. To get their values in the first step, you set all the base and input propositions to false and the 'init' proposition to true, then propagate these values through the network until you have a consistent mapping as described above. It may be helpful to think of this as a 'zeroth' step. Once this is done, the values of each base proposition for the first step (ie the initial state) can be set by setting each base proposition to the value of its single input (which is, by definition, a transition component). Once this step is computed you back up the base proposition values and set init to false, never to be made true again. Then, when getNextState is called, you set each input proposition corresponding to the moves in the joint move to true and all other input propositions to false, then propagate until you have a mapping consistent with the base and input values. You then set the base propositions for the next state from the calculated transition values, just as you did to get the initial base proposition values above.

Let's step through the pictured network in this way:

Step 0:

(true o1) = false
(true o2) = false
(true o3) = false
(does white a) = false
(does white b) = false
(does black a) = false
(does black b) = false
init = true

(true o1) is false, so (goal white 0) and (goal black 0) are both false, and both ANDs are false (as they both take (true o1) as an input). As a result, both anons are false and the transitions connecting to (true o2) and (true o3) are false. (true o2) and (true o3) are false by definition, so the goal propositions to which they connect are false, and because they're both false the OR to which they connect is also false, making the terminal proposition false. init is true, making the transition connecting to (true o1) true.

So, the output from this step is this:

all goal propositions are false
terminal = false
(true o1) transition = true
(true o2) transition = false
(true o3) transition = false

Step 1:

We take the base proposition values from the transitions calculated in step 0, so:

(true o1) = true
(true o2) = false
(true o3) = false

For this example, let's say white plays b and black plays a

(does white a) = false
(does white b) = true
(does black a) = true
(does black b) = false
init = false

Now let's propagate:

init is false, so the transition connecting to (true o1) is false.
(true o1) is true, so (goal black 0) = true and (goal white 0) = true. That is, the goal values for both players are 0 in this state. However, this means little since, as we'll soon see, the state is not terminal.
(does white a) is false, so the AND connecting to the left anon is false and so the transition connecting to (true o2) is false.
(does white b) is true and (true o1) is true, so the AND connecting to the right anon is true and the transition connecting to (true o3) is true.
(true o2) and (true o3) are both false (remember, the true value we just calculated for (true o3)'s input transition doesn't come into play until the NEXT step), so like last time, the goal propositions to which they connect are false and the OR is false, making the terminal proposition false (so as I said, we've shown that the state is not terminal).

So, the output from this step is this:
(goal white 0) = true
(goal black 0) = true
all other goal propositions are false
terminal = false
(true o1) transition = false
(true o2) transition = false
(true o3) transition = true

Step 2:

(true o1) = false
(true o2) = false
(true o3) = true

(true o1) is false, so (goal white 0) and (goal black 0) are false and the two ANDs are false. Let's not worry about the input propositions, as they cannot possibly affect the game from here.
(true o2) is false, so (goal white 10) and (goal black 90) are false. The OR might be false, or it might not be.
(true o3) is true, so (goal white 90) and (goal black 10) are true. (true o3) represents a true input to the OR, so the OR is true. The OR is true, so the terminal proposition is true.

We have reached a terminal state. The goal propositions set (note that a valid propnet should have exactly one goal proposition set for each player in a terminal state, no more and no less) are (goal white 90) and (goal black 10). So, the game has ended with scores of 90 and 10 for white and black respectively.

If you didn't already understand the contents of this post, I hope you do now. If not, let me know.

Lars Ericson
Junior Member

Posts: 67

Picturing the propnet of a game using code from GGP Base Jul 20, 2015 17:28:57 GMT -8

Quote

Post by Lars Ericson on Jul 20, 2015 17:28:57 GMT -8

Thanks for stepping through it for me. The intuition I was looking for specifically was to see connected components and cut points in the propnet for Best Buttons and Lights, in the hopes of seeing some way to reduce the problem to simpler sub-problems. Alternatively, by re-simplifying the propnet after each move, to see it split into connected components or a simpler form that is easier to solve. For reference, here is the propnet output from GGP Base for Stanford bestbuttonsandlights:

coursera-forum-screenshots.s3.amazonaws.com/3f/e35f302f4611e584468b8e41a5b373/aha.gv.jpg

Here is another more discouraging and unhelpful view, by running the same DOT file through GEPHI:

coursera-forum-screenshots.s3.amazonaws.com/bb/90a3302f4711e5bac4e52db6f312be/aha_gephi.png

Last Edit: Jul 20, 2015 17:29:52 GMT -8 by Lars Ericson

General Game Playing

Picturing the propnet of a game using code from GGP Base

Post by Lars Ericson on Jul 19, 2015 19:00:10 GMT -8

Post by Steve Draper on Jul 20, 2015 4:22:36 GMT -8

Post by Jarrod Torriero on Jul 20, 2015 16:21:11 GMT -8

Post by Lars Ericson on Jul 20, 2015 17:28:57 GMT -8

Quick Reply