NADCO-2D Soccer 2D Simulation Team Description Paper 2011
Mohammad Ali Sadeghi Marasht
Department Of Computer Software Engineering Islamic Azad University - Northern Tehran Branch; Department of Artificial Intelligence and Multi-Agent Simulation NADCO Educational Robotics Corporation
Abstract This paper outlines the high-level Team-Contributing Skills, emphasizes on the use of the Coach, and highlights the main Individual Agents' Skills designed and implemented by our team within last year.
1 Introduction
The NADCO-2D team leader started his career in the soccer 2D simulation league in 2004. He has been away from the competitions for a few years and began continuing to work again two years ago with the SAMIN team. The team's name changed to Lion-Griffins last year. The NADCO-2D team is continuing the Lion-Griffins efforts. The team leader has participated in several worldwide competitions such as IranOpen2006, IranOpen2010, IranOpen2011, GermanOpen2010 and AUTCup2010 so far. He is also the founder of the Artificial Intelligence and Multi-Agent Simulation Department of the NADCO Educational Robotics Corporation which many students attend it each year. We have chosen the Agent2D-2.1.0 base source code as the code to work on due to the good implementation of low-level layer.
2 Defense System
Our current defensive system is divided into four individual sub systems which let the defenders to possess or keep away the ball under massive attacks, or get position in the highest valued points of the middle defense region in the formation. The defenders are selected according to a defensive decision tree by using an evaluation algorithm. The sub systems are discussed below in more details.
2.1 Block
Block skill is how defenders forestall the ball and possess it. Our Block skill used to choose the closest defender to the ball as the blocker and assume a block point ahead of the opponent offender. Although we were expecting it to work good, we faced problems with stamina decrease on the long pursuing of the ball and the long dribble skill of the Helios2010 team was able to completely pass our blocker. The method changed as described below.
2.1.1 Block Point and Blocker
2.1.1.1 Block Point. The block point is a predicted point on the block route from the inertia point of the ball toward our target or ahead. A tuning parameter is assigned to optimize the angle of this block route between zeros to the angle to our target. The distance of the block point to the ball position is firstly 8 meters, and is corrected when blocker assignment procedure is done.
2.1.1.2 Blocker. The blocker choosing method is determined through defenders positions. The near defenders and midfielders positions are evaluated using the factors including {distance to ball, distance to block point, Y-diff to block route, remaining stamina, reach cycles to block point, angle from block point and target point, body direction}. The highest valued defender is assigned as the blocker.
2.1.1.3 Block Point. The block point length is corrected according to formula 1.
$$d = -0.0003x^3 + 0.0099x^2 + 0.1109x + 5.0909$$
Where x is the absolute length of the ball position, and d refers to the block point difference to the ball in length.
2.1.2 Block Behavior
The blocker will choose a method for possessing the ball according to the ball region. This phase is begun when blocker is already on the block route.
- 2.1.2.1 Normal Behavior. This behavior is chosen when the ball is in a dangerous region. In this method, the blocker approaches toward the ball and uses the ballintercept methods to possess it.
- 2.1.2.2 Support Behavior. In this behavior, the blocker asks the nearest defender to the ball-owner behind him to intercept the ball. This is done using the say command, which is also used when the blocker faces stamina problem and is not able to continue perusing the ball-owner in other situations.
2.2 Hassle
Our Hassle skill is one kind of a Play-On Mark in which the defenders who are not blockers, try to keep a good close distance to each of opponent offenders, so the ballowner faces difficulties to find a proper teammate to pass the ball to. The hasslers get position not on the pass routes, but behind the offenders. This will bring two opportunities. One is to be able to enter the Block System rapidly and become the blocker; another is to prevent the ball-owner to send a through pass which will cause in reaching to the ball earlier than the opponent. The "Maximum Weighted Bipartite Matching" [1] employment has enhanced our previous pair-making procedure.
2.3 Mark
The Mark tactic is how to get position in front of the opponents so they cannot have eye contact with the ball owner and receive the ball passed to them. Since we have integrated the Hassle skill during the Play-On play, our Mark skill is dedicated to the Set-Plays in which the opponent agents are positioning according to their static formations. Our Mark skill is divided into two parts, which are to mark the opponents in their set-plays, and to escape from being marked by the opponents in our set-plays.
2.4 Clear Ball
It is a reliable skill in which the agent kicks the ball to the furthest positions to save the target. The clear point is calculated using either three methods. At first it tries to make a long distance pass to a further teammate which will cause in a rapid offense. If fails, it looks for open routes among players by iterating the pitch within the widest angle from its position. At last, it kicks the ball in a specific angle with maximum power.
3 Positioning System
Although the players get position in their home positions according to their formation files by default, we already know that the predefined home positions will not do best for every situation. Thus we have integrated higher-level algorithms which evaluate the field's points and weight them to bring a better positioning system. They are brought below in more details.
3.1 Global Positioning
Mostly, the offside line is a remark for changing the home positions into better ones. Besides, the ball does not move smoothly as defined in the formation files most of the time, but is kicked rapidly among different points of the field so the players cannot correctly make position in their home positions. Global Positioning is a simple position correction skill to cover these issues.
3.2 Formation Changing
Our midfielders (numbers 2, 3, 6 and 7) are the most important players in the team. They are totally responsible for bringing the ball from defense half to offense half and vice versa. They make a quarter rotations when they are blocking or passing forward. They are the reason of changing the formation among 6-2-2 in the defense half, 3-5-2 in the middle and 4-2-4 in the offense half. Fig. 2 shows their responsibilities in defensive, normal and offensive strategies.
3.3 Field View Coverage
It is a low-level skill which manages the players view commands to cover the entire field. It recursively iterates the field for a better view angle and view width according to the ball and other teammates and opponents positions which helps the team to have an updater feeling of the environment.
4 Offense System
(This section contains subsections listed below)
4.1 Pass
It is almost the most important skill in the soccer game. Basically our pass skill is implemented oriented on calculation. It consists of four types which an evaluator chooses the best among them according to the ball region.
4.1.1 Direct Pass Routes
Points are evaluated upon some factors such as {distance to ball, position in the field, nearest opponent, X-diff and Y-diff to ball, body velocity, body direction}. The highest valued point is chosen to pass the ball to. This type is mostly used in the opponent half when indirect passes are more risky and may lose the ball.
4.1.2 Leading Pass Routes
It is similar to the previous one, while the examined point is a bit ahead of the teammate's current position. This distance is less than 10 meters and is a fraction of the distance to ball. This type is more used in the self-half from the midfielders to the side forwards and wings to move the ball quicker.
4.1.3 Through Pass Routes
While it is to send the ball through the opponent defenders to behind them, an accurate algorithm is implemented. Except the previous factors, we benefit a reach cycle predicting function to check the probability of sending the ball to the desired point.
As Fig. 3 shows, the intersection of the ball routes (black lines) with teammate routes (red lines), outputs some points which are suitable for evaluation. The teammate routes have Θ difference in angle. The bigger absolute width of the teammate, the more is assigned to Θ. The ball routes have d1 difference in length on the 0° teammate route. The d1 value is almost 1 meter but may be shorter in more dangerous regions. The d2 value is the total length of the 0° teammate route which is 25 meters at most. Each intersecting points is evaluated using the factors such as {nearest opponent reach cycles, teammate reach cycles, position in the field, d1, Θ, distance to ball}. The highest valued point is selected as the best through pass point.
4.1.4 Requested Pass Routes
It is a delayed type of pass in which the non-kickable teammates try to get position in valuable points and ask for the ball in their desired positions. As we know, it is possible to hear the said messages in the next cycle, and the ball-owner can archive their requests for a short period of cycles. So the delay between asking for ball and kicking it by the ball-owner is between one to 5 cycles, which will cause in early moving of the teammate to the reception position. Thus the teammate will reach the ball before the opponent defender.
4.1.5 Verification the Pass Routes
Verifying the pass routes is the most important part of the calculation which leads to success or failure of the passing procedure. We have implemented our verification algorithm based on factors including {distance to pass point, ball first speed, ball reach cycles}. Then it checks the opponents for factors including {body direction, reach cycles, kickable distance, tackle distance, body velocity, turn cycles, goalie catch distance}. The procedure is to add up all the cycles that take an opponent to reach the pass route and compare it to the cycles that take the ball to pass that point.
4.2 Pass Maximum Weighted Graph
Our idea came from how we can move the ball from center positioned roles to the offensive roles that have a much better goal situation, within the least cycles of game time and fewer pass kicks. In our methodology, the teammates are the nodes of a weighted graph, the ball is the root node and the attacker is the destination node. The best pass routes are the edges of this graph. As we have implemented an evaluation method for pass routes, the edges are weighted according to the probability of successful ball reach. The algorithm traverses the graph to find a short path from the ball to the attacker. If one path is created, then kick command is sent. Otherwise, the algorithm adds up the edges' values to find the highest valued path.
Consider Fig. 4 as the beginning situation of this method. The ball-owner knows which teammates are proper to pass the ball to (black lines). Each near teammate also finds the possible pass receivers from itself and uses the say command to say up to 2 teammates' positions, numbers and pass routes values (red lines).
Fig. 4.1 visualizes the weighted graph created by the ball owner. The ball-owner kicks it to the first node after itself and the receiver calls this method again. The next weighted graph is quite similar to the previous one.
As it is viewable in Fig. 4.2, numbers 7, 9, 10 and 11 are positioning quite similar to their positions in Fig. 4.1. But number 9's position is changed more in Fig. 4.3.
This low noise is needed to be predicted by the assigned values to each pass route by the teammates. So Ci is the respected coefficient. It contains the estimated move distance according to the duration of the ball reach among teammates, i.e. the distance between number 9's positions in Fig. 4.2 and Fig. 4.3 during the reach cycles of the ball from number 11's position to number 7's position.
4.3 Dash (AKA Long-Dribble)
In this type of moving forward, the agent kicks the ball to the front space and moves as fast as possible to get and kick it again. In this pattern, the agent can move toward the opponent half and their target with the highest speeds so it can pass aside the opponent defenders and reach the target rapidly. The involved factors in this skill are {current ball position, next ball position, current stamina, predicted next stamina, body direction, body velocity, existence of opponents and teammates in near positions, reach cycles to the next ball position, minimum reach cycles of the opponents to the next ball position}.
5 Coach
(This section contains subsections listed below)
5.1 Environment Analysis
Since we have a full comprehension on the ways the coach receives the server's observations data, we can utilize a few methods to process the environment and discover the probabilistic weaknesses in the defending lines and/or the complete team formation.
To do so, we have integrated an algorithm to find the dangerous opponents and advise the defenders for making pair with them to restrict their space of move with or without the ball. One problem is to handle the limitation of the free say message of the coach to 300 cycles. As we can estimate, not only all the opponent's agents are not dangerous but we can just count at most three of them as these ones. So the free form say message length belongs to the routine positions of these players in a loop of about 300 cycles in a shortened form. So the players can gain access to the information of their space of play and continue marking them with predicted points to move to until the next advice form the coach. The dangerous opponents are the closest of them to our target in front of the danger region that have the maximum absolute width value. The side defenders are responsible for hassling them while other defenders and midfielders may block them or intercept the ball.
5.2 Statistics Review
As another coach duty to accomplish, a Statistic Review of the match is processed and printed each 1500 cycles in complete form of the realistic soccer matches information.
6 Future Plans
In this team description paper, we described our researches and efforts in our team NADCO-2D. As our future plans, we are working on ANN Repeated Decision Maker and Online Opponent Modeling methods. We also are impressed by the WrightEagleBase framework [2] and will start up another version of our team on this base in near future.
References
- Molitor, P.: Algorithmen für das Maximum Weight Matching Problem in bipartiten Graphen. Master's thesis, Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, 1989.
- WrightEagle Soccer Simulation 2D Team, WrightEagleBASE, http://wrighteagle.org/2D/