Collaborative agents
UCM agents for the Geometry Friends game AI competition
About Collaborative agents
Geometry Friends is a two-player cooperative platform game developed by GAIPS INESC-ID. The game is composed of a series of levels in a two-dimensional, physics-driven world in which two agents, a circle and a rectangle, must collect as many diamonds as possible in the least amount of time. The agents participate individually or cooperatively, depending on the game mode.
Every year, Geometry Friends competitions are held in association with international conferences such as the Conference of Games (CoG) and the International Joint Conference on Artificial Intelligence (IJCAI), which consist of the implementation of AI agents capable of solving some of the levels. There are three categories or modes of participation: Circle Track, Rectangle Track and Cooperation Track. Although the game was initially designed to foster cooperation, it was extended with levels in which only one of the two characters, either the circle or the rectangle, competes. These levels allow for dealing with the complications of the physical environment and solving planning problems, without initially getting into the challenges of cooperation. Typically, the Circle Track competition presents challenges more related to interaction with the physical environment where high precision in the execution of actions is required. On the other hand, the Rectangle Track, focuses on planning and puzzle solving while in the Cooperation Track, communiaction and communication and coordinated actions are key.
Rectangle Track Level
Circle Track Level
Cooperative Track Level
UCM Agents
The students Alberto Almagro Sánchez and Juan Carlos Llamas Núñez, led by Prof. Belén Díaz Agudo and Prof. Antonio A. Sánchez Ruiz, have developed intelligent agents - the UCM agents - capable of solving the vast majority of the existing levels to date, and which have won the Rectangle and Cooperative Tracks and came a close second position in the Circle Track in the IJCAI/CoG 2023 competitions. This project was part of the Undergraduate Final Project 'Development of Artificial Intelligence techniques for the dynamic and collaborative environment Geometry Friends', which is published with free access at Docta Complutense. Furthermore, all the open code associated with the project is accessible on our GitHub repository alberalm/TFG-Geometry-Friends.
Actions
Each agent has its own set of actions according to its characteristics. The circle can roll to the right or left and can also jump. The rectangle can slide left and right and is also able to morph. This means that it can change its shape continuously while keeping its area (and mass) constant. The range of shapes varies from one in which its base is wide and in its height is small, to one in which its base is narrow and has maximum height, all the way through a square shape. However, the rectangle cannot jump, making reaching the highest points of the level with this agent often a challenge.
Agents also interact with the environment and with each other. Agents bounce off obstacles that are not of their same colour, i.e. the rectangle bounces off black and yellow obstacles and goes through green ones, while the circle bounces off green and black obstacles and goes through yellow ones.
Strategy
Our approach to the problem has been to inject expert knowledge into UCM agents. To do so, the resolution of each level is divided into three phases: representation of the level by means of a graph, planning of the movements to be executed and execution of the plan.
In the first phase, platforms are identified, movements (which are connections between platforms) are generated and a filtering to retain a minimal complete set of movements is applied. As a result, a graph illustrating the level and various pathways between platforms is built, where the nodes depict the platforms, while the edges represent movements to traverse to other platforms or reach diamonds.
Example Circle Level
Identification of platforms and movements
Graph representation
In the second phase, a high-level plan is generated, i.e., a path in the graph that let the agent(s) collect all of the diamonds and which is composed of movements that change platforms or capture diamonds. The plan is generated by performing a time-limited breadth-first search with repetition control over the graph. During the execution phase, a real-time replanning and alternative paths to avoid moves that proved to be difficult are also taken into account.
Circle plan: (I) jump to the right-hand side platform, (II) jump to the top platform and (III) capture the diamond.
The third and final phase is the execution of the plan. Each type of movement that we have identified has a different script that encode the atomic actions to be exectud by the agent(s) in order to successfully complete the movement. Here are some of the different types of moves for the circle and the rectangle, as well as a compilation of cooperative moves and behaviours, and what the agents are told to do in those situations.
Circle moves
JUMP: during the first phase, the parabolic jumps of the circle are simulated and during the third phase, they are executed.
FALL: likewise, parabolic falls from the edges of the platforms are simulated and executed, taking into account rebounds with objects.
CLIMB: With this move, the circle is able to roll over small heaps or stairs without the necessity to jump.
Rectangle moves
FALL: a fall is executed considering the angular rotation around center of mass.
DROP: the rectangle morphs up to fall between two close platforms.
MONOSIDEDROP: similar to a DROP, but the small gap is between a platform and a wall.
BIGHOLEDROP: first way to execute the move (the gap is too large to just DROP).
BIGHOLEDROP: second way to execute the move (the gap is too small to just FALL).
BIGHOLEDROP: third way to execute the move (all of them are learnt with Q-Learning).
TILT: the rectangle leans on the vertex of the object and tilts.
HIGHTILT: similar to a TILT but the landing platform is higher and it needs to gain more speed.
BIGHOLEADJ: when the gap is too big to slide this type of move is needed.
Cooperative moves
TRANSPORT: the circle uses the rectangle as a platform and the rectangle transports the circle while the circle keeps the balance.
TRANSPORT: while transporting the circle, the rectangle can slide through small gaps between platforms. between two close platforms.
CIRCLETILT: in this move, the rectangle can use the circle as a support point to tilt and get to a higher platforms it wouldn't reach on its own.
BASIC LANDING: the circle waits for the rectangle to stablish its position and then proceeds to jump and land on top of the rectangle.
REBOUND LANDING: when the landing is not smooth, the rectangle has to prevent the circle from falling.
POSITION EXCHANGE: when agents need to go to opposite sides of a platform and they aren't in the proper order, they must change its position.
RECTANGLE MOVES ASIDE: this is to avoid interfering with circle's trajectory, but as soon as the circle is high enough, moves to serve the circle as a platform.
RECTANGLE AVOIDS CIRCLE: As well as in jumps, the rectangle also has to avoid colliding with the circle in certain falls.
FAILED JUMP: when a jump is failed, the rectangle follows the circle to save time so that it lands on it again to try the jump once more.
2023 Geometry Friends Competition
The purpose of our work has been to participate in the 2023 Geometry Friends competition which is associated with the prestigious international conferences IJCAI and CoG. The competition is subdivided into three tracks: the Circle Track, the Rectangle Track and the Cooperative Track . Each mode is regulated by a scoring system that takes into account the number of diamonds collected, the time spent and whether or not each level has been completed, i.e. all the diamonds in the level have been reached before the level time expires.
Agents are evaluated on a total of 10 levels, 5 public which is available from the beginning of the competition to help the developement of solutions, and 5 private levels which are kept hidden until the end of the participation period, to avoid over-specialization. Each agent is executed 10 times in each of the 10 levels and the final score is obtained by adding the score of each level, which is the arithmetic mean of the scores of the 10 runs in that level. The score for each run is calculated using the formula
$$\mathrm{SCORE}=V_{\mathrm{completed}}\times \frac{maxTime-agentTime}{maxTime} + (V_{\mathrm{collected}}\times N_{\mathrm{collected}})$$
where Vcompleted is the score received for completing the level, maxTime is the time limit of the level, agentTime is the time spent by the agent completing the level, Vcollected is the score for getting a diamond and Ncollected is the number of diamonds obtained. The values of Vcompleted, Vcollected, and maxTime are provided by the organisation in each of the editions and may not be the same for all the levels.
During the first phase of the competition, when only public levels where evaluated we led on the three tracks, being the Circle Track the only one in which we did not have a significant margin over the next participant. Our slight advantage came from the lower elapsed times we had over the rest of the participants.
Finally, in the second phase, all agents were evaluated on the private levels, which had remain unknown. The results were excellent, as we came first with a big lead over the runner-ups in the Rectangle Track and Cooperative Track and second, closely behind the winners, in the Circle Track. The final scores of each of the Tracks are available here and we can see a summary of them bellow:
| Circle Agent | Total score |
|---|---|
| thunder | 5,388 |
| UCMAgent | 5,358 |
| KIT Agent 2017 | 5,328 |
| amitai | 4,126 |
| test2023 | 2,641 |
| asura | 1,421 |
| AgentWithPrediction2016 | 1,370 |
| Rectangle Agent | Total score |
|---|---|
| UCMAgent | 6,449 |
| thunder | 5,035 |
| RRT Agent 2017 | 4,493 |
| test2023 | 4,051 |
| asura | 2,670 |
| AgentWithPrediction2016 | 1,740 |
| Cooperative Agents | Total score |
|---|---|
| UCMAgent | 6,256 |
| thunder | 3,141 |
| zvbe2022 | 2,600 |
| asura | 1,560 |
| AgentWithPrediction2016 | 1,230 |
Circle Track
Among the circle levels, the one that finally decided our position on the leaderboard was level 6. This level had appeared before in previous competition, and it looks like this:
Level 6 of the circle competition
The strategy is not obvious at first, and all human players with whom we tested the game struggled solving it. The most problematic feature of this level is that you cannot recover if you fall from the upper platforms, which is likely due to how physics work when hitting the ceiling. The key to solve the level is going to the left-hand side before going to the right-hand side, which our agent succesfully identified. However, the landing on the narrow platform and a small variation on the necessary speed makes it hard to complete the level, even if you know what you are supposed to do. Our agent manages to complete it around half the times, getting 2 out of the 3 available diamonds in the rest of the attempts.
This level turned out to be the deciding factor. The Thunder agent, our main competitor, managed to complete it in 6 out of the 10 runs, one more than our UCM Agent. With perfect results in the other levels, we obtained a close 2nd place. It is worth noting the bronze medal went to the KIT Agent which completed the deciding level 4 times, so the podium scores were extremely close one to another for the Circle Track. Bellow, a video showing the performance of our Circle UCM Agent in the levels of the 2023 GF Circle Track Competition is displayed.
Rectangle Track
In the Rectangle Track, every level seemed easy for the UCM Agent, who managed to build a big gap to the second best agent. Very rarely (around 1 every 20 runs), our agent got stuck in level 9. Unfortunately, this happened in one of the runs of the competition, but it did not have any impact on the leaderboard. A video of our Rectangle UCM Agent completing the levels of the 2023 GF Rectangle Track Competition is displayed bellow.
Cooperative Track
In the Cooperative Track, most of the levels were similar to previous years' levels. The UCM Agents sweep away the competition, doubling the second-place finisher in total points. The results show level 6 is problematic for our agents. After picking the first two diamonds, they always got stuck in this position:
Level 6 of the cooperative competition
This happens because of a discretization error in our implementation, in which our agents think they are able to slide under the black block when they actually cannot. This is something we knew could happen, but it was a design decision in which the pros significantly outweighted the cons. Every other level was completed almost every time without issues, as shows the following video whith the performance of our Cooperative UCM Agents in the 2023 GF Cooperative Track Competition.
Local Competitions
Before the 2023 Geometry Friends - IJCAI/CoG Competition took place, we tested the UCM Agents against the best agents from previous years and human players in a set of levels from previous competitions.
For the human players, we selected a group of 15 students with ages ranging from 18 to 25, all having some experience with video games. They were given a brief explanation of the game mechanics and the controls, and were able to play the game for around 20 to 30 minutes on some test levels. Afterwards, they were asked to play the levels of three official competitions, and we recorded their performance for comparison. Most of these were supervised by one of the authors of this work, who was available to answer any questions the players had and made sure the players did not cheat, as for the competition levels they were only given one attempt. This was done to ensure the players were not able to learn the best strategy for each level, which would be unfair for the agents.
The only human player who was not supervised followed the instructions specified in this document and his results were similar to the rest of the players. The results of the human players were used to calculate the average human score, which was used as a reference for the performance of the agents.
On the other hand, we made an estimation of the optimal score for each level, which was calculated by an expert player who played the levels multiple times and tried to find the best strategy for each of them. Some of the rectangle levels made use of bugs in the game physics, which is why scores may seem too high for some of them. These results served as a reference for the performance of the agents. We recorded most of the rectangle levels, and the videos can be found in our Github .
For the rest of the agents, we used the submitted versions of the best performing agents available in the official competition website. These and ours were executed 10 times in each of the levels, and the final score was calculated as the arithmetic mean of these scores. We used the same values for Vcompleted and Vcollected as in the official competitions, which vary from one to another. The results of the local competitions are presented in the following sections.
Circle results
For the circle, we replicated the 2014, 2017 and 2022 competitions, and measured the performance of our circle agents, the UCM Agent and the UCM QLearning (an alternative version with worse results), against the MARL Agent, the AG Agent, the average human and the winner agent of each of those years. In the following, the results for each of the competitions are presented, as well as a video of our UCM Agent completing the levels.
2014 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 10,451 |
| UCM Agent | 9,364 |
| MARL Agent | 8,978 |
| Average Human | 7,987 |
| UCM QLearning | 7,001 |
| AG Agent | 6,743 |
| 2014 Winner (CIBot) | 4,337 |
2017 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 4,425 |
| UCM Agent | 4,309 |
| 2017 Winner (KIT Agent) | 4,203 |
| MARL Agent | 4,119 |
| Average Human | 4,095 |
| AG Agent | 4,075 |
| UCM QLearning | 3,765 |
2022 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 19,942 |
| UCM Agent | 18,266 |
| Average Human | 17,122 |
| AG Agent | 16,835 |
| 2022 Winner (KIT Agent) | 16,628 |
| MARL Agent | 16,390 |
| UCM QLearning | 13,266 |
Rectangle results
For the rectangle, we replicated the 2014, 2016 and 2022 competitions, and measured the performance of our rectangle agent, the UCM Agent, against the NKUST Agent, the Sub Goal A star Agent, the average human and the winner agent of each of those years. In the following, the results for each of the competitions are presented, as well as a video of our UCM Agent completing the levels.
2014 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 10,462 |
| UCM Agent | 8,733 |
| NKUST Agent | 7,157 |
| Average Human | 6,842 |
| 2014 Winner (CIBot) | 6,466 |
| Sub Goal A Star Agent | 4,365 |
2016 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 4,933 |
| Human Agent | 3,999 |
| UCM Agent | 3,917 |
| NKUST Agent | 3,137 |
| Sub Goal A Star Agent | 1,000 |
| 2016 Winner (CIBot) | 892 |
2022 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 17,758 |
| Human Agent | 15,413 |
| UCM Agent | 15,306 |
| NKUST Agent | 7,099 |
| 2022 Winner (RRT Agent) | 6,402 |
| Sub Goal A Star Agent | 5,512 |
Cooperative results
For the cooperative agents, we replicated the 2013, 2017 and 2022 competitions, and measured the performance of our cooperative agents agent, the UCM Agents, against the MARL Agents, the NKUST Agents and the winner agents of each of those years. In the following, the results for each of the competitions are presented, as well as a video of our UCM Agents completing the levels.
2013 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 10,458 |
| UCM Agent | 6,937 |
| 2013 Winners (CIBot) | 4,308 |
| NKUST Agents | 1,209 |
| MARL Agents | 1,087 |
2017 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 4,321 |
| UCM Agent | 3,736 |
| MARL Agents | 3,209 |
| NKUST Agents | 1,268 |
| 2017 Winners (RRT Agents) | 1,026 |
2022 Competition
| Agent | Total score |
|---|---|
| Optimal Agent | 18,200 |
| UCM Agent | 14,760 |
| 2022 Winners (zvbe10 Agents) | 6,722 |
| NKUST Agents | 5,687 |
| MARL Agents | 5,448 |
Explainability System
With the help of the visual debugger that comes with the game, we have developed an explainability system that allows to understand the agent's motivation for actions or movements at different levels of abstraction. This has proved to be vitally useful both for us as developers and for people outside the project as this system helps to understand the decisions made by the agents, what each agent is doing at any given moment or what their short-term sub-goals are.The following video shows the interface of the cooperative mode explainability system.
The interface is divided horizontally by agent and vertically by level of abstraction. The left-hand side shows the circle information and the right-hand side shows the rectangle information. The top panel displays information about the immediate objectives of each of the agents (e.g. 'To catch the diamond D0 with a JUMP' or 'To stay on the platform R2 to be the take-off platform of the circle'), as well as the status (e.g. 'Flying' or 'Recalculating the landing point of the circle'). The lower panels show the individual plans of the circle and the rectangle. The side panels show lower-level information such as the speed, the action each agent is taking, the distance to its next target point and its target speed. On the level itself, the vertical and horizontal components of each agent's velocity are displayed, as well as the plans, the next target points, the platform each agent is on and labels of the movements, diamonds and platforms.
