Message Boards Message Boards

Game Trees vs. Game DAGs

Posted 2 years ago

A question about the new Stephen Wolfram blog post, Via reddit, andrewl_ :

Are these any different than game trees?

A: If you really want to know, do the calculations!

Thanks to Click-to-copy and WFR, it should be easier than ever to try and keep up. Admittedly, there is a slight delay in getting source code + documentation published. In the meantime we can at least use the fully-functional Click to Copy. In all of the following functions wrapped by C2C[fun] can be grabbed from the blog post or the attached notebook (thanks Nik!):

TreeQ[C2C[TTTData]["GameGraph"]]
Out[]=False

It would be nice if the following actually worked, but it doesn't:

TimeConstrained[
 gameTree = C2C[MultiwayDeletionsGraph][C2C[TTTData]["GameGraph"]],
 60]

Not my fault! According to wikipedia, this Tree Graph should have 255,168 leafs, which could probably mean 500K+ vertices in total--And we don't really want to sit around waiting for that to compute.

Instead we can just count unique the paths through the DAG using DirectedAcyclicEvaluate::

PathCountTTT = Association[
   ResourceFunction["DirectedAcyclicEvaluate"][
     C2C[TTTData]["GameGraph"], {_List :> 1}
     ]["VertexWeights"]];

And use this meta-data to get the big numbers:

Total[PathCountTTT[#] & /@ Join[
   Flatten[Values[C2C[TTTData]["FirstWinStates"]], 1],
   C2C[TTTData]["DrawStates"][9]]]
Out[] = 255168

Total[Values[PathCountTTT]]
Out[]= 549946

But as a further example, let's try MultiwayDeletionsGraph on the 2x2 X's and O's game. In fact, we don't even need NestWhileGraph because the state space is small and easy to enumerate directly:

