Alice2022: Team Description Paper
Fan Wang, XueTao Lin and Yu Xiao.
Robotics and Innovation Technology Lab
School of Computer and Information
HeFei Normal University, P. R. China
Miracle.hftc@gmail.com

Abstract. This team description paper mainly explains the work of Alice2D at this stage.

According to the characteristics of our team , based on past research, our team iscommitted to studying the Monte-Carlo tree algorithm and reinforcement learningalgorithm. Changes to defense strategy optimization. After many tests, we continuously
optimize the team code, which has greatly improved the performance of the court.
Keywords: Monte-Carlo tree, SVM, Reinforcement learning

1Introduction

Alice2D was founded in 2016, by the Hefei Normal University Student Innovation
Laboratory of a group of robot-loving soccer students. Our team code is based onAgent2D3.1.0 [1] which was released by Hidehisa Akiyama. It also includes fragments ofreleased code of Marlik12[2]. On the basis of the accumulation of data left by the former
Alice2D captains, after several rounds of code iteration, the unique version was finallyformed. We sincerely thank all the open source developers involved for their help in
lowering the bar for us to participate in 2D competitions. In the 2017 World Tournament,
the team won the seventh place in the regular season and won the championship in thechallenge, 7th place in the 2018 World Cup regular season. In China, our team is also
named Miracle, winning the third place in China division of the 2019 RoboCup World
Cup and the third place in China division of the 2021 RoboCup World Cup.

2

Related Work

Here, we will study the chapter published by the 2D team. Cyrus2D team studied using
the server's full state mode to obtain the data set to predict the full state behavior of theball holder and optimize the perspective of the agent. FRA-UNIted team studies the useof deep Q-learning (DQN) algorithm to improve the learning speed of agent. Helios2021
team is committed to considering the ability differences between their own players andtheir opponents to exchange players' positions, so as to optimize the role allocation ofheterogeneous players. Yushan 2021 implemented the digital twin framework, used HFOtools to build the overall portrait of the team, and conducted in-depth analysis for the key
areas of attack of different teams on this basis.
These theories helped us develop the idea of modifying the source code and evaluate thechanges by running the game against the relevant binary pieces.

3Block based on Monte Carlo tree search

During the match, the ball handler's actions are ahead of other players, due to themechanism that players can accurately know their own actions and situations during the T
period, but the understanding of others can only come from the notification offered bySoccer Server during the T+1 period. Therefore, if our players only take actions thatcorrespond to the opposing ball handler’s actions, there may be a delay of one or morecycles. However, using Monte Carlo tree search to predict outcomes can solve thisproblem. Monte Carlo tree search algorithm consists of four processes: selection,expansion, simulation and feedback. During the selection process, we assume that theMonte Carlo tree will start when the opposing team takes possession of the ball and enters
our player's territory, or when the opposing team gains possession of a special mode ballto stop the game. Then the child node of the Monte Carlo tree is the state transition
generated by the state prediction after the defensive action output by Agent in thecompetition. In other words, the child node is our simulation of the defensive action. The
search algorithm starts at the root node and selects a path to the leaf node (a state thatmeets the expected value or is below the standard value, for example: The enemy passes
the ball, we trigger the interception logic, etc.) according to certain policies, expand theleaf node and do Monte Carlo simulation, record the results at the same time, and finally
update the value of the node according to the path of the simulation results. The successrate for each simulated state is the ratio of the number of times the node achieves theexpected payoff action to the number of times it is traversed.[4]Fig.1.The rectangle is the root node, the circle is the child node, the diamond is the leaf node4

Decision of shooting based on SVM

Shooting has the same nature as passing and intercepting, it is a confrontation with theopposing defender and the goalkeeper. Based on data mining techniques and 2,000 gamesof Alice2021 versus Helios2021 and Cyrus2021, we found that high speed shooting
increased the success rate of field goals.[7]We will consider the shooting points from the goaliepos, goalievel, goalieNeckangle,goaliebody, ballpos, ballvel, offsenseNeckangle, offsensbody, the distance between theball and the goalkeeper, the position of the opposing player seen in the forward's visualrange, and so on. And since different teams have different defensive strategies in thepenalty area, it is difficult for us to predict the movements of opposing defenders andgoalkeepers.

