Experiments with Online Reinforcement Learning in Real-Time Strategy Games
A Real-Time Strategy (RTS) game is a computer game in which players intend to defeat opponents by gathering resources, building bases, and exploring game fields. It demands players to monitor opponents’ behaviors and to be adaptive on taking counter strategies.
Most of game developers use RL or other learning algorithms in the test phase of game programming or around this phase (Laird and van Lent 2005). The learning algorithm is well tested before a game product is shipped out to the target customers.
We compare a basic RL technique, SARSA (Sutton and Barto 1998), with a more sophisticated method, Q-learning (Watkins 1989), within the proposed framework in the game. As expected, the Q-learning performs beter than the SARSA in the studied game.
2.2 RTS - Real Time Strategy
The RTS game is often split into a campaign part and a skirmish part. In the campaign part human players are playing a battle against computer players with a lower or greater amount of units/buildings. In a skirmish game both sides start on an equal size, and therefore the strategies to beat the computer players depends much on players’ skills. It differs from the
campaign part where the strategies rely on a level setup in the game. Using RL in the campaign part of an RTS game seems over-skilled and is essentially not needed because computer players can be easily hard-coded without being dull for human players to defeat. The skirmish part on the other hand demands to have RL since the policy could be primed against certain types of behaviors while still being improved after a single skirmish
game is ended. Some part of the policy table might also be updated during the course of games. RL implementation seems quite difficult, but the potential is certainly present.
2.3 TBS - Turn Based Strategy
Turn based games are traditionally divided into turns where only one player/opponent is allowed to make decisions regarding his/her play. The turn offers RL to have sufficient time to update policies and execute them. In the typical game Civilization (Civilization 1991) RL residing in the top level could decide to put a city near a certain resource, but the follow-up actions, such as creating units, moving them to the spot and starting up cities, might challenge RL. Some TBS games adopt simultaneous turns to make opponents act at the
same time as computer players, which turns the TBS almost into real time movement. This structure allows little time to learn the policy, but would not be impossible for RL use.
The TBS game structure gives RL opportunity to have reasonable time to make up the policy; however, this must still be fast since players will not be pleased with waiting for too long before they can take a new turn. In general, RL is quite suitable in the TBS genre.
Initialize for all states s 2 S and actions a 2 A the value Q(s, a)
to a constant value
Repeat for each episode:
Initialize s
Choose a for s using the policy _
Repeat for each step in the episode, until s is terminal:
Execute action a and save reward r and next state s0
Choose a0 for s0 using _
Q(s, a) = Q(s, a) + _[r + Q(s0, a0) − Q(s, a)]
s = s0 and a = a0
Figure 2: The SARSA calculates the Q-value for each non-terminal state
where _ is the step-size parameter and the reward discount factor.
Initialize for all s 2 S and a 2 A the value Q(s, a) to a constant value
Repeat for each episode:
Initialize s
Repeat for each step in the episode, until s is terminal:
Choose a for s using _
Execute action a and save reward r and next state s0
Q(s, a) = Q(s, a) + _[r + maxa0Q(s0, a0) − Q(s, a)]
s = s0
Figure 3: The Q-learning updates the Q-value whenever action a is executed
in state s leading to new state s0.
4.2 Test 1: SARSA versus Q-learning
The first test aims for a comparison between two RL techniques: the SARSA and the Q-learning. As we expect the computer game using the RL does really better than the scripted player and the Q-learning technique outperforms the SARSA, which verifies the online RL benefit and fast convergence in the Q-learning.
