Home

Awesome

Sorting-Battle

Sorting Battle is an open-source competitive puzzle game similar to Tetris Attack. Its original purpose is to design an end-to-end reinforcement learning (RL) environment where the trained models can have practical use in the game.

The RL models are trained using the Sorting Battle Gym, which aims to achieve feature parity with the SortGame Core. This is achieved through code tracing and implementing the same unit tests.

Refer to our presentation slides for an overview.

Installation

You'll need the following:

Repository Walkthrough

Here are the most important directories in the Assets directory:

FAQ

Why use RL? Wouldn't more traditional search algorithms perform better?

Our decision to use RL is mostly due to three reasons:

  1. It is hard to define a good heuristic for Sorting Battle.
    • One class of search algorithms aims to optimize a heuristic function greedily using algorithms like A*. However, we've found it difficult to define such a heuristic function here.
    • For example, one might greedily try to clear all lines whenever possible, but clearing each line can change the rest of the board, removing other lines.
    • If we were to "rate" each board's state with a heuristic function instead: One might punish taller boards, but taller boards also allow longer vertical lines, so it's hard to say that taller boards are definitely not preferred.
  2. Search algorithms have a hard time dealing with real-time games in general, compared to turn-based games like Chess or Go.
    • You usually find search algorithms in planning an optimal solution from the current state. However, in our game, informative game states are scattered sparsely across the time domain. This means search algorithms must compute a lot of simulation steps to get a good solution.
    • For stochastic algorithms like Monte Carlo Tree Search (MCTS), it may also take a lot of steps for each simulated game to end. The legal action space for each step can also be very large, especially if there are a lot of number blocks on the board, increasing the width of the search tree. And so, MCTS would have a hard time converging to a good solution too, not to mention the performance concerns that come with maintaining such a big search tree.
  3. RL algorithms are easier to implement and maintain compared to sophisticated search algorithms that rely on specifically-tuned heuristics.

Our RL model can make decisions almost instantly without the memory overhead of a search tree. We believe that it's ultimately the best choice for our application.

However! Our C# framework can still support search algorithm-based implementations, theoretically. Such an implementation would have to inherit from AIController. Feel free to submit a pull request if you managed to design a good search algorithm to play our game!

Why did you not use ML-Agents Toolkit? Wouldn't it be more convenient?

  1. ML-Agents Toolkit requires RL developers to install Unity, which can be annoying if you don't usually use Unity.
  2. ML-Agents Toolkit's training process is much more inefficient compared to a pure Python implementation.
    • The training process for ML-Agents Toolkit involves either using the Unity Editor or a separate build of the game (which can be headless in our case), and using a communication bridge to marshall data (input/output) from and to the Python runtime (which would contain the RL model).
    • Whatever the case, the entire Unity runtime must be included in the training process, which involves animating objects that the RL model would not care about.
    • And of course, interprocess communication across C# and Python can also hurt performance.
  3. ML-Agents Toolkit leaves less space for customization.
    • This project started as a term project for a Machine Learning course, and we wanted finer control on the model's architecture. ML-Agents Toolkit's built-in models cannot be modified (although it does happen to have a PPO implementation), so we had to use Python one way or another.

But of course, now that this project has graduated into an open source project, this is no longer a hard requirement. See Issue #2.

Contributing

It is recommended that you try out the open issues first.

In general, please try to mimic the coding style in the existing codebase, and remember to use the Test Runner window to detect regressions before submitting pull requests. Also, avoid moving/renaming files to reduce conflict.

License