According to the one-step ahead model, the analysis of the success rate ofshots should be based on the state of the ball, the opposing defenders and goalkeeper inthe following period. Although we cannot predict the other's actions, it is possible topredict that from the next cycle, the fastest cycle the opponent can intercept the ball. As
long as the ball crosses the goal line in less time than the opponent can intercept it, the ballcan break the defense. Based on this basic idea, we classify the ball that can break throughthe defense and the ball that cannot break through the defense, and try our best to find thehyperplane with the greatest credibility. Due to noise and random error, it is not absolutely
possible to determine the initial speed of the ball after it is kicked out, and the predictionof the opponent is based on the state of the ball after it is kicked out. Therefore, N samples
are evenly collected for the possible speed of the ball after being kicked out, and theinterception analysis is carried out. We take that the ball can pass through the opponent's
defense as the expected state, assuming that M samples meet the expected state, then theprobability of successful shooting is𝑃=𝑀
𝑁We first normalized N data samples, and then selected gaussian radial basis function as kernel function for truncation analysis, namely𝑘(𝑥𝑖,𝑥) = 𝑒𝑥𝑝⁡( ‒| 𝑥𝑖 ‒ 𝑥| 2)[8]𝑥
𝜎 depending on the speed of the shot, 𝑖 consists of Ballvel, Dist, and Angle.
2𝜎2

Based on the results of the interception analysis, we then search for the hyperplane withthe greatest reliability from factors such as goaliepos, goalievel, and goaliebody. Thedistance calculation formula is as follows:𝑑=𝜔 𝑇𝑥 + 𝛾∥𝜔∥X is the coordinates of the support vector sample points, and ω and γ are the parametersof the hyperplane equation.
Experimental results show that compared with the SVM method, the former improves the success rate of shooting with a threshold value.

Fig.2.Analysis of shooting speed

5Judgement on the offensive and defensive situation of the team
based on reinforcement learning

In the game, the team formation has three states: offense, defense and transition.

Since

teams use different formations on offense and defense, players have different bases. If theplayer cannot identify the offensive and defensive state in a timely and accurate manner,
it will cause the efficiency of the execution of the running logic of the player to be reduced
due to the distance between the wrong base and the correct base, thus affecting the overall
strength. [3,6]Agent2D determines the offensive and defensive situation mainly based on the shortest
interception period of players. However, teams are prone to misjudgments due to noise,heterogeneous types, and random errors during matches. Therefore, we use more diverse
factors to determine offensive and defensive situations.
5.1

The Basic Process of Reinforcement Learning [11]In Markov decision processes (MDP), the agent can perceive the worldmodel as thecurrent environment state, and can execute any action in the action set. In the T cycle, theenvironment state is 𝑆𝑡. After the agent selects the 𝐴𝑡 action to execute, the environment
state 𝑆𝑡 changes from to 𝑆𝑡 + 1, and the R𝑒𝑤𝑎𝑟𝑑(𝑆𝑡,𝐴𝑡) is fed back to the agent at the sametime. In each subsequent cycle, the agent iterates repeatedly until it reaches the final state.
The action evaluation function 𝑄(𝑆𝑡,𝐴𝑡) represents the maximum attenuation cumulative
mean value obtained after the agent selects the action A𝑡 in the state, that is, the feedback
reward obtained after the agent executes the action plus the value that each cycle follows
the optimal strategy. The formula is expressed as:
𝑄(𝑆𝑡,𝐴𝑡) = 𝑅(𝑆𝑡,𝐴𝑡) + 𝛾𝑚𝑎𝑥𝑄(𝑆𝑡 + 1,𝐴𝑡)
where 𝛾(0 < 𝛾 < 1). In order to make Q-learning converge in an appropriate period, it isnecessary to add an appropriate learning rate to the formula. After introducing thelearning rate α, the formula of Q learning algorithm can be expressed as:
𝑄(𝑆𝑡,𝐴𝑡) = (1 ‒ 𝛼)𝑄(𝑆𝑡,𝐴𝑡) + 𝛼(𝑅(𝑆𝑡,𝐴𝑡) + 𝛾𝑚𝑎𝑥𝑄(𝑆(𝑡 + 1),𝐴𝑡))
Where 𝛼(0 < 𝛼 < 1).
5.2

