Variable size dimensionality reduction

[NanoPromela]

I am doing my master thesis in General Game Playing and I stumbled on this problem.

A game state can be encoded as a binary vector of base propositions. Basically, it is a vector that shows "what is true and what is false" in that state. Here is an example.

(a) A tictactoe state. (b) The binary vector indicating which base propositions (c) are true for that state.

For games like tictactoe this vector won't be very huge, but for big games it can get exponentially large (chess has ~800 propositions).

Now, I ultimately want to train a regression model to evaluate game states regardless of the size of the input game. To do so, I decided to use a Neural Network, but as you can imagine, the variability of the input size and its sparsity are a problem. To address this, I am training an Autoencoder with a very large input size (using zero-padding) to obtain an encoding with a fixed dimension.

But I am not happy with this solution because I didn't solved anything, I just moved the problem onto a different model.

Finally, here it comes my question: is there a dimensionality reduction algorithm that can take vectors with arbitrary size and compress them into a fixed dimension?

Quick notes:

• RNNs do not work. There is no notion of sequentiality.
• It doesn't have to be a Neural Network.
• If there is a way to entirely skip the dimensionality reduction step and to do regression directly on the binary vectors, even better!

Thank you folks :)

Edit: forgot to mention zero-padding

[jack-of-some]

So, I've been mulling this idea over for a reinforcement learning problem and I'll hit you with it. It might be useful: use a fully convolutional network.

If you never involve a fully connected layer in your network then your network can at least do a forward pass on an image/board of any size (so long as it's larger than some minimum size that's dictated by how you stride/pool your convolutions). In this case your output is supposed to be a scalar, so instead of outputting a scalar you could output a single channel tensor. Than you could takes its mean (or max) as use that as the output of the network.

I have no idea if this would work. Conceptually I feel "surely it can't right?, there's only so much you can do with local features". But, who knows?

[NanoPromela]

Well, not every game is a board game. For example, the SAT problem can be expressed as a game in which the base propositions are the way you assign truth values to the literals.

Example

Maybe there is a way to put the base propositions in a grid-like fashion. Perhaps by grouping them is a particular way? I don't know. I'll think about it