Nemesis Team Description 2010
Mehrab Norouzitallab, Amin Javari, Alireza Noroozi, S.M.A. Salehizadeh, Kourosh Meshgi
Amir Kabir University of Technology, Hafez Ave., Tehran, Iran
Abstract In our study, we tried to develop our teams in such a way that machine learning techniques and advanced artificial intelligence tools have the main role in improving skills and increasing team performance. We consider soccer simulation platform as an uncertain and dynamic environment, so we develop learning algorithms according to this important feature and agent's partial observability.
Introduction
The Nemesis team was established in 2004 aiming to develop our team in such a way that machine learning techniques and advanced artificial intelligence tools have the main role in improving skills and increasing team performance. Each year, new members are joining our team to further their studies on these fields and use this simulation environment and previously implemented team as their basis of work. Nemesis is founded to serve as a platform for machine learning schemes such as artificial neural networks, evolutionary algorithms and reinforcement learning. Today this team is used as a platform for testing new ideas on as long as implementing latest papers to observe their dynamics. Several course projects and master these are implemented on this base too.
Nemesis base is updated by HELIOS 2008 code release under GPL and since then we change our Formation strategy to Fuzzy ARTMAP [8], add a Mark skill based on Maximum Weighted Bipartite Matching [1], improve our Block skill by enhancing a method called neuroHassle [5], and improve Offensive positioning by the means of PSO algorithm [2]. Also we introduce a framework called Mental Simulation [6] for Decision making. There are many more improvements everywhere in the code e.g. major improvement of Passing, minor debug of Dribbling and so on.
As a software cycle policy our team publishes the code at the end of March annually, and lots of complementary material along with source code will be available on: http://mnt.ir/nemesis
Marking
Mark skill is one the important defensive skills in soccer simulation. We formulated this task as an assignment problem, in which our players should observe and follow opponent players to confine their collaborative offensive abilities. To address this assignment problem we employ "Maximum Weighted Bipartite Matching" as the framework of this task assignment problem and make use of Hangarian algorithm to solve it [1]. Note that this skill is under training and not fully embedded inside the source code so far.
Applying MWBM Structure to Player Marking Problem
There are plenty of considerations regarding the efficient assignment of our defenders to opponent team attackers via Marking. First we establish the bipartite graph comprising teammate defenders on one side and attackers on the other side as the graph's nodes such that, each edge has a weight, w(i,j) which represents the importance of marking player j by player i. In order to calculate these weights a linear function of the effective factors is defined, as follows.
$$w(i,j) = \frac{1}{m} \sum_{k=1}^{m} C_k F_k(i,j)$$
Where m is the number of effective factors, F represents the value extracted for feature, and C is the respective coefficient. Table 1 contains a list of these features which can be classified into two classes: the factors which determine the ability of defender to mark the attacker $(F_1, F_2)$, and those correspondent with the risk of the opponent $(F_3, F_4, F_5, F_6)$. These features are defined based on several expert rules and are based mathematical formulas.
Effective factors for calculating weights of the MWBM structure for Mark skill
| Factor | Description | Value | |
|---|---|---|---|
| Defender | $F_1$ | Distance from defender home position to mark position | The less this distance is, the higher value should be set to $F_1$ |
| $F_2$ | Distance form defender current position to mark Position | The less this distance is, the higher value should be set to $F_2$ | |
| Attacker | $F_3$ | Confidence of attacker position | The more accurate estimation of attacker point, the more accurate Mark position is calculated. Therefore other factors reach the more accurate values. |
| $F_4$ | Distance form attacker position to ball position | The nearer the attacker position to the ball position is, the more likely the attacker can receive the pass | |
| $F_5$ | How dangerous the marking area is | The areas in which the probability of shoot or one-to-Goalie state is higher, assumed to be dangerous areas. This probability specifies the extent of hazardousness. | |
| $F_6$ | Distance from mark position to the nearest point on goal line | The less this distance is, the more danger is occurred. |
Parameters Tuning
The weights of MWBM can be optimized in two fashions: First, applying more effective factors ($F_i$), and second tuning the parameter ($C_i$).The six factors considered in Table 1 perform good enough to address the first issue. Thus, here we propose an approach to adjust the coefficients in such a way that the resulted weights lead to a promising MWBM structure for the Mark skill.
A training procedure is introduced to fine tune these parameters. In this scenario the attacker players of opponent team and the defender player of our team is in the field and in each episode the ball is granted to an attacker. Our player should mark opponent players based on MWBM. An evolutionary algorithm (e.g. PSO, ES, DE, etc.) could be applied to adjust the parameters based on these trainings. In our implementation, Particle Swarm Optimization method [2] is hired to maximize the fitness function resulted from the outcome of the scenario [3]. This fitness function is indeed the value obtained from Eq. 2 and the optimization procedure adjusts the values of $C_i$.
Block Skill
Defending against incoming attacks and recapturing the ball is a crucial task for each team. Defending strategy consist of two sub-task: Positioning and Hassling. The former task aims to arrange players in free spaces so that they are capable of intercepting potential opponent passes, covering the direct defending player, marking the attacker player possesses the ball, and avoiding opponent to have clear shoot toward the goal (section 2). The latter task is to improving the aggression skill of defender in the manner that they can interfere the opponent ball leading player, "hassle" him, and bringing ball under their control while simultaneously hindering him from dribbling ahead. The task assignment should maximize the collaborative defense utility [5].
Brainstromers team has employed an effective scheme for the hassling task since RoboCup 2007 competitions called neuroHassle[5]. We are working on an enhanced version of this approach to be embedded in our block mechanism. The architecture of our proposed solution differs slightly from the one explained in [5] yet use similar basics and training concepts. We added the distance between ball and our goal and amount of remaining stamina of the defender to the inputs of learning MLP neural network and also grant different amount of stamina to defender in each training episode to consider realistic situation of the game. In order to enable exploration to find better and more effective solution for defense, we use criteria of energy saving mixed with Boltzman exploration to modify online greedy policy during training. The idea behind this choice is that although large sets and random episodes with start situation brings about a good level of state space exploration as assumed in [5], but the found policy may be not efficient in the terms of stamina, and yet may not cover various dribbling tricks enough and not generalized properly. In this regard we plan to improve our block system with these ideas: Enable a defender to shout for help if his stamina level decreases to a critical level, energy saving scheme for players when the score of the team is in good winning margin trying to lead scenario to time out, early hassle in opponent field in the case of low number of opponent players around, and train a defender to hassle when one more player from each team of attacker and defender are present in the field to enable hassling player to block the passes from the source.
Positioning
Formation Strategy
In the last version of Nemesis, we used Fuzzy ARTMAP as knowledge based neural network for extraction of expert knowledge [8]. As a result a model of behavior could be formed combining low-level behavior and expert knowledge. Experimental tests performed last year showed that the proposed model exhibits a higher performance than the conventional BPN. Our current framework is to some extent different. We added the current position of the agent to the current inputs of the neural network and generate the home position. This would result to a completely dynamic positioning framework.
Offensive Positioning
We introduce two circular regions, one for each player of our team and the other around the original position obtained by the positioning method, both with the radius of 10. Then, we quantize the intersection area between these 2 circles into 40 points. Finally, we weight these 40 points plus the original positioning point according to the same procedure that proposed for tuning the parameters in Mark skill development but using completely different features as illustrated in Table 2.
Effective factors for calculating weight of each candidate offensive positioning point
| Factor | Description | Value |
|---|---|---|
| F1 | Distance from the point to the nearest point on the opponent goal line | Lower values are better. |
| F2 | Difference of the angle between the upper frame of the goal and the point, and the angle between the lower frame of the goal and the point (goal view angle) | The higher this value is, the more likely to shoot toward the goal. |
| F3 | Distance from the point to the nearest face2face opponent | Higher values are better. |
| F4 | Probability of receiving the pass in that point | Higher values are better. Calculated by a simple geometric algorithm. |
| F5 | Number of cycles takes to reach the point | Lower values are better. |
| F6 | Distance from home position to the point | Lower values are better. |
| F7 | Distance from ball position to the point | Lower values are better. |
Decision Making
Klein made a decision model called Recognition-Primed Decision Model [6]. The model solves the problem by considering the situation, recognizing it, recalling the situation's experience and implementing it. The decision maker knowing the situation, also know the goal should be followed, cues should be used to gather information, expectations should be monitored and course of action should be implemented. Although, the model has various aspects, we focus here on its mental simulation part. When a decision maker engaged in a complicated situation, after recognizing the situation and recalling the solution, he or she tends to be assured of its success. This is done usually when decision maker senses their insufficient cognition of the environment. Therefore, he or she scans the course of action for tuning, modifying or even omitting it and making a new solution. Klein calls this process, mental simulation. All of the mental simulation is done mentally before implementing the course of action or even while implementing it. The mental simulation process defined there based completely on the human cognitive abilities and is similar to the findings of Hastie in [7].
In the 2D soccer, the teams plan to win opponent is very similar to this kind of decision making. Especially when an unpredictable change occurs in the middle of the game it is very important to guess the opponent's plan and proposing a proper strategy to conquer. This framework is a new viewpoint to decision making and we plan to further our study in this area and use it as our future work.
Conclusion
In this study, we proposed some of our novel strategies and methods to improve the important skills and important tasks in an appropriate way. A new framework introduced to address the player marking, which has been based on the maximum weight bipartite matching structure. A new dynamic formation strategy is suggested updating our last Fuzzy ARTMAP scheme too. We proposed an efficient approach for offensive positioning which can overcome the opponent team defensive and marking strategy. The block skill is improved via reinforcement learning approach. Finally we introduced a new framework for the decision making problem and we will further our study on it as our future work.
References
[1] M. Paul. Algorithmen für das Maximum Weight Matching Problem in bipartiten Graphen. Master's thesis, Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, 1989. [2] R.C. Eberhart, J. Kennedy, "A new optimizer using particle swarm theory," Proceedings of the Sixth International Symposium on Micro Machine and Human Science (MHS'95), Nagoya, Japan, 1995, pp. 39–43. [3] L. Messerschmidt and A. P. Engelbrecht, "Learning to play games using a PSO-based competitive learning approach," IEEE Trans. Evol. Comput., vol. 8, no. 3, pp. 280–288, Jun. 2004. [4] M. M. Korjani, A. Afshar, M. Norouzitallab, M. B. Menhaj, "Dynamic Autonomous Agent Positioning Based on Computational Intelligence," Proceedings of IAENG Conferences, IMECS 2009. [5] T. Gabel, M. Riedmiller, F. Trost, "A Case Study on Improving Defense Behavior in Soccer Simulation 2D: The NeuroHassle Approach," RoboCup 2008: Robot Soccer World Cup XII, LNCS, Berlin, Springer Verlag. [6] G. Klein, Sources of Power: How People Make Decisions, Cambridge, MIT Press, MA, United States, (1998). [7] R. Hastie, and N. Pennington, Explanation-Based Decision Making, In T. Connolly, H.R. Arkes, and K.R.C. Hammond (Eds.), Judgment and Decision Making, An interdisciplinary reader, pp. 212-228, Cambridge University Press, United States, (2000). [8] M. Norouzitallab, M.M Korjani, S.M.A. Salehizadeh, A. Pourshoghi, D. Khashabi, A. Razaghpanah, P. Kaviani, and M. Vosoughpour, "Nemesis Team Description 2009," RoboCup 2009, Graz, Austria, 2009.