I love computer and video games, especially online games. However, it has always bothered me that people with lots of free time has an advantage over me (who does not have lots of free time) when playing these games. How then can I compensate for my lack of free time ? The answer is to use programming. I’ve successfully done this a few times…read on.
When I played Hattrick, I had trouble negotiating for soccer players, because negotiations took place through an auction system. Being online at the time of the final auction was essential to getting players for a low price. Staying awake until dawn was not an option. Some of my friends usually set the alarm in order to wake up in time, but I never liked these exaggerations. So I created a program to bid on my behalf – it was a parser for the auction page, and it bid according to predefined parameters set up by me. I later added additional functions to the program, and my friends kept using it for a long time, even after I stopped playing Hattrick.
Currently I am playing World of Warcraft and I still do not have much free time. How can I gain some advantage over those with plenty of free time ? If I was able to use the correct items (armor, weapons etc.) in the game, it would be helpful. WOW is a very complex game and it would be impossible to do that manually. So, Tadeu Maia, who also plays WOW, suggested that we should create a program to find the best options. Calculating all options would take a long time. The solution is to use some heuristic to find the best item combinations. The first option that came to mind was to use genetic algorithms, and this reminded me of an algorithm that I used a long time ago called “Simulated Annealing”
“The Simulated Annealing algorithm is based on the fact that when a material is melted and cooled slowly, this material reaches a state of crystallization in which the molecules are perfectly ordered. The algorithm specifies an initial temperature, a decrement function of the temperature, a condition of balance for each temperature and a condition of convergence”.
In computing terms, Simulated Annealing is used to find the best configuration of a system by minimizing (or maximizing) the value of an associated cost function. Regarding WOW, we can use the values of Attack Power (AP) combined with Armor to generate a cost function. Alternating the items chosen, we will have different values of AP and Armor and, therefore, a different cost. The goal is to get the best items configuration that would result in greater value for both parameters within a certain proportion.
The first step is choosing an initial configuration. This can be achieved by a random choice or by a simple heuristic. After the choice is made, the algorithm itself is initiated. The algorith makes random changes to some items, usually for different types of classes of characters (Warrior, Priest, Paladin, etc.) – we have a lot of items available. With this change it creates a new state for the system and a new cost is estimated. The cost difference is also calculated Δc = c1 – c2. If Δc < 0 then this new configuration will become the current configuration. If Δc ≥ 0 then the new configuration is accepted with probability 
, where T is the current temperature of the system. Otherwise, it is rejected and the configuration is returned to the previous state. The probability to accept a configuration, where Δc ≥ 0, serves to prevent the cost function becoming confined to a local maximum. In order to accept bad change, the algorithm expects that in future steps, the subsequent changes will produce a best configuration. It should be noted that this method is heuristic. At the beginning of the Annealing algorithm, when the temperature is higher, the probability of accepting bad change is greater. As the temperature decreases, the system tends to find a better balance. This is an analogy to the physical process of melting material, because when subjected to high temperatures, molecules are in a state of complete disarray.
The algorithm has a condition of balance for each temperature. For the system to switch to a lower temperature a fixed number of iterations should occur without changing the current configuration, i.e., without finding a better configuration. Because of this, the algorithm will find a better solution within a neighborhood of solutions (a local maximum). The algorithm parameters, for instance initial temperature, number of iterations prior the balance etc, are usually established empirically and should be adjusted according to the program usage.
It seems incredible (I did not believe it until I saw the results) but we can obtain a really good solution using the Annealing algorithm. We plan on implementing our program in Python and I think it will be a great deal of fun.
