A propnet is a graph containing a node for every sentence that can be true according to the game rules. A propnet for tic-tac-toe would contain a node for each of
(cell 1 3 x)*, (line o), and (legal xplayer (mark 2 2)). (There are no variables; the rules have been "flattened" into a form dealing only with fully grounded sentences.)In addition to the proposition nodes, propnets contain nodes representing logic gates. Three types of logic gates suffice: AND gates, OR gates, and NOT gates. The graph is directed, so these gates have inputs and outputs. A gate takes on the value of For example,
(row x), (col x), and (diag x) are all inputs to an OR gate, which has (line x) as an output. All the rules of the game are expressed through these logic gates.In addition, we have transition nodes, which act like flip-flops on a circuit board: they collect outputs from one state that become inputs in the next state. For example, there is a transition node between
(next (cell 1 1 o)) and (cell 1 1 o).If we want to figure out what's going on in a particular state, first we set the base propositions to the appropriate values, then we go through all the other nodes in the graph and set them according to their input values. Then we can go ahead and query the terminal, legal, and goal nodes.
The main use of propnets is to build a rules engine that can be To spread a bit of the conventional wisdom from the aforementioned Stanford class: The players that did best in the class competition tended to involve generating a propnet, then turning it into code which would then be compiled and used as the rules engine.
The propnet-based state machine I originally wrote for the class was roughly as efficient as the ProverStateMachine from GGP-Base, and often slower. (The ProverStateMachine is rather slow relative to Prolog-based rules engines.) When I wrote a new one for Alloy, I knew what I was doing, so the result is in most cases 20 to 100 times faster. When I did an experiment with Java-based compilation, I got similar speedups even though the generated code was much less polished. Sam Schreiber tells me that TurboTurtle's state machine is even faster, by a significant margin.
The main problem with using propnets is building them. This can take a long time and use a lot of memory. In many cases, propnet generation will fail, leaving the gamer to rely on a backup rules engine (assuming it can recover successfully from running out of memory).
Efficient propnet generation can be a difficult problem. I spent a chunk of the summer of 2010 writing the OptimizingPropNetFactory, which will get its own post(s) someday. It can create smaller propnets for a wider variety of games than the original PropNetFactory (both are in GGP-Base), but still runs out of memory on large games like chess or amazons**. There's still room for improvement, but new propnet generation code should leverage what's already been tried and tested instead of starting from scratch. Unfortunately, the OptimizingPropNetFactory code as it stands is poorly factored and difficult to read, and it may be a while before I can adapt it into something more extensible.
Along with using propnets for faster rules engines, I've also experimented with using propnets to reason about games and found it a bit easier to think about than dealing with GDL directly or through a theorem prover. This has included making some reusable tools for reasoning: for example, when a certain set of nodes have certain values, what are the easy-to-find consequences of that (perhaps across multiple turns)? With that tool in place, it's easy to write code to, for example, detect latches (nodes that, once true, are true for the rest of the game). Some of this reasoning has made its way into Alloy.
In short, propnets are a powerful tool for fast rules engines and reasoning about games, but they won't work for every game.
* In the current "standard" for propnet generation, base propositions omit the "true" that normally identifies them. I'm hoping to change this to remove some confusion between sentences and functions. You can do this yourself by commenting out the call to normalizePropositions() in OptimizingPropNetFactory.create().
** The reason it fails on amazons is because of the huge number of moves that are possible: there are 100 squares, and a move specifies three of them (square moved from, square moved to, square that an arrow gets fired at). I believe that if a version of amazons separated the movement and arrow-shooting into separate turns, building a propnet would
No comments:
Post a Comment