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 OpeningsMy 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 HeuristicsSince 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 pruningBecause 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?
What type of reinforcement learning can I do restricted to ~200MB on an average smartphone?
reinforcement learning;gaming;game ai;architecture;combinatorics