kd-tree algorithms, Qix, and human-assisted fun!

I reviewed some parallel versions of kd-tree spatial partitioning algorithms for a study group earlier this summer. I've always thought there are some very intriguing parallels between kd-tree algorithms and the classic videogame Qix. It's likely that this was intentional on the game designers' part, but there is still a lot we can learn from observing the function of both.


Pictures (from top): kd-tree partitioning, screenshot of Qix.
kd-tree

Qix emulator

A kd-algorithm (k = number of subdivisions, d = number of dimensions) partitions n-dimensional space in an optimal manner. The approach is called "kd-tree" beacuse the partitioning proceeds hierarchically. Each subpartition is represented by a set of child nodes in a classification tree, so that the number of levels in the tree are equivalent to the number of subpartitions. So, for example, if you divide a 2-D space (e.g. square) in half, the next subdivision will occur on both of the resulting rectangles, resulting in bisection which can be applied recursively. The purpose of partitioning space is to assign objects in the space to a series of optimally-derived sets. This is the case because each partitions is symmetrical. Thus, you could employ a kd-tree algorithm to assign spatially-distributed points into a classification scheme, or to subdivide a volume into increasingly smaller partitions. Pure computational applications of kd-tree searches involve discovering nearest-neighbor relationships between sets of points in a space. This algorithm runs in O(log N) time, which means that a relationship between the number of subpartitions required and the time it takes to approximate solutions is sublinear, with higher numbers of subpartitions taking exceptionally long to approximate.

By contrast, the objective in Qix is to "secure" asymmetrical partitions of a square while avoiding a spiraling series of line segments called the Qix in addition to several sparks that follow along the perimeter of non-partitioned space. The player must claim space up to 75% of the area to advance to the next level. In doing such, the player takes a number of chunks or varying size and shape, from very large to very small. While recursion is possible in Qix, it is not the partitions that are subdivided, but rather the original square. As you can see, even though the objectives of Qix are not identical to the kd-tree algorithm, Qix can provide some insight into how kd-tree or its variants might be solved, a situational algorithm if you will.


Picture of strategies from top: middle, concentric, and lateral.
Middle Strategy

Concentric Strategy

Lateral Strategy

In these examples, several strategies can be employed, all of them with the same goal, but taking variable amount of time to achieve. There are additional costs, especially for the lateral strategy, of losing turns and subpartition size. This variable amount of time to completion is based on where the partitions are made and their size, as the Qix and sparks obstacles are moving targets so to speak. As a result, the tree representation of a Qix game is highly irregular, with missing children and a variable depth (as compared to a fixed parameter value for k in kd-tree strategies). In addition, while Qix offers no fixed target or goal for optimization, it does provide a mechanism for constraint optimization.

This connection (kd-Qix, if you like) also got me thinking about human-assisted solutions to optimization algorithms. In artificial intelligence, there exists an idea called AI-completeness. Analogous to NP-completeness, the idea is that any conceivable artificial intelligence will not be able to approximate or solve certain problem solutions, and so human knowledge/expertise must be added. While the kd-tree algorithm is not formally classified as AI-complete, perhaps optimization can be helped along in some contexts by adding in real-time human knowledge/expertise. There are also some interesting information-theoretic consequences related to the different Qix strategies (see examples above)and their related partition size distributions that could be of use to the study of kd-tree optimization.

Here are some examples of human-assisted computing applications from the scientific literature (not directly related to this problem, but still useful):

Human-Assisted Motion Annotation


Human-Assisted Graph Search: It’s Okay to Ask Questions


As a side note, Qix is an example of the understated elegance of early videogames: the designers often used a very simple underlying principle or mechanism (primarily because early videogames designs had little graphical support or computational power to back them up, at least judged by today's standards). So the designers had to be creative in making games that people actually wanted to play.

Algorithms for Parallel Universes (potentially)

This last week, I attended a seminar called "Proven Algorithmic Techniques for Manycore Processors", presented by the Virtual School of Computational Science and Engineering (VSCSE), which is sponsored by the NCSA at the University of Illinois Urbana-Champaign (the same people who head up the Blue Waters supercomputer initiative). The topic was developing algorithms suitable for the architecture of many-core processors. This seminar opened by eyes to the challenges imposed by large, non-uniform datasets, not only in the context of parallel computing, but also as a broader research topic for statisticians and applied mathematics.

The focus of this seminar was on applications for the Graphical Processing Unit (GPU) technology developed by nVIDIA. The level and extent of instruction, especially from Dr. Hwu, was excellent. This is part of the NCSA summer school initiative, which is very useful for covering niche topics. I attended the "Big Data for Science" seminar last year, which was also very good). Here are my written notes from the session (I always find that written notes helps along the learning process).