Training with reinforcements on the example of the game "tic-tac-toe"

Tic-tac-toe is a game studied far and wide, and the development of AI for it can be reduced to organizing the decision tree described in Wikipedia . This article will consider the solution of the game through training with reinforcement and approximation of the value functions.

Prep

We accept the following rules:

• The agent goes first and plays "crosses".
• The agent will only make decisions with maximum value.
• With a 5% chance the agent will make probing decisions.
• Only if the agent wins, he gets a reward.

The next step is to prepare the value function for the agent. In our case, the value function will be the state table of the game, in which a value from 0 to 1 will indicate that a particular state is “better” than another. Initially, we set in our table that all winning combinations (three crosses in a row, column or diagonally) give a probability equal to 1. Similarly, all the states with three zeros are 0. For all other states, the probability is 0.5.


In order to simplify the compilation of a probability table, we assume that

$$

$$3 ^ 9 = 19683$$

states. Of course, half of these combinations is impossible, but the code was not optimized for the purpose.
')

Course of the game

Opponent will be a person who accordingly will play for zeroes and periodically succumb. During the game, there will be a change in the value of its states. In order to properly evaluate the actions of the agent, it is necessary to record the sequence of those states that he chose and at the end of the game to recalculate them. The formula for calculating the value of V (s) will be as follows:

$$$V (s) = V (s) + A * [V (s') - V (s)]$,

where A is the size of the step affecting the speed of learning. V (s') - the value of the action at the end of the game (1 - if won, 0 - otherwise).

The size of the step affects whether the opponent’s strategy changes or not. If you need to take into account the variability of the strategy, then you need to leave the step size constant. Otherwise, if the step is reduced to zero, the agent will stop his training.

The use of probing moves (having no high value) allows you to check conditions that, because of the high value of other moves, would never have been fulfilled, which gives a small chance of changing the strategy to a winning side.



In the above located code, possible moves are selected (states in which elements are identical to the current state of the field, and there is one more cross). Then, either an arbitrary move (with a probability of 5%) or a “greedy” move (with maximum value) is selected from the obtained states. At the end of the selection, this move is recorded in a separate array of moves made.

At the end of the game, there is a recalculation of the value of the moves made, as already mentioned.

Total

→ Program and project in C ++ Builder 6

In this example, one aspect of reinforcement learning was briefly reviewed. If the agent usually contacts the environment, then in this example the training was carried out with the opponent player. Although this example is quite simple, it may seem that this method in other examples will be very limited than it really is.

Used Books

Training with reinforcements / R.S.Sutton, E.G. Barto - Moscow: BINOM. Laboratory of knowledge, 2014