3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I just want to point out that training and executing don't have to be done on the same device. E.g. (as far as I know) Tensorflow allows you to train a NN on a powerful machine (e.g. PC with GPUs) and then deploy the trained NN on a much less powerful machine, e.g. an Android phone. $\endgroup$ – user12889 Oct 27 '17 at 2:32
  • $\begingroup$ @user12889 That's a great point and you're not the only one to indicate this NN capability. Part of this initiative will be to see if we can do "mini-NNs" on the local mobile devices, where the local automata get "tuned" by playing against their human, with the intent of leveraging evolutionary game theory (the idea being that each discrete automata is unique do to the "personalization".) But if we find we need to produce strong AI for an expert-player version of the product, the NN capability you mention will surely be extremely effective! $\endgroup$ – DukeZhou Oct 27 '17 at 17:30
  • $\begingroup$ Edited to poke the question. This is a question which can have lot of implications in portable ML algos. $\endgroup$ – DuttaA Sep 13 '18 at 8:55
  • $\begingroup$ @DuttaA thanks for the poke. When I originally asked it, I wasn't even sure how valid of a question it was. (Luckily, there's been some recent clarification of the approach in terms of the project, where learning algorithms will be the final part, and are still some ways off;) $\endgroup$ – DukeZhou Sep 16 '18 at 22:48
2
$\begingroup$

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 1181× 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

$\endgroup$
  • 1
    $\begingroup$ Don't apologize! I really appreciate you taking the time, and this answer is helpful. Really it's only 9 values over 81 positions, but the game mechanics result with endgame states with ~10 dead cells where no integers can be legally played. Because of the tractable endgame, we don't need to even go that deep, and merely track openings. $\endgroup$ – DukeZhou Aug 23 '17 at 19:59
  • 2
    $\begingroup$ PS I added a slight edit to your first suggestion to the description for the reinforcement-learning tag. Thanks for getting involved. If you want to discuss further tweaks, feel free to open a chat, and invite me from a comment here. $\endgroup$ – DukeZhou Aug 23 '17 at 20:01
  • $\begingroup$ I would love to participate in modeling the AI, if you do not mind from the intellectual property point of view. $\endgroup$ – A.Rashad Aug 23 '17 at 20:03
  • 1
    $\begingroup$ email me dz@deterministicgames.com (I'm a bit of a dinosaur myself;) $\endgroup$ – DukeZhou Aug 25 '17 at 1:09
  • $\begingroup$ Done, email sent $\endgroup$ – A.Rashad Aug 25 '17 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.