WIP: Optimal GF/Ability/Junction assignments for FF8

You'll get there pretty quick then, this is a very classical CS problem. I'm implementing a recursive "divide and conquer" algorithm which partitions the GFs in to three bins (one for each character). Then, at each stage in building up the partition, I run it through an arbitrary number of filters... if any filter should fail, I kill that branch and it then "prunes" (via backtracking) so that the total problem space gets reduced.

It's a very similar strategy to what is commonly used in Chess AI algorithms, although usually those take advantage of other "forward-looking" optimizations (versus my "backwards looking" ones).

If that all sounds complicated... it is, but you'll be learning it soon enough! The whole thing boils down to about 50 lines of code so it's not too bad. Here's the partition algorithm itself, btw, in case you were curious:

def partition(count, elements, filters):
    if not elements:
        yield [set() for _ in range(count)]
    else:
        elements = set(elements)
        p_set = {elements.pop()}

        for partitions in partition(count, elements, filters):
            nonempty = [ x for x in partitions if x ]
            empty = [ x for x in partitions if not x ]

            for i in range(len(nonempty)):
                candidate = list(nonempty)
                candidate[i] = candidate[i] | p_set
                candidate += empty
                if all(filt(candidate) for filt in filters):
                    yield candidate

            if empty:
                candidate = list(empty)
                candidate[0] = candidate[0] | p_set
                candidate += nonempty
                if all(filt(candidate) for filt in filters):
                    yield candidate

Here, count is the number of partitions I'm making (3 for the case of FF8's 3-character parties), elements would be the set of GFs I'm assigning, and filters is a list of functions that return True or False based on a partition assignment.

/r/FinalFantasy Thread