Multi-Agent sliding puzzle

screenshot of the project. It shows chess pieces on a checker.

A course that I thought to be fascinating was about multi-agent systems. In those systems, the agents access information about their environment and then execute an action or communicate with other agents. 

Multi-agent systems are great to implement decentralized solutions. Often more complex, it is sometimes necessary when there isn't an obvious solution because multi-agent systems tend to find the best solution for their given problem without intervention.

Core of our multi-agent system

The goal of this project "MAS sliding puzzle" is to develop a decentralized solution to an overcrowding problem: 

Several pieces are dispersed randomly on a grid and the goal of each piece is to stand on a unique cell of the grid. It's an easy problem as long as there's only a few pieces but it becomes hard when pieces get in the way of each other.  

An example of such difficult situation is when correctly placed pieces needs to move to allow the passage of other pieces. 

Agents can access some information about their environment and use this to decide its action. The possible actions of an agent are moving to an empty cell, send a message to an adjacent agent or wait. 

The functionalities we developed were:

  1. Intelligent agents running on multiple threads of execution
  2. Environment generation ( which ensure a solution exists) 
  3. Communication between agents

We are happy with the visual of our project. The agents are chess pieces and a cell is green when the agent on top is correctly placed.

Illustration video

My team and my role

I worked with Alicia Rocchia, a classmate.

I wanted to prepare myself for my internship at the National Institute of Informatics by coding with Unity, which I never done before and I knew that I would use it. 

My classmate didn't have any use in learning Unity so we decided that I would handle all the coding while Alicia would participate in the system conception and handle the writing of the report. 


One of the main hurdle of multi-agent systems is to multi-thread the agents and maintain synchronicity. From our experience with Java, we knew that it was possible but I convinced my teammate that Unity would handle parallelism gracefully.  

Plus, using Unity makes it easier to add visuals and monitoring the attributes or our objects. 

We used to collaborate on our diagrams.

Code is on Github .

You can also access  our report (french) 

Purpose and goal

The purpose was to get hands-on experience implementing a multi-agent system and , consequently, to get an sense of the technical difficulties, as well as the usefulness, of a decentralized solution. 

I used a tutorial about the making of a basic chess game to get a grasp on how to use GameObjects in Unity. I kept the 3D models but heavily adapted all the rest until I had a basic multi-agent system.

In order to use Unity, we made the choice to implement our own multi-agent system instead of using (and learning to use) an existing framework.

We made the choice of an "intelligent agents" approach, meaning that the decision-making process of our agents is quite complex. The alternative is to design our system to create the emergence of a solution with simple rules, which require advanced knowledge. 

Emerging Behavior

Our basic system display examples of complex behavior involving multiple agents. One such behavior is the formation of cycles of agents, where several agents form a chain so that they can all get closer to their goals without blocking each other.


As expected when using a new tool, I had to invest time on learning Unity.

In the end, there are still edge cases that our algorithm struggle to solve. We improved this behavior by adding a 20% probability for an agent to make a random move, which allows our agents to get out of a unsolvable situation.

Lessons learned

I have put more work in this project than expected by my teacher because I was interested in the subject and Unity. I don't regret it but I realized it's another project thatI should have started with lower expectations.

This project was a challenge for myself to prove that I can learn a new technology and have solid results in the span of a few months and I believe that it is a success!

app icon