State Description

There are many factors to be considered in the process of state transition. In most cases,
when the offensive state changes to the defensive state, there will be such a situation: ouroffensive line is near the enemy's restricted area, the defensive line is near the midfield
line, the sum of the distance between the ball and the two lines is at a large value, and theball quickly approaches the defensive line; Most of the players from both sides gathered
near the enemy's restricted area. When changing from defensive state to offensive state,
you only need to replace the marker values such as offensive line and defensive line ofboth sides.
The final state of defensive state can be described as that most of our players return to thestandard point; Can perform other defensive tasks; We regain the ball right; There arespecial modes (ball out of bounds, foul, etc.).
The final state of offensive state can be described as our goal; The ball is intercepted byan enemy player; Special mode appears (same as the final state of the defensive state)
5.3

Action Set

The action set is a collection of advanced individual actions that can be executed by theagent. The action set can be expressed as: {Intercept, Block, Tack, Mark, Assistdefense,Formation, Shot, Pass, Cross, Dribble, Selfpass}
5.4

Determination of Reward

Take the transition from offensive state to defensive state as an example, Reward = Basic
Reward + Internal Reward. The basic reward refers to the artificial division of areas. Thecloser an area is to the ball, the higher the basic reward. The internal rewards are mainly
determined by the distance between the ball and the offensive line, the defensive line, theaverage distance between the players on both sides, etc.
5.5

Updated Q Value

The Q value update formula in this paper is:𝑄(𝑆𝑡,𝐴𝑡) = (1 ‒ 𝛼)𝑄(𝑆𝑡,𝐴𝑡) + 𝛼(𝑅(𝑆𝑡,𝐴𝑡) + 𝛾𝑚𝑎𝑥𝑄(𝑆(𝑡 + 1),𝐴𝑡))
When the environment reaches the final state, the Q value can be updated once according
to the above formula.

5.6

Application

The fast execution of attack defense transformation can effectively prevent the occurrenceof throughpass, combined with data mining and linear regression. We get the following
formula.
Suppose the ball goes from point A to point B in N cycles. So the ball's initial velocity,𝑣0 is𝑣0 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒/(1 +𝑏𝑎𝑙𝑙𝑑𝑒𝑐𝑎𝑦 ∗ (1 ‒ ball𝑑𝑒𝑐𝑎𝑦𝑁)
1 ‒ 𝑏𝑎𝑙𝑙𝑑𝑒𝑐𝑎𝑦)[10]Distance represents the Distance from A to B and ball_decay represents the velocity
decay rate of the ball. With this calculated muzzle velocity, we decide whether we canintercept it or not, and if not, we choose another defensive logical run. By modifying
Alice2021's formula, we get a formula to calculate the interception success rate.
𝑝𝑎𝑠𝑠𝑠𝑢𝑐𝑐𝑒𝑠𝑠(𝑑,𝛼,𝑓,𝜀) ={1(1 + 𝑑)

2𝛼𝑓∗𝛼

Π

𝑚𝑎𝑥 ∗ (1 + 𝑑) ∗ Π∗ +𝑓[∗ 1‒

1(1 + 𝑑)2∗𝛼Π]} ∗

11+𝜀

[5,9]

