Machine learning to improve strategy game AI

Question

I am currently working on a simple strategy game as a hobby and I am starting to think about designing an AI to add opponents in the game. The idea behind the game is that you are a space explorer and that you have to achieve the highest possible score. Your score is the sum of the total number of planets you have explored + the length of time you have managed to keep the game going. Each planet that you explore gives you some resources points which decay with time and a fixed expense which remains constant over time and is discounted from your resource point pool every Unit of Time. As you can see if you don't explore fast enough then you will eventually run out of resource points, which is when the game stops.

I am now looking into adding an AI and I was wondering if it wouldn't be easier to use machine learning algorithms than code an whole AI entirely based on conditionals.

My idea was to record the player's activity every X amount of time as well as the current state of some game variables.

So I would have something like :

actions = {0 : nothing, 1: move, 2: explore, 3: search, etc ... }

And then I would record variables such as:

 variables = [ time_since_last_action, resource_pts, knowledge_pts, number_of_discovered_planets, number_of_explored_planets, time_in_game, current_expenses, current_resource_income, current_knowledge_income, current_active_events, etc...]

Then I would use some machine learning algo (as a black box) to find a relationship between game variables and actions to make. I would also record the final score at the end of each game so that the AI learns more from successful games than unsuccessful ones (or even better set a score threshold above which to send the data to the AI).

I am also thinking that by maybe feeding two different AI's with different data over a few games I could then let them teach one another.

And finally, since I am not quite sure myself what the optimal game strategy should be maybe I could get some valuable information out of the process (eg: how does each variable affects the action outcome, or the overall score).

I'm thinking that since my game is relatively simple that could be a good opportunity to get into machine learning as well (since I am also doing this project to learn).

Any thoughts or directions towards interesting resources /tutorials would be very welcome.

Answer 1

Firstly, I'd try a simple greedy AI strategy that just goes to the nearest unexplored planet and explore it. It could be enough to make the game interesting while not making the AI invincible.

With that said, supposing you want to practice ML, or want it just for fun, there are a few options:

• Store the input-output vectors you mentioned from human game-playing and use supervised learning (start with logistic regression) to teach the AI;
• Instead of supervised learning, you may want to try Reinforcement Learning. You can apply it with a human playing the game on-the-fly or fully autonomously, by letting the agent select actions (this is the common setup for RL, but may be too much slower to train). The reward at each step is the difference of points from last step. Since you have continuous input variables and discrete actions, I'd recommend to use some form of function approximation. This paper shows how to use Q-learning (and TD-Learning) with linear function approximation correctly.
• Finally, you may want your AI to play the game and use only the final score to improve. This would lead you to Genetic Algorithms. Basically, run a lot of random AI's (may be a bunch of logistic regressors with random weights). Select the best ones, apply crossover and mutation and start over with a new generation of agents. After doing it for many generations, you'll find pretty good agents.

Other interesting references:

• Games containing machine learning AI
• Genetic Algorithms in games
• Using a Genetic Algorithm to Create Adaptive Enemy AI
• The Blind Game Designer - Darwinism in a fast pace, casual action game
• What are some examples of computer games which use machine learning?
• Are there any games that contain a machine learning AI?
• Machine learning in digital games: A survey