Group Abstract Group Abstract

Message Boards Message Boards

Game Trees vs. Game DAGs

Posted 3 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
Posted 2 years ago
POSTED BY: Brad Klee
Posted 3 years ago
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