Where D is the vertical distance between the passer and the receiver, α is the range of vis
ual Angle of the passer, F is the ability value of the passer, ε the interference of the player on the other side of the ball.
The experiment proves that it has a good effect on defending TP.Where D and F can be p
rovided by Soccer Server, while
𝛼 = 𝑎𝑟𝑐𝑐𝑜𝑠(𝑥 1 ‒ 𝑥 ) ∗ (𝑥 2 ‒ 𝑥 ) + (𝑦 1 ‒ 𝑦 ) ∗ (𝑦 2 ‒ 𝑦 )(𝑥1 ‒ 𝑥)2 + (y1 ‒ 𝑦)2 ∗ (𝑥2 ‒ 𝑥)2 + (𝑦2 ‒ 𝑦)2[9](𝑥,𝑦)are the coordinates of the passing player,(𝑥3,𝑦3)are the coordinates of the receiving
player,(𝑥1,𝑦1) = (𝑥3,𝑦3 ‒ 5),(𝑥2,𝑦2) = (𝑥3,𝑦3 + 5).
𝑛𝜀 = ( )/2𝑛0
𝑛0 is the threshold for the number of our players near the passing player.

Fig.3.Analyze pass success rates

6

Summary and Outlook

This team description paper describes the methods and algorithms implemented in thecode. To demonstrate the effectiveness of these strategies, we conducted a series ofcomputational experiments, as shown in the table below.
Table 1. Comprehensive results.
Before and after improvement

Diff Goals

Diff Points

Game Count____________________________________________________________________
Before improvement4148100

After improvement3093100____________________________________________________________________
Over the past year, our team has made improvements to formations and evaluators,
continued to refine the Monte Carlo algorithm's decision tree, and made modifications to
the types of players on the court in conjunction with portfolio strategy. There are still a lotof issues that need to be addressed in our team. In the future, our team will continue toimprove the algorithm, optimize scripting language, data mining, log analysis and othersections, and focus on the transition from Player module to Coach module.

We will learn from other teams' strengths and improve our weaknesses. We sincerely wish
the robot football simulation 2D will get better and better.
Thanks again to Mr.Cheng Zekai , Yushan team and MT team for their contribution to 2D
Alliance and guidance to our team members!

References
1. Akiyama, H., Nakashima, T.: Helios base: An open source package for the robocup
soccer2d simulation. In:Robot Soccer World Cup. Springer. 2013, pp. 528–535.
2. Tavafi, A., Nozari, N., Vatani, R., Yousefi, M.R., Rahmatinia, S., Pirdir, P.: MarliK 2012 Soc
cer 2D Simulation Team Description Paper. In: RoboCup 2012 Symposium and Competitions: Team Description Papers, Mexico City, Mexico, June 2012. (2012)
3. ZeKai-Cheng, NingYu-Xie, Feng-Zhang. et al. YuShan2019 Team Description Paper for
RoboCup2019, The 23th annual RoboCup International Symposium, Australia, 2019.
4. Zekai Cheng, Feng Zhang1 , Bolun Guang1 and Liting Wang. YuShan2021 Team Description
Paper for RoboCup2021.
5. Fan Wang, YuTang Guo,XingQi Zheng and XinYu Liu. Alice2021 Team Description Paperfor RoboCup2021.
6. CHENG Zekai,XIE Ningyu,YANG Sichun,SHE Xingxing. Application of digital twinframework based on RoboCup simulation 2D. Dec 2020.
7. Yuan Song,Gan Liu,Can Wang,Zekai Cheng.Research and application of RoboCup2D log filedata Mining. November 2015.
8. LIU Yang,W ANG Hao,FANG Bao-fu,YAO Hong-liang.Application of the method of support
vector regression in RoboCup. Oct.2007
9. Potter M.A,De J.K.Cooperative co-evolution:an architecture for evolving coadaptedsubcomponents[J].Evolution Computation,2000,8(1):10-29.
10. Yili Zhou,Xiangqin Bo. RoboCup passing strategy based on speed selection.2013.