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).
