I just started writing some code to check statistical properties of Block Party (results will be published soon) and have been thinking about party search quite a bit recently. (For those interested, the code so far can be accessed at the block party github repository.)
Party search is an interesting problem in a few respects, but I want to start with an idea I’m calling a search strategy’s halting distribution. This is a probability distribution over time which shows how frequently an algorithm halts (finds a party) at what times. So, for example, if I always look for all-different parties (call this strategy A) I might expect my halting distribution to be fairly concentrated around a moderate amount of time (since there will almost always be an all-different party, this single routine is very likely to halt). However, looking for all-differents can take longer than, say, looking only at same color. Let strategy B be to first look for a party of the same color, and then failing that find one which is all-different. B will have two density spikes, one early on (since looking at same colors is somewhat easy), and then another which occurs at the time strategy A’s peak occurs plus the amount of time it takes for the same-color algorithm to return null. If A and B both find all-differents in the same amount of time with low enough variance, and if there is no same-color party at least half the time, we should expect A to outperform B.
Now that we have a bit of an understanding about how search algorithms can have different halting distributions, lets consider a mathematical curiosity referred to as nontransitive dice. Suppose (you don’t have to believe that it exists, just pretend!) that there are halting distributions which are proportional to a set of nontransitive dice (they will likely have much more continuous distributions). We now have nontransitive search algorithms, which when run against one another give rise to a rock-paper-scissors cycle. This results in a fascinating metagame in competitive block party wherein players keep track of other players’ party types and adjust their search algorithms to be expected to outperform the others. I would even venture to conjecture that despite non-equal hardware (some people’s brains run some routines faster, call it G or whatever) a (not too much) disadvantaged player could still outperform a better player by playing the metagame properly.
Some future work I’d be excited to explore in this area would be coding algorithms which exhibit different halting profiles given times on subroutines. If this were combined with some scientific research (e.g. if we knew the range of time it can take people to asses which color is most prevalent on a board and other such subroutines, memory constraints, etc.) then we could theoretically model different people playing block party and devise algorithms which optimize given their particular subroutine time distributions. In the shorter term (not requiring human research) it would be fascinating to put together a comprehensive enough library of subroutines with which many party search algorithms can be created and have a competition where, under different parameters of how long subroutines take to operate, algorithms compete head to head. This gets extra interesting when you consider that in a head-to-head match, algorithms are able to see what types of parties the opponent is taking, thereby giving some clues as to what the opposing algorithm’s subprocesses are (and thus clues to the halting profile). This creates a metametagame where programming teams are coding algorithms which have different metagame profiles showing how they evolve and deliberately adding noise to the signal of which strategies they’re using.
Interested in creating the subroutine library or competing in the coding tournament? Want to share your thoughts about party search or other relevant literature? Comment below or email g at 3pxh.com!
[Three Pixel Heart is hiring. If you’re a energetic, multifaceted funlover who likes what we do, give us a shout!]