What type of reinforcement learning can I do restricted to ~200MB on an average smartphone?

Question

This concerns a set of finite, non-trivial, combinatorial games [M] in the form of an app. A sample game can be found here.

Because this is a mass market product, we can't take up too much space, and the AI needs to be able to run locally since connectivity cannot be assumed. The current size of the Android kernel is < 7MB.

The goal is not sheer AI strength, but respectable AI strength, sufficient to beat the above-average human player. (The current strongest, weak automata, using a few heuristics, is already capable of beating the average human player.)

Because the games are finite, the gametrees eventually become tractable, allowing for perfect endgames. Resource stealing strategies and trap-avoidance can also be effected with shallow look-ahead at all phases, and the patterns are much easier for automata to recognize than for humans.

In this context, reinforcement would be mostly utilized to "tune the automata to the style of the human player," and produce different automata on different devices, which could subsequently play against each other as proxies for their human partners.

The game data can be stored efficiently, initially requiring only 2 bytes per position (a value 0-9 and a coordinate 1-81, although the number of coordinates will grow in basic game extensions, and require 2 bytes for larger-order gameboards such as "Samurai" Sudoku.) So the first turn on a given game requires only 2 bytes, the second turn bytes, etc., up to between 50 and 70 turns on an 81 cell gameboard. Additionally, because it's a square grid, we can reduce for symmetry. But even with an average number of turns at 50, that's only about 40,000 games for 200MB.

• Weighting Openings

My feeling is that reinforcement would be useful in weighting openings. If the game data is a string, these strings can be compared, and the smaller the sample size (the fewer the turns included,) the more connections there will be. In this case, the sequence doesn't matter, only the set of value/coordinates for a given turn. Abstraction can be utilized in that certain individual value/coordinates are interchangeable. My thought is the automata can weight openings based on how often they lead to desirable outcomes in the form of a win.

• Weighting Heuristics

Since we're having good, initial results with heuristics, and these are the most efficient method of decision-making, I'm thinking about weighting evaluation functions so that certain heuristics take precedence under different conditions. (For instance, when to expand vs. when to consolidate. When to make a choice with immediate benefit over a choice with long-term benefit. Introduction of meta-strategies that modify foundation strategies.)

• Database pruning

Because the allocated volume will be capped, it's probably going to be necessary to "prune" the database when info is no longer relevant. (For instance, when a new strategy emerges that renders previous strategies obsolete.) We also probably need a method to help the automata to recognize such situations, so it doesn't persist in potentially obsolete strategies for more than two games without starting to try alternatives.

---

Q: Can reinforcement learning be meaningfully applied toward these goals under these restrictions?

Q: Are my inclinations for approaching this useful or problematic?

Q: Are there methods I'm not considering that could be applicable under these restrictions?

Answer 1

I skimmed through your question and understood that the state/action space is finite, so in this case, RL would be a good option for storage.

The most basic RL technique will keep track of a matrix Q ∈ ℝ^s×a, where s is number of possible states, and a is number of possible actions.

In addition to a small overhead of agent's parameters:

• α ∈ [0,1] learning parameter
• γ ∈ [0,1] discount rate,
• ε ∈ [0,1] exploration rate

If you have a total of 81 states and 10 actions, then your storage would be in the neighborhood of 850 double words.

If your AI will track different states per location, e.g. possible values 0 to 9 + a null, then your state space will grow to 11 * 81 = 968 and the final value matrix will be Q ∈ ℝ^968×10 ≈ 20Kb.

Update

I am terrible sorry, I made a terrible mistake in my calculations. if you are to keep track of 11 possible values in 81 locations, then the correct number should be 11⁸¹× double word size, that is a big number.

Of course, if this is Sudoku and you and you are not considering illegal moves as possible states, then definitely this will be a way smaller number, but you will still keep track of an action space that is as big as the state space.

You might need to use function approximation instead, or some sort of action state space compression.

sorry