# Hybrid Training Strategies: Improving Performance of Temporal Difference Learning in Board Games +
## 2 Materials and Methods
### TD-Learning Agent  
In order to examine alternative training procedures, a TD learning agent has been developed in the C++ language for each board game considered (tic-tac-toe and 4 \(\times\) 4 Connect-4). The generated C++ programs, which include the various training techniques assessed, only account for -400 noncomment source lines (NCSLs) of code each, due to the algorithm's straightforwardness.  
Regular tic-tac-toe and Connect-4 game rules are assumed in our implementation of both TD agents. We will assume that the opponent of the TD agent always plays first.  
The distinct game states are indicated by an n-digit number with potential digits 0 (an empty position), 1 (a position occupied by the opponent), and 2 (a position held by the TD agent). In theory, this means that there are 3\({}^{\rm n}\) potential states, but owing to game rules, some of them are not attainable. The TD agent seeks to travel from a given state to the state with the highest estimated utility of all the attainable states in each game. It will perform a random move if all of the attainable states have the same estimated utility.  
After playing an elevated number of games against an opponent (training phase), these utilities represent an estimate of the probability of winning from every state. These utilities symbolize the states' values, and the whole set of utilities is the learned value function. State A has a higher value than state B if the current estimate of the probability of winning from A is higher than it is from B.  
For every potential state of the game, utilities are initially set to zero. When each game is over, the TD agent updates its utility estimates for all of the states that were traveled  
Figure 2: A finished game of Connect-4 on a 4 \(\times\) 4 board, won by the blue player.  
throughout the game as follows: The utility function for the final state of the game (terminal state) will be \(-1\) (opponent won), +1 (TD agent won), or 0.2 (game tied up). Due to the unique nature of tic-tac-toe and 4 \(\times\) 4 Connect-4, a little positive incentive is provided to game ties, as the game will end in a tie if played intelligently. Utilities are updated backward for the rest of the states visited throughout the game, by updating the current value of the earlier state to be closer to the value of the later state.  
If we let \(s\) denote the state before a move in the game and \(s^{\prime}\) denote the state after that move, then we apply the following update to the estimated utility (\(U\)) of state \(s\):  
\[U(s)\gets U(s)+\alpha\;[\;\gamma U(s)-U(s)\;] \tag{1}\]  
where \(\alpha\) is the learning rate and \(\gamma\) is the discount factor parameter. Because this update rule uses the difference in utilities between successive states, it is often called the temporal difference, or TD, equation. After many training games, the TD agent converges to accurate estimates of the probabilities of winning from every state of the game.  
The pseudocode detailed in Box 1 performs the update of the utilities for all the states visited throughout a game, after the game has finished, using the TD Equation (1).  
**Box 1.** Update of utilities after each game, using the TD update rule equation.  
// U: Utilities for all possible states  
// seq: sequence of states visited in the last game  
// n_moves: number of moves in the last game  
if (TD_agent_won) {  
U[current_state] = 1.0;  
else if (opponent_won) {  
U[current_state] = -1.0;  
else { // tied up  
U[current_state] = 0.2;  
for (i = 1; i <= n_moves; i++) {  
// this is the TD update rule equation  
// ALPHA -> learning rate; DF -> discount factor  
U[seq[n_moves-i]] += ALPHA*(DP*U[current_state]-U[seq[n_moves-i]]);  
current_state = seq[n_moves-i];As an example, in Figure 3 we can see the estimated utilities by the tic-tac-toe TD agent (X-player) after having played an elevated number of training games, for all reachable states in three different games, given three distinct initial positions occupied by the opponent (O-player).