gtt1 = Graph[ResourceFunction["ToDirectedAcyclicGraph"][
   NearestNeighborGraph[Select[
     Tuples[{-1, 0, 1}, 4], 0 <= Total[#] < 2 &]  ], {0, 0, 0, 0}],
  VertexCoordinates -> Automatic,
  GraphLayout -> "LayeredDigraphEmbedding"]

gtt2 = Graph[C2C[MultiwayDeletionsGraph][gtt1,  {{0, 0, 0, 0}}],
 GraphLayout -> "LayeredDigraphEmbedding",
 AspectRatio -> 1/2]

Out[]=

game dag

game tree

And you can easily verify in this particular case that path count on the DAG equals leaf count on the tree. But what is actually happening here? And what is happening in general?

The new state-space exploring function MultiwayDeletionsGraph (soon to be a WFR) typically does not produce TreeGraph outputs. Blog sections "Walks and Their Multiway Graphs" and "The Icosian Game & Some Relatives" show examples from the more general case where exploration paths can be confluent by first branching apart and later merging together. However, the inputs in subsequent sections are state spaces without time ordering. What happens in general is that two paths visit the same graph components but in different order, but that certainly can not happen if vertices are uniquely associated with a time.

In the case of a directed acyclic input to MultiwayDeletionsGraph, I think it is not too difficult to prove that the output must be a tree, and if the input DAG is a game DAG, then the output tree is a game Tree. In every such case I would expect that pathcount via DirectedAcyclicEvaluate should give the same answer as leaf count on the game tree.

However, what we really want to know about is FAIRNESS, another metric computable by DirectedAcyclicEvaluate. Fairness is related to partial probabilities by time reversal symmetry. In fact, there is a nice theorem with obvious analogs about time-ordered, quantum mechanical propagators, which regrettably did not make it past the outline stage of the writing process. :( As is often said, more work remains to be done...

POSTED BY: Brad Klee
4 Replies

(Comment zero: "Game DAGs" is an unappealing name, and the popularity of game theory shows just how important nomenclature is. However, for the lack of an alternative, I will keep using it below).

It may be interesting to contrast not only game trees and game DAGs, but (both with) games in extensive form. Game trees are explicitly confined for (two-player) sequential games of perfect information. As far as I understand, game DAGs are also meant to be used in a similar context (as well as for "puzzles", i.e.(?), decision problems with perfect information). Games in extensive form allow for the modelling of imperfect information through the use of information sets.

Initially, I thought that game trees were used instead of something like game DAGs purely by historical accident, or perhaps because game trees were easier to generate (you don't have to worry about conflating identical game states). [Note: I'm sure though that Chess/Go engines actually work on game DAGs - it would be immensely wasteful to multiply the calculations on game states that are merely reached by a different sequence of moves. So when those who write engines for Chess/Go AI claim they work with "game trees", they may simply not express themselves accurately].

Now, I suspect game trees were usually discussed in this "raw form" because they are easier to transform into an extensive form game which also features information sets.

Grand Project Question: to what extent and how can the functions used here and in the Games & Puzzles blog post be transferred for analyzing (at least two-player) games with sequential moves but incomplete information?

POSTED BY: Zsombor Méder

The nomenclature doesn't worry me too much, but would using "game graph" or optionally "directed acyclic game graph" at least avoid the pitfall of throwing around acronyms?

As to your important question--The tools we developed are highly localized, and their main drawback is that they don't automatically deal with loop termination. Aside from that, the real problem is that some state spaces are just too big to fully enumerate (think chess). This problem already shows up when the game graph exceeds say 100,000 vertices.

Let's say we have an extraction or a fragment of the game graph, which is small enough not to break the system. The fragment should be generated as comprehensively as possible, to ensure no gains or losses are missed. The farthest look-ahead nodes will have imperfect information, which could possibly be represented by probabilistic values. These would be computed directly from naive scoring functions or perhaps more surely from a prepared data set concerning player's experiences winning, losing, and drawing.

To Summarize: If perfect information isn't available, then we can't use a perfect information vertex function with DirectedAcyclicEvaluate, but we can still use a probabilistic vertex function. The farthest look-ahead vertices are initial conditions that need to be set somehow, and if there are loops in the game graph, they need to be unrolled.

POSTED BY: Brad Klee

Unfortunately the Reddit crowd doesn't seem too interested in source code. Oh well, here is the documentation for MultiwayDeletionsGraph anyways. And here's another example of the DAG to Tree theorem:

(* c2c from WFR*)
g1 = Function[{dim}, 
   Graph3D[#, GraphLayout -> "SpringElectricalEmbedding"
      ] &@With[{moves = Association[
        # -> VertexOutComponent[GridGraph[{dim, dim}], #, {1}] & /@ 
         Range[dim^2]]}, 
     ResourceFunction["NestWhileGraph"][
      Thread[{moves[#[[1]]], #[[2]] + 1}] &, {{1, 0}}, 
      UnsameQ[Union[First /@ Flatten[VertexList /@ #, 1]], 
        Range[dim^2]] &, All]]][5]

spacetime graph

ResourceFunction["MultiwayDeletionsGraph"][g1, {{1, 0}}, 
 GraphLayout -> "LayeredDigraphEmbedding", AspectRatio -> 1/2]
TreeGraphQ[%]

tree-ification

MultiwayDeletionsGraph was also analyzed with scrutiny to try and achieve optimal times. During this process I found one nice trick using KeyDrop, which you can read from the source code. In the example above, running up from l.t. 100 vertices to 10K+ takes only about 1 second, decently fast.

To make this more interesting for the audience, let me ask a basic question about graph conversion: Is there a more idiomatic way to "tree-out" a directed acyclic graph (while maintaining eq. between path count and leaf count)? How much faster does it go?

I tried this exercise and obtained a speedup of 5x. However, the more specific function is not good for self-avoiding walks, so please do not mistake this for wasted time! That being said, if you have more optimizations or notice bugs to be fixed, please let me know, thanks! --Brad

POSTED BY: Brad Klee

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: EDITORIAL BOARD
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract