Because of the asymmetry between game roles (first/second player) we decided to learn the Q function separately for either role. Learning the Q function directly required holding a table between each possible pair to a real value. As the number of states increases this representation becomes very large (for our version of FIAR it is O(3⁴⁸)). To overcome this problem we didn’t represent Q(s,a) directly, learned a linear approximation of it instead: Q_a(s) approximation for each action a (chosen column). Thus we represent the global Q-function as a sort of one level decision tree.

The linear function approximation receives a vector of board features (see next section) representing the current state and returns some linear combination of these features. The learning process goal is to finds the locally optimal weights of this linear combination.

SARSA learning algorithm, as its name implies, requires a 5-tuple for its update rule. In FIAR there's no immediate reward for actions not leading to a victory or loss - only the terminating move receives a reward. So the Q-values of terminating states are either 1 for victory or -1 for loss. Because these values need to propagate to the Q-Values of earlier states, we choose the gamma discount factor to be 1.

Our update rule was:

• 1. Raw board state - each game cell has a feature representing its state (6*8=48 features):
  
  • 1 – player owned cell
    
  • -1 – opponent owned cell
    
  • 0 – neutral cell
    
• 2. Action based potential – for each player for each column we'll have a the following features: (2*3*8 = 48)
  
  • Completion to 3 in top used row
    
  • Completion to 3 in top unused row
    
  • Completion to 4 in top unused row
    
• 3. Global board features
  
  • Parity – Because 4 in a row is a fully observable 2 player game, board parity information plays an important role. If a player has a threat on an even row, and all columns contains an even number of columns it can force a win. (see Zugzwang analysis in Allis, 1988 ^[1])
    
  • Two features that represent whether the above condition is true for the agent and for the opponent.

• Training will be done by having two copies of the player playing each other. Both learning their respected roles.
• Bootstrapping was achieved by hard coding:
• winning moves – will cause victory rewards to be awarded early
• random start moves – Allowing us to explore more of the state space
• self play – Allows player to be more challenged as the learning process continues
• Learning rate   . t – number of games played so far in the training session.

This way we achieve a properly decaying learning rate.

• Discount factor   – one, because rewards are only given at the end of the game.
• Epsilon – in order to balance between exploration and exploitation we'll choose the next action with a  policy.  We tested three methods used to determine  throughout the training:
• A constant value: with probability ε we choose a random action, otherwise – a greedy action.
• Epsilon decreasing strategy: decreasing epsilon as the learning progresses allows us to explore more at the beginning of the learning process and exploit as we converge. We tested two methods:
  • . We reduce the exploration rate after each game. The value of c will affect the time it will take  to converge to zero. It is common to choose .
  • Using a reduction function: .
• Q Approximation weights – These are the values to be learned by the training process.

• Gamma was set to 1
• Initial epsilon value was set to 0.9
• The epsilon update method chosen was annealing
• Altogether we played 2 million games:
  • We ran a session of 1 million games with an annealing factor 0.99999
  • We ran another session of 1 million games with an annealing factor 0.9999. This run continued the learning of the previous run (meaning the initial epsilon of this run is the final epsilon of the previous run), the only difference was the change of the anneal factor.