Study material on factoring

I don't have any academic material to point you at, but I can provide a very high level outline of how Sancho performs its factoring analysis (which is not based on any other work). Essentially it boils down to:

1) Build and perform normal optimizations (nothing to do with factoring) on a propnet (just to get the smallest propnet we can to analyze from)

2) Build a dependency map of which base and input props each base prop depends on non-transitively (so stopping at transitions and inputs, but when calculating the dependencies of an input itself start from its corresponding legal)

3) From the map generated in (2) create a full transitive map (if A depends on B, and B depends on C then mark A as also dependent on C)

4) Identify the subset of base props that only depend on other base props, and is closed under the dependency operation (that is base props that are not dependent on inputs, or on base props that are themselves dependent on inputs). This subset (which may be empty in some games) we term the 'control set'. It's usually things like step counters and who has control in non-simultaneous move games)

5) Examine the terminal (and goal) networks to see if they are disjunctive (currently we only factorize disjunctively factorizable games by this analysis). If they are, construct the transitive dependency set for each disjunct (do this independently for the terminal network and each goal value).

6) From each such identified dependency set remove the control set if it appears.

7) Identify sets of the disjunctive dependency sets formed by different possible unions of them, such that the resulting sets form a partition (define an equivalence relation) on both the base props (apart from the control set) and the moves [allow some base prop and moves to map to a null set if necessary]

8) If you can identify such a partitioning of the base and input props, then it is a disjunctive factor, and may be independently searched.

9) Create a state mask of the base props that appear in each factor, and another mask for the moves (legals) that appear in it. When given a starting state to search from (say at the start of the game, or the start of a move) search independently in each factor, using the masks to create factor states, and legal moves within the factor

There are some tricky parts associated with determining terminality within a factor (the overall propnet might require a legitimate state in EVERY factor to calculate terminality correctly), but it's addressable in various ways (most cleanly by generating fresh propnets for the factors only, though that's not actually what we do); and also with deciding which factor's move to play in cases where multiple factors have multiple choices available (those cases also require the introduction of pseudo-noops to each factor, but the only game I am aware of that requires this is Breakthrough w/walls)

Some other situations that can be argued to be factorization cases (multiple TicTacToe, multiple Hamilton, ...) we don't handle by explicit factorization, but instead by simple elimination of irrelevant parts of the game (those that cannot impact our eventual goal state). This has some complications of its own (moves in 'irrelevant' sub-games can actually be viewed as noops in the 'relevant' part, and if that game has any sort of Zugzwang concept, then they need to be retained, at least as noops). Also this can lead to what amounts to elimination of irrelevant opponents (roles whose moves have no impact at all on our own eventual goal value), which requires some special handling.

Finally there is one more case we handle, which might be argued to be factorization, which is Sudoku-like games. The analysis needed there relies on some of the dependency information used in the disjunctive factor analysis and some of the concepts of a partitioned move-space, but is quite complex and not otherwise related to the above. I plan a blog post to talk about much of this in more detail at some point (but probably not until at least July 29th ;-))