GPU Programming is one of those things that... if I ever had more time for, I'd definitely like to get more into. As such, I have a myriad of ideas and concepts I'd love to try on the GPU.

Yeah yeah yeah, "program, don't just talk" is the online standard. But talking / spitballing / brainstorming is a lot of fun. So lets lighten up a bit and talk about more ambitious projects and/or spitball some ideas.

Something that's been simmering for the past few years for me is a GPU-based Binary Decision Diagram. BDDs are the primary data-structure for representing boolean functions exhaustively. Specifically the classic ROBDD (though there's many competing BDDs)

I'm talking about the actual mathematical relation, the full truth table, the whole gamut, represented in just one data-structure in a unique form. In particular, all collections of boolean functions have exactly one ROBDD, meaning you can simply perform a BDD-X vs BDD-Y equivalency test to prove that two different boolean synthesis are equivalent.

I've spitballed this idea plenty of times before in the Puyo Puyo community (a relatively obscure Japanese puzzle game), as perhaps the basis of an AI. In particular, Puyo Puyo players are able to "foresee" good patterns vs bad patterns, and my theory is that a BDD representing all possible drops (regardless of the random-number generator) can allow an AI to plan ahead in a simple greedy fashion.

BDDs have a peculiar set of properties you see that make them ideal for solving #P-complete problems (that is: counting-NP complete). You can determine the number of solutions to a BDD in linear time (!!!), though the creation of the BDD in the first place is #P-complete (ie: probably harder than NP-complete).

I have a feeling that expert human players are foreseeing the future in this manner. There are patterns our eyes see when playing this game, and its seemingly akin to a BDD being manipulated and calculated (each BDD manipulation is exponential time in worst-case, but linear time in optimistic cases).

Where the GPU comes in is that each "branch" of the BDD can be explored and calculated in parallel. A BDD at its root has 2-branches, then 4 after the 2nd generation, then 8 after the 3rd generation, (etc. etc.) worst-case scenario. Furthermore, all operations are recursive, local.

This means that BDDs could be explored, and calculated, by a parallel system. In theory anyway. This leads to an interesting parallel vs sequential paradox: the more efficient the BDD, the more sequential it is (the more of a straight-line it looks like). But the less-efficient the BDD is, the more parallel it is (ie: the more parallel branches can be explored in... erm... parallel). This means that a GPU would be inefficient at small, efficient, linear BDDs... but far superior at large, inefficient, exponentially branching BDDs. An AI that relies upon GPUs traversing BDDs would have to bet on "enough" inefficient branching to make parallelism worth it, but "not enough" branching to make it infeasible / NP-complete exponential.

So maybe its one of those things I should solve with CPU-algorithms sequentially first. But... heh... too many side projects in any case.

Anyway, I've got a lot of other project ideas to spitball. But lets talk about some, especially if yours is a parallel problem that might be able to be done on a GPU.