This looks like the kind of game that a Reinforcement Learning algorithm could learn to play. If you are learning from the game objects directly (as opposed to wanting to have the agent learn from viewing the screen), then it should be relatively straightforward to do so - by which I mean that it will involve some new concepts, a little maths, and maybe take you a few weeks to learn enough and run enough experiments on the AI to the point where you have something good. But at least you should not need a cluster of GPU servers to run your learner.
However, I have no clue how to apply Q-learning to this task. For example, how could the coder possibly know what future reward another move will bring?
That is a major part of RL - the algorithms that are part of RL all solve this issue. Therefore the coder does not need to know how to calculate future reward, just an immediate reward. For the example game, it looks like you can grant a reward of $+1$ for every frame where the player does not crash. An RL algorithm that can solve this environment should figure out through "trial and error" which actions will keep the game running.
Q Learning achieves this by keeping track of estimates of future value and updating them across time steps - if action $a_1$ in state $s_1$ consistently leads to a later state $s_2$ with a high value, then Q learning will update its estimate of the value of $Q(s_1,a_1)$ to be high as well. The estimates start very poorly, but updates work their way back through time steps as the agent learns, and provided things don't go wrong, eventually it will learn that one action will lead to higher value than another, and it be able to consistently choose it.
This is such a basic question that if you want to use RL, even if you find a library that implements the whole thing for you, that you clearly need to study some foundations of RL. There are a few different places you can do that. I can suggest two that I have used:
Both are online, free and comprehensive introductions to the subject. You can find shorter, more direct introductions online if you search for e.g. "Q Learning Tutorial".
Be prepared to spend hours just learning enough about the topic that you understand how to structure your data and interface with the game in order to create a learning environment for your AI.
- In this case, the player has infinitely many actions. How would I apply RL to this case?
This is a good question. Some algorithms are better than others. Q Learning cannot work with infinitely many actions. However, you could choose a discrete set of mouse points - e.g. maybe 64 - at different angles and distances from the player (red dot) and try and get the values of those. That would allow you to try with Q learning, and is worth considering because RL that properly solves large action spaces is harder to understand and work with. You could look into the DQN algorithm for this. In short, the DQN algorithm uses history of actions and their immediate results to train a neural network to estimate the values of each action.
If you really want to solve large action spaces properly, then you need to be looking into Policy Gradient methods. Two popular and effective PG algorithms are A3C and DDPG. These are tougher to learn and implement. They use neural networks to learn multiple functions, one of which is the policy - this directly selects which action to take, given a current state/observation.
- Is RL a good approach to solving this task?
It is definitely possible to use RL to do what you want.
- Is there a handy Java library which would allow me to use a RL algorithm (as a block-box) to solve this problem?
I could not find one on a brief search. To get started, you might want to look at java-reinforcement-learning which implements some of the algorithms from Sutton & Barto, so would be a good starting point. Most of the other Java packages I found covered basics and learning material, but would not be plug-and-play for your game.
If you do find a library, you will need to have learned enough basic RL to be able to follow how to use it.
- Are there alternatives?
One alternative that might work well for your game environment, and be a little easier to understand and implement would be to combine a policy function (like a neural network) with an evolutionary algorithm that tries out variations of the policy. The go-to algorithm here is probably NEAT, and it is capable of solving simple game agents effectively. Your game should be a reasonable fit for NEAT because the scoring system of survival time makes for a good fitness function.
One thing that could really be worth trying before diving into the (very hard to understand) A3C and DDPG algorithms is the Cross-Entropy Method. It is a really simple RL agent that has some similarities to genetic algorithms (it selects "best" items, but instead of from the population, it is from random behaviour of the same individual), but doesn't always scale too well. However, it might work well for your game.
