What knowledge do I need in order to write a simple AI program to play a game?

Question

I'm a B.Sc graduate. One of my courses was 'Introduction to Machine Learning', and I always wanted to do a personal project in this subject.

I recently heard about different AI training to play games such as Mario, Go, etc.

What knowledge do I need to acquire in order to train a simple AI program to play a game? And what game do you recommend for a beginner?

This is what I know in Machine Learning so far -

• Introduction to the course and to machine learning. K-Nearest Neighbor algorithm, and K-means algorithm
• Statistical Inference
• Gaussian Mixture Model (GMM) and Expectation Maximization (EM)
• Probably Approximately Correct (PAC) model, including generalization bounds and model selection
• Basic hyperplane algorithms: Perceptron and Winnow.
• Support Vector Machines (SVM)
• Kernels
• Boosting weak learners to strong learners: AdaBoost
• Margin-Perceptron
• Regression
• PCA
• Decision Trees
• Decision Trees pruning and random forests

Answer 1

There are multiple ways to approach solving game playing problems. Some games can be solved by search algorithms for example. This works well for card and board games up to some level of complexity. For instance, IBM's Deep Blue was essentially a fast heuristic-driven search for optimal moves.

However, probably the most generic machine learning algorithm for training an agent to perform a task optimally is reinforcement learning. Technically it is not one algorithm, but an extended family of related algorithms that all solve a specific formalisation of the learning problem.

Informally, Reinforcement Learning (RL) is about finding optimal solutions to problems defined in terms of an agent that can observe the state of an environment, take actions in that environment and experience rewards which are somehow related to the state and action. RL solvers need to be designed to cope with situations where rewards are received later than when important actions were taken, and this is usually achieved by the algorithm learning an internal expectation of later rewards associated with state and/or state-action pairs.

Here are some resources for studying Reinforcement Learning:

• Reinforcement Learning: An Introduction (Second Edition)

• Algorithms for Reinforcement Learning (PDF)

• Udacity Reinforcement Learning course

• David Silver UCL lectures on Reinforcement Learning

You will find the subject itself is quite large as more and more sophisticated variations of the algorithms are necessary as the problem to solve becomes harder.

Starting games for studying reinforcement learning might include:

• Tik-tac-toe (aka Noughts and crosses) - this can be solved easily using search, but it makes for a simple toy problem to solve using basic RL techniques.

• Mazes - in the reinforcement learning literature, there are many examples of "grid world" games where an agent moves in single N,E,S,W steps on a small board that can be populated with hazards and goals.

• Blackjack (aka 21)

If you want to work with agents for playing video games, you will also want to learn about neural networks and probably in some detail - you will need deep, convolutional neural networks to process screen graphics.

A relatively new resource for RL is OpenAI Universe. They have done a lot of work to package up environments ready to train agents against, meaning you can concentrate on studying the learning algorithms, as opposed to the effort of setting up the environment.

---

Regarding your list of current skills: None of them are directly relevant to reinforcement learning. However:

• If you can understand the maths and theory from your previous course, then you should also be able to understand reinforcement learning theory.

• If you have studied any online or batch supervised learning techniques, then these can be used as components inside a RL framework. Typically they can be used to approximate a value function of the game state, based on feedback from successes and failures so far.

Answer 2

It highly depends on the type of game and the information about the state of the game that is available to your AI.

Some of the most famous game playing AIs from last few years are based on deep reinforcement learning (e.g. Playing Atari with Deep Reinforcement Learning), which is normal reinforcement learning (e.g. Q-learning) with a deep neural network as reward value function approximation. These approaches receive the raw pixels of the game plus the points of the player, and output the actions of a game pad, much like a human. In order to do something like that, you need to master reinforcement learning (see Sutton and Barto's seminal book) and deep learning (see Ian Goodfellow et al. book), and then how to fuse them into deep reinforcement learning (search for "reinforcement learning" in any curated list of deep learning papers like this one).

However, if the information about the game that is available to your AI is more structured than that (e.g. position of the player, description of the environment), you can do well with more classical approaches where you decompose your game into tractable problems and solve each one algorithmically e.g. by searching with A*.

Answer 3

What you are looking for is called Reinforcement Learning. At my university, there is a complete course ($15 \cdot 3h = 45h$) only to introduce students to this topic. Here are my (mostly german) lecture notes to probabilistic planning. I would say this is definitively an advanced topic for machine learning.

Topcis to learn about

• Markov Decision Processes (MDPs)
  • Policy and Value iteration
  • Project: Rock-Paper-Scissors / Tic-Tac-Toe
• Partially Obversable Markov Decision Processes
  • Project: Black Jack
• Reinforcment learning
  • Q-Learning
  • SARSA

Other simple games

• Pong
• Inverted Pendulum
• Backgammon

Other resources

• OpenAI Gym
• Book by Sutton