2
$\begingroup$

How would you go about training an RL Tic Tac Toe (well, any board game, really) application to learn how to play successfully (win the game), without a human having to play against the RL?

Obviously, it would take a lot longer to train the AI if I have to sit and play "real" games against it. Is there a way for me to automate the training?

I guess creating "a human player" to train the AI who just selects random positions on the board won't help the AI to learn properly, as it won't be up against something that's not using a strategy to try to beat it.

$\endgroup$
1
$\begingroup$

The approach will vary depending on some features of the game:

  • How many players (two for tic tac toe and many classic games).

  • Whether it is a "perfect information" game (yes for chess and tic tac toe), or whether there is significant hidden information (true for most forms of poker)

  • Whether the game is zero sum. Any game with simple win/loss/draw results can be considered zero sum.

  • Branching complexity of the game. Tic tac toe has relatively low branching factor, at worst 9, and reduces by one each turn. The game of Go has branching factoraround 250.

  • Action complexity of the game. A card game like Magic the Gathering has huge complexity even if the number of possible actions at each turn is quite small.

The above traits and others make a large impact on the details of which algorithms and approaches will work best (or work at all). As that is very broad, I will not go into that, and I would suggest you ask separate questions about specific games if you take this further and try to implement some self-playing learning agents.

It is possible to outline a general approach that would work for many games:

1. Implement Game Rules

You need to have a programmable API for running the game, which allows for code representing a player (called an "agent") to receive current state of the game, to pass in a chosen action, and to return results of that action. The results should include whether any of the players has won or lost, and to update internal state of the game ready for next player.

2. Choose a Learning Agent Approach

There are several kinds of learning algorithms that are suitable for controlling agents and learning through experience. One popular choice would be Reinforcement Learning (RL), but also Genetic Algorithms (GA) can be used for example.

Key here is how different types of agent solve the issues of self-play:

  • GA does this very naturally. You create a population of agents, and have them play each other, selecting winners to create the next generation. The main issue with GA approaches is how well they scale with complexity - in general not as well as RL.

  • With RL you can have the current agent play best agent(s) you have created so far - which is most general approach. Or for some games you may be able to have it play both sides at once using the same predictive model - this works because predicting moves by the opposition is a significant part of game play.

2a. How self-play works in practice

Without going into lines of code, what you need for self-play is:

  • The game API for automation and scoring

  • One or more agents that can use the API

  • A system that takes the results of games between agents and feeds them back so that learning can occur:

    • In a GA, with tournament selection, this could simply be saving a reference - the id of the winner - into a list, until the list has grown large enough to be the parents for the next generation. Other selection methods are also possible, but the general approach is the same - the games are played to help populate the next generation of agents.

    • In RL, typically each game state is saved to memory along with next resulting state or the result win/draw/lose (converted into a reward value e.g. +1/0/-1). This memory is used to calculate and update estimates of future results from any given state (or in some variants used directly to decide best action to take from any given state). Over time, this link between current and next states provides a way for the agent to learn better early game moves that eventually lead to a win for each player.

    • An important "trick" in RL is to figure out a way for the model and update rules to reflect opposing goals of players. This is not a consideration in agents that solve optimal control in single agent environments. You either need to make the prediction algorithm predict future reward as seen from perspective of the current agent, or use a global scoring system and re-define one of the agents as trying to minimise the total reward - this latter approach works nicely for two player zero sum games, as both players can then direcly share the same estimator, just using it to different ends.

  • A lot of repetition in a loop. GA's unit of repetition is usually a generation - one complete assessment of all existing agents (although again there are variants). RL's unit of repetition is often smaller, individual episodes, and the learning part of the loop can be called on every single turn if desired. The basic iteration in all cases is:

    • Play anything from one move to multiple games, with automated agents taking all roles in the game and storing results.
    • Use results to update learned parameters for the agents.
    • Use the updated agents for the next stages of self-play learning.

3. Planning

A purely reactive learning agent can do well in simple games, but typically you also want the agent to look ahead to predict future results more directly. You can combine the outputs from a learning model like RL with a forward-planning approach to get the best of both worlds.

Forward search methods include minimax/negamax and Monte Carlo Tree Search. These can be combined with learning agents in multiple ways - for instance as well as in planning stages using the RL model, they can also be used to help train a RL model (this is how it is used in Alpha Zero).

| improve this answer | |
$\endgroup$
0
$\begingroup$

One solution would be to simply play the AI against itself (which yields good results for the tic tac toe example, I've tried it), but a much more interesting approach is to train two networks at the same time and have them play against each other.

It's called a Generative adversarial network (GAN) and it's very promising. It is able to make realistic images and much more.

It's quite easy to implement both solutions so I'd recommend doing both and seeing for yourself since each problem is different.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Maybe you should explain how GANs can specifically help in this situation. $\endgroup$ – nbro Feb 3 at 11:33
  • $\begingroup$ Thank you for your response. Do you have any non-NN examples of how I can train? $\endgroup$ – mason7663 Feb 7 at 9:27

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.