"Cascading constraint" optimization problem

First, I just made up the name, sorry if it refers to something else. In the “games you didn’t finish” I said regarding Kingdom Hearts Re: Chain of Memories:

A very brief problem statement is that we’re drawing from an arbitrary pool of cards with various properties to create an ordered queue. Each consecutive set of three cards in this queue must satisfy some (invariant) constraint. After every consecutive triple is determined to have been met successfully, the second and third cards of each triple are re-enqueued. We continue doing this constraint check until we either have fewer than 3 cards after re-enqueing, or a triple fails to meet the given constraint.

The trick is, each card has a weight, and the deck has a weight limit. The trick is to create a deck from your pool within the weight limit that satisfies the constraint a maximal number of times.

Here’s a more thorough description:

You are given an ordered deck c ∈ D with n slots, and have a (non-unique) collection of cards c∈C where each c is represented by an ordered triple (v,w, t) where v represents the value of the card in the range [0,9], w represents the “weight”, and t represents the “type” (similar to suits in normal cards – this is only important for certain sleights).

The limits of the deck are such that (Σ[sub]c ∈ D[/sub] c.w) <= n. That is, the sum of the weights of all cards in the deck must not exceed the number of slots n. For simplicity’s sake, a deck is also a queue. That is, any operation on the deck must draw the cards from the top of the deck in order, you cannot seek to an arbitrary card*. For instance, in the deck of cards with values v (5,4,4,2,5), the next sleight (see below) must take 5,4,4 in order.

Our goal is to make a “sleight” deck. A sleight (s) is an operation on 3 consecutive cards** such that if constraint(c1,c2,c3) is met, the sleight executes. One example is the Blitz sleight, which checks if all 3 cards have a type in the attack class (a “class” is kind of like “red” or “black” in cards – it’s an arbitrary group of multiple types/suits) and that the sum of the values of c1,c2, and c3 are in the range [10,15]. So in the example above, assuming all cards are attack cards, the deck (5,4,4,2,5) we would add 5+4+4=13 and check if it’s within the sleight threshold, which it is.

A more complicated example is the “Sonic Blade” sleight which checks if the values are between 20-23 and all cards are “attack” cards, and the type t of c1,c2, and c3 are all different.

So why is this a “cascading” constraint? Well, we have to introduce another operation: reloading. When the size of the deck stack drops below 3, we “reload” the deck. It’s a bit hard to explain this in words, but I’ll try. In programming terms, the easiest way to think of it is this: consider a second, initially empty temporary deck D2. When a sleight is executed, it will enqueue the second and third arguments into the new deck. “Reloading” will enqueue all cards remaining in D into D2 and swap D and D2 as the active deck. Again, using the example above –

D = (5,4,4,2,5)
// D is now (2,5)
// D is now (4,4,2,5), because the sleight got rid of the first card

So now we can get to the actual problem statement:

Given a pool of cards, write an algorithm to construct a deck that does not exceed some weight limit n that executes the maximal number of sleights across all reloads. The end-state is when a sleight is no longer possible. That is, either the current triad in the deck does not satisfy the conditions for a sleight (e.g. the deck (3,3,3) would not satisfy a Blitz deck because 9 is not in the range [10,15]) or there are fewer than 3 cards in the deck after reloading.

Again, here’s the example I made in my post in the Game Room:

5 5 3 5 2 4 6 2 -> 5 3 2 4 6 2 -> 3 2 6 2 -> 2 6 2

This deck executes the Blitz sleight. First it executes the sleights (5,5,3),(5,2,4). After reload its state is (5,3,2,4,6,2) and executes the sleights (5,3,2),(4,6,2). Then it reloads into (3,2,5,2) and executes (3,2,5). Then it reloads to (2,6,2) and executes (2,6,2). Then it reloads to (6,2) and we’ve halted after executing 6 sleights.

I’ve mostly glossed over the card weights w and the deck size limit n, mostly because I don’t know the weights off the top of my head and the deck limits are way too big to facilitate simple examples. However, do note that the deck limit is absolutely imperative to the challenge. Generally, higher value cards have bigger weights, except the 0 value card which is the most weighty***. I think this is at least as hard as the Knapsack problem, and I honestly have no idea where to begin constructing a non-naive algorithm for it.

This is mostly for fun, but I thought I’d post it for ideas.

Here is a Go script that simulates our Blitz deck, as well as having commented code examples of a few other sleights.

  • This isn’t actually true in the game, but sleight decks aren’t very useful if you have to seek to execute them.

** There are actually a couple sleights in the game that use 2 cards, but they’re not good enough to actually build decks around so I’m omitting them for simplicity.

*** This is because in-game 0 is a “trump card”. This is mostly irrelevant to sleights

A clarification regarding reloading: after playing the first sleight from the deck 5 5 3 5 2 4 6 2, is it possible to reload it immediately to 5 3 5 2 4 6 2? Or does one always play triplets of cards until there is less than three cards left, and then reload?

In the game: Yes, it is possible to reload whenever
For our purposes: No, you have to consume until you have fewer than 3 cards, at which point you automatically reload.

Edit: The reason is because in-game, the more you reload, the longer it takes to do it (leaving you vulnerable to nasty attacks). While we could try maximizing value while minimizaing weight AND meeting constraints AND minimizing reloads, it’s easier to just formulate it the way I did.

So far, I’ve figured out several ways to literally make this the knapsack problem, but they all involve things like “construct all sets of non-overlapping constraint-meeting triples” or “construct all decks that reload at least once” and stuff. You can hash the results of computing the number of sleights each produces, but I still think there’s a better way.

Well, that makes things easier, removing choice is always nice for simplifying a problem. :slight_smile:

Anyway… some facts are clear: the maximum possible number of sleights for an n-card deck is n - 2. Let’s term this an optimal n-deck. In order for a deck to be optimal, it must be an optimal k-deck (for some k) after each reload. Which means that enumerating all optimal decks is simpler than enumerating all decks. That is:
First find all optimal 3-decks.
Create all optimal 4-decks by prepending a card to an optimal 3-deck.
Create all optimal 5-decks by prepending a card to an optimal 4-deck.
Create all optimal 6-decks from optimal 4-decks by inserting cards before the first card and after the first two cards.
In general, create optimal n-decks from optimal (n - floor(n/3))-decks by inserting a card every two cards.

Of course, the problem with this method is that the best deck may not be optimal in this manner: one can imagine the case where one is left with three cards that do not form a sleight. A more general thought of this type is that in order to create an n-card deck with k sleights, there must first be a (n - floor(n/3))-card deck with k - floor(n/3) sleights. Using the first method to find the largest optimal deck, and then looking for decks that have at least two more cards and one more sleight might work.

Assuming I understood the problem correctly, at least. :slight